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

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.

• That only deals with the case where $n=pq$. What if $n=p^2q$, $pqr$ etc.? – Lord Shark the Unknown Feb 3 at 5:17
• $$\varphi(m)=m\prod_{p\mid m}\left(1-\frac{1}{p}\right)$$ and the primes dividing $m$ and $m^2$ are the same, so $\frac{\varphi(m)}{m}=\frac{\varphi(m^2)}{m^2}$. – Jack D'Aurizio Feb 3 at 13:27

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)$$.
• Even more generally $$\phi(n^m)=?$$ – lab bhattacharjee Feb 3 at 5:30
• @labbhattacharjee asked for a more general formula than OP: $\phi(n^m)=n^{m-1}\phi(n)$ – J. W. Tanner Feb 3 at 5:33
• In particular, when $n$ is prime, $\phi (n^m)=n^{m-1} (n-1)$ – J. W. Tanner Feb 3 at 5:34
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.
$$\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)$$.