How to invert Euler's totient $\varphi$ I am writing this one since I have struggled a lot, at the very beginning of my Analytic Number Theory Course, to learn how to invert Euler's Totient. I wanted to find an algorithm, but, given the fact that inverting $\varphi$ is an NP-hard problem, I didn't find too much.
Feel free to comment and improve.

The problem is:
Find all positive integers $n$ such that $\varphi\left(n\right)=k$,
  for a given $k$. To fix the ideas, let us take $k=18$.

 A: First step: define the set:
$$S\left(k\right):=\left\{ \text{prime }p:\;\left(p-1\right)\mid k\right\}$$
In this case it is:
$$S\left(18\right):=\left\{ \text{prime }p:\;\left(p-1\right)\mid 18\right\}=\left\{ 2,3,7,19\right\} $$
The result is a set $\left\{ p_{1},p_{2},\dots,p_{n}\right\}$. Obviously, every solution $E$ of the equation $\varphi\left(n\right)=k$ is of the form
$$p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{n}^{a_{n}}\;\;a_i\in\mathbb{N},i=1,2,\dots,n$$
Second step: (not mandatory, but I find it very useful later). For every prime divisor $p_i$ found in the previous step, determine $\varphi\left(p_{i}^{a_{i}}\right)$ and stop when you find the first $i$ such that $\varphi\left(p_{i}^{a_{i}}\right)>k$. In fact, the property of the Euler function:
$$\varphi\left(p^r\right)=p^r-p^{r-1}$$
grants that after that index $i$ there is no more 'useful' power of the prime - meaning that all other powers of the prime are greater than $k$.
We have:
$$\begin{array}{ccccc}
\varphi\left(2\right)=1 & \varphi\left(2^{2}\right)=2 & \varphi\left(2^{3}\right)=4 & \varphi\left(2^{4}\right)=8 & \varphi\left(2^{5}\right)=16\end{array}$$
$$
\begin{array}{ccc}
\varphi\left(3\right)=2 & \varphi\left(3^{2}\right)=6 & \varphi\left(3^{3}\right)=18\end{array}
$$
$$
\begin{array}{cc}
\varphi\left(7\right)=6 & \varphi\left(19\right)=18\end{array}
$$
Third step: analyse all the cases of $\prod_{i=1}^{n}p_{i}^{a_{i}}$, starting from the highest prime.
In our case, the generic solution can be written as $2^a3^b7^c19^d$; the highest prime is 19. Two cases arise: either $d=0$ or $d=1$. If $d=1$ then:
$$\varphi\left(2^{a}3^{b}7^{c}19\right)=\varphi\left(2^{a}3^{b}7^{c}\right)\varphi\left(19\right)=18\varphi\left(2^{a}3^{b}7^{c}\right)$$
imposing the RHS equal to 1 gives raise to two more cases: either $a=0$ or $a=1$, leading to the solutions $E_1=19\cdot1=19$ and $E_2=19\cdot2=38$.
Analyse the case $d=0$; rewrite the generic solution as $2^a3^b7^c$ Consider that $\varphi\left(7\right)=6$ so $c$ cannot be 1. In fact, in that case, it should be $\varphi\left(2^a3^b\right)=3$, which is not possible. 
So, $c=d=0$; rewrite the generic solution as $2^a3^b$. The given equation has solution if and only if $b=3$. This gives raise to the cases $a=0$ and $a=1$, leading to the solutions $E_3=27\cdot1$ and $E_4=27\cdot2=54$.
Final note: this is a quick'n'dirty approach. You should have no problem, except for the computational weight. The real risk here is forgetting some cases. That's why I suggest to draw somehow a tree or a matrix to help visualising all the possible combinations.
