# Euler Phi-Function

• May 12th 2009, 02:54 AM
jp3105
Euler Phi-Function
Find all n such that phi(n) = n/3.
Any help is much appreciated.
• May 12th 2009, 03:44 AM
PaulRS
To start with, note that, since $\phi(n)$ is either 1 or an even number, n must be even.

Remember that: $
\phi \left( n \right) = n \cdot \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}
{p}} \right)}
$
(the products go over the prime numbers p dividing n)

Thus: $
\phi \left( n \right) = \tfrac{n}
{3} \Leftrightarrow \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}
{p}} \right)} = \tfrac{1}
{3} \Leftrightarrow 3 \cdot \prod\limits_{\left. p \right|n} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n} p
$

Now since 3 is a prime number, and $
3\left| {\prod\limits_{\left. p \right|n} p } \right.
$
it follows that 3 is one of the prime factors in the product. Thus: $2\cdot
\prod\limits_{\left. p \right|n;p \ne 3} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n;p \ne 3} p
$
and 2|n thus: $
\prod\limits_{\left. p \right|n;p \ne 3;p \ne 2} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n;p \ne 3;p \ne 2} p
$
and this is only possible if there are no other prime factors.

Thus: $
n = 2^\alpha \cdot 3^\beta
$
with $\alpha,\beta\in \mathbb{Z}^+$

And conversely this number satisfies the condition for any $\alpha,\beta\in \mathbb{Z}^+$