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

Пусть 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) ). Но многие читатели этой книжки очень скоро будут преподавать математику в средней школе, а некоторые, может быть, уже сейчас занимаются этой благородной деятельностью. Поэтому я не могу удержаться и приведу здесь еще один изящный вариант доказательства теоремы Ферма, доступный среднему школьнику или, по крайней мере, школьнику из школы с углубленным изучением математики.

 

 


2012-12-21 • Просмотров [ 972 ]