Find all $n$ such that $\varphi(n)=20$

Question

How can I find all integers such that $\varphi(n)=20$, where $\varphi$ is the Euler-totient function

I've seen somewhere that $\varphi(n)\ge\sqrt{n}$, for all $n$ except $n=2$ and $n=6$, without proof (and I think the proof is quite challenging). Is there an elementary way to find it ?

Answer 1

HINT:

If $n=\prod_{r=1}^mp_r^{u_r},\phi(n)=\prod_{r=1}^mp_r^{u_r-1}(p_r-1)$ for $u_r\ge1\forall r$

So, for each prime $p_r$ that divides $n,p_r-1$ must divide $20$

Answer 2

To work this out, you would note that the Eule phi function is weakly multiplicative, that is, f(ab) = f(a) f(b), only if a, b have no common divisors.

So it is a matter of going through the various prime and prime-powers, for numbers that divide N=20, eg

 2 (1) 4 (2)  8 (4)       16 (8)
 3 (2)                     9 (6)
 5 (4) 25 (20)            125 (100)
                           7   (6)
 11 (10)                  121 (110)

You then work out what numbers multiply to N, by working from the end

 11 (10)      (2) comes from 3, 2*3 and 4
 25 (20)      (1) comes from 1 and 2

None of the numbers against 2 or 3 are multiples of 5, so this is complete

 20:  33, 44, 50, 25, 66