Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2000/01/11.pdf Дата изменения: Fri Dec 23 19:25:38 2005 Дата индексирования: Tue Oct 2 00:09:40 2012 Кодировка: Windows-1251

МАЛАЯ

ТЕОРЕМА

ФЕРМА
5555 14

11

множители:
7

a - a = a a -1 =a a -1 a +1 =
Поскольку
2

e

6

je

3

= a a -1 a + a +1 a +1 a - a +1 .

b

je

3

ge

2

j

10. а) Докажите, что 2222

jb

ge

2

j

a + a +1 = a + a- 6 + 7 a + a - 6 =
и

e

2

j

2

a - a +1 a - a -6 имеем: 7 a - a a a -1 a -2 a + 3

2

2

b

gb

gb

b gb g bmod 7g = b a + 2 gba - 3 g b mod 7 g , g ba + 1gba + 2gba - 3g bmod 7g .
= a-2 a+3

Произведение семи последовательных целых чисел кратно 7.
Упражнение 5. Докажите, что а) наибольший общий делитель чисел вида a7 a равен 42; б) наибольший общий 9 делитель чисел вида a a равен 30. (Заметьте: 30 не кратно 9. Это находится в согласии с тем, что число 9 не простое, а составное.)

+ 18 на 7. остаток от деления числа 13 + 15 10 11. Докажите, что число 11 1 оканчивается на два нуля (т.е. кратно 100). 10 12. а) Найдите все целые числа a, для которых a + 1 оканчивается цифрой ноль. б) Докажите, что ни при каком 100 целом a число a + 1 не оканчивается цифрой ноль. 13. Пусть n четное число. Найдите наибольший общий делитель чисел вида a n a, где a целое число. 14. Пусть n натуральное число, n n> 1. Докажите, что наибольший общий делитель чисел вида a a, где a пробегает множество всех целых чисел, совпадает с наибольшим общим n делителем чисел вида a a, где a = 1, 2, 3,..., 2 n . (Заметьте: из этого следует, что наибольший общий делитель чисел вида n a a, где a целое, совпадает с наибольшим общим делителем чисел такого вида, где a натуральное.)

FH

+ 5555
16

2222

IK

17

кратно 7. б) Найдите
19 20

Общий случай
И каждого в свою уложат яму. Эжен Гильвик

Теперь рассмотрим число p = 11. Очевидно,

a - a = a a10 - 1 = a a5 - 1 a5 + 1 =
=
4 3 2

11

Тут не так-то просто догадаться, как быть дальше. Но полный перебор всех 11 остатков все еще возможен. И когда мы его выполним, окажется, что значения много4 3 2 члена a + a + a + a + 1 кратны 11 при a 3, 4, 5 или 3 4 2 9 mod 11 , а значения многочлена a a + a a + 1 кратны 11 при a 2, 6, 7 или 8. Между прочим, если мы раскроем скобки в произведении (a 3)(a 4)(a 5)( a 9), получим

d aba - 1ge g

id

id

a + a + a + a +1 a +1 a - a + a - a +1 .

jb

i

Выпишем в строчку числа 1, 2, 3, ..., p 1, домножим каждое из них на k, где k не кратно p, и рассмотрим остатки от деления на p. Например, при p = 19 и k = 4 получим таблицу 1. В нижней строке таблицы те же
Таблица 1

ge

4

3

2

j

п
4a 4a mod19

1 4 4 10 40 2

2 8 8 11 44 6

3 12 12 12 48 10

4 16 16 13 52 14

5 20 1 14 56 18

6 24 5 15 60 3

7 28 9 16 64 7

8 32 13 17 68 11

9 36 17 18 72 15

b

п
4a 4a mod19

e

a - 7a + 12 a - 14a + 45 a + 4a + 1 a - 3a + 1 =
= a + a - 10a + a + 1 a + a + a + a + 1
4 3 2 4 3 2

2

je

2

je

2

je

2

b

j

mod 11 .

g

Аналогично можно проверить, что (a 2)(a 6)(a 4 3 2 7)(a 8) a a + a а + 1 mod 11 . Что дальше? При p = 13, если действовать нашим способом, придется возводить в двенадцатую степень числа от 1 до 12 или раскрывать скобки в произведении тринадцати множителей: a 6, a 5,..., a + 5, a + 6. Заниматься этим не хочется, даже если ограничиться возведением в степень чисел 1, 2, 3, 4, 5, 6 или перемно2 2 2 жать 'всего лишь' шесть скобок: ( a 1)( a 4)( a 2 2 2 9)( a 16)( a 25)( a 36). Чем больше p, тем больше вариантов надо перебирать. Поэтому мы прекратим разбор частных случаев и перейдем к доказательству малой теоремы Ферма, которое охватывает сразу все простые числа p.

b

g

самые числа, что и в верхней, только они расположены в другом порядке! Оказывается, это общий закон: не только при p = 19 и k = 4, но при любом простом p и не кратном p целом числе k всегда получатся те же самые числа 1, 2, 3, ..., p 1, возможно, записанные в некотором другом порядке. Почему? Ну, во-первых, в нижней строке не может появиться 0, ибо произведение не кратных простому числу p чисел a и k не может быть кратно p. Во-вторых, все числа нижней строки разные (это легко доказать 'от противного': если бы числа ak и bk давали при делении на p одинаковые остатки, то разность ak bk = (a b)k была бы кратна p, что невозможно, поскольку a b не кратно p). Этих двух замечаний достаточно: ненулевых остатков от деления на p существует p 1 штук, все они вынуждены по одному разу появиться в нижней строке таблицы.
Упражнения 15. Существует ли такое натуральное n, что число 1999n оканчивается на цифры 987654321? 16. Если целое число k взаимно просто с натуральным числом n, то существует такое натуральное число x, что kx 1 кратно n. Докажите это. 17. Если целые числа a и b взаимно просты, то любое целое число c представимо в виде c = ax + by, где x, y целые числа. Докажите это.

Упражнения 6. а) Произведение любых четырех последовательных целых чисел кратно 24. Докажите это. б) Произведение любых пяти последовательных целых чисел кратно 120. Докажите это. в) Докажите, что a 5 5a3 + 4a при всяком целом a кратно 120. 7. Для любого натурального a число a5 оканчивается на ту же цифру, что и a. Докажите это. 5 5 8. Докажите, что m n mn кратно 30 при любых целых m и n. 4 9. Если число k не кратно ни 2, ни 3, ни 5, то k 1 кратно 240. Докажите это.
3*

Как вы помните, малая теорема Ферма утверждает, что при любом целом k и простом p число k p k = k k p -1 - 1

d

i