When can I stop checking if $ \varphi(n) $ is equal to some integer - Euler Totient Function Take the example $ \varphi(n) = 12 $
After I split into factors $(12 \times 1), (6 \times 2), (4 \times 3)$
I know that $ \varphi(13) = 12 $ and $ \varphi(2) = 1 $, hence $ n = 13 \times 2 = 26 $ is one value for $ n $ since $ gcd(13, 1) = 1 $
But how do I know that there doesn't exist some value like 121 such that $ \varphi(121) = 12 $
I saw this somewhere, it had something to do with the limit when factorised into primes but I can't remember how it was done.
Could someone please explain at what point i can stop checking $\varphi(n)$'s
Thanks a million !
 A: Here are $\varphi$ values for various prime powers:
Powers of $2$ ($2,2^2,$ etc.) have (possibly usable) $\varphi$ values respectively of $1, 2, 4$  (the next $\varphi$ value is $8$, which won't help get you to $\varphi(n)=12$.
Powers of $3$ have usable $\varphi$ values of $2, 6$.
Powers of $5$ have usable $\varphi$ values of $4$.
Powers of $7$ have usable $\varphi$ values of $6$.
Powers of $11$: none are usable.
Powers of $13$ have usable $\varphi$ values of $12$.
Any higher primes have no usable powers.
You now can mix and match to find the $6$ (I think) possible solutions.
A: Splitting 12 into its factors gives you an idea of what primes/prime powers might be involved in any $n$ with $\phi(n)=12$. Examining each factor of 12:


*

*$1$: can arise from 2

*$2$: can arise from 3 or 4

*$3$: not possible

*$4$: can arise from 5 or 8

*$6$: can arise from 7 or 9

*$12$: can arise from 13


Since 3 is not a possible value for $\phi$, we're looking at composing $\phi(n)$ from the 6x2, 6x2x1, 12 or 12x1 options. We can't use the same prime from different contributors though.
Option for $n$ are then $7\times 3=21, 7\times 4=28, 9\times 4=36, 7\times 3\times 2=42, 13$ and $13\times 2=26$ 
Maximum $n$ is therefore $42$.

Any given totient value, $t$, can only be generated by at most one prime and at most one prime power.


*

*Prime $p$ with $\phi(p)=t$ is only possible if $t+1$ is prime.

*Prime power $q=p^k, k>1$ has totient $\phi(q) = p^{k-1}\phi(p)= p^{k-1}(p-1)$. Therefore if $t$ is the totient of a prime power, that prime must be the same as the largest prime factor of $t$ (call that $s$) and the residue of $t$ after all factors of $s$ are divided out must be $s-1$.

A: One way in general is to use the known lower bounds for $\phi(n)$. For example, we could use
$$ \phi(n) > \frac{n}{e^\gamma \log \log n + \frac{3}{\log \log n}}  $$ for $n>2$.
This gives a good upper bound on $n$ with $\phi(n)=k$. Even for such a small $k$ like $k=12$ we see that for $n>56$ this gives already $\phi(n)>12$. Then it is easy to check the cases $n\le 56$. 
In general there can be several values of $n$ with $\phi(n)=k$ for a given $k$. For $k=12$ these are $n=13,21,26,28,36,42$. 
Finally for every integer $m\ge 1$ there is a $k$ such that $\phi(n)=k$ has exactly $m$ solutions. This was an old conjecture of Sierpinski. 
A: You can stop checking at $6n$, but that's just a rule of thumb.
Remember the formula for the totient function: for $p$ prime, $\phi(p) = p - 1$, for powers of primes we have $\phi(p^\alpha) = (p - 1)p^{\alpha - 1}$, and that the function is multiplicative conditioned on coprimality.
So to find out how many answers there are to $\phi(m) = n$, you're essentially looking for all ways to express $n$ as a product of numbers of the form $(p - 1)p^{\alpha - 1}$. (There are no odd numbers of this form except for $1$). But you have to watch out for some numbers that can be expressed in these forms multiple ways, like for example $4 = 5 - 1 = (2 - 1)2^3$.
After picking out the appropriate divisors, you figure out if they correspond to a prime or a power of a prime or both, combine them in ways to multiply to $n$, and then you multiply the primes and powers of primes corresponding to those combinations of divisors to obtain the various values of $m$. This way you obtain a finite set of distinct numbers, one of which must be the smallest and another one the greatest.
The divisors of $12$ are $1, 2, 3, 4, 6, 12$. We don't need to worry about $3$, since it's not $1$ less than a prime nor of the form $(p - 1)p^{\alpha - 1}$. After examining these divisors and grouping them, you should find that $1 \times 2 \times 6 = 12$ leads you to $2 \times 3 \times 7 = 42$, which is greatest possible $m$ such that $\phi(m) = 12$.
You can of course program a computer to do this, but for a quick-and-dirty program, or even in Wolfram|Alpha, this is too sophisticated. Besides $6n$, another quick and dirty way to overshoot the maximum $m$ is to take the prime factorization of $n$, and $2$ to the exponents of the primes, e.g., for $12 = 2^2 \times 3$ compute $2^3 \times 3^2 = 72$, which overshoots the maximum $m$ by $30$ rather than $79$. This is not a big deal for small numbers, but with largish numbers it can be grossly inefficient.
In Wolfram|Alpha, you can do something like Select[Range[72], EulerPhi[#] == 12 &]. Anything more sophisticated than that requires Wolfram Mathematica.
