Properties of the euler totient function

Question

Why is it that the euler totient function has the following condition true based on its definition?

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

A proof would be awesome and an intuition on why this is true would be even better!

(to prove it I thought of using multiplicativity of the totient function but that would not work because p is not coprime to itself :( )

A more detailed explanation of the wikipedia article will get a like and accepted answer.

To get accepted, giving an explanation on why the number of multiples of p is $p^{k-1}$ will be an important factor. Also, are the multiples of p we are excluding between 1 to $p^k - 1$ or to $p^k$?

Some kind of counting argument is necessary to get accepted.

Answer 1

Any positive integer $x$ less than $p^k$ can be written in base $p$ as $$ x = a_0 + a_1 p + a_2 p^2 + \cdots + a_{k-1} p^{k-1} $$ where $a_i \in \{0, 1, 2, \ldots, p-1\}$. Then $x$ is not relatively prime to $p^k$ iff $p \mid x$ iff $a_0 = 0$. Thus if we want $x$ to be relatively prime to $p^k$ we have $p-1$ choices for $a_0$ and $p$ choices for each of the other $k-1$ coefficients, hence $\varphi(p^k) = (p-1)p^{k-1}$.

Answer 2

Here is intiution....

Take $p^2$. How many numbers in the range $1 \ldots p^2$ are not co-prime to it? They are precisely $p$, $2p$, $3p$ ... $p^2$. There are exactly $p$ of them. So the number co prime to $p^2$ is $$ \phi(p^2) = p^2 -p = p (p-1)$$

You can do the same for $p^3$ to get $$ \phi(p^3) = p^3 -p^2 = p^2 (p-1)$$

You can turn this into a proof by induction if you so wish.

Answer 3

I find it intuitive to think in terms of "what are the chances of not being coprime to $p^k$?"

Once you realize that "coprime to $p^k$" is synonymous with "not divisible by $p$", it suggests the proportion of numbers up to $p^k$ which are coprime to $p^k$ is $1 - \frac1p$, motivating the quantity $p^k(1-\frac1p)$.

The same reasoning applies to general $n$ (but takes more effort to justify carefully): "coprime to $n$" is synonymous with "not divisible by any of the prime factors of $n$", and if you can convince yourself that the individual probabilities are independent this suggests $\phi(n) = n\prod_{p\mid n} (1-\frac1p)$.

Answer 4

$p^k$ only shares common factors with other multiples of $p$. How many multiples of $p$ are there under $p^k$?: $\frac{p^k}{p}=p^{k-1}$ Just look at 8 for example. There are 4 multiples of 2 under and including 8. To get the totient value by definition exclude from $p^k$ all the values under it that share a common factor, of which there are $p^{k-1}$.

Answer 5

Another explanation (much of which is implicit in the other answers):

A number $n$ is not coprime to $p \iff \text{gcd}(p,n) \neq 1 \iff \text{gcd}(p,n) = p \iff n$ is a multiple of $p$. Now the multiples of $p$ between $1$ and $p^k$ are precisely the numbers $mp$, for $1 \leq m \leq p^{k-1}$, of which there are $p^{k-1}$. Subtracting these from the total gives $p^k - p^{k-1} = \phi(p^k)$.