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

Question

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$?

Answer 1

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

Answer 2

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