2
$\begingroup$

I Want to prove that:

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

the direction is :

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

or I'm not even close?

  • 0
    sorry i thought that it is obvious φ is Euler totient function.2012-04-15

3 Answers 3

6

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

  • 0
    this is the way i was looking for, thanks.2012-04-16
6

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

3

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

  • 1
    BTW, this also proves more generally that $\varphi(n^k) = n^{k-1} \varphi(n)$ for all $k$.2012-04-16