Using Euler's Totient Function, how do I find all values n such that $\phi(n)=12$? [duplicate]

How do I generalize the equation to be able to plug in any result for $\phi(n)=12$ and find any possible integer that works?

Solution 1:

Assuming you mean to solve $\phi(n)=12$, you can use the formula for $\phi(n)$ that consists of factoring $n$ and then replacing one copy of every prime $p$ that occurs by $p-1$. You need such $p-1$ to divide $12$, so the only $p$ that can occur are $2,3,5,7,13$, and since occurrence with multiplicity at least $2$ also gives a factor $p$, this cannot happen for $5,7,13$. Also you need a factor $3$, which means you need one of $3,7,13$. Now it is not hard to write down the complete list of (factored) values for $n$: $13,2\times 13,2^2\times7,3\times 7,2\times3\times7,2^2\times3^2$.

Solution 2:

Note that $\lim_{n \rightarrow \infty} \varphi(n) = \infty$, so for any $k \in \mathbb{Z}^+$, the equation $\varphi(n) = k$ has at most finitely many solutions. How to find all of them?

Solutions to $\varphi(n) = k$ for very small values of $k$ can easily be worked out by hand and probably should be as a good exercise. For instance if $\varphi(k) \leq 4$ then $n$ can only be divisible by primes $2$, $3$ and $5$, i.e., $n = 2^a 3^b 5^c$ for natural numbers $a,b,c$. Since $\varphi(5^2) = 5(5-1) = 20$, we must have $c \in \{0,1\}$. Since $\varphi(3^2) = 3(3-1) = 6$, we must have $b \in \{0,1\}$. Since $\varphi(2^4) = 2^3(2-1) = 8$, we must have $a \in \{0,1,2,3\}$, which leaves us with $2 \cdot 2 \cdot 4 = 16$ values of $n$ to check.

The above method will work for any value of $k$, but it gets very slow as $k$ grows. You could still do it for $k = 12$ -- the value you asked about -- but I wouldn't want to do it by hand even for $k = 50$, say.

In fact for even moderately large $k$ this a problem to get your computer to solve. However, you should and can do something faster than the method sketched out above. Better is to use one of the known explicit lower bounds for $\varphi$. In fact this problem came up in a research project for graduate students that I led at UGA a few years back, and the following simple lower bound was perfectly adequate for our purposes:

(1) $\varphi(n) \geq \sqrt{n}$, for $n > 6$

(I learned this originally from wikipedia, although its article on the totient function seems no longer to include this result.)

Thus, assuming $k > 4$ (we did the other case above!) so $n > 6$, using this inequality to find all values of $\varphi(n) = k$ you just need to evaluate the $\varphi$ function at all positive integers in the range $[1,k^2]$: no problem for a computer.

What if you are working with really large $k$? Well, there is in fact a much better inequality

(2) $\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}$, for $n > 2$.

This is extremely close to being sharp: if we omitted the $\frac{3}{\log \log n}$ term in the denominator, the right hand side would get ever so slightly larger, but this is large enough for the inequality to be false for infinitely many $n$. I have not given the matter any deep thought, but if anyone knows a faster way to enumerate the solution set to $\varphi(n) = k$ for large $k$ than by a brute-force search using (2) above, I would be interested to know.