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

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

11

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

ков (заново доказав малую теорему Ферма и теорему Эйлера в формулировках, которые позволят решить многие интересные задачи), о первообразных корнях, функции Кармайкла, числах Мерсенна и о многом другом. Статья насыщена интересными задачами. Вряд ли возможно при первом чтении решить их все. Но мы уверены: многие из них настолько заинтригуют вас, что рано или поздно все они будут решены самостоятельно или с помощью раздела 'Ответы, указания, решения'.

М

Ы РАССКАЖЕМ О ПЕРИОДИЧНОСТИ ОСТАТ-

Малая теорема Ферма гласит: a p a (mod p) для любого целого числа a и простого числа p. В частности, если a не кратно p, то a p-1 1 (mod p). Функция Эйлера n это количество взаимно простых с числом n и не превосходящих n натуральных чисел. Например, p = p 1 для любого простого p. В m m m первой части для n = p1 1 p2 2 K ps s , где p1 , p2 , ..., ps различные простые числа, m1 , m2 , ..., ms натуральные числа, доказана общая формула

bg bg

Напоминание
Как помнит читатель первой части статьи, числа a и b сравнимы по модулю n, если a b кратно n, т.е. a b = = kn, где k целое число.
Продолжение. Начало см. в 'Кванте' ?1

n = p1

b g e je p j = ep -
m1 m2 2 m1 1

K p p1
m1 -1

ej je p
ms s

= - p2
m2 -1

m2 2

j K e

ps s - p

m

m s -1 s

j

.

Теорема Эйлера это обобщение малой теоремы Ферма на случай составного модуля: a b n g 1 (mod n), где a целое число, взаимно простое с натуральным числом n.

3*

Иллюстрация М.Сумниной


12
Периодичность остатков

КВАНT 2000/?3

Таблица 2
Ч

Мы заняты делом, отвлечься не можем: мы числа в тетради все множим и множим. А.Котова

1 1 2 4 8 5 10 9 7 3 6

2 2 4 8 5 10 9 7 3 6 1

4 4 8 5 10 9 7 3 6 1 2

8 8 5 10 9 7 3 6 1 2 4

5 5 10 9 7 3 6 1 2 4 8

10 10 9 7 3 6 1 2 4 8 5

9 9 7 3 6 1 2 4 8 5 10

7 7 3 6 1 2 4 8 5 10 9

3 3 6 1 2 4 8 5 10 9 7

6 6 1 2 4 8 5 10 9 7 3

1 2 4 8 5 10 9 7 3 6

Остатки от деления на 11

Какие остатки дают степени двойки при делении на 11? Посмотрите на таблицу 1. Таблица 1
n
2n 1 2 2 4 4 3 8 8 4 16 5 5 32 10 6 7 8 9 10 11 12

64 128 256 512 1024 2048 4096 9 7 3 6 1 2 4

2n(mod11) 2

Дальше можно не продолжать: 210 + n = 210 2n 1 . 2n = = 2n mod 11 , остатки будут повторяться с периодом 10. Между прочим, средняя строка таблицы излишняя: в нижней строке каждое следующее число это остаток от деления на 11 удвоенного предыдущего числа. Как бы то ни было, 210 1 mod 11 . Ничего удивительного в этом нет, это всего лишь частный случай малой теоремы Ферма. Интереснее другое: в нижней строке таблицы 1 присутствуют все ненулевые остатки от деления на 11. Например, 3 2 8 , 5 2 4 , 7 27 , 10 25 mod 11 . Другими словами, для любого целого числа a, не кратного 11, существует такое s, что

b

g

Таблица 3
+ 0 1 2 3 4 0 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 0 2 2 3 4 5 6 7 8 9 0 1 3 3 4 5 6 7 8 9 0 1 2 4 4 5 6 7 8 9 0 1 2 3 5 5 6 7 8 9 0 1 2 3 4 6 6 7 8 9 0 1 2 3 4 5 7 7 8 9 0 1 2 3 4 5 6 8 8 9 0 1 2 3 4 5 6 7 9 9 0 1 2 3 4 5 6 7 8

