Can someone please help me with this proof.

Find all n such that phi(n) = n/3.

Any help is much appreciated.

Printable View

- May 12th 2009, 02:54 AMjp3105Euler Phi-Function
Can someone please help me with this proof.

Find all n such that phi(n) = n/3.

Any help is much appreciated. - May 12th 2009, 03:44 AMPaulRS
To start with, note that, since $\displaystyle \phi(n)$ is either 1 or an even number, n must be even.

Remember that: $\displaystyle

\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: $\displaystyle

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

3\left| {\prod\limits_{\left. p \right|n} p } \right.

$ it follows that 3 is one of the prime factors in the product. Thus: $\displaystyle 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: $\displaystyle

\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: $\displaystyle

n = 2^\alpha \cdot 3^\beta

$ with $\displaystyle \alpha,\beta\in \mathbb{Z}^+$

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