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

Будем доказывать по индукции. Давайте сначала проверим для n = 2. Очевидно, что делится и на 1, и на 2, а дальше мы будем делать следующее: рассматривать выражение, где в обеих степенях на одну двойку больше и в доказательстве предполагать, что для меньшего количества двоек мы уже все доказали.

(Идея индукции заключается в том, что мы доказываем два факта: если для какого-то числа наше условие верно, то и для оно тоже будет верно (эта часть решения называется "переход") и что наше условие верно для некоторого минимального числа , в нашем случае для 2 (эта часть решения называется "база"). Зная эти два факта, мы можем сказать, что раз для это верно, то и для (по 1 факту), а раз для 3, то и для 4 и т. д.)

Базу мы уже доказали, осталось доказать переход.

, степень 2 в скобочках (назовем ее ) — это число из предыдущего шага индукции, то есть делится на числа от 1 до и нам нужно теперь доказать, что делится на все числа от 1 до . Возьмем какое-то число из ряда от 1 до и представим , как , где нечетное. Теперь нам нужно доказать, что делилось на (это очевидно, так как степень ) и делилось на .

Вторая часть верна, так как , если (в случае утверждение о том, что делится на очевидно), потому что мы в рассматриваем числа не превосходящие и взаимно простые и так как , то не взаимно просто с , а значит меньше хотя бы на 1. Значит и делиться на , поэтому делилось на .