b

g

b

g

a2

s

А сейчас внимание:
a
10

b

mod 11 .
s 1 = 1 mod 11 .

g

2

e j = e2 j
s 10

10 s

b

g

5 6 7 8 9

Таким образом, при p = 11 мы проверили малую теорему Ферма не только для a = 2, но для любого ненулевого остатка a. Красиво и неожиданно, не правда ли?
Упражнение 1. Рассматривая степени двойки, докажите малую теорему Ферма для а) p = 13; б) p = 19.

Что такое первообразный корень?

Число g называют первообразным корнем по простому модулю p, если числа g, g 2 , ..., g p -1 дают разные (ненулевые) остатки при делении на p. Другими словами, g первообразный корень, если для любого целого числа a, не кратного числу p, существует такое s , что a g s mod p .

b

g

Упражнение 2. а) Какие из чисел 1, 2, 3, 4 являются первообразными корнями по модулю 5? б) Какие целые числа являются первообразными корнями по модулю 7?

Число 2 первообразный корень по модулю 11

В разделе 'Таблицы умножения' первой части статьи, как помните, мы составили таблицу умножения по модулю 11. Тот факт, что 2 первообразный корень, позволяет нам так переставить ее столбцы и строки, что таблица приобретет гораздо более внятный вид (табл.2). Если a g s и b g t , то ab g s g t = g s + t mod 11 . Это

сводит умножение по модулю 11 к сложению по модулю 10 (именно по этому модулю рассматриваются числа s и t). Давайте рассмотрим таблицу сложения по модулю 10 (табл.3). Таблицы 2 и 3 очень похожи! Математик сказал бы, что мультипликативная 1 группа вычетов Z11 (ее элементы ненулевые классы вычетов по модулю 11) изоморфна аддитивной 2 группе Z10 вычетов по модулю 10. Наивно говоря, изоморфизм это взаимно однозначное отображение, сохраняющее операцию. 3 Например, изоморфизм между Z10 и Z11 можно установить, сопоставив каждому s из чисел s = 0, 1, ..., 9 число 2 . При этом сумме s + t mod 10 будет, как мы уже говорили, сопоставлено произведение 2s 2t mod 11 .

b

g

b

g

b

g

1 От латинского 'умножать'. 2 От латинского 'складывать'. 3 Точное определение изоморфизма можно найти, например, в 'Алгебре' Ван дер Вардена (М.: Наука, 1976).


МАЛАЯ

ТЕОРЕМА

ФЕРМА

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 год).


14
n

КВАНT 2000/?3

10. Натуральные числа a, b, n таковы, что a - k кратно k n b для любого натурального числа k b . Докажите, что a = b .

!% $ ! ' %
Рис.2

" " & ! ! !" # !& & % " ! !! ! ! $ ' $ " % !$ & '

!' # !#

Степени числа a по модулю F

Для любого целого числа a, не кратного простому p, -1 рассмотрим числа 1, a, a2 , ..., a p . Ни одно из них не кратно p. Поскольку ненулевых остатков от деления на p существует всего p 1 штук, а мы рассматриваем p чисел, то какие-то два из них дают один и тот же остаток:

ar a
a
s -r

s

>

mod p ,

C

#

где 0 r < s < p . Сокращая на a r , получаем:
1 m od p ,
s -r

>

C

на p равен 1. Значит, т. е. остаток от деления числа a последовательность остатков от деления степеней числа a на p периодическая.
Упражнения 11. а) Пусть число n нечетно и не кратно 5. Докажите, что существует кратное n число, записываемое одними единицами. б) Если целое число a и натуральное n взаимно просты, то существует такое k, что сумма 1 + a + a 2 + ... + ak кратна n. Докажите это. n 12. а) Докажите, что для любого натурального n числа 8 + 1 n и 5 4 + 1 составные. б) Существует бесконечно много составn ных чисел вида 10 + 3 . Докажите это. (Неизвестно, существует n ли бесконечно много простых чисел вида 10 + 3 .) в) Пусть a, b, c натуральные числа, b > 1. Докажите, что среди чисел вида n ab + c бесконечно много составных.

