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

Малая теорема Ферма
МАЛАЯ ТЕОРЕМА ФЕРМА

9

В.СЕНДЕРОВ, А.СПИВАК

Ч

класса от ученика географического, экономического, политологического или коррекционного класса? Тем, что он больше размышляет над задачами? Да, и этим тоже. Но не только. Еще он знает малую теорему Ферма. Программы обучения математике бывают разные: можно начать с подробного изучения геометрии, можно с комбинаторики, кто-то начинает с теории множеств, все не перечесть. Но малая теорема Ферма прочно вошла в программу математических классов. Компьютерщики

ЕМ ОТЛИЧАЕТСЯ УЧЕНИК МАТЕМАТИЧЕСКОГО

авторы учебника 'Конкретная математика' Р.Грэхем, Д.Кнут и О.Паташник тоже включили ее в тот набор сведений, с которым они знакомят своих студентов. Формулируется эта теорема, открытая советником парламента Тулузы (Франция) Пьером Ферма (16011665) в 1640 году, очень коротко: если p простое число, a целое число, то a p а кратно p. Сразу и не видно, почему скромное с виду утверждение столь важно. Тем не менее, оно заслуживает величайшего внимания. Мы начнем с материала, который доступен семикласснику, а закончим недавними открытиями в криптографии.

Иллюстрация В.Хлебниковой
3 Квант ? 1


10
Частные случаи

КВАНT 2000/?1

Если из книги вытекает какой-нибудь поучительный вывод, он должен получаться помимо воли автора, в силу самих изображенных фактов. Ги де Мопассан

Из любых двух последовательных целых чисел a и a + 1 одно четное, а другое нечетное. Поэтому произведе2 ние a(a + 1) = a + a четно при любом целом a. 2 Делимость числа a + a на 2 можно доказать и подругому, разобрав два случая: 2 если a четно, то a тоже четно, а сумма двух четных 2 чисел a и a четна; 2 если a нечетно, то a тоже нечетно, а сумма двух 2 нечетных чисел a и a четна. Вот так доказывают замечательное свойство многочлена 2 a + a. Впрочем, при F = 2 в малой теореме Ферма 2 фигурирует другой многочлен: a a = (a 1)a. Все его значения в целых точках четные числа (докажите!). Теперь рассмотрим многочлен =3 =. Его легко разложить на множители:

равен 2 или 3, то в дело вступает четвертый множитель. (Для тех, кто еще не привык работать с остатками, объясним: если a = 5b + 2, т. е. если a дает остаток 2 при 2 2 2 делении на 5, то a + 1 = 5b + 2 + 1 = 5 5b + 4b + 1 . Аналогично можно рассмотреть случай a = 5b + 3.) Есть и другой способ:

b

g

e

j

a + 1 = a - 2 a + 2 + 5,

2

b

gb

g

значит, если нас интересуют только остатки от деления на 2 5, то a + 1 можно-таки заменить на (a 2)(a + 2). Формулой это записывают так:

a +1 a -2 a +2

2

a - a = a a -1 = a a -1 a +1 .
Получили произведение трех последовательных целых чисел: a 1, a и a + 1. Как мы уже знаем, это произведение четно. Поскольку из любых трех последовательных чисел 3 одно кратно 3, их произведение (a 1)a(a + 1) = a a кратно 3 (и, значит, даже кратно 6).
Упражнение 1. При любом целом a сумма a 3 + 5a кратна 6. Докажите это.
4

3

e

2

jb

gb

g

Предложенное в 1801 году К. Ф. Гауссом обозначение ' ' еще не раз будет использовано нами. По определению, a сравнимо с b по модулю n, если a b кратно n, т. е. a b = kn, где k целое число. Обозначение ab mod n оказалось удачным потому, что свойства сравнений похожи на свойства обычных равенств. Сравнения можно складывать: если a b mod n и c d mod n , то a + + c b + d mod n . В самом деле, по определению, a = = b + kn и c = d + ln, где k, l целые числа. Значит,

b

gb

gb

mod 5 .

g

b

g

b

g

b

g

b

g

a + c = b + kn + d + ln = b + d + k + l n ,

b b

gb gb

g g

bg g

что и требовалось. Аналогично, формулы

Многочлен = = при a = 2 и a = 3 принимает значения 4 2 2 = 14 и 3 3 = 78. Конечно, эти значения четны, но никакого общего делителя кроме 2 (и 1) у них нет. Не повезло! Впрочем, число 4 составное, а малая теорема Ферма говорит только о многочленах вида a p a, где p простое число. Пусть F= 5. Вычислим несколько значений многочлена 5 a a. При a = + 1 и при a = 0 получаем ноль. Смотрим 5 5 5 5 дальше: 2 2 = 30, 3 3 = 240, 4 4 = 1020, 5 5 = 5 = 3120, 6 6 = 7770,... Все эти значения кратны числу 30. Поскольку 30 = 2 3 5, доказательство делимости на 30 распадается на три части: во-первых, надо доказать, 5 что a a кратно 2; во-вторых, a 5 a кратно 3; в-третьих, 5 a a кратно 5. 5 Первая часть очевидна: числа a и a либо оба четны, либо оба нечетны. Не вызывает затруднений и вторая часть: 5 4 2 2 2 a - a = a a -1 = a a -1 a +1 = a -1 a a +1 a +1 ,
4

