Let $n$ be a positive integer. Show that $n\phi(n)=\phi(n^2).$

Question

I'm currently working in the following Euler's theorem exercise:

Let $n$ be a positive integer. Show that $n\phi(n)=\phi(n^2).$

Here are my thoughts:

If $n$ is prime, then

$$\phi (n^2) = n^2-n = n(n-1) = n \phi (n).$$

If $n$ is not prime and $p$ and $q$ are prime factors of $n,$ then

$$\phi (n^2) = (p^2-p)*(q^2-q)$$ $$\phi (n^2) =p(p-1)*q(q-1)$$ $$\phi (n^2) =p\phi(p)*q\phi(q)$$ $$\phi (n^2) =pq \phi(pq)$$ $$\phi (n^2) = n \phi(n)$$

Is that enough proof? Is there a more general one? Am I missing something? Any hint will be really appreciated.

Answer 1

More generally, let $n=p_1^{k_1}p_2^{k_2}...p_r^{k_r}.$ Then $$n^2=p_1^{2k_1}p_2^{2k_2}...p_r^{2k_r},$$ $$ \phi(n)=n(1-1/p_1)(1-1/p_2)...(1-1/p_r),$$and $\phi(n^2)=n^2(1-1/p_1)(1-1/p_2)...(1-1/p_r) = n \phi(n)$.

Answer 2

Or, without directly mentioning any of the prime factors:

The set of integers relatively prime to $n$ is exactly the same as the set of integers relatively prime to $n^2$ (because the same list of primes divide them). Also, $n+k$ is relatively prime to $n$ if and only if $k$ is. That gives us $\phi(n)$ relatively prime integers in $[1,n]$, $\phi(n)$ in $[n+1,2n]$, $\phi(n)$ in $[2n+1,3n]$, and so on up to $[(n-1)n+1,n^2]$. With $n$ disjoint sets of size $\phi(n)$, that's $n\cdot \phi(n)$ total integers relatively prime to $n$ (or $n^2$) in $[1,n^2]$. Done.

Answer 3

$\phi(n)=n\prod_{p_i|n}(1-\frac 1{p_i})$, so $n\cdot\phi(n)=n^2\prod_{p_i|n}(1-\frac 1{p_i})=n^2\prod_{p_i|n^2}(1-\frac 1{p_i})=\phi(n^2)$.

Answer 4

Since everything that could have been said, has already been said, let me add those probabilistic intuitions involving $\varphi$ function (because I like them)-

Note that if $a$ is coprime to $n^2$, then $a$ is coprime to $n$ if and only if $a\le n$. So, if we take the set of all numbers coprime to $n^2$ and pick one at random, then the probability that this randomly chosen integer is coprime to $n$ is precisely $1/n$. But, this probability (by definition) is also $\varphi(n)/\varphi(n^2)$. So, $$\frac{\varphi(n)}{\varphi(n^2)}=\frac 1n$$ and hence, $$\varphi(n^2)=n\varphi(n)$$ which is what was required.

Note that a similar line of argument also proves $$\varphi(n^k)=n^{k-1}\varphi(n)$$