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

Предположим, что у есть простой нечётный делитель причём при Тогда

что невозможно. Допустим, что не является степенью двойки. Если при то для различных простых причём Функция Эйлера вычисляется как Обозначим через степень вхождения в число Тогда

так как все нечётны. Это значит, что что невозможно.

Таким образом, если — не степень двойки, то Если опять же в силу нечётности всех имеем

что опять ведёт к противоречию.

Итак, если — не степень двойки, то для некоторого нечётного простого и тогда Тогда условие можно переписать как

и пользуясь получаем, что При этом и — чётное, значит могут подойти Они действительно все подходят, что даёт ответы

Наконец, разберём случай, когда Для такого сумма делителей Подставляя в условие, получаем Если то

противоречие. Однако, подходит, что также даёт ответы и