ac = b + kn d + ln = bd + knd + bln + kln2 =

b

a - c = b + kn - d + ln = b - d + k - l n ,

gb

g

b

= bd + kd + bl + kln n позволяют утверждать, что сравнения можно вычитать и умножать. Коли можно умножать, то можно и возводить в степень: если a b mod n , то для любого натурального m m числа m верно сравнение a b mod n . Сокращать сравнения надо с осторожностью:

b

g

b

g

b

g

но

6 36 (mod 10), 1/ 6 (mod 10).

b
b

произведение трех последовательных чисел всегда кратно 3. Чуть сложнее третья часть. Нет, конечно, из пяти последовательных целых чисел обязательно одно кратно 5, так что произведение (a 2)(a 1)a(a + 1)(a + 2) 2 кратно 5. Но a + 1 (a 2)(a + 2). Как же быть? Самый бесхитростный способ перебрать все подряд остатки от деления на 5: любое целое число при делении на 5 дает в остатке 0, 1, 2, 3 или 4. Если остаток равен 0, то кратен 5 второй множитель произведения 2 (a 1)a(a + 1)( a + 1). Если остаток равен 1 или 4, то кратен 5 первый или третий множитель. Если же остаток

e

je

je

jb

gb

ge

j

Упражнения 2. Решите сравнение 3 x 11 mod 101 . 3. Какие целые числа x удовлетворяют сравнению 14x 0 mod 12 ? 4. Пусть k 0. Докажите, что а) если ka kb mod kn , то a b mod n ; б) если ka kb mod n и числа k, n взаимно просты, то a b mod n .

Продолжим изучение многочленов вида a p a: докажем, что при любом целом a число =7 = кратно 7. Как всегда, можно рассмотреть все 7 остатков от деления на 7 7 7 7 7: 0 0 = 0, 1 1 = 0, 2 2 = 126 = 7 18,..., 6 6 = = 279930 = 7 39990. (Можно и чуточку сэкономить: поскольку любое целое число представимо в виде a = 7b, 7b + 1, 7b + 2 или 7b + 3, очевидно, при проверке малой теоремы Ферма для p = 7 можно ограничиться рассмотрением случаев a = 0, 1, 2 и 3.) Но бездумная проверка не может научить нас ничему интересному. Лучше рассмотрим разложение на

b g

g

b

g

g

b

g

b

g


МАЛАЯ

ТЕОРЕМА

ФЕРМА
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


12

КВАНT 2000/?1

кратно p. Значит, для чисел k, не кратных p, теорему можно формулировать следующим образом: Теорема 1. Если целое число k не кратно простому p -1 числу p, то k дает остаток 1 при делении на p. Доказательство. Поскольку остатки от деления на p чисел k, 2k, 3k, ..., (p 1)k это (с точностью до перестановки) числа 1, 2, 3, ..., p 1, то k 2k 3k K p - 1 k 1 2 3 K p - 1 mod p , откуда p -1 k p -1 ! p-1 ! mod p .

Таблица 3

Ч
1 2 3 4 5 6 7 8 9 10

1 1 2 3 4 5 6 7 8 9 10

2 2 4 6 8 10 1 3 5 7 9

3 3 6 9 1 4 7 10 2 5 8

4 4 8 1 5 9 2 6 10 3 7

5 5 10 4 9 3 8 2 7 1 6

6 6 1 7 2 8 3 9 4 10 5

7 7 3 10 6 2 9 5 1 8 4

8 8 5 2 10 7 4 1 9 6 3

9 9 7 5 3 1 10 8 6 4 2

10 10 9 8 7 6 5 4 3 2 1

bg b gb
k
p -1

b gb g

gb g

g

Сократив на (p 1)!, получим желаемое:

1

b

mod p .

А тот, кто не решил упражнение 4 б) и не знает, почему сравнения можно сокращать (на число, взаимно простое с модулем), пусть рассуждает следующим образом: по-1 скольку произведение k p - 1 p - 1 ! кратно p, а число -1 (p 1)! не кратно p, то число k p 1 кратно простому числу p.

e

jb

g

Таблица 4

