How to invert Euler's totient $\varphi$

104 Views Asked by At

I am writing this one since I have struggled a lot, at the very beginning of my Analytic Number Theory Course, to learn how to invert Euler's Totient. I wanted to find an algorithm, but, given the fact that inverting $\varphi$ is an NP-hard problem, I didn't find too much. Feel free to comment and improve.

The problem is:

Find all positive integers $n$ such that $\varphi\left(n\right)=k$, for a given $k$. To fix the ideas, let us take $k=18$.

1

There are 1 best solutions below

0
On

First step: define the set:

$$S\left(k\right):=\left\{ \text{prime }p:\;\left(p-1\right)\mid k\right\}$$

In this case it is:

$$S\left(18\right):=\left\{ \text{prime }p:\;\left(p-1\right)\mid 18\right\}=\left\{ 2,3,7,19\right\} $$

The result is a set $\left\{ p_{1},p_{2},\dots,p_{n}\right\}$. Obviously, every solution $E$ of the equation $\varphi\left(n\right)=k$ is of the form

$$p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{n}^{a_{n}}\;\;a_i\in\mathbb{N},i=1,2,\dots,n$$

Second step: (not mandatory, but I find it very useful later). For every prime divisor $p_i$ found in the previous step, determine $\varphi\left(p_{i}^{a_{i}}\right)$ and stop when you find the first $i$ such that $\varphi\left(p_{i}^{a_{i}}\right)>k$. In fact, the property of the Euler function: $$\varphi\left(p^r\right)=p^r-p^{r-1}$$ grants that after that index $i$ there is no more 'useful' power of the prime - meaning that all other powers of the prime are greater than $k$.

We have:

$$\begin{array}{ccccc} \varphi\left(2\right)=1 & \varphi\left(2^{2}\right)=2 & \varphi\left(2^{3}\right)=4 & \varphi\left(2^{4}\right)=8 & \varphi\left(2^{5}\right)=16\end{array}$$ $$ \begin{array}{ccc} \varphi\left(3\right)=2 & \varphi\left(3^{2}\right)=6 & \varphi\left(3^{3}\right)=18\end{array} $$ $$ \begin{array}{cc} \varphi\left(7\right)=6 & \varphi\left(19\right)=18\end{array} $$

Third step: analyse all the cases of $\prod_{i=1}^{n}p_{i}^{a_{i}}$, starting from the highest prime.

In our case, the generic solution can be written as $2^a3^b7^c19^d$; the highest prime is 19. Two cases arise: either $d=0$ or $d=1$. If $d=1$ then: $$\varphi\left(2^{a}3^{b}7^{c}19\right)=\varphi\left(2^{a}3^{b}7^{c}\right)\varphi\left(19\right)=18\varphi\left(2^{a}3^{b}7^{c}\right)$$ imposing the RHS equal to 1 gives raise to two more cases: either $a=0$ or $a=1$, leading to the solutions $E_1=19\cdot1=19$ and $E_2=19\cdot2=38$.

Analyse the case $d=0$; rewrite the generic solution as $2^a3^b7^c$ Consider that $\varphi\left(7\right)=6$ so $c$ cannot be 1. In fact, in that case, it should be $\varphi\left(2^a3^b\right)=3$, which is not possible.

So, $c=d=0$; rewrite the generic solution as $2^a3^b$. The given equation has solution if and only if $b=3$. This gives raise to the cases $a=0$ and $a=1$, leading to the solutions $E_3=27\cdot1$ and $E_4=27\cdot2=54$.

Final note: this is a quick'n'dirty approach. You should have no problem, except for the computational weight. The real risk here is forgetting some cases. That's why I suggest to draw somehow a tree or a matrix to help visualising all the possible combinations.