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

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.

• You might take a look into this: - jstor.org/stable/2308462
– anonymous
Feb 27, 2011 at 3:32
• 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, 2011 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. Feb 27, 2011 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:

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

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

• Ambikasaran: Amazing ;) Many thanks. I really appreciated it. Feb 27, 2011 at 8:02

See these:

I needed this recently and sketched the following algorithmic approach, so I might as well put it here. It's not terribly efficient but it works.

Input: Integer $$k>0$$

Output: All solutions $$x$$ of $$\varphi(x)=k$$.

Pseudocode:

• Let $$Q = \{d+1; d \mid k \text{ and } d+1 \text{ is prime}\}$$
• For all $$R \subseteq Q$$:
• Set $$l = \prod_{r \in R} (r-1)$$
• If $$l \mid k$$ and all prime factors of $$\frac{k}{l}$$ lie in $$R$$:
• Report $$x=\frac{k}{l}\cdot \prod_{r\in R} r$$

It is based on the fact that if prime $$q\mid x$$, then $$q-1 \mid \varphi(x)=k$$, so all prime factors of $$x$$ must come from a suitable divisor $$d \mid k$$ for which $$d+1$$ is a prime. There are only finitely many of these so we store them in a set $$Q$$. Then for each combination of these primes, there is at most one $$x$$ which has exactly these prime factors. It also immediately implies there is at most $$2^{\tau(k)}$$ solutions (where $$\tau(k)$$ is number of positive divisors of $$k$$).

For example if $$\varphi(n) = 8$$, then $$k=8$$ and divisors $$d$$ of $$k$$ are $$1,2,4,8$$. So primes $$d+1$$ form $$Q=\{2,3,5\}$$. Then for each $$R \subseteq Q$$ we compute: $$\begin{array}{c|c|c|c|l} R&l= \prod_{r \in R} (r-1)&\frac{k}{l}&x=\frac{k}{l}\cdot \prod_{r\in R} r\\ \hline \emptyset&1&2^3&\text{None}\, ( \{2\} \not\subseteq \emptyset ) &\\ \{2\}&1&2^3&16& \\ \{3\}&2&2^2&\text{None}\, (\{2\} \not\subseteq \{3\})& \\ \{5\}&4&2^1&\text{None}\, (\{2\} \not\subseteq \{5\})& \\ \{2,3\}&2&2^2&24& \\ \{2,5\}&4&2^1&20& \\ \{3,5\}&8&1&15& \\ \{2,3,5\}&8&1&30& \\ \end{array}$$ Hence $$x \in \{15,16,20,24,30\}$$.

This can be futher optimized when programmed, for example instead of iterating over all subsets $$R \subseteq Q$$ we can backtrack whenever $$\prod_{r \in R} (r-1) \mid k$$ cannot be satisfied, and so on...

For smaller values of $$k$$ it might be feasible to match the prime decomposition of $$k$$ to the product formula for $$\phi(n)$$, and then go through the different possible cases. For example with $$k = 12$$ (Ex. 1(c) of Chapter 2 of "Introduction to Analytic Number Theory" by Tom M. Apostol) :

$$n = 13$$ is an obvious solution as $$\phi(p) = p - 1$$ for any prime $$p$$, and clearly any solution $$n$$ is $$\geq 13$$.

Consider $$n = p_1^{a_1} \cdots p_k^{a_k}$$, where $$p_i$$ are distinct primes with $$p_1 < p_2 < \ldots < p_k$$, and $$a_i \geq 1$$.

From the product formula for $$\phi(n)$$ : $$\phi(n) = ( p_1^{a_1-1} \cdots p_k^{a_k-1} ) \cdot (\: (p_1-1) \cdots (p_k-1) \:) = m \cdot l \mbox{, say}$$

where every factor $$(p_i - 1)$$ is even, except possibly the first which is $$1$$ when $$p_1 = 2$$.

If $$2 \nmid l$$ then $$k = 1$$ and $$p_1 = 2 \therefore n = 2^{a_1}$$, therefore from the product formula for the totient function, $$\phi(n) = n/2$$. In the present case this implies $$n = 24$$, but $$\phi(24) = 8$$, so below we can assume $$2 \mid l$$.

Since we require $$m \cdot l = 12 = 2^2 \cdot 3$$ and $$2 \mid l$$, from the prime decompositions we must have one of the following possibilities :

1. $$m = 2 \cdot 3$$, $$l = 2$$
2. $$m = 3$$, $$l = 2^2$$
3. $$m = 2$$, $$l = 2 \cdot 3$$
4. $$m = 1$$, $$l = 2^2 \cdot 3$$

Case (i) $$n$$ even.

Then $$p_1 = 2$$. If $$k = 1$$ then $$n$$ is a power of $$2$$ but this cannot give $$\phi(n) = 12$$ as seen above. Thus assume $$k \geq 2$$.

