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

Первый способ. Если в разложение входит какое-то нечётное простое число в некоторой натуральной степени то и кратно что, в свою очередь, кратно как разность двух нечётных чисел. В противном случае либо тогда либо откуда Если то чётно и В ином случае Что и требовалось.

Второй способ. Разобьём числа на пары следующим образом: Заметим, что при чётном число останется без пары. В этом случае делит то есть оно точно не учтётся в Ясно, что НОД НОД Отсюда следует, что для каждой пары либо оба числа учитываются в либо нет. Значит, является суммой нескольких двоек, то есть делится на Осталось заметить, что при хотя бы одна пара вида найдётся.