# Euler phi function

• March 25th 2013, 10:43 AM
Kanwar245
Euler phi function
How can I show by induction that

$\phi(p^k) = p^{k-1}(p-1)$ where $\phi(p) = p - 1$
• March 25th 2013, 04:28 PM
johng
Re: Euler phi function
This is not an inductive proof, but it is very simple:

Attachment 27693
• March 26th 2013, 02:41 PM
Kanwar245
Re: Euler phi function
I'm actually trying to come up with an inductive proof; I know how to think about this in terms of counting which makes sense. However, in terms of induction I don't know how to show it.