How to solve the equation $\phi(n) = k$? 
Let $\phi(n) $ is the numbers of number that are relatively prime to n.
  Then, how could we solve the equation $\phi(n) = k, k > 0?$

For example:  
$\phi(n) = 8 $
I can use computer program to check all numbers that are relatively prime to $n$, but I think there must be an easier way to approach this problem.  
Base on this formula:
$$\prod_{i=0}^{k} p_{i}a^{a_i} $$
The only thing I can see is n must not have a prime factor > 9, otherwise $\phi(n) > 8 $.
I really don't know where to start :( ? A hint would be greatly appreciated.
 A: See these:


*

*Inverting the totient function at MathOverflow

*Complexity of Inverting the Euler Function at arxiv

*Complexity of Inverting the Euler Function in Mathematics of Computation
A: This is too long to be comment and hence the post.
$\phi(n) = 8$. Note that $\sqrt{n} \leq \phi(n) \leq n-1$.
This implies $n$ is at most $64$. So you could write a brute force computer and compute $\phi(n)$ when $n \in [9,64]$.
A better way would be as follows.
Let $n=\displaystyle \prod_{i=1}^k p_i^{\alpha_i} \Rightarrow \phi(n) = \displaystyle \prod_{i=1}^k p_i^{\alpha_i-1} (p_i-1)$.
First note that $n$ can be of the form $\displaystyle 2^\alpha \left( \prod_{i=1}^k p_i \right)$ i.e. the exponent of the odd primes in the prime factorization of $n$ is $1$. This is so, because if not these primes will then divide $\phi(n) = 8$ which is not possible.
If $k=0$, then we have $n=2^{\alpha}$, $\displaystyle 2^{\alpha-1} = \phi(n) = 2^3 \Rightarrow \alpha=4$. Hence, $k=1 \Rightarrow n=16$.
Let $k=1$. Then we have $n=2^{\alpha} p_1$. 
If $\alpha = 0,1$, then $\displaystyle (p_1-1) = \phi(n) = 2^3 \Rightarrow p_1 = 9 \Rightarrow \text{ Not possible}$.
If $\alpha = 2$, then $\displaystyle 2 (p_1 - 1) = \phi(n) = 2^3 \Rightarrow p_1=5$. Hence, $n=20$.
If $\alpha = 3$, then $\displaystyle 2^2 (p_1 - 1) = \phi(n) = 2^3 \Rightarrow p_1=3$. Hence, $n=24$.
Now let $k=2$. Then we have $n=2^{\alpha} p_1 p_2$. 
If $\alpha = 0,1$, then $\displaystyle (p_1-1)(p_2-1) = \phi(n) = 2^3 \Rightarrow p_1 = 3, p_2 = 5$. Hence, $n=15$ when $\alpha = 0$ and $n=30$ when $\alpha = 1$
If $\alpha = 2$, then $\displaystyle 2(p_1-1)(p_2-1) = \phi(n) = 2^3 \Rightarrow (p_1-1)(p_2-1) = 4 \Rightarrow \text{ Not Possible}$.
$k=3$ is not possible since $(3-1) \times (5-1) \times (7-1) > 8$.
Hence, the only solutions (hope I have not missed any case) are:
$$n=15,16,20,24,30$$
Similar idea extends to other problems where we want to find the inverse of the totient function.
A: I needed this recently and sketched the following algorithmic approach, so I might as well put it here. It's not terribly efficient but it works.
Input: Integer $k>0$
Output: All solutions $x$ of $\varphi(x)=k$.
Pseudocode:

*

*Let $Q = \{d+1; d \mid k \text{ and } d+1 \text{ is prime}\}$

*For all $R \subseteq Q$:

*

*Set $l = \prod_{r \in R} (r-1)$

*If $l \mid k$ and  all prime factors of $\frac{k}{l}$ lie in $R$:

*

*Report $x=\frac{k}{l}\cdot \prod_{r\in R} r$
It is based on the fact that if prime $q\mid x$, then $q-1 \mid \varphi(x)=k$, so all prime factors of $x$ must come from a suitable divisor $d \mid k$ for which $d+1$ is a prime. There are only finitely many of these so we store them in a set $Q$. Then for each combination of these primes, there is at most one $x$ which has exactly these prime factors. It also immediately implies there is at most $2^{\tau(k)}$ solutions (where $\tau(k)$ is number of positive divisors of $k$).
For example if $\varphi(n) = 8$, then $k=8$ and divisors $d$ of $k$ are $1,2,4,8$. So primes $d+1$ form $Q=\{2,3,5\}$. Then for each $R \subseteq Q$ we compute:
\begin{array}{c|c|c|c|l}
R&l= \prod_{r \in R} (r-1)&\frac{k}{l}&x=\frac{k}{l}\cdot \prod_{r\in R} r\\
\hline
\emptyset&1&2^3&\text{None}\, ( \{2\} \not\subseteq \emptyset ) &\\
\{2\}&1&2^3&16& \\
\{3\}&2&2^2&\text{None}\, (\{2\} \not\subseteq \{3\})& \\
\{5\}&4&2^1&\text{None}\,  (\{2\} \not\subseteq \{5\})& \\
\{2,3\}&2&2^2&24& \\
\{2,5\}&4&2^1&20& \\
\{3,5\}&8&1&15& \\
\{2,3,5\}&8&1&30& \\
\end{array}
Hence $x \in \{15,16,20,24,30\}$.
This can be futher optimized when programmed, for example instead of iterating over all subsets $R \subseteq Q$ we can backtrack whenever $\prod_{r \in R} (r-1) \mid k$ cannot be satisfied, and so on...
