I am asked to find all positive integers $n$ such that $\phi(n)=6$, and to prove that I have found all solutions.

The way I am tackling this is by constructing all combinations of prime powers such that when passed to Euler's function will yield $6$.

For example, I know that $\phi(7)=6$, $\phi(3^2)=6$, and $\phi(2)=1$. Therefore, the numbers should be $7$, $7\cdot2=14$, $3^2=9$, and $3^2\cdot2=18$.

I believe that there cannot possibly be any others because of the way the $\phi$ function is defined. What do you guys think?

  • 1
    $\begingroup$ To get a tight proof, use the fact that your function is multiplicative. The prime power decomposition can't have two odd primes, else $\varphi(n)$ is divisible by $4$. So we are down to $2^a$ (impossible) or $2^ap^b$, where $p$ is odd prime. But must have $p \le 7$. Continue. $\endgroup$ – André Nicolas Apr 4 '12 at 14:32
  • $\begingroup$ You can also use the fact that $p|n \Rightarrow p-1 | \phi(n)$ to find the possible odd primes. $\endgroup$ – N. S. Apr 4 '12 at 14:55
  • $\begingroup$ Similar question for 12 instead of 6: math.stackexchange.com/questions/101566/… $\endgroup$ – Martin Sleziak Apr 4 '12 at 15:06
  • $\begingroup$ @MartinSleziak, thank you for the link. I suggest this thread be closed as a duplicate. $\endgroup$ – wjm Apr 4 '12 at 15:09
  • 1
    $\begingroup$ Possible duplicate of How to solve the equation $\phi(n) = k$? $\endgroup$ – Yanior Weg May 7 at 6:55

We give an "examination of all cases" solution. Use the fact that $\varphi(n)$ is multiplicative. Let $$n=2^a p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},$$ where the $p_i$ are distinct odd primes, the $e_i$ are $\ge 1$, and $a \ge 0$. Then $$\varphi(n)=\varphi(2^a)\varphi(p_1^{e_1})\varphi(p_2^{e_2})\cdots \varphi(p_k^{e_k}).$$

We find all $n$ such that $\varphi(n)=6$. If $k \ge 2$, then since $\varphi(p_i^{e_i})$ is even, $\varphi(n)$ is divisible by $4$, so cannot be equal to $6$.

If $k=0$, then $\varphi(n)=\varphi(2^a)$. But $\varphi(2^a)=1$ if $a=0$ and $\varphi(2^a)=2^{a-1}$ if $a \ge 1$. So if $k=0$ we cannot have $\varphi(n)=6$. We conclude that $k=1$. Thus $n$ must have the shape $2^ap^e$, where $a \ge 0$ and $p$ is an odd prime.

But $\varphi(p^e)=p^{e-1}(p-1)$. It follows that $p \le 7$. If $p=7$, then $p-1=6$, so we must have $e=1$ and $\varphi(2^a)=1$. This gives the solutions $n=7$ and $n=14$.

We cannot have $p=5$, for $4$ divides $\varphi(5^e)$.

Let $p=3$. If $e \ge 3$, then $\varphi(3^e)\ge (3^2)(2)$. So we are left with the possibilities $e=1$ and $e=2$.

If $e=1$, then $\varphi(n)=\varphi(2^a)(2)$. This cannot be $6$.

Finally, we deal with the case $e=2$. Note that $\varphi(3^2)=6$. So to have $\varphi(2^a3^2)=6$, we need $\varphi(2^a)=1$, which gives $n=9$ and $n=18$.


Following condition has to be satisfied :

$$\frac{n}{e^{\gamma}\ln(\ln n)+\frac{3}{\ln(\ln n)}} < 6 \leq n-1$$

where $\gamma \approx 0.577$

Hence : $n\in [7,27]$

Therefore you have to check integers from this interval only...

Solution should be : $n \in\{7,9,14,18\}$


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.