в ряду 1, 2, ...,

р взаимно простыми с р будут все числа,

таким образом, ф (р) — 1; соответствующий случай

Эйлера был ранее доказан Ферм.

Теор е ма Фер й. Если р— простое число и а не

на р, 110

aP-1=l (mod р).

П р и м е ч а н и е. Это предложение часто называют «малой

теоремой Ферма» в отличие от так называемой «великой теоремы

Ферма» о невозможности решения в целых положительных чи-

слах уравнения при целом п (это утвержде-

ние, доказательством которого Ферма, по его свидетельству, обла-

дал, как известно, не доказано до настоящего времени). Если изме-

рять важность той или другой теоремы её ролью и значением

в развитии данной отрасли науки, то следовало бы, пожалуй, при-

нять обратную терминологию. Если «великая» теорема когда-либо

будет доказана, то сам этот факт, насколько здесь возможно пред-

видение, не даст науке никакой опорной точки для значительных

новых достижений и, по всей вероятности, останется более или

менее изолированным, Напротив, установленная нами «малая» тео-

рема уже давно стала важнейшим орудием исследования и притом

не только в теории целых чисел, но и в значительно более широких

областях арифметики и алгебры.

Мы переходим теперь к установлению вида функции

означающей число натуральных чисел, не превосходящих т и вза-

имно простых с т.

Прежде всего мы докажем, что если числа т и п взаимно про-

сты, то

9 (ТП) (Т) 9 (П).

Чтобы подсчитать ф (тп), удобно расположить натуральные•

числа от до тп в следующую таблицу:

280

ЭЛЕМЕНТЫ ТЕОРИИ

П р им е р. ф (10) 4;

— 1 (mod 10)-

В частном случае, когда модулем

2.

ЧИСЕЛ

7' = 2401

служит простое

число р,

кроме р;

теоремы

делится

nz-}-k

2tn+k

т

2m

31П

пт

и постараться определить, сколько эта таблица содержит чисел,

взаимно простых с произведением тп. Но для того, чтобы быть