Что такое порядок?

Наименьшее натуральное число k , для которого ak 1 mod p , называют порядком (не кратного p) числа a по модулю p. Очевидно, числа a, a2 , ..., ak 1 дают при делении на p разные остатки, а дальше последовательность периодичk +1 a , a k + 2 a 2 , ... При этом на: a

>

C

m; сравнение a p -1 1 получается из сравнения a k 1 возведением в m-ю степень.) Теорема 3. Порядок k не кратного простому p целого числа a является делителем числа p 1. Доказательство. Идея в том, что все p 1 ненулевых остатков от деления на p мы разобьем на циклы вида {x, ax, ..., a k -1 x }. Каждый такой цикл состоит из k остатков. Например, при p = 41 и a = 10 разбиение изображено на рисунке 2, на котором стрелочкой показано действие операции умножения на 10 ('по модулю 41', т.е. мы каждый раз не только умножаем на 10, но и берем остаток от деления на 41).6 В общем случае, проведя от каждого ненулевого остатка x стрелочку к остатку от деления на p числа ax, мы получим рисунок, на котором из каждого ненулевого остатка выходит одна стрелочка и к каждому ненулевому остатку ведет тоже одна стрелочка (если бы к какому-то остатку y вели стрелочки от x1 и x2 , то выполнялись бы сравнения ax1 y ax2 mod p , откуда x1 x2 (mod p), так что x1 = x2 ). Теорема 3 доказана.

>

C

>C

Теорема Эйлера

ak a

2k

a

3k

K 1 mod p ,

>

C

а другие степени числа a не сравнимы с 1 по модулю p. Если вместо простого числа p вы рассмотрите любое натуральное число n, то аналогичным образом cможете доказать следующую важную теорему. Теорема 2. Если целое число a взаимно просто с натуральным числом n, то существует бесконечно m много таких натуральных m, что a - 1 кратно n. Все они являются кратными наименьшего из них (которое называют порядком числа a по модулю n).
Упражнения 13. Если целое число a взаимно просто с натуральным n и если НОД > r, s C 1 mod n . Докажите это. 14. Зная, что порядок числа a = 10 по модулю p = 19 равен 18, выясните, при каких k число 11K1 кратно 19. 13 2
a r a s 1 mod n , то a

Рассмотрев вместо простого p любое натуральное число n, аналогичным образом можно доказать, что порядок (по модулю n) взаимно простого с n целого числа a делитель числа n . При этом a > n C 1 mod n . Последнее утверждение, как вы помните, носит имя Леонарда Эйлера.

>C

>

C

Упражнения 16. Существует ли такое натуральное число k, что сто последних цифр десятичной записи числа 3k совпадают со ста последними цифрами числа 7k ? 17. Если a и b взаимно простые натуральные числа, то >bC >a C a +b 1 mod ab . Докажите это. 18. Существует бесконечно много натуральных чисел n, для 2 n которых 2 + n кратно 100. Докажите это. 19. Для любого простого числа p существует бесконечно много n чисел вида 2 - n , кратных p. Докажите это. 20. а) Последние две цифры квадрата любого натурального числа и его 22-й степени совпадают: n 2 n 22 mod 100 . Докажите это. б) Докажите, что n103 n 3 mod 1000 для любого целого числа n. n n n 21. Докажите, что последние цифры чисел вида а) n ; б) n (n натуральное) образуют периодическую последовательность, и найдите длину ее наименьшего периода. 1999 1999 22. Найдите четыре последние цифры числа а) 3 ; б) 2 ;

>

C

>

C

>

C

>

C

>

C

15. Если число 1000...01 кратно 19, то оно кратно 13. Докажите это.

k

Разбиение на циклы

