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

Пусть Пусть взаимно просто с тогда взаимно просто с Рассмотрим число Тогда взаимно просто с Заметим, что кратно по теореме Эйлера, а кратно , поскольку делится на . Следовательно, делится на . Значит, все простые делители числа входят в в тех же степенях, что и в само при этом число больше; следовательно, у него есть другой простой делитель. Итого, по числу мы получили у которого количество различных простых делителей больше. Теперь рассмотрим тогда взаимно просто с и у числа есть некоторые простые делители. Производя аналогичную процедуру, за шагов мы получим число у которого не менее различных простых делителей.