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

МАЛАЯ

ТЕОРЕМА

ФЕРМА

13

Числа на окружности
Для любых трех стоящих подряд чисел a, b, c рисунка 1 разность b 2 - ac кратна 11. И это не случайный курьез, а частный случай общей конструкции: взяв первообразный корень g по простому 2 модулю p, рассмотрим геометрическую прогрессию g, g , ... p -2 p -1 и выпишем вдоль окружности остатки от деления ..., g , g ее членов на p. (Рисунок 1 иллюстрирует случай g = 2 и p = 11, заставка к статье случай g = 6 и p = 13.) $ Дело вот в чем: если числа a, b, c " образуют геометрическую прогрессию, ! 2 то выполнено равенство b = ac . (А поскольку мы заменяли числа на их & остатки от деления на p, то вместо % равенств получаем сравнения по моду# ' лю p.) Итак, когда мы докажем, что по проРис.1 стому модулю p существует первообразный корень 4 , то одновременно докажем и возможность такого расположения чисел 1, 2, ..., p 1 вдоль окружности, при котором для любых трех стоящих подряд чисел a, b, c разность 2 b - ac кратна p. Упражнение 3. Пусть n составное. Можно ли так расположить числа 1, 2, ..., n 1 вдоль окружности, чтобы для любых 2 трех стоящих подряд чисел a, b, c разность b - ac была кратна n?

по модулю 23. (А вот 2 и 3, как можно убедиться, являются.)
Упражнение 6. Найдите наименьшее простое число p, для которого существует a, не сравнимое по модулю p ни с одним из чисел 1, 0, 1 и такое, что ни a, ни a не являются первообразными корнями по модулю p.

Когда a

m

- 1 делится на ak - 1 ?

От числовых примеров перейдем к более абстрактным рассуждениям. Прежде всего напомним формулы сокращенного умножения:
a2 - 1 = a - 1 a + 1 ,

a 3 - 1 = a - 1 a2 + a + 1 ,
и вообще,
an - 1 = a - 1 a

b

b

ge

gb

g

j

b

gd

n -1

+a

n -2

+K+ a + 1 .

i

Теорема 1. Если a, k, m натуральные числа, a > 1, m k то a - 1 делится на a - 1 в том и только том случае, когда m делится на k. Доказательство. Если m = kn, то

am 1 = ak 1 ak bn 1g + ak b

b

gd

n 2

g + ... + ak + 1 .

i

Степени двойки по модулю 17

Рассмотрим остатки от деления степеней двойки на 17 (табл.4). Таблица 4
n
2n(mod17) 1 2 2 4 3 8 4 16 5 15 6 13 7 9 8 1

Обратно, если m не делится на k, то разделим m на k с остатком: m = kn + r, где 0 < r < k, и рассмотрим равенство
a
kn + r

-1 = a

kn + r

- a + a - 1 = ar a

r

r

e

kn

- 1 + ar - 1 .

je

j

Зацикливание произошло слишком рано: 28 1 mod 17 . Поэтому не все ненулевые остатки от деления на 17 остатки от деления степеней двойки. Например, в нижней строке таблицы 4 нет числа 5, так что разность 2n - 5 не кратна 17 ни при каком натуральном n.
Упражнения 4. Докажите, что ни при каком натуральном n число 1719n - 3 не кратно 17. 5. Среди чисел вида 2n - 3 бесконечно много чисел, кратных 5, и бесконечно много чисел, кратных 13, но нет ни одного числа, кратного 65 (= 5 13). Докажите это.

b

g

Число ar - 1 не делится на ak - 1 , поскольку 0 < ar - 1< < ak - 1 . Теорема доказана.
Упражнения 7. Если число an - 1 простое, a > 1 и n > 1, то a = 2 и n p простое. Докажите это. (Не при всяком простом p число 2 - 1 11 простое: например, 2 - 1 = 2047 = 23 89 . Простые числа вида p 2 - 1 называют числами Мерсенна 5 . В настоящий момент известно 38 чисел Мерсенна и неизвестно, конечно или бесконечно их множество. В 1997 году было найдено число Мерсенна 2976221 2 - 1 , а 1 июня 1999 года нашли наибольшее из известных 26972593 на сегодняшний день: 2 - 1 .) n 8. Если a + 1 простое число, a, n натуральные числа, a > 1, то a четно и n степень числа 2. Докажите это. (Простые числа вида 2
2 0
2 n

Степени тройки по модулю 17

+ 1 называют числами Ферма. Их известно всего
1 2

Давайте начнем не с двойки, а с тройки и, не забывая переходить к остатку от деления на 17, будем умножать, умножать и умножать на три: 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1. Мы получили все 16 возможных ненулевых остатков от деления на 17. Значит, 3 первообразный корень по модулю 17. Не для каждого простого числа p в качестве первообразного корня годятся 2 или 3. Например, легко проверить, что

пять: 2 + 1 = 3, 2 + 1 = 5, 22 + 1 = 17, 22 + 1 = 257 и 2 + 1 = = 65537. Существуют ли другие, неизвестно. Неизвестно и то, конечно или бесконечно множество простых чисел вида p = 2 = a + 1 .) n m 9. а) Число 2 - 1 делится на 2 + 1 тогда и только тогда, когда n делится на 2m. Докажите это. б) Для каких натуральных чисел n m m существует такое натуральное n, что 2 + 1 делится на 2 - 1 ?
2

2

3

4

211 1 311 mod 23 ,
так что ни 2, ни 3 не являются первообразными корнями
4 А мы это докажем, хотя и не в этом номере журнала.
4 Квант ? 3

b

g

5 Марен Мерсенн (15881648) занимался математикой, теорией музыки, физикой и философией. Он был товарищем Р. Декарта по учебе в иезуитском колледже и членом монашеского ордена минимов. Мерсенн сыграл выдающуюся роль как организатор науки. Он состоял в переписке с Р. Декартом, Ж. Робервалем, Б. Паскалем, Х.Гюйгенсом, Б.Кавальери, Б.Френиклем де Бесси, Дж.Валлисом и др. Вокруг него образовался кружок ученых, который стал основой для создания Парижской Академии наук (1666 год).