Теорема (Эйлера)
Пусть m>1 , (a,m)=1 , j ( m ) – функция Эйлера. Тогда:
a j ( m ) º 1(mod m) .
Доказательство. Пусть х пробегает приведенную систему вычетов по mod m :
x=r 1 ,r 2 ,...,r c
где c= j (m) их число, r 1 ,r 2 ,..., r c - наименьшие неотрицательные вычеты по mod m . Следовательно, наименьшие неотрицательные вычеты, соответствующие числам ax суть соответственно:
r 1 , r 2 ,..., r c
– тоже пробегают приведенную систему вычетов, но в другом порядке. Значит:
a × r 1 ºr j 1 (mod m)
a × r 2 ºr j 2 (mod m)
...
a × r c ºr j c (mod m)
Перемножим эти с штук сравнений. Получится:
a c r 1 r 2 ...r c ºr j 1 r j 2 ... r j c (mod m)
Так как r 1 r 2 ...r c = r 1 r 2 ... r c ¹ 0 и взаимно просто с модулем m , то, поделив последнее сравнение на r 1 r 2 ...r c , получим a j ( m ) º 1(mod m) .
Вторая теорема этого пункта – теорема Ферма – является непосредственным следствием теоремы Эйлера (конечно, при схеме изложения материала, принятой в этой книжке).
Теорема (Ферма)
Пусть р – простое число, р не делит a . Тогда:
a p-1 º 1(mod p) .
Доказательство 1. Положим в условии теоремы Эйлера m=p , тогда j (m)=p-1 (см. пункт 14 ) . Получаем a p-1 º 1(mod p) .
Необходимо отметить важность условия взаимной простоты модуля и числа a в формулировках теорем Эйлера и Ферма. Простой пример: сравнение 6 2 º 1(mod 3) очевидно не выполняется. Однако можно легко подправить формулировку теоремы Ферма, чтобы снять ограничение взаимной простоты.
Следствие 1. Без всяких ограничений на a Î Z ,
a p º a(mod p) .
Доказательство. Умножим обе части сравнения a p-1 º 1(mod p) на a . Ясно, что получится сравнение, справедливое и при a , кратном р .
Конечно, доказательство 1 теоремы Ферма получилось столь коротким благодаря проведенной мощной предварительной подготовке ( доказана теорема Эйлера и изучены свойства функции j (m) ). Но многие читатели этой книжки очень скоро будут преподавать математику в средней школе, а некоторые, может быть, уже сейчас занимаются этой благородной деятельностью. Поэтому я не могу удержаться и приведу здесь еще один изящный вариант доказательства теоремы Ферма, доступный среднему школьнику или, по крайней мере, школьнику из школы с углубленным изучением математики.
