1
$\begingroup$

This question already has an answer here:

I am having trouble with understading how inverse totient function works. I know it can have multiple solutions but I don't understand how to find all of them for bigger numbers. For example how would one approach to problem of solving this equation:

ϕ(n) = 180

I do understand that one should represent ϕ(n) by product rule and somehow conclude numbers by combining product rule expression for ϕ(n) to get all numbers n. But it seems as very long process that I don't understand. My question is how I should think when looking at prime numbers expression for ϕ(n) and how should I eliminate some results? I was trying searching other similiar question and I still can't find some general algorithm for solving this problem. Thanks!

EDIT: I would like to know how to calculate this problem by hand

$\endgroup$

marked as duplicate by Yanior Weg, Misha Lavrov, GNUSupporter 8964民主女神 地下教會, Leucippus, Lee David Chung Lin May 8 at 5:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

5
$\begingroup$

Let's take $\varphi(n)=180$ as an example. We'll take a systematic approach, going through each of the possibilities.


First, we write $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$, where $p_1,p_2,\cdots,p_k$ are distinct primes and $e_i\ge 1$ for all $1\le i\le k$. Then we know:

$$\varphi(n)=p_1^{e_1-1}(p_1-1)p_2^{e_2-1}(p_2-1)\cdots p_k^{e_k-1}(p_k-1)$$

So what we need to do, is find primes such that $p-1\mid 180$. Or, equivalently (and easier), we need to check for every divisor $d$ of $180$ whether $d+1$ is prime. Only the primes we find then, can be factors of $n$. So let's see: the divisors of $180$ are (using $180=2^2\cdot 3^2\cdot 5$):

$$\{1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180\}$$

And so we add $1$ to each of these, and check whether or not they are prime. The set we then have left, is (we'll call it $S$):

$$S:=\{2, 3, 5, 7, 11, 13, 19, 31, 37, 61, 181\}$$

Now let's say we have a prime $p\in S$, such that $p^2\mid n$. Then, $p\mid 180$; thus, $p\in\{2,3,5\}$. Those are the only prime that $n$ can have more than once. Now note that $\gcd(a,b)=1$ implies $\varphi(ab)=\varphi(a)\varphi(b)$. Now let's finally find some solutions!


Let $n=181\cdot m$. Then $\varphi(n)=180=180\varphi(m)$; We now have to solve $\varphi(m)=1$. We see two solutions, $m=1$ and $m=2$, resulting in solutions, $\color{red}{n=181}$ and $\color{red}{n=362}$.

Let $n=61\cdot m$. Then $\varphi(n)=180=60\varphi(m)$; We now have to solve $\varphi(m)=3$. We can do this the same method described above (the set of divisors of $3$, $\{1,3\}$, add one, check if prime, get $\{2\}$, and see that $\varphi(2^{e_1})=3$ never happens). No solutions.

Let $n=37\cdot m$. Then $\varphi(n)=180=36\varphi(m)$; We now have to solve $\varphi(m)=5$. No solutions.

Let $n=31\cdot m$. Then $\varphi(n)=180=30\varphi(m)$; We now have to solve $\varphi(m)=6$. We find $m\in\{7,9,14,18\}$, resulting in $\color{red}{n=217}$, $\color{red}{n=279}$, $\color{red}{n=434}$, and $\color{red}{n=558}$.

Let $n=19\cdot m$. Then $\varphi(n)=180=18\varphi(m)$; We now have to solve $\varphi(m)=10$. We find $m\in\{11,22\}$, resulting in $\color{red}{n=209}$ and $\color{red}{n=418}$.

Let $n=13\cdot m$. Then $\varphi(n)=180=12\varphi(m)$; We now have to solve $\varphi(m)=15$. No solutions.

Let $n=11\cdot m$. Then $\varphi(n)=180=10\varphi(m)$; We now have to solve $\varphi(m)=18$. We find $m\in\{19,27,38\}$, resulting in $n=209$, $\color{red}{n=297}$ and $n=418$.

Let $n=7\cdot m$. Then $\varphi(n)=180=6\varphi(m)$; We now have to solve $\varphi(m)=30$. We find $m\in\{31,62\}$, resulting in $\color{red}{n=217}$ and $n=434$.


Now we've arrived at the factors that $n$ can contain multiple times. Luckily, we've already handled all the other possible prime factors, so that we know $2$, $3$ and $5$ are the only primes dividing $n$. Note however that if $5\not\mid n$, then $5\mid\varphi(n)$ will never happen, since neither $2$, $2-1$, $3$ and $3-1$ contain a factor $5$. Thus, $5\mid n$ (we already knew $n$ could be divisible by $5$, but now we know it needs to). The same is true for $3$. Thus, there are two cases left; $2\mid n$ or $2\not\mid n$. In the first case, write $n=2^a3^b5^c$ and use the formula to see

$$180=2^23^25=\varphi(2^a3^b5^c)=2^{a-1}(2-1)3^{b-1}(3-1)5^{c-1}(5-1)=2^{a+2}3^{b-1}5^{c-1}$$

but then $a=0$; contradiction, we assumed $a\ge 1$. Now the second case, $2\not\mid n$; We write $n=3^b5^c$ and use the formula to see

$$180=2^23^25=\varphi(3^b5^c)=3^{b-1}(3-1)5^{c-1}(5-1)=2^33^{b-1}5^{c-1}$$

and we see this leads to a contradiction (since the left-hand side is not divisible by $8$ but the right-hand side is).


Therefore, we've checked all the possibilities and have found all solutions ($10$ total).

$\endgroup$
  • $\begingroup$ Thanks, this is very well explained! $\endgroup$ – TijuanaTaxi May 2 '17 at 1:53
2
$\begingroup$

$\phi(n) = \prod_{p^k \| n} p^{k-1} (p-1)$ so what you need is trying the combination of primes $\le 181$ such that $p-1 | 180$. Also $k=1$ or $k=2$ or $\phi(k)$ is even, and if $k$ is odd then $\phi(2k)=\phi(k)$.

Since $5 | 180$ there are two possible cases :

  • or $n=5^2m$ and $180 = \phi(n) = \phi(5^2) \phi(m) =20\phi(m)$ ie. $ \phi(m) = 9$ impossible since it is odd

  • or $p | n$ for some $p$ such that $5 | p-1$ and $p-1 | 180$ : which means $p=11, 31,61$ or $181$, so that $n = pm$ with $ \phi(m) = 18,6,3$ or $1$.

    $\phi(m)=3$ is impossible. $\phi(m) = 1$ iff $m=1$ (or $m=2$). $\phi(m)=6$ iff $m = 7$ (or $m=2.7$..) or $m=3^2$, $\phi(m)=18$ iff $m=19$ $m=3^3$.

Thus the solution are : $ 181, 31.7, 31.3^2,11. 19, 11.3^3$ and $2. 181, 2.31.7, 2.31.3^2,2.11. 19,2. 11.3^3$

$\endgroup$
  • $\begingroup$ You missed quite a couple of solutions. There are $10$ total (Wolfram alpha agrees with me on this). Each of your solutions multiplied by $2$ also forms one (you've mistakenly assumed "$k=1$ or $\varphi(k)$ is even", while $\varphi(2)=1$) $\endgroup$ – vrugtehagel May 1 '17 at 23:11
  • $\begingroup$ @vrugtehagel Yes right, tks $\endgroup$ – reuns May 1 '17 at 23:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.