Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I Want to prove that:

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

the direction is :

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

or I'm not even close?

share|improve this question
1  
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

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
    
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}$$

share|improve this answer

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

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.