The value of Euler function of $\phi(p^k)$ when $p$ is prime and $k$ is a positive integer?
Prove that the value of Euler function of $\phi(p^k)$ when $p$ is prime and $k$ is a positive integer is,
$$\phi(p^k)=p^k-p^{k-1}$$
I saw similar posts for the same questions, but I am still confused about the following.
Question: the divisors of $p^k$ are,
$$1, p, p^2, p^3, \cdots, p^k$$
Those divisors should not be relatively prime to $p^k$ as the $gcd(p^k, divisor_i) \ne 1$. We can see that we have $p^k$ such divisors that are not relatively prime to $p^k$ as I understand it.
Also, we have multiples of $p$ up to $p^k$ cannot be relatively prime to $p^k$ for the same reason as $gcd(p^k, multipleP_i) \ne 1$,
$$p, 2p, 3p, \cdots, p^{k-1}p$$
Clearly we have $p^{k-1}$ of such multiples, so we should have the total number of numbers that are not relatively prime to $p^k$ as (based on how I understand it),
$$\phi(p^k)=p^k-p^{k-1}$$
Question: How do we know that those only multiples of $p$ and divisors of $p^k$ are the only possibilities of the numbers not to be relatively prime to $p^k$? How do we know that there are not other numbers in between that could also be not relatively prime to $p^k$?
$\endgroup$ 101 Answer
$\begingroup$Suppose $p$ is prime and $x,k\in \Bbb N.$
(1). If $\gcd(x,p^n)>1$ then for some prime $q$ we have $q\,|\,\gcd(x,p^n)\,|\,p^k,$ so $q|p^k.$ But the only prime divisor of $p^k$ is $p,$ by the uniqueness of prime decomposition, so $q=p,$ so $p=q\,|\,\gcd(x,p^n)\,|\,x,$ so $p|x,$ so $$\exists y\in \Bbb N\,(x=py).$$
(2). If $\gcd(x,p^n)=1$ then $p\not |\,x\;$ ( otherwise $p>1$ is a common divisor of $x$ and of $p^k$) so $$\neg \exists y\in \Bbb N\,(x=py). $$
Therefore $$\{x\in \Bbb N: x\le p^k\land \gcd (x,p)>1\}=\{x\in \Bbb N: x\le p^k\land p|x\}=$$ $$=\{py: y\in \Bbb N\land py\le p^k\}.$$ This last set (above) has the same number of members as $\{y\in\Bbb N: y\le p^{k-1}\}$ does, which is $p^{k-1}$ members. Therefore $\phi(p^k)=p^k-p^{k-1}.$
$\endgroup$ 2
