How to solve the equation $\phi(n) = k$?

elementary-number-theory

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.

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.

You might take a look into this: