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

Обозначим через степень вхождения двойки в разложение числа

Лемма. Пусть — натуральное число. Если делится на некоторое простое то и делится на некоторое простое Более того, если делится на простое то при этом равенство достигается тогда и только тогда, когда и

Доказательство. Если в разложении числа нет простых, больше или равных то их нет и в разложении Пусть Тогда

Каждое из чисел больше нуля, поэтому если таких чисел хотя бы два, или одно из них хотя бы то Иначе где Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем, что ни один из членов последовательности не делится ни на одно простое число, большее или равное Предположим противное, и пусть делится на простое Тогда, согласно лемме, для каждого число делится на некоторое простое Согласно лемме, последовательность начиная с будет не возрастать. Поскольку убывать бесконечно она не может, то, начиная с некоторого момента, она стабилизируется, и опять же из леммы, при всех достаточно больших Тогда

то есть

Поскольку то делится на Значит, а Следовательно, начиная с некоторого момента и Но тогда последовательность по модулю зацикливается, а поскольку зацикливается без предпериода. Значит, найдётся что делится на что невозможно.

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

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