Math Help - Euler Phi Function - finding all solutions

1. Euler Phi Function - finding all solutions

I have a question about finding all positive integers n such that

$\phi (n) = m$ where m is given.

For example $\phi (n) = 12$
===========================================

For this problem or any problem, how do you know that the possible number of solutions are finite and you are not missing any.

Regarding, to $\phi (n) = 12$, here is how I approached it.

If p | n, then (p-1) | 12. So, the possible p - 1 =1, 2, 3, 4, 6, 12 since they are factors of 12.

As a result, the possible values of p = 2, 3, 4, 5, 7, 13 but since p is a prime that leaves only p = 2, 3, 5, 7, 13.

From here, how would I continue?

I know that $n = p_{1}^{a_{1}} .... p_{k}^{a_{k}}$, then
$\phi (n) = \phi(p_{1}^{a_{1}})...\phi(p_{k}^{a_{k}})$, so would I have to check every 1,2,...,k for each single p's?

Thank you for reading. Any help is greatly appreciated.

2. For smallish values of m, like m=12, it is possible to enumerate all the integers n with $\phi(n)=m$, if you go about it systematically.

Remember that if $n=\prod p^\alpha$ is the factorisation of n into prime powers, then $\phi(n) = \prod p^{\alpha-1}(p-1)$. So if you want to find the possible values of n with $\phi(n)=m$, you should start by looking for all the factors of m of the form $p^{\alpha-1}(p-1)$.

Let's take the example m=12. The factors of 12 that are of that form are

$1 = 2^0(2-1)\quad($so $1 = \phi(2))$,
$2 = 3^0(3-1) = 2^1(2-1)\quad($so $2 = \phi(3) = \phi(4))$,
$4 = 5^0(5-1)\quad($so $4 = \phi(5))$,
$6 = 7^0(7-1) = 3^1(3-1)\quad($so $6 = \phi(7) = \phi(9))$,
$12 = 13^0(13-1)\quad($so $12 = \phi(13))$.

The only ways that we can make 12 as a product of these numbers are $12=12 = \phi(13)$, $12=1\times12 = \phi(2)\phi(13)$, $12=2\times6 = \phi(3)\phi(7) = \phi(3)\phi(9) = \phi(4)\phi(7) = \phi(4)\phi(9)$, and $12=1\times2\times6 = \phi(2)\phi(3)\phi(7) = \phi(2)\phi(3)\phi(9)$.

Notice that there is no way to write 3 in the form $p^{\alpha-1}(p-1)$, so we cannot make use of the factorisation $12=3\times4$. On the other hand, there are two ways to write each of the numbers 2 and 6 in that form, which gives us four ways to make use of the factorisation $12=2\times6$. Also, we can slip in a factor $1=\phi(2)$ to any factorisation that does not already include a term arising from a power of 2, such as $2=\phi(4)$ (but we can have, for example $12=1\times2\times6 = \phi(2)\phi(3)\phi(7)$, where the 2 arises from $\phi(3)$ rather than $\phi(4)$).

Thus there are eight numbers n with $\phi(n)=12$, namely 13, 21, 26, 27, 28, 36, 42 and 54.