Упражнения 18. Найдите остаток от деления числа 32000 на 43. 19. Если целое число a не кратно 17, то a 8 1 или a 8 + 1 кратно 17. Докажите это. 61 61 20. Докажите, что m n mn кратно 56786730 при любых целых m и n. 2 p 21. Найдите все такие простые числа p, что 5 + 1 кратно p. 22. Пусть p простое число, p 2 . Докажите, что число p p 7 5 2 кратно 6p. p -1 p -1 p- 23. Если p простое число, то сумма 1 + 2 + ... + p - 1 1 при делении на p дает остаток p 1. Докажите это. 24. Шестизначное число кратно 7. Его первую цифру стерли и затем записали ее позади последней цифры числа. Докажите, что полученное число тоже кратно 7. (Например, из кратных 7 чисел 632387 и 200004 таким образом получаем числа 323876 и 42, которые тоже кратны 7.) 25. Пусть p простое число, отличное от 2, 3 и 5. Докажите, что число, записанное p 1 единицей, кратно p. (Например, 111111 кратно 7.) 26*. Д окажите, что для любого простого p число 11...1122...22...99...99, состоящее из 9p цифр (сначала p единиц, потом p двоек, p троек, ..., наконец, p девяток), при делении на p дает такой же остаток, как и число 123456789.

Ч
1 2 3

1 1 2 3

2 2 0 2

3 3 2 1

Таблица 5

b

g

Ч
1 2 3 4 5 6 7 8 9 10 11

1 1 2 3 4 5 6 7 8 9 10 11

2 2 4 6 8 10 0 2 4 6 8 10

3 3 6 9 0 3 6 9 0 3 6 9

4 4 8 0 4 8 0 4 8 0 4 8

5 5 10 3 8 1 6 11 4 9 2 7

6 6 0 6 0 6 0 6 0 6 0 6

7 7 2 9 4 11 6 1 8 3 10 5

8 8 4 0 8 4 0 8 4 0 8 4

9 9 6 3 0 9 6 3 0 9 6 3

10 10 8 6 4 2 0 10 8 6 4 2

11 11 10 9 8 7 6 5 4 3 2 1

Таблицы умножения
Назло ей я все-таки помножил землекопов. Правда, ничего хорошего про них не узнал, но зато теперь можно было переходить к другому вопросу. Л.Гераскина

Рассмотрим все n 1 разных ненулевых остатков от деления на n. Составим таблицу умножения, написав на пересечении a-го столбца и b-й строки остаток от деления на n произведения ab. Например, при n = 5 получим таблицу 2, при n = 11 таблицу 3.
Таблица 2

Ч
1 2 3 4

1 1 2 3 4

2 2 4 1 3

3 3 1 4 2

4 4 3 2 1

Поскольку в обоих примерах число n простое, в каждой строке, как и в каждом столбце, возникает некоторая перестановка чисел 1, 2, ..., n 1. Если же рассмотреть составное число, то в таблице обязательно встретится нуль. Например, при n = 4 имеем 2 2 0 (табл.4); не лучше ситуация и при n = 12 (табл.5): опять в некоторых строках есть нули! И вообще, при любом составном числе n = ab, где 1 < a, b < n, на пересечении a-й строки и b-го столбца стоит остаток от деления ab на n, т.е. 0. Итак, если n составное, то имеются делители нуля ненулевые остатки a и b, произведение ab которых кратно n, иными словами, равно нулю по модулю n. Но даже при составном n в некоторых строках таблицы умножения нет нулей. В таблице 4 таковы первая и третья строки, а в


МАЛАЯ

ТЕОРЕМА

ФЕРМА

13

таблице Подумав в тех и числом n Давайте

5 первая, пятая, седьмая и одиннадцатая. немного, можно понять, что нули присутствуют только тех строках, номера которых имеют с общий делитель, отличный от 1 (докажите это!). же вычеркнем из таблицы все такие строки и
Таблица 7

б) Сумма квадратов трех целых чисел кратна 7 в том и только том случае, когда сумма четвертых степеней этих чисел кратна 7. Докажите это. 30. 31. 32. n> 7 кратно 10. Докажите, что число 7 9999 Каковы три последние цифры числа 7 ? Если целое число a взаимно просто с натуральным числом 1, то сравнение ax b mod n равносильно сравнению
r1
7 7 7 7 7 7 7 7

Ч
Таблица 6
1 5 7 11

1 1 5 7 11

5 5 1 11 7

7 7 11 1 5

11 11 7 5 1

Ч
1 3

1 1 3

3 3 1

x a b mod n . Докажите это. n! 33. Если n нечетное натуральное число, то 2 1 кратно n. Докажите это. 34*. Найдите все натуральные n > 1, для которых сумма n n n 1 + 2 + ... + n - 1 кратна n. 35*. Для каждого натурального числа s существует кратное ему натуральное число n, сумма цифр которого равна s. Докажите это.

b

g

b

g

b

g

столбцы. (Если n простое число, то вычеркивать ничего не придется.) При n = 4 получим таблицу из двух строк и столбцов (табл.6), а при n = 12 останется таблица размером 4 Ч 4 (табл.7).
Упражнение 27. Заметьте, что каждая из таблиц 27 симметрична относительно обеих своих диагоналей. Докажите, что это так для любого n.

