Properties of the euler totient function

Solution 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}$.

Solution 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.

Solution 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)$.

Solution 4:

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)$.