Функция Эйлера для p^m

[xyzman]

Встретил такую формулу расчета ф-ии Эйлера для простого $p$ в степени $m$:

$$\varphi(p^m)=p^m-p^{m-1}$$

Не могу догадаться каким образом была получена эта формула. Подскажите?

[AD]

xyzman в сообщении #194134 писал(а):

каким образом была получена эта формула.

Прямо по определению. Соображайте, какие числа взаимно просты с $p^m$.

[xyzman]

Те, которые не равны $0, p, 2p, 3p, ..., p^m-p$

[AD]

xyzman в сообщении #194136 писал(а):

Те, которые не равны $0, p, 2p, 3p, ..., p^m-p$

И сколько чисел Вы только что перечислили?

[xyzman]

Посчитал бы, но многоточие мешает.

[Xaositect]

xyzman писал(а):

Посчитал бы, но многоточие мешает.

'
$0\cdot p, 1\cdot p, 2\cdot p,\dots, (p^{m-1}-1)\cdot p$

[AD]

xyzman в сообщении #194144 писал(а):

Посчитал бы, но многоточие мешает.

Ну а сколько я тут чисел перечислил: $1, 2, 3,\ldots, n$?
А тут: $2, 4, 6, \ldots, 2n$?
А если вот так: $0, n, 2n, \ldots, n^2$?

[xyzman]

Теперь не мешает! Спасибо за помощь!