# How to prove that $φ(n^2) = n * φ(n)$?

I Want to prove that:

$$φ(n^2) = n * φ(n)$$

the direction is :

$$φ(nm) = φ(n)φ(m)$$

or I'm not even close?

-
What is $\varphi$? When does $\varphi(nm)=\varphi(n)\varphi(m)$ hold? Always? Please care for the details. Regards, – user21436 Apr 15 '12 at 21:09
First, define $\phi(x)$. Second, what is its relevance to number theory? Third, are there any known theorems, postulates, conjectures, identities, or general thoughts associated with this function that could make your life easier? If yes to any of those five, please include them. – 000 Apr 15 '12 at 21:10
The formula you suggested only works when $n$ and $m$ are relatively prime, right? I think I would try to prove it using one of the explicit formulas for $\phi(n)$, or maybe straight from its definition. – Hurkyl Apr 15 '12 at 21:10
@KannappanSampath, you beat me, buddy. – 000 Apr 15 '12 at 21:10
sorry i thought that it is obvious φ is Euler totient function. – Rami Apr 15 '12 at 21:20

Well this formula works for $\gcd(n,m)=1$ if your function is the Euler totient function.

But note that $\phi(p^k)=p^k(1-\frac 1p)$ so that $\phi(p^{2k})=p^{2k}(1-\frac 1p)=p^k\phi(p^k)$ (a proof is here).
From this you should deduce that indeed $\phi(n^2)=n\phi(n)$.

-
this is the way i was looking for, thanks. – Rami Apr 16 '12 at 11:45

HINT: Suppose that $m_1,\dots,m_{\varphi(n)}$ are the positive integers in $\{1,\dots,n\}$ that are relatively prime to $n$. Which integers in $\{n+1,n+2,\dots,2n\}$ are relatively prime to $n$? How about in $\{2n+1,2n+2,\dots,3n\}$? In $\{kn+1,kn+2,\dots,(k+1)n\}$?

It doesn’t hurt to start by looking at numerical examples. For instance, with $n=6$:

$$\begin{array}{c} \color{red}1&2&3&4&\color{red}{5}&6\\ \color{red}{7}&8&9&10&\color{red}{11}&12\\ \color{red}{13}&14&15&16&\color{red}{17}&18\\ \color{red}{19}&20&21&22&\color{red}{23}&24\\ \color{red}{25}&26&27&28&\color{red}{29}&30\\ \color{red}{31}&32&33&34&\color{red}{35}&36 \end{array}$$

-

Here is a proof based on Euler's product formula: $$\dfrac{\varphi(n^2)}{n^2} = \prod_{p\mid n^2} 1-\dfrac1p = \prod_{p \mid n} 1-\dfrac1p = \dfrac{\varphi(n)}{n}$$

It does not really matter what is in the product, just that the set of primes dividing $n^2$ is the same as the set of primes dividing $n$.

-
BTW, this also proves more generally that $\varphi(n^k) = n^{k-1} \varphi(n)$ for all $k$. – lhf Apr 16 '12 at 1:22