Функция Эйлера
В 1763 году Леонард Эйлер (17071783) ввел обозначение n (читают: фи от эн) для количества r остатков, взаимно простых с n. Например, 1 = 1, 4 = 2, 12 = = 4. Если число p простое, то p = p 1. Легко вычислить m и p , где m натуральное число. В самом деле, m выпишем все p возможных остатков: 0, 1, 2, ..., p m 1. Из них кратны p в точности остатки 0, p, 2p,..., p m p. Значит, 1 m m m -1 m p =p -p = p 1- . p

bg

Теорема Эйлера
Чтобы обобщить малую теорему Ферма на случай составного числа n, оставим в таблице умножения только те строки и столбцы, в которых нет нулей, т.е. рассмотрим взаимно простые с n остатки от деления на n. В новой таблице строки (и столбцы) отличаются друг от друга лишь порядком, в котором расположены числа. Другими словами, если мы для натурального числа n выпишем все остатки a1 , a2 , ..., ar , взаимно простые с n, и домножим каждый из них на взаимно простое с n число k, то получим числа ka1 , ka2 ,..., kar , которые тоже взаимно просты с n и дают разные остатки при делении на n (докажите!). Итак, строка остатков от деления на n чисел ka1 , ka2 ,... ..., kar может отличаться от строки a1 , a2 , ..., ar только порядком расположения чисел. Поэтому точно так же, как для простого p, для составного n имеем:

ej

bg

bg

bg

bg

ej

Давайте вычислим 1000 количество чисел первой тысячи, которые не кратны ни 2, ни 5. Для этого из 1000 вычтем сначала 500 именно столько в первой тысяче четных чисел. Не забудем вычесть и 200 столько в первой тысяче чисел, кратных 5. Что еще? Еще мы должны учесть, что некоторые числа (оканчивающиеся цифрой 0) кратны и 2, и 5. Таких чисел 100 штук; каждое из них мы учитывали оба раза, а надо было только один раз! Поэтому правильный ответ дает формула

b

g

F GH

I JK

1000 = 1000 500 200 + 100 = 400.
Упражнения
ab 36. Найдите 2 5 , где a, b натуральные числа. 37. Пусть p, q различные простые числа. Найдите а) pq , ab б) p q , где a, b натуральные числа.

b

g

ka1ka2 K kar a1a2 K ar mod n ,
откуда

b

g

Значит, ar кратно n. Посколь12 r ку числа a1 , a2 , ..., ar взаимно просты с n, то k 1 кратно n. Если n простое число, то r = n 1 и получаем в точности утверждение малой теоремы Ферма. В общем же случае приходим к теореме Эйлера: Теорема 2. Если k целое число, взаимно простое с r натуральным числом n, то k 1 кратно n, где r количество взаимно простых с n натуральных чисел, не превосходящих n.
Упражнения 28. Докажите, что если число k не кратно 3, то а) k 3 при делении на 9 дает остаток 1 или 8; б) k 81 при делении на 243 дает остаток 1 или 242. 3 3 3 29. а) Если a + b + c кратно 9, то хотя бы одно из целых чисел a, b, c кратно 3. Докажите это.
4 Квант ? 1

ek - 1ja a K a 0 b произведение ek - 1ja a K
r 12 r r

mod n .

g

38. Решите уравнения: а) 7

FH

IK

di

bg

FH IK
x

= 294; б) 3 5

FH

x

y

IK

= 360.

В принципе, примененный нами способ позволяет вычислить n для любого натурального числа n. Например, чтобы вычислить 300 , мы можем выписать все числа от 1 до 300 и вычеркнуть 150 четных чисел, а также 100 чисел, кратных 3, и 60 чисел, кратных 5. Затем мы должны вспомнить, что некоторые числа вычеркнуты дважды (а иные даже трижды), и 'восстановить справедливость', т.е. к числу 300 150 100 60 прибавить 50 чисел, кратных 2 3 = 6, а также 30 чисел, кратных 2 5 = = 10, и 20 чисел, кратных 3 5 = 15. Но и этого недостаточно: каждое из десяти чисел, кратных 2 3 5 = = 30, было сначала трижды выброшено (как кратное 2, 3, 5) и затем трижды возвращено (как кратное 6, 10, 15). Но выбросить эти 10 чисел все-таки надо! Поэтому

bg

bg

300 = 300 - 150 - 100 - 60 + 50 + 30 + 20 - 10 = 80 .

bg


14

КВАНT 2000/?1

Ничего сложного, как видите, нет. Но с ростом количества простых делителей числа n мы будем получать ответ, в котором все больше и больше слагаемых и вычитаемых. В статье Н. Васильева и В.Гутенмахера 'Арифметика и принципы подсчета' (Приложение к журналу 'Квант' ?2 за 1994 год) это все подробно объяснено. А здесь мы изложим другой способ. Теорема 3. Функция Эйлера мультипликативна, т.е.
mn = m n

получаем
y1 y
2

b

mod m .

g

b g b gbg e j= je p
as s

для любых взаимно простых натуральных чисел m и n. aa a Следствие. Если n = p1 1 p2 2 K ps s , где p1 , p2 ,..., p s различные простые числа, a1 , a2 ,..., as натуральные числа, то
n = p1 1 p2

