# For what integers $n$ does $\phi(2n) = \phi(n)$?

For what integers $n$ does $\phi(2n) = \phi(n)$?

Could anyone help me start this problem off? I'm new to elementary number theory and such, and I can't really get a grasp of the totient function.

I know that $$\phi(n) = n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\dfrac1{p_k}\right)$$ but I don't know how to apply this to the problem. I also know that $$\phi(n) = (p_1^{a_1} - p_1^{a_1-1})(p_2^{a_2} - p_2^{a_2 - 1})\cdots$$

Help

-

Euler's $\phi$ function is multiplicative. More elaborately if for $a,b\in N$ with $(a,b)=1$ then $\phi (ab)=\phi (a)\phi (b)$. So let $n=2^km$ with $m$ being odd. Then we have if $k\ge 1$, \begin{align} \phi (n)&=\phi(2^k)\phi(m)=2^{k-1}\phi(m) \\ \phi(2n)&=\phi(2^{k+1})\phi(m)=2^{k}\phi(m)\end{align} So $\phi (n)\ne \phi(2n)$. So $k<1\Rightarrow k=0\Rightarrow n$ must be odd.

Another easy proof: Let $n=2^k\prod_{i=1}^{n}p_i^{\alpha_i}$ with $k\ge 1$ and $2\ne p_i =$ primes, then we have $\phi (n)=\frac{n}{2}\prod_{i=1}^{n}(1-\frac{1}{p_i})$ and $\phi (2n)=\frac{2n}{2}\prod_{i=1}^{n}(1-\frac{1}{p_i})$.Can $\phi (n)$ be equal to $\phi(2n)$? Now consider $n=2k+1$ and find $\phi (n)$ and $\phi (2n)$. What do you see?

-
I know that the function is multiplicitive, but I don't understand how to use that information. Sorry. –  Ozera Jul 10 '13 at 15:46
I guess the 2nd proof will clear things up. –  Abhra Abir Kundu Jul 10 '13 at 15:47
Actually I'm not really sure what it says, but I'm going to continue thinking about what the importance of it being multipicitive. –  Ozera Jul 10 '13 at 15:56
Now is it clear @Ozera –  Abhra Abir Kundu Jul 10 '13 at 16:08

Hint If $n$ is odd, then gcd$(n,2)=1$ thus

$$\phi(2n)=\phi(2) \phi(n) \,.$$

If $n$ is even, write $n=2^km$ with $m$ odd and $k \geq 1$.

$$\phi(n)=\phi(2^k) \phi(m) \,.$$ $$\phi(2n)=\phi(2^{k+1}) \phi(m) \,.$$

-

Hint: You may also prove in general that

$$\varphi(mn)=\frac{d\varphi(m)\varphi(n)}{\varphi(d)}$$

where $d=\gcd(m,n).$

-
+1 Nice remarking the fact. :-) –  Babak S. Aug 22 '13 at 7:36
The formula you gave is incorrect. It should have been $$\phi(mn) = \frac{d\phi(m)\phi(n)}{\phi(d)}$$ –  Balarka Sen Jan 17 '14 at 15:32
Dear @BalarkaSen, yes, thanks for the correction. –  Ehsan M. Kermani Jan 18 '14 at 20:15