Функция Эйлера и теорема Эйлера из ТЧ

Так как функция Эйлера мультипликативна, то если — это примарный сомножитель в разложении то является степенью двойки, что возможно только в двух случаях: или Легко видеть, что если не является степенью двойки, то не простое. Поэтому любой примарный сомножитель это либо степень двойки, либо одно простое число Ферма, то есть простое вида

Положим (отметим, что не все из них простые). Так как и взаимно просты, то функция Эйлера от каждого из них является степенью двойки. Пусть

где и — простые числа Ферма. Заметим, что

поэтому любое число Ферма больше произведения всех меньших.

Среди различных чисел и выберем наибольшее, пусть это Если оно в разложении числа то очевидно, что будет сильно больше числа Значит, оно в разложении числа Пусть делится на но не делится на (возможно,

Рассмотрим числа и по модулю Все числа Ферма, которые есть в разложении, кроме дают остаток от деления на дает остаток от деления на Тогда с одной стороны дает остаток такой же, как а с другой стороны — Значит,

Тогда а число делится на и на Если то и, следовательно, число — степень двойки. Покажем, что случай невозможен. В этом случае число делится на и на Пусть Тогда

— противоречие.

Пусть Тогда а Если — произведение всех чисел Ферма, меньших то а откуда и что запрещено условием. В противном случае

— снова противоречие.