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

Для подходит далее считаем Пусть Будем искать, такое что

Пусть не делится на не делится на Покажем, что кратные подходят.

Сделаем оценку на рассмотрев по модулю при

так как по модулю принимает только значения Отдельно рассмотрим случай

Получаем, что Тогда для любого имеем:

Из тогда по теореме Эйлера имеем:

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

Сделаем оценку на

Тогда аналогично получаем, что:

для всех Аналогично случаю для по теореме Эйлера:

для кратных Тогда подходит