bg e je j = ep
a a2

K p

a1 1

- p1

a1 -1

a2 2

- p2

a2 -1

j K e

ps s - p

a

a s -1 s

j

.

Вспомнив, что 0 y1 , y2 < m, получаем: y1 = y2 . Аналогично, сравнение по модулю n приводит к равенству x1 = x2 . Итак, все mn чисел таблицы дают разные остатки при делении на mn. Но возможных остатков от деления на mn ровно столько же, сколько чисел в таблице! Значит, рассматриваемые числа дают все возможные остатки от деления на mn. Другими словами, для любого числа d = = 0, 1,..., mn 1 существует и единственна такая пара целых чисел x, y, что 0 x < n, 0 y < m и d mx + + ny mod mn . В таблице 8 четные числа образуют четыре столбца, а числа, кратные 5, образуют одну строку. Это не случайно:

b

g

Доказательство теоремы 3. Рассмотрим числа вида mx + ny, где 0 x < n и 0 y < m. Запишем их в виде таблицы размером n Ч m. Например, при n = 5 и m = 8 получаем таблицу 8.
Таблица 8

НОД(mx + ny, m) = НОД(ny, m) = НОД(y, m); аналогично, НОД(mx + ny, n) = НОД(x, n). По этой причине в рассматриваемой таблице числа, взаимно простые с m, расположены в m столбцах (тех, где y взаимно просто с m), а числа, взаимно простые с n, образуют n строк. Теперь доказательство теоремы 3 не составляет труда: чтобы d было взаимно просто с mn, необходимо и достаточно, чтобы d было взаимно просто с числами m и n. Такие числа d лежат на пересечении m столбцов (состоящих из чисел, взаимно простых с m) с n строками (состоящими из чисел, взаимно простых с n). Всего получаем 'решетку' из m n чисел, что и требовалось доказать.

x\ y
0 1 2 3 4

0 0 8 16 24 32

1 5 13 21 29 37

2 10 18 26 34 42

3 15 23 31 39 47

4 20 28 36 44 52

5 25 33 41 49 57

6 30 38 46 54 62

7 35 43 51 59 67

bg

bg

bg

b g bg

bg

Остатки от деления на mn всех чисел этой таблицы разные. В самом деле, если бы какие-то два остатка совпали, то было бы выполнено сравнение
mx1 + ny1 mx2 + ny
2

Упражнения 39. Запишем числа от 0 до mn 1 в таблицу из m строк и n столбцов (табл.9).

Таблица 9
0 1 2 ... ... ... ... ... ...

b

mod mn ,

g

n1
2n 1 3n 1 ... ...

где 0 x1 , x2 < n и 0 y1 , y2 < m. Отсюда следуют два сравнения: mx1 + ny1 mx2 + ny2 mod m и mx1 + ny1 mx2 + ny2 mod n .

n
2n

n+1
2n + 1 ... ... (m 1)n + 1

n+2
2n + 2 ... ... (m 1)n + 2

b b

g g

... ...
(m 1)n

Первое приводит к сравнению
ny1 ny
2

b

mod m ,

g

mn 1

из которого вследствие взаимной простоты чисел m и n

а) Составьте такую таблицу для m = 3 и n = 4. Зачеркните в ней сначала все четные числа, а затем те из оставшихся чисел, которые кратны 3. Заметьте, что незачеркнутыми остались в

Рис.1


МАЛАЯ

ТЕОРЕМА

ФЕРМА

15

точности числа, взаимно простые с 12, и что незачеркнутые числа не образуют решетки. б) Докажите теорему Эйлера по следующему плану: 1) числа, взаимно простые с n, заполняют собой n столбцов таблицы 9; 2) остатки от деления на m всех m чисел любого столбца таблицы 9 различны; 3) в каждом столбце присутствует ровно m чисел, взаимно простых с m; 4) число взаимно просто с mn тогда и только тогда, когда оно взаимно просто с n (такие числа лежат в n столбцах) и взаимно просто с m (в каждом столбце таких чисел m ). 40. Окружность разделили n точками на n равных частей. Сколько можно построить различных замкнутых ломаных из n равных звеньев с вершинами в этих точках? (Две ломаные, получающиеся одна из другой поворотом, считаем одинаковыми. На рисунке 1 изображены все такие ломаные при n = 20.) 41. Для любых натуральных чисел m и n докажите равенства: а) m n = HOK m, n HOД m, n ; б) mn = HOK m, n HOД m, n ; в) m n НОД m, n = mn НОД m, n . г) Пусть m и n натуральные числа, причем НОД(m,n) > 1. Докажите неравенство mn > m n . 42. Решите уравнения: а) x = 18; б) x = 12; в) x x =

bg

Получилось некоторое 78-значное число x. Затем взяли 64-значное простое число p и 65-значное простое число q. Перемножили их (не вручную, разумеется, а на компьютере): pq = 11438162575788886766932577997614661201021829 67212423625625618429357069352457338978305971235639 58705058989075147599290026879543541. Теперь главное:
yx
9007