Пусть целое число a не кратно порядок числа a по модулю сформулировать малую теорему кратно k. (Т.е. p 1 = km для

простому p и пусть k p. Как при помощи k Ферма? А вот как: p 1 некоторого натурального

в) 2

2000 3

.

6 Эти циклы тесно связаны с разложениями обыкновенных дробей со знаменателем 41 в периодические десятичные дроби (см. статью Л. Семеновой 'Периодические дроби' в 'Кванте' ?2 ).


МАЛАЯ
7 7 z

ТЕОРЕМА

ФЕРМА
2

15

23*. Докажите, что уравнение x + y = 1998 не имеет решений в натуральных числах. 24*. Для любого целого числа k 1 существует бесконечно n 2 много натуральных чисел n, для которых число 2 + k составное. Докажите это. (Аналогичное утверждение для k = 1 мы доказать не умеем: существует или нет бесконечно много составных чисел вида 2
2 n

База случай m = 3. Число a - 1 = (a 1)(a + 1) кратно 8, поскольку одно из соседних четных чисел a 1 и a + + 1 кратно 4. Переход. Пусть утверждение верно для некоторого m 3 . Рассмотрим разложение на множители:

+ 1 , неизвестно.)

a

2

m -1

-1 = a

FH

2

m- 2

-1 a

IK FH

2

m -2

+1 .

IK

Усиление теоремы Эйлера
Рассмотрим утверждение теоремы Эйлера при n = 360. Очевидно, 360 = 23 5 9 = 4 4 6 = 96. Значит, для любого целого числа a, взаимно простого с 360, выполнено сравнение

bgc
a
a

h

Поскольку первый множитель правой части делится на m 2 , а второй множитель четен, произведение делится на 2m +1 , что и требовалось доказать.
Упражнение 26. Пусть a нечетно, m 3 . а) Решите сравнение m m 2 2 mod 2 . б) Докажите, что сравнение x a mod 2 разрешимо для тех и только тех a, для которых a 1 mod 8 .
x a
2

96

1 mod 360 .
1 mod 360 .

А на самом деле верно даже сравнение
12

b

g

e

j

e b

g

j

b

g

Для доказательства достаточно применить теорему Эйлера к каждому из модулей 8, 5 и 9:

a 4 1 mod 8 ,
a 1 mod
4

a 6 1 mod

и заключить, что a12 1 по каждому из модулей 8, 5 и 9, а значит, и по модулю 360. В общем виде это можно сформулировать следующим образом. Рассмотрим разложение
n = p1 1 p2 2 K p
m m ms s

b b b

g 5g 9g

, ,

Через n обозначим такое наименьшее натуральное число k, что a k - 1 кратно n для любого числа a, взаимно простого с n. Функцию называют функцией Кармайкла. Легко понять, что для любого натурального числа l, не кратного n , существует такое взаимно простое с n целое l число a, что a 1 mod n . Чтобы это доказать, разделим / с остатком l на n . Имеем:

bg

Функция Кармайкла

bg

b bg

g

l = n q + r,

где q целое неотрицательное, 0 < r < n . При этом

bg

числа n в произведение степеней различных простых множителей. Обозначим через f n наименьшее общее кратное чисел pi
3

f(360)= НОК = НОК 4, 6, 4 = 12.) Тогда при любом целом a, взаимно простом с n, справедливы сравнения

ej e2 j, e3 j, b5g
mi 2

, где i = 1, 2, ..., s. (Например,

bg

a

fn

bg

1 mod pi

где i = 1, 2, ..., s; следовательно,

e

mi

j

,

a

fn

bg

1 mod n .

Упражнение 25. а) Для каких натуральных n верно равенство f(n) = n ? m б) Пусть n > 4 и n не представимо ни в виде p , ни в виде 2 p m , где p нечетное простое, m натуральное. Докажите, что невозможно так расположить все n меньших n и взаимно простых с ним натуральных чисел вдоль окружности, чтобы для 2 любых трех стоящих подряд чисел a, b, c разность b ac делилась на n. (Другими словами, для этих n нет первообразного корня, т.е. нет числа g, порядок которого по модулю n равен n .)

