2
$\begingroup$

I Want to prove that:

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

the direction is :

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

or I'm not even close?

  • 1
    What is $\varphi$? When does $\varphi(nm)=\varphi(n)\varphi(m)$ hold? Always? Please care for the details. Regards,2012-04-15
  • 0
    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.2012-04-15
  • 0
    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.2012-04-15
  • 0
    @KannappanSampath, you beat me, buddy.2012-04-15
  • 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