bg

bg

bg

b

mod pq .

g

= 12;

= x/n, где n натуральное число, натуральное число, n > 1.

b g b g d b gi d b g d b gi b b gbg b g b gd bg b bg FH x IK = x x; д) b xg = x г*)
2 2

b gi g b gi gbg bg bg /2; е) b x g = x/3; ж*) b x g n > 3; з) bnx g = b x g , где

Понимаете? Они опубликовали и произведение pq, и число 9007, и сам метод шифрования (и, разумеется, число y). Было даже сказано, что из чисел p и q одно 64значное, а другое 65-значное. В секрете остались только сами числа p и q. Требовалось найти x. Эта история завершилась в 1994 году, когда Аткинс, Крафт, Ленстра и Лейланд расшифровали эту фразу. Числа p и q оказались равны p = 349052951084765094914784961990389813341776463 8493387843990820577, q = 327691329932667095499619881908344614131776429 67992942539798288533. В книге 'Введение в криптографию' (М., МЦНМО, 1998 г.) сказано: 'Этот замечательный результат (разложение на множители 129-значного числа) был достигнут благодаря использованию алгоритма разложения чисел на множители, называемого методом квадратичного решета. Выполнение вычислений потребовало колоссальных ресурсов. В работе, возглавлявшейся четырьмя авторами проекта и продолжавшейся после предварительной теоретической подготовки примерно 220 дней, на добровольных началах участвовало около 600 человек и примерно 1600 компьютеров, объединенных сетью Internet.' К сожалению, рассказ о методе квадратичного решета увел бы нас далеко в сторону от основной темы. Потому оставим его до лучших времен, а здесь обсудим основную идею системы RSA (по первым буквам фамилий авторов: Rivest, Shamir, Adleman). Идея очень красива. Во-первых, зная p и q, можно найти pq = (p 1)(q 1). Во-вторых (и это главное!), если

= n

Шифры с открытым ключом
На вопрос, что он написал в шифровке, Штирлиц ответил: 'Не помню. Теперь это знает только Центр.'

Вообразите, что вам нужно получить зашифрованное сообщение от вашего друга, но вы с ним не договорились заранее, каким шифром будете пользоваться. Как быть? Существует ли такой метод шифрования, что его можно сообщить всему миру (в том числе и вашему другу, и врагам), но это не даст врагам возможности расшифровать сообщение? Это был бы замечательный шифр: в отличие от старых шифров, где главный секрет ключ, знание которого позволяет и зашифровывать, и расшифровывать сообщения, новый шифр 'с открытым ключом': каждый может зашифровывать, но только автор шифра может расшифровать получаемые сообщения.
Шифр RSA
...Так начались необычайные события, которые вовлекли в свой круговорот немало людей. Е.Велтистов

bg

ef = 1 + k pq ,
где e, f, k натуральные числа, то для любого числа x, взаимно простого с pq, по теореме Эйлера имеем

bg

Скорее всего, шифр с открытым ключом уже В 1978 году три математика Ривест, Шамир зашифровали некоторую английскую фразу ли награду в 100$ первому, кто расшифрует

изобретен! и Адлеман и пообещасообщение

x

ef

= x x

ej

k pq

bg

x 1 = x

b

mod pq .

g

y = 968696137546220614771409222543558829057599911 2457431987469512093081629822514570835693147662288 3989628013391990551829945157815154. Они подробно объяснили способ шифрования. Сначала фразу бесхитростно (a = 01, b = 02, c = 03,..., z = 26, пробел = 00) записали в виде последовательности цифр.
4*

Вы поняли, что такое e и f? В нашем примере e = 9007 (единственное обязательное математическое требование к числу e его взаимная простота с числом (p 1)(q 1); впрочем, брать e = 1 или e = (p 1)(q 1) 1 вряд ли разумно, если хотите сохранить секреты). А число f, как уже было сказано, решение сравнения
ef 1

d

mod pq .

b gi

(В Приложении рассказано, как алгоритм Евклида позволяет решать такие сравнения.)


16
Сравнения

КВАНT 2000/?1

y x

f

ef

x

b

mod pq

g

показывают, что для нахождения x достаточно найти f остаток от деления y на pq. (Числа выбраны так, что x < pq. При этом x не кратно ни p, ни q. Не подумайте, что это всерьез нас ограничивает: если p и q большие числа, то вероятность того, что x нацело разделится на p или q, пренебрежимо мала. Кроме того, можно предусмотреть в алгоритме, чтобы в случае чего сообщение x было автоматически как-то так чуть-чуть изменено, без изменения его смысла, что x и pq станут взаимно просты.) Почему многие надеются, что шифр RSA является шифром с открытым ключом? Да потому, что числа pq и e можно сделать общедоступными. Тогда зашифровать сообщение сможет любой, у кого есть компьютер (и какаянибудь программа, позволяющая выполнять действия с многозначными числами). Расшифровать сообщение легко, если мы знаем число f. Но единственный известный ныне способ нахождения числа f требует нахождения чисел p и q, т.е. разложения произведения pq на множители. А эффективных алгоритмов решения этой задачи пока нет (удача 1994 года не в счет: если бы в числах p и q было не 64 и 65, а хотя бы по 300 цифр, то и ресурсов сети Internet не хватило бы!). Впрочем, нет сейчас и доказательства того, что никто никогда не научится быстро (математик сказал бы: 'за время, полиномиальное от количества цифр') разлагать числа на простые множители.

