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.

  • 2
    $\begingroup$ 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) $\endgroup$ – user17762 Feb 27 '11 at 3:38
  • $\begingroup$ @ Sivaram Ambikasaran: Thank you for the information. Can you give me one example of dividing into cases. Let take $\phi(n) = 8$. Thank you. $\endgroup$ – Chan Feb 27 '11 at 5:42

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:


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

  • $\begingroup$ Ambikasaran: Amazing ;) Many thanks. I really appreciated it. $\endgroup$ – Chan Feb 27 '11 at 8:02

You might take a look into this:

  • $\begingroup$ @Chandru1: Thanks for the link. $\endgroup$ – Chan Feb 27 '11 at 5:42

See these:


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.