b

g

bg

bg

bg

Сравнения по модулю 2m

Пусть m натуральное число, m 3 . Теорема Эйлера утверждает, что a для любого нечетного 1 mod 2 числа a. На самом деле верно более сильное утверждение:
2
m -1

e

m

j

g b g 1 m od n g , a откуда для числа k = НОК b mg, bng имеем a 1 b m od m g , a 1 b mod ng , так что a 1 b mod mng . Таким образом, bmng k . Осталось доказать, что bmng делится как на bmg , так и на bn g . Сделаем это 'от противного'. Пусть, например, l = bmng не делится на bm g . Тогда существует такое число b, взаимно простое с m, что b / 1 bmod m g . Рассмотрим число a, для которого a b bmod mg и a взаимно просто с n. Очевидно, a b /1 bmod mg , что и
a
m

Поскольку r < n , хотя бы для одного взаимно простого с n числа a сравнение a r 1 mod n не выполнено. Это и требовалось доказать. Функция Кармайкла обладает еще одним интересным свойством: mn = НОК m , n для любых взаимно простых натуральных чисел m и n. В самом деле, если целое число a взаимно просто с числами m и n, то по определению

bg

al = a

e

n

bg

j

q

bg

ar .

b

g

bg

b g bg b b

bg

1 mod m ,

n

k

k

k

l

7

l

l

требовалось доказать.

a

2

m -2

1 mod 2

Его легко доказать по индукции.
4*

e

m

j

.

7 Почему такое a существует? Например, можно рассмотреть числа вида b + mx, где x = 1, 2, ..., n. Они дают разные остатки при делении на n. Поскольку этих чисел n столько же, сколько классов вычетов по модулю n, то среди них найдется и нужное нам a.


16

КВАНT 2000/?3

Функция Кармайкла от степеней простых чисел такова: 2 = 1, 4 = 2, 2 m = 2 m -2 при m 3 , p m = = p m -1 p - 1 для любых нечетного простого p и натурального m.

bg

b

g

bg

ej

ej

Упражнение 27*. Докажите это, считая известным, что если p нечетное простое, то для любого k < p 1 существует такое не кратное p число g, что g k 1 mod p . /

b

g

на q. Докажите, что q 1 mod n . (Биркгоф и Вандивер, используя свойства многочленов деления круга, доказали в 1902 году, что для любых (кроме одного исключительного случая, о котором сказано ниже) натуральных взаимно простых чисел a и b, где a > b, и для любого натурального числа n > 2 существует простой делитель q разности a n - b n , не являющийся делителем ни одной разности a m - b m , где m < n. Единственное исключение: a = 2, b = 1, n = 6.)

b

g

Следствия из малой теоремы Ферма
Теорема 3 позволяет легко решать многие задачи, которые без нее или очень трудны, или вообще недоступны. Рассмотрим букет таких задач, начав с одной из тех пяти, которые сформулированы в конце первой части статьи.
Простые делители чисел вида a + a + a + a + 1
4 3 2

Простые делители чисел видаa
2 2 a -1 mod p ,

2n

+1

Если a + 1 делится на простое число p, p 2 , то откуда
4

b

g

a=a

Если сумма a 4 + a3 + a2 + a + 1 кратна простому числу p, то число

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

5

b

тоже кратно p. Рассмотрим два случая. Пусть a 1 mod p . Тогда a 4 + a3 + a2 + a + 1 4 3 2 1 + 1 + 1 + 1 + 1 = 5 mod p , так что число p должно быть делителем числа 5. Попросту говоря, p = 5. Пусть теперь a 1 mod p . Тогда порядок числа a по / модулю p равен 5. Поскольку порядок является делителем числа p 1, то p 1 делится на 5. Итак, если простое число p является делителем числа 4 3 2 вида a + a + a + a + 1 , то p = 5 или p 1 mod5 .