Упражнение 43 (М1086). С числом разрешено производить две операции: 'увеличить в 2 раза' и 'увеличить на 1'. За какое наименьшее число операций можно из числа 0 получить число а) 100; б) 9907; в) n, если в двоичной системе счисления n имеет вид a m a m -1 K a1a 0 ?

Алгоритм Евклида
Алгоритм Евклида это способ отыскания наибольшего общего делителя, основанный на формуле НОД(a,b) = НОД(a bq, b), которая верна для любых целых чисел a, b, q. (Докажите эту формулу!) Подробно о нем рассказано в статье Н.Васильева 'Алгоритм Евклида и основная теорема арифметики' (Приложение к журналу 'Квант' ? 6 за 1998 год). Собственно говоря, нам нужен даже не алгоритм Евклида, а основанный на нем способ решения линейных уравнений. Итак, даны два взаимно простых числа e и m (в интересовавшем нас случае m = pq , но здесь это не важно). Нужно найти такие числа f и k, что

bg

ef = 1 + km. Если бы m было не очень большим, то можно было бы выполнить полный перебор всех m остатков. Но если m большое, то перебор нереален. Оказывается, алгоритм Евклида позволяет быстро решать эту задачу. Чтобы объяснить, как он работает, рассмотрим пример: e = = 9007, m = 19876. (Мы хотели взять сто-с-лишним-значное число m, но в последний момент струсили.) Уравнение 9007 f = 1 + 19876 k можно записать в виде 9007f = 1 + 9007 2k + 1862k, т.е. 9007(f 2k) = 1 + 1862k. Обозначим a = f 2k. Тогда 9007a = 1 + 1862k. Заметьте: получилось уравнение того же типа, что и исходное, только коэффициенты стали меньше. Теперь следующий шаг: 1862 4a + 1559a = 1 + 1862k, т.е. 1559a = 1 + 1862(k 4a). Обозначим k 4a = b, тогда 1559a = 1 + 1862b. Далее, 1559(a b) = 1 + 303b. Обозначив a b = c, получаем уравнение 1559c = 1 + 303 b. Дальше так же: 44c = 1 + 303(b 5c), d = b 5c, 44 c = 1 + 303d; 44(c 6 d) = 1 +39d, x = c 6d, 44x = 1 + 39d; 5x = 1 + 39(d x), y = d x, 5x = 1 + 39 y. Машина продолжила бы вычисления дальше, пока коэффициент при одной из неизвестных не стал бы равен 1. А мы остановимся уже здесь: очевидно, x = 8, y = 1 одно из решений

Приложение
Как возводить в большую степень?
Чтобы возвести число x в 9007-ю степень, по определению, достаточно выполнить 9006 умножений. Но можно обойтись и меньшим числом операций: вычислить x , x = x ,..., x
8 2

ваться формулой
x
9007

FH

2048

IK

2

=x

4096

, наконец, x
4 8 32

FH

4096

IK

2

di
2

2

=x, x

4

FH IK
4

2

=

=x
512

8192

и воспользо-

=xx x x x

2

x

256

x

x

8192

,

которая основана на том, что в двоичной системе счисления 9007 имеет вид
9007
10

= 100011 001011 112 .

Понимаете? Мы разложили 9007 в сумму 1 + 2 + 4 + 8 + 32 + + 256 +512 + 8192 и смогли сильно сэкономить: обошлись 13-ю возведениями в квадрат на первом этапе вычислений и 7-ю умножениями на втором этапе. Всего 20 умножений вместо 9006. Огромная экономия! (Для придирчивого читателя отметим, что выше следовало бы говорить не об умножениях, а об умножениях по модулю pq: дабы количество цифр не росло катастрофически, мы всякий раз должны не только перемножать, но и брать остаток от деления на pq. Но сейчас разговор не об этом.) Преимущества изложенного метода возведения в степень тем нагляднее, чем больше показатель степени. Например, если показатель степени состоит не из четырех цифр, как 9007, а из нескольких десятков или сотен цифр, то наивный способ не то что утомителен, а неосуществим ни на каких, даже самых мощных, компьютерах. А основанный на двоичной системе работает и в такой ситуации!

Окончание см. на с. 37


ШКОЛА

В

'КВАНТЕ'

