6
$\begingroup$

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

I know that $\phi(n) = \phi(P_1^{a1})\cdots\phi(P_k^{ak}) = (P_1^{a1}-P_1^{a1-1})\cdots(P_k^{ak}-P_k^{ak-1})$ but I'm not really sure how to apply it in a way that helps.

The only thing I could think to try was all cases of $n$ being even or odd, and $n$ being divisible by $3$ or not, however I could not get this to work.

Any help is appreciated, thanks.

$\endgroup$
1
  • 2
    $\begingroup$ How are $\varphi(2n)$ and $\varphi(n)$ related? The same for $\varphi(3n)$ and $\varphi(n)$. $\endgroup$ Oct 27 '14 at 0:16
4
$\begingroup$

Based on your formula for $\varphi(n)$, for any prime $p$,

$$\varphi(pn)= \left\{\begin{array}{ccc} (p-1)\varphi(n)& \text{if} & p\not\mid n \\ p\varphi(n) & \text{if} & p\mid n\end{array} \right. $$

If you apply this for $p=2$ and $p=3$ you should be able to come to something useful.

$\endgroup$
3
$\begingroup$

If $3$ divides $n$, then $\varphi(3n)=3\varphi(n)\ne \varphi(2n)$.

If $3$ does not divide $n$, then $\varphi(3n)=2\varphi(n)$. This is $\varphi(2n)$ if and only if $2$ divides $n$.

These observations should be enough for you to finish.

$\endgroup$
2
$\begingroup$

Hint: write $$ n = 2^a 3^b c $$with $2\nmid c, 3\nmid c$ and appy the formula.

$\endgroup$
0
$\begingroup$

Only for $n$ satisfying $n \equiv 2 \pmod 6$ or $n \equiv 4 \pmod 6$.

Remember that the totient function is multiplicative. This means that if $\gcd(a, b) = 1$, then $\phi(ab) = \phi(a) \phi(b)$. Also remember that $\phi(2) = 1$ and $\phi(3) = 2$, and the formula for $\phi(p^\alpha)$ where $p$ is some prime.

Let's look at this modulo 6.

  • If $n \equiv 1 \pmod 6$, then $\phi(2n) = \phi(n)$ and $\phi(3n) = 2 \phi(n)$, so $\phi(2n) \neq \phi(3n)$.
  • If $n \equiv 2 \pmod 6$, then $n = 2^\alpha m$ (where $\alpha$ is some integer and $m$ is odd), $\phi(2n) = 2^\alpha \phi(m)$ and $\phi(3n) = 2 \times 2^{\alpha - 1} \phi(m) = 2^\alpha \phi(m)$, so $\phi(2n) = \phi(3n)$ as desired.
  • If $n \equiv 3 \pmod 6$, then $n = 3^\alpha m$ (where $\alpha$ is some integer and $m$ is not a multiple of 3), so we have $\phi(2n) = 2 \times 3^{\alpha - 1}\phi(m)$ and $\phi(3n) = 2 \times 3^\alpha \phi(m)$ (notice the exponents), so $\phi(2n) \neq \phi(3n)$.
  • If $n \equiv 4 \pmod 6$, then $n = 2^\alpha m$ (where $\alpha$ is some integer and $m$ is odd), so we have $\phi(2n) = 2^{\alpha + 1} \phi(m)$ (because the 4 contributes 1 to 2's exponent) and $\phi(3n) = 2 \times 2^\alpha \phi(m) = 2^{\alpha + 1} \phi(m)$, so $\phi(2n) = \phi(3n)$ as desired.
  • If $n \equiv 5 \pmod 6$, then $\phi(2n) = \phi(n)$ and $\phi(3n) = 2 \phi(n)$, so $\phi(2n) \neq \phi(3n)$.

Clearly odd numbers don't work for this. It should be easy enough for you to see that $n \equiv 0 \pmod 6$ does not work. That leaves us even numbers that are not multiples of 3.

$\endgroup$

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.