ge

4

3

2

j

b

b

b

g

g

g

Значит, порядок числа a равен одному из чисел 1, 2 и 4. Первый и второй случаи невозможны, поскольку сравнение a2 1 противоречит сравнению a 2 -1 mod p . В третьем случае в силу теоремы 3 имеем: p 1 делится на 4. Мы доказали довольно общее и часто используемое утверждение: любой нечетный простой делитель числа 2 a + 1 имеет вид p = 4k + 1 (а не 4k + 3). Рассуждая аналогично, можно доказать, что если p n нечетный простой делитель числа a 2 + 1, то p 1 делится n +1 на 2 .

e j b-1g
22

2

= 1 mod p .

b

g

b

g

b

g

Верно и обратное: для любого простого числа p = 2n +1k + 1 n существует кратное ему число вида a2 + 1 . Доказать это очень легко, если знать теорему о существовании первообразного k корня g. В самом деле, пусть a = g . Тогда

Когда мы докажем теорему о существовании первообразного корня, то поймем, что верно и обратное утверждение. А именно, для p = 5 годится a = 1, а для простого числа p = 5k + 1 годится a = g k , где g первообразный корень по модулю p. В самом 5k деле, g = g p -1 1 mod p . Следовательно, произведение множитель не делится на p, второй должен делиться, что и требовалось доказать. Упражнения 28 (М1324). Ни при каком целом a число a + a + 1 не кратно а) 5; б) 11; в) 17; г) 6m 1, где m натуральное число. Докажите это. 29. Докажите, что всякий положительный делитель числа 4 2 a - a + 1 дает остаток 1 при делении на 12. 30. Докажите, что если порядок числа a по простому модулю p равен 2 а) 3, то число a + a + 1; б) 4, то число a 2 + 1; в) 15, то число a8 - a7 + a5 - a4 + a3 - a + 1 кратно p. (Тот, кто знаком с многочленами деления круга, скажет, что это упражнение частный случай общего утверждения: число a имеет порядок k тогда и только тогда, когда k делитель числа p 1 и k a 0 mod p .) 31. Если по простому модулю p число a имеет порядок а) 3, то порядок числа a + 1 равен 6; б) 10, то порядок числа 3 2 a - a + a - 1 равен 5. Докажите это. 32. а) Пусть a натуральное число, a > 1, p простое, p p > 2. Докажите, что всякий простой делитель q числа a + 1 является делителем числа a + 1 или имеет вид q = 2pm + 1, где m натуральное. б) Пусть a, b взаимно простые целые числа, n натуральное, n n q простое, a - b делится на q, и пусть ни для одного m m отличного от n делителя m числа n разность a - b не делится
2

Число g не сравнимо с единицей по модулю p, но квадрат этого числа есть g p -1 1 mod p . Поэтому
a
2 n

b

p -1 2

g

a

2

n

=g

n 2k

=g

b

p -1 2

g.

b

b

a - 1 a + a + a + a + 1 = a - 1 кратно p. Поскольку первый

ge

4

3

2

b

j

g

=g

b p -1g

2

g

-1 mod p ,

b

g

5

что и требовалось. Упражнения 33. Если числа a и b взаимно nпросты, то всякий нечетный n 2 2 простой делитель p числа a + b дает остаток 1 при делении на 2 . Докажите это. 34. Пусть a, n натуральные числа, причем a четно. Докажиn 2 те, что числа n и a + 1 взаимно просты. 35. Пусть a, n натуральные числа. Докажите, что n a) если a + 1 делится на n + 1, то a и n нечетны; б) если a нечетно и a > 1, то существует бесконечно много n натуральных n, для которых a + 1 делится на n + 1. n 36. а) Пусть n > 1 и 2 + 2 делится на n. Докажите, что n четно. б) Существует бесконечно много таких натуральных n, что n 2 + 2 кратно n. Докажите это. 37 (Международная математическая олимпиада, 1996 г.). Пусть a, b такие натуральные числа, что 15a + 16b и 16a 15b квадраты натуральных чисел. Найдите наименьшее возможное значение меньшего из этих квадратов.
n +1

