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

  • $\begingroup$ 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. $\endgroup$
    – fleablood
    Feb 28 '18 at 1:14
  • $\begingroup$ 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? $\endgroup$
    – 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$.

  • $\begingroup$ Is there a typo with ≠=? $\endgroup$
    – 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$.

  • $\begingroup$ Hi, I am having trouble understanding why the numerator is not a multiple of $p_k$ and why it will not be cancelled out? i.e. why it will survive reduction but the others won't $\endgroup$ Mar 6 at 22:40
  • 1
    $\begingroup$ @Larry: If the numerator was divisible by $p_k$, then since $p_k$ is prime, at least one of the factors of the numerator would have to be divisible by $p_k$. But $p_k$ is the largest of $p_1,,,,,p_k$, so $p_k$ is greater than each of the factors of the numerator. $\endgroup$
    – quasi
    Mar 6 at 23:02
  • $\begingroup$ Thank you very much @quasi $\endgroup$ Mar 7 at 0:39

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.