Then, in the product $$l$$, the factor $$(p_1 - 1) = 1$$ and the distinct factors $$(p_2 - 1), \cdots, (p_k - 1)$$ are all divisible by $$2$$.

Case (1) $$\Rightarrow k = 2$$ and $$p_2 = 3$$, to achieve $$l = 2$$. Thus the primes of $$n$$ are $$2$$, $$3$$. Since $$m = 2 \cdot 3$$ we must have $$a_1 = a_2 = 2$$. Thus $$n = 2^2 \cdot 3^2 = \mathbf{36}$$.

Case (2) $$\Rightarrow k \leq 3$$, otherwise there would be too many $$2$$'s in $$l$$. But $$k = 2 \Rightarrow p_2 = 5 \Rightarrow$$ primes of $$n$$ are $$2, 5$$, but $$m = 3 \Rightarrow$$ $$3$$ a prime of $$n \therefore$$ contradiction. And $$k = 3 \Rightarrow p_2 - 1 = p_3 - 1 = 2 \Rightarrow p_2 = p_3 \Rightarrow$$ contradiction. Thus case (2) is not possible.

Case (3) $$\Rightarrow$$ there is only one $$2$$ in $$l$$ $$\Rightarrow$$ $$k = 2$$. Then to achieve $$l = 2 \cdot 3$$, $$p_2 = 7 \therefore$$ primes of $$n$$ are $$2, 7$$, and $$m = 2 \Rightarrow a_1 = 2, a_2 = 1$$. Thus $$n = 2^2 \cdot 7 = \mathbf{28}$$.

Case (4) $$\Rightarrow k \leq 3$$. $$k = 2 \Rightarrow p_2 - 1 = l = 12 \therefore$$ primes of $$n$$ are $$2, 13$$ and $$m = 1 \Rightarrow a_1 = a_2 = 1 \therefore$$ $$n = 2 \cdot 13 = \mathbf{26}$$. $$k = 3 \Rightarrow (p_2 - 1)(p_3 - 1) = 2^2 \cdot 3$$ with $$2 \mid (p_2 - 1)$$ and $$2 \mid (p_3 - 1) \Rightarrow p_2 - 1 = 2 \cdot 3$$ and $$p_3 - 1 = 2$$ (or vice-versa) $$\Rightarrow$$ since $$p_2 < p_3$$, $$p_2 = 3$$ and $$p_3 = 7$$. Thus the primes of $$n$$ are $$2, 3, 7$$ and $$m = 1 \Rightarrow a_1 = a_2 = a_3 = 1 \therefore n = 2 \cdot 3 \cdot 7 = \mathbf{42}$$.

Case (ii) $$n$$ odd.

Here all $$p_i$$'s are odd, $$k \geq 1$$, and every factor $$(p_i - 1)$$ is even.

Case (1) $$\Rightarrow k = 1$$ and $$p_1 = 3$$. But $$m = 2 \cdot 3 \Rightarrow p_1^{a_1-1} = 2 \cdot 3$$ which is even - a contradiction as $$p_1$$ odd. Thus case (1) is not possible.

Case (2) $$\Rightarrow k \leq 2$$. $$k = 1 \Rightarrow p_1 = 5$$. But $$m = 3 \Rightarrow p_1^{a_1-1} = 3 \Rightarrow$$ contradiction as $$p_1 = 5$$. $$k = 2 \Rightarrow p_1 - 1 = p_2 - 1 = 2 \Rightarrow p_1 = p_2 \Rightarrow$$ contradiction. Thus case (2) is not possible.

Case (3) $$\Rightarrow k = 1$$ and then $$p_1 = 7$$. But $$m = 2 \Rightarrow p_1^{a_1-1} = 2 \Rightarrow$$ contradiction as $$p_1 = 7$$. Thus case (3) is not possible.

Case (4) $$\Rightarrow k \leq 2$$. $$k = 1 \Rightarrow p_1 = 13$$. Then $$m = 1 \Rightarrow a_1 = 1 \therefore n = \mathbf{13}$$. $$k = 2 \Rightarrow$$ since $$2 \mid (p_1 - 1)$$ and $$2 \mid (p_2 - 1)$$, so $$(p_1 - 1) = 2 \cdot 3$$ and $$(p_2 - 1) = 2$$ (or vice-versa). But $$p_1 < p_2 \therefore$$ $$p_1 = 3, p_2 = 7$$, and $$3, 7$$ are the prime factors of $$n$$. Since $$m = 1$$, $$a_1 = a_2 = 1 \therefore n = 3 \cdot 7 = \mathbf{21}$$.

Thus the solution is $$\{13, 21, 26, 28, 36, 42\}$$.