2
$\begingroup$

I managed to find that $\phi(3n) = 3\phi(n) \implies 3|n$ via contradiction:

Suppose that 3 does not divide n. Then gcd(3, n)=1, because 3 is a prime. Which, in turn, implies that $\phi(3n) = \phi(3)\phi(n)$ since Euler's totient function is multiplicative.

Also, note that $\phi(3) = 2$.

However, by hypothesis, $\phi(3n) = 3\phi(n)$, therefore we arrive at the conclusion that $3\phi(n) = 2\phi(n)$

$\phi(n)>0, \forall n \implies 3=2$. Contradiction!
$\therefore 3|n $

However, I can't find my way back. I have tried writing n as $n=3^\alpha m$, where 3 does not divide m. Therefore, $3n = 3^{\alpha+1}m$, which implies that $\phi(3n) = (3^{\alpha+1}-3^\alpha)\phi(m)=3^\alpha(3-1)\phi(m)$ but that only takes me as far as $\phi(3n) = 2.3^\alpha \phi(m)$, and I see no way of progressing (or if that even is the right path).

Does anyone have any suggestions? (Also, it's my first post here, any feedback is very welcome!)

$\endgroup$
  • $\begingroup$ If $n=3^am$ as you have written (with $a≥1$) , then $\varphi(n)=3^{a-1}\times 2 \times \varphi (n)$, Now look at $\varphi(3n)$. $\endgroup$ – lulu Apr 8 '18 at 19:52
  • $\begingroup$ Wouldn't that be $\phi(n)= 3^{\alpha-1}.2.\phi(m)$ ? The new $m$ in the totient function is what's throwing me off. $\endgroup$ – Pedro Orlando Apr 8 '18 at 20:13
  • $\begingroup$ Yes, that's what I meant. $\endgroup$ – lulu Apr 8 '18 at 20:25
1
$\begingroup$

You're on the right track, but the argument can be simplified, avoiding contradiction.

Write $n=3^\alpha m$ with $\alpha\ge0$ and $\gcd(3,m)=1$ and compute:

$\phi(3n) = \phi(3^{\alpha+1}m) = \phi(3^{\alpha+1})\phi(m)$

$3\phi(n) = 3\phi(3^{\alpha})\phi(m)$

Now note that $\phi(3^{\alpha+1}) = 3\phi(3^{\alpha})$ iff $\alpha>0$, that is, iff $3$ divides $n$.

The same argument works for any prime: $\phi(pn) = p\phi(n)$ iff $p$ divides $n$.

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