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

Выпишем подряд строки чисел, образующиеся в результате очередного шага. Получим некоторую таблицу. Попробуем выяснить, сколько раз в -й строке этой таблицы встретится число Будем говорить, что в нашей таблице встречается пара натуральных чисел если числа и стоят рядом в одной строке, причём справа от

______________________________________________________________________________________________________________________________________________________

Лемма. Если натуральные числа и взаимно просты, то пара встречается в таблице ровно один раз; если же и имеют общий делитель (отличный от то пара не встретится в таблице ни разу.

Доказательство. Индукция по База очевидна. Шаг индукции. Пусть (случай аналогичен). Пара может встретиться в таблице в том и только том случае, когда в ней встречалась пара Числа и являются одновременно либо взаимно простыми, либо нет. Для пары утверждение справедливо по предположению индукции. Поэтому утверждение верно и для пары

______________________________________________________________________________________________________________________________________________________

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