How can I show by induction that

$\displaystyle \phi(p^k) = p^{k-1}(p-1)$ where $\displaystyle \phi(p) = p - 1$

Printable View

- Mar 25th 2013, 10:43 AMKanwar245Euler phi function
How can I show by induction that

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

Attachment 27693 - Mar 26th 2013, 02:41 PMKanwar245Re: 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.