Euler's formula question

[shoqan]

Можете объснить почему р-1 делит ф(n) if p divides n. Here p is prime, ф(n)-euler’s function

[Arhaner (Abdildin Amir)]

Вспомни что \phi(ab) = \phi(a) \cdot \phi(b) где (a, b) = 1 (мультипликативность)
А значит если n = p^a \cdot k, где (p, k) = 1, то \phi(n) = \phi(p^a) \cdot \phi(k)
Но вспомним что \phi (p ^ a) = p ^ a - p^{a - 1} = p^{a - 1}(p - 1) \implies
p - 1 \vert \phi(p ^ a) \vert \phi(n) \implies p - 1 \vert \phi(n)

[shoqan]

спасибо, поняла!