# Let $\phi$ be Euler's totient function, find all $n$ such that $\phi(n) = \frac{1}{3} n$.

Let $\phi$ be Euler's function, find all $n$ such that $\phi(n) = \frac{1}{3} n$.

Now while yes I've seen this proof asked before, I'm looking for a specific approach using this theorem.

That is if $n = \prod p^c$, then $\phi(n) = n\prod_{p \mid n} (1 - \frac{1}{p})$.

Not really sure how to continue here. Consider the largest prime divisor of $n$?

• So we need $\prod (1 - \frac 1p) = \frac 13$ but we know $3|n$ and so we need $\prod_{p\ne 3} (1-\frac 1p) =\frac 12$ and that can only be $(1 -\frac 12)$ so the only factors are $2$ and $3$ which must be factors. Of the top of my head with little think I'd say is is all $2^a3^b$ but, sure I'm overlooking something vital. – fleablood Feb 28 '18 at 1:14
• Hint: obviously we must have $3$ as a divisor of $n$. Writing $n=3^am$, with $m$ prime to $3$, we deduce that $\varphi(n)=2\times 3^{a-1}\times \varphi(m)$ hence we must have $\varphi(m)=\frac m2$. Can you do that one? – lulu Feb 28 '18 at 1:19

We need $n\prod_{p|n}(1 - \frac 1p) = \frac 13 n$ so

$\prod (1-\frac 1p) = \frac 13$

Now to get $3$ in the denominator we must have $3|n$.

So $(1 - \frac 13)\prod_{p|n; p\ne3}(1-\frac 1p)= \frac 13$ so

$\prod_{p|n;p\ne =3} (1 - \frac 1p) = \frac 12$.

To have $2$ in the denominator we must have $2|n$ so

$(1 - \frac 13)(1-\frac 12)\prod_{p|n;n\ne 2; n\ne 3} (1- \frac 1p) = \frac 13$ so $\prod_{p|n;n\ne 2; n\ne 3} (1- \frac 1p) =1$ and the only prime factors of $n$ are $2$ and $3$.

So $n$ may be any number of the form $2^a3^b; a\ge 1; b\ge 1$.

• Is there a typo with ≠=? – SS' Feb 28 '18 at 4:28

Yes, focus on the largest prime.

If the distinct prime factors of $n$, in ascending order, are $p_1,...,p_k$, then since $$\prod_{i=1}^k \left(1-\frac{1}{p_i}\right)=\prod_{i=1}^k \frac{p_i-1}{p_i}$$ it's clear that the numerator of the expanded product will not be a multiple of $p_k$.

But the denominator of the expanded product is a multiple of $p_k$, hence the factor $p_k$ of the denominator will survive the reduction to lowest terms.

By hypothesis, the reduction to lowest terms yields the fraction ${\large{\frac{1}{3}}}$, hence we must have $p_k=3$.

It follows that $n=(2^a)(3^b)$, where $a$ is a nonnegative integer, and $b$ is a positive integer.

But if $a=0$, then $\phi(n) = {\large{\frac{2}{3}}}n$, hence we must have $a > 0$.

Finally, if $n=(2^a)(3^b)$, where $a,b$ are positive integers, it's easily verified that $\phi(n) = {\large{\frac{1}{3}}}n$.