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

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

#

В.СЕНДЕРОВ, А .СПИВАК
Напоминание
Малая теорема Ферма гласит: если а целое число, не делящееся на простое число р, то a p -1 1 делится на р. Функция Эйлера n это количество натуральных чисел от 1 до n, взаимно простых с n. Функция Кармайкла n это такое наименьшее натуральное число k, что для всякого целого числа а, взаимно простого с натуральным числом n, разность a k 1 делится на n. Число g называют первообразным корнем по модулю n, если для всякого целого а, взаимно простого с n, существует такое натуральное число m, что m g a mod n . Подробно об этих и многих других понятиях и теоремах арифметики можно прочитать в предыдущих частях статьи. Там не было доказано существование первообразного корня по простому модулю. Пришла пора это сделать.

том и только том случае, когда s и p 1 взаимно просты.
Упражнения 44. Докажите это. 45. Для того чтобы число a было первообразным корнем по простому модулю p, необходимо и достаточно, чтобы a не делилось на p и ни для какого простого делителя q числа p 1 разность ab p -1g q - 1 не делилась бы на p. Докажите это. 46. Найдите наименьшее натуральное число, являющееся первообразным корнем по модулю а) 23; б) 41; в) 257. 47. a) Проверьте, что 2 не является первообразным корнем по модулю 263, а 2 является. 3 б) Пусть a - a не делится на 83. Докажите, что ровно одно из чисел a и a является первообразным корнем по модулю 83. 48. a) Пусть p простое число, p 1 mod 4 . Докажите, что число a является первообразным корнем по модулю p тогда и только тогда, когда само число a первообразный корень по модулю p. б) Пусть p простое число, p 3 mod 4 . Докажите, что число a является первообразным корнем по модулю p тогда и только тогда, когда порядок числа a по модулю p равен (p 1)/2.

Видна закономерность? Если нет, посмотрите на таблицу 7, составленную для p = 13.
Таблица 7
a k a k 1 1 7 12 2 12 8 4 3 3 9 3 4 6 10 6 5 4 11 12 6 12 12 2

bg

bg

b

g

В ней порядки делители числа 12. Посчитаем, сколько раз встречаются в нижней строке таблицы 7 числа 1, 2, 3, 4, 6 и 12 (табл.8).
Таблица 8
Порядок В стречается 1 1 2 1 3 2 4 2 6 2 12 4

b

g

Первообразные корни
Первообразные корни по модулю 11

Число 2 первообразный корень по модулю 11. Какие еще есть первообразные корни по этому модулю? Для ответа не нужно перебирать все числа 3, 4, 5, ..., 9, 10 и составлять для каждого из них таблицу. Некоторые степени двойки можно сразу отбросить:

b

g

Порядки классов вычетов

А вот степени двойки 21 2 , 2 8 , 7 2 7 и 2 9 6 , показатели которых взаимно просты с 10, являются первообразными корнями. (Обдумайте это!) И вообще, если g первообразный s корень по простому модулю p, то g является первообразным корнем в
Окончание. Начало см. в 'Кванте' ?1, 3.
4*

c2 h = 2 1 , c2 h = 2 1, e2 j 1 , e2 j 1 , e2 j 1 bmod 11g
25 4 10 5 20 5 2 6 5 8 5

В таблице 5 для каждого ненулевого остатка a mod 11 указан его порядок k. Как и должно быть, порядки делители числа 10. Давайте посчитаем, сколько раз в нижней строке

b

g

Таблица 5

.
3

a k

1

2

3

4 5

5 5

6

7

8

9

10 2

1 10 5

10 10 10 5

таблицы 5 встречаются числа 1, 2, 5 и 10. Ответы запишем в виде таблицы 6.
Таблица 6
Порядок В стречается 1 1 2 1 5 4 10 4

Если вы все еще не догадались, составьте такие таблицы для нескольких других простых чисел p, и рано или поздно увидите, что в нижних строках этих таблиц значения функции Эйлера: 1 = 1, 2 = 1, 3 = 2, 4 = 2, 5 = 4, 6 = = 2, 10 = 4, 12 = 4. Великий немецкий математик К.Ф.Гаусс (17771855) в 'Арифметических исследованиях', опубликованных в 1801 году, доказал, что это не случайность, а общий закон. Теорема 4. Среди p 1 ненулевых классов вычетов по простому модулю p порядок k, где k делитель числа p 1, имеют ровно (k) классов вычетов. (В частности, для любого простого числа p существует (p 1) первообразных корней по модулю p.) Для доказательства теоремы 4 мы используем теорему Безу и одно интересное свойство функции Эйлера.

bg

bg

bg

bg bg bg

bg bg

Теорема Безу

Для тех, кто знаком с делением многочленов с остатком, теорему Безу1 можно сформулировать и до1 Этьен Безу (17301783) французский математик.