bg b

g

Когда 2n + 1 делится на n?

Этот вопрос один из нас задал себе скорее в шутку, чем всерьез. И очень долго мы оба не понимали, что закономерности, обнаруживаемые в вычислениях, производимых следующей программой 8 , имеют самое непосредственное отношение к малой теореме Ферма.
8 Программу для нас написал В.Иофик тогда абитуриент, а сейчас студент мехмата МГУ.


МАЛАЯ

ТЕОРЕМА

ФЕРМА

17
кратно n и n > 1, поголовно делятся на 3? Подумав несколько недель, мы поняли: надо рассмотреть наименьший простой делитель p числа n. Тогда
2 -1 mod p .
n

b

Значит, 22 n 1 mod p , и поэтому порядок числа 2 по модулю p является делителем числа 2n. Поскольку он не превосходит p 1 и поскольку число n не имеет простых делителей, меньших p, есть единственная возможность: порядок числа 2 по модулю p равен 2 . Это значит, что 22 1 mod p , т. е. p = 3, что и требовалось доказать.

b

g

g

b

g

Результаты работы этой программы таковы: 2n + 1 делится на n при n = 1, 3, 9, 27, 81, 171 9 , 243, 513, 729, 1539, 2187, 3249, 4617, 6561, 9747, 13203 10 , 13851, 19683, 29241, 39609, 41553, 59049, 61731, 87723, 97641, 118827, 124659, ... Все эти числа (кроме единицы, но она не в счет) делятся на 3. И среди них присутствуют все степени тройки. Как это объяснить? Со степенями тройки мы разобрались мгновенно: по k k +1 индукции легко доказать, что 2 3 + 1 делится на 3 . И мы сразу сообразили, что верно следующее утверждение: если n кратно 3 и 2n + 1 кратно n, то 23n + 1 кратно 3n. В самом деле,

2

3n

+ 1 = 2n + 1

e

первый множитель кратен n, а второй кратен 3. (Почему? Потому что из условия 2n -1 mod n имеем 2n 2 2 1 ( m o d 3),откуда 2n - 2n + 1 -1 - -1 + 1 0 mod 3 .) Но это все не отвечало на самый наивный и самый интересный вопрос: почему числа n, для которых 2n + 1

jFH e2 j
n

2

- 2n + 1 ;

I K

b

g

di

b

bg bg

g

Упражнения 38. Пусть a, n натуральные числа, n > 1. Докажите, что если a n + 1 делится на n, то наименьший простой делитель числа n является делителем числа a + 1. 39. Пусть n натуральное n число, n > 3 и 2 + 1 кратно n. Докажите, что а) n кратно 9; б) если n > 9, то n кратно 27 или 19; в) если n делится на простое число p 3 , то p 19 ; г*) если n делится на простое число p, причем p 3 и p 19 , то p 163 . a b 40. Если 2 + 1 кратно b и 2 + 1 кратно a, где a > 1 и b > 1, то a и b кратны 3. Докажите это. 41 (М1260*). Найдите все такие натуральные n, для которых n 2 2 + 1 кратно n . n 42. а) Если 2 - 1 кратно n, то n = 1. Докажите это. б) Докажите, что существует бесконечно много натуральных n чисел n, для которых НОД 2 - 1, n > 1. в) Пусть a натуральное число, a > 2. Докажите, что n множество натуральных чисел n, для которых a - 1 кратно n, бесконечно. 43. Пусть a натуральное число, a > 1. n а) Существует бесконечно много n таких, что a + 1 делится на n. Докажите это. n б) При каких a существует число n > 1 такое, что a + 1 2 делится на n ?

e

j

(Окончание следует)

9 Заметьте: предыдущие числа степени тройки, а 171 = =19 9. 10 Впервые возник отличный от 3 и 19 простой множитель: 13203 = 163 81.
5 Квант ? 3