3
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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?

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

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

$\endgroup$
4
$\begingroup$

Hint: You may also prove in general that

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

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

$\endgroup$
  • 1
    $\begingroup$ The formula you gave is incorrect. It should have been $$\phi(mn) = \frac{d\phi(m)\phi(n)}{\phi(d)}$$ $\endgroup$ – Balarka Sen Jan 17 '14 at 15:32
  • $\begingroup$ Dear @BalarkaSen, yes, thanks for the correction. $\endgroup$ – Ehsan M. Kermani Jan 18 '14 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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