37
жатся 'гармошки' колебаний (см. рис.2, точечные кривые). Кроме того, можно предложить и другую схему измерений. Например, зарядить конденсатор от какого-либо источника, затем отключить последний и сохранять на пластинах постоянный заряд (вот тут-то и пригодится пренебрежимо малая электропроводность жидкости). Тогда при прохождении через конденсатор жидкости с различным содержанием газа в пузырьках будет изменяться разность потенциалов между пластинами. Такие приборы существуют и называются емкостными датчиками. Надо признаться, что такими способами мы найдем только суммарный относительный объем газовой фазы, а не концентрацию пузырьков. Не худо было бы определить как-нибудь и их средний размер. Нужно, следовательно, использовать еще какие-то физические явления и приборы (например, оптические)... Так что, прежде чем открыть бутылку нарзана, подумайте о числе пузырьков и законах физики. И приятного аппетита!

штук в кубическом метре, но все они одинаковы и находятся в среднем на одном и том же расстоянии друг от друга порядка 1 3 N . И в результате найдем некоторую эффективную, или среднеобъемную, диэлектрическую проницаемость такой пузырьковой жидкости. Но даже эту скромную программу выполнить не очень легко, да это и не обязательно делать сейчас до конца на основе двух рассмотренных выше примеров ясно, что результат будет зависеть от суммарного объема пузырьков, попавших в конденсатор, и что временнбя зависимость тока будет скорее всего иной, чем в упомянутых примерах. А что еще мы не учли в этих случаях? Многое. Например, что диэлектрик втягивается в конденсатор. Это значит, что в первом случае 'снарядного' течения газовый пузырь, попавший в конденсатор, будет сжиматься слева и справа двумя пробками жидкости. То же самое будет происходить и с пузырьковой жидкостью, если суммарный объем пузырьков будет непостоянен в пространстве, так что дви-

жение такой газожидкостной смеси в конденсаторе не будет равномерным. Далее, в реальности существует сопротивление проводов и внутреннее сопротивление источника напряжения. Если их сумма равна r, то разность потенциалов между пластинами конденсатора запишется в виде
q Ct

и уже не будет постоянной величиной. А если учесть еще индуктивность цепи L и соответствующую ей ЭДС самоинdI дукции - L , то закон Кирхгофа dt даст стр ашное дифференциальное уравнение для заряда:

>C

= U - rI t

>C

=U, dt C t dt которое описывает затухающие колебания. Решить это уравнение сложно, так как емкость конденсатора изменяется со временем (в этом-то и состоит суть метода), но можно ожидать, что на вышенарисованные кривые зависимости заряда и тока от времени налоL
2

dq

2

+r

dq

+

q

>C

Малая теорема Ферма
(Начало см. на с. 9)
последнего уравнения. Зная x и y, легко находим d = x + y = 9, c = x + 6d = 62, b = d + 5c = 319, a = b + c = 381, k = b + 4a = 1843, f = a + 2 k = 4067. Победа! Числа k и f найдены! (Проверка: 9007 4067 = = 36631469 = 1 + 19876 1843.) Упражнение 44* (для тех, кто очень любит программировать). а) Найдите число f, которое нашли Аткинс, Крафт, Ленстра и Лейланд. б) Расшифруйте фразу, зашифрованную в 1978 году Ривестом, Шамиром и Адлеманом.

началась в древности, а существование бесконечного множества которых доказано в 1994 году. Малую теорему Ферма не обязательно доказывать именно так, как это сделано выше. Во второй части мы изложим другие способы. Один из них приведет к теореме о существовании первообразного корня по простому модулю и далее к теореме о строении мультипликативной группы вычетов по (не обязательно простому) модулю n. Чтобы вы лучше оценили силу результатов второй части статьи, подумайте над следующими задачами. Все они будут решены во второй части. Не огорчайтесь даже в том случае, если ни одна из них не получится: это не упражнения, а довольно трудные задачи! Задачи 1. Существует ли такое составное число n (число Кармайкла), что для любого целого числа a разность an a кратна n? n 2. Ни для какого натурального числа n число 2 + 1 не кратно n + 1. Докажите это. 3. Если 2n + 1 кратно n, то n = 1 или n кратно 3. Докажите это. 4. Для каких n числа 1, 2,... ..., n 1 можно расставить вдоль окружности так, чтобы для лю- # ! бых подряд идущих чисел a, b, c разность b2 ac была кратна n? (На рисункае 2 изображен случай n = 7.) 5. Для каких простых чисел " p существует такое целое число a, что a4 + a3 + a2 + a + 1 кратно p? $ Рис. 2

Что дальше?
Что остается от сказки потом, После того, как ее рассказали? В.Высоцкий

Подытожим. В первой части статьи мы доказали малую теорему Ферма и ее обобщение теорему Эйлера. Рассказали о практическом применении теоремы Эйлера в криптографии. Правда, осталось тайной, откуда взялись числа p, q (точнее говоря, как можно конструировать большие в несколько десятков или сотен цифр простые числа). Во второй части мы расскажем об основанных на малой теореме Ферма методах конструирования больших простых чисел. Расскажем и о числах Кармайкла, история которых