Доказательство 1-го свойства функции Эйлера

Вывести формулу φ(p^a) = (p^{a - 1})(p - 1), где φ — функиця Эйлера, p — простое число, a ≥ 1.

Преобразуем. φ(p^a) = p^a - p^{a - 1} = p^{a - 1}(p - 1) = p^a (1 - 1/p). Это просто для иллюстрации хода мысли.

Теперь обратим внимание, что для p^a имеется p^{a - 1} - 1 целых чисел, которые делятся на p и, следовательно, имеют общие множители с p^a: 1p, 2p, ..., (p^{a - 1} - 1)p. Тогда положительные целые меньше p^a и взаимно простые с p^a есть (p^a - 1) - (p^{a - 1} - 1) = p^a - 1 - p^{a - 1} + 1 = p^a - p^{a - 1} = p^a(1 - p^-1) = p^a(1 - 1/p).

математика