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.

Let $\phi(n) $ is the numbers of number that are relatively prime to n.
Then, how could we solve the equation $\phi(n) = k, k > 0?$

For example:

$\phi(n) = 8 $

I can use computer program to check all numbers that are relatively prime to $n$, but I think there must be an easier way to approach this problem.

Base on this formula: $$\prod_{i=0}^{k} p_{i}a^{a_i} $$
The only thing I can see is n must not have a prime factor > 9, otherwise $\phi(n) > 8 $. I really don't know where to start :( ? A hint would be greatly appreciated.

share|improve this question
2  
Solving for $n$ involves splitting the problem into cases and arguing out which divides what. However, $\phi(n) = k$ has only finitely many solution for every $k$ since $\phi(n) \geq \sqrt{n}$ for $n>6$. (For odd $k>1$, no solution exists) –  user17762 Feb 27 '11 at 3:38
    
@ Sivaram Ambikasaran: Thank you for the information. Can you give me one example of dividing into cases. Let take $\phi(n) = 8$. Thank you. –  Chan Feb 27 '11 at 5:42

3 Answers 3

up vote 7 down vote accepted

This is too long to be comment and hence the post.

$\phi(n) = 8$. Note that $\sqrt{n} \leq \phi(n) \leq n-1$.

This implies $n$ is at most $64$. So you could write a brute force computer and compute $\phi(n)$ when $n \in [9,64]$.

A better way would be as follows.

Let $n=\displaystyle \prod_{i=1}^k p_i^{\alpha_i} \Rightarrow \phi(n) = \displaystyle \prod_{i=1}^k p_i^{\alpha_i-1} (p_i-1)$.

First note that $n$ can be of the form $\displaystyle 2^\alpha \left( \prod_{i=1}^k p_i \right)$ i.e. the exponent of the odd primes in the prime factorization of $n$ is $1$. This is so, because if not these primes will then divide $\phi(n) = 8$ which is not possible.

If $k=0$, then we have $n=2^{\alpha}$, $\displaystyle 2^{\alpha-1} = \phi(n) = 2^3 \Rightarrow \alpha=4$. Hence, $k=1 \Rightarrow n=16$.

Let $k=1$. Then we have $n=2^{\alpha} p_1$.

If $\alpha = 0,1$, then $\displaystyle (p_1-1) = \phi(n) = 2^3 \Rightarrow p_1 = 9 \Rightarrow \text{ Not possible}$.

If $\alpha = 2$, then $\displaystyle 2 (p_1 - 1) = \phi(n) = 2^3 \Rightarrow p_1=5$. Hence, $n=20$.

If $\alpha = 3$, then $\displaystyle 2^2 (p_1 - 1) = \phi(n) = 2^3 \Rightarrow p_1=3$. Hence, $n=24$.

Now let $k=2$. Then we have $n=2^{\alpha} p_1 p_2$.

If $\alpha = 0,1$, then $\displaystyle (p_1-1)(p_2-1) = \phi(n) = 2^3 \Rightarrow p_1 = 3, p_2 = 5$. Hence, $n=15$ when $\alpha = 0$ and $n=30$ when $\alpha = 1$

If $\alpha = 2$, then $\displaystyle 2(p_1-1)(p_2-1) = \phi(n) = 2^3 \Rightarrow (p_1-1)(p_2-1) = 4 \Rightarrow \text{ Not Possible}$.

$k=3$ is not possible since $(3-1) \times (5-1) \times (7-1) > 8$.

Hence, the only solutions (hope I have not missed any case) are:

$$n=15,16,20,24,30$$

Similar idea extends to other problems where we want to find the inverse of the totient function.

share|improve this answer
    
Ambikasaran: Amazing ;) Many thanks. I really appreciated it. –  Chan Feb 27 '11 at 8:02

You might take a look into this:

share|improve this answer
    
@Chandru1: Thanks for the link. –  Chan Feb 27 '11 at 5:42
    
@Chan: Dont forget to accept an answer. –  anonymous Feb 27 '11 at 5:56

See these:

share|improve this answer
    
Thank you. –  Chan Feb 27 '11 at 5:43

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.