Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  André Nicolas Apr 4 '12 at 14:32
    
You can also use the fact that $p|n \Rightarrow p-1 | \phi(n)$ to find the possible odd primes. –  N. S. Apr 4 '12 at 14:55
    
Similar question for 12 instead of 6: math.stackexchange.com/questions/101566/… –  Martin Sleziak Apr 4 '12 at 15:06
    
@MartinSleziak, thank you for the link. I suggest this thread be closed as a duplicate. –  Josué Molina Apr 4 '12 at 15:09
    
Even if it is a duplicate, (+1) for a well-posed question. –  The Chaz 2.0 Apr 4 '12 at 17:24
add comment

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.