How to solve equations of the type: $\phi(n)=m$? How to solve equations of the type: $\phi(n)=m$?
I have, for instance, $\phi(n)=6$. I never saw that kind of questions. I would really appreciate any lead on it.
 A: As I'm sure you know, $\phi(n)$ gives you the number of natural numbers smaller than $n$ and relatively prime to it. By a general theorem, 
$$\phi(n) = n\prod_{p\mid n} \left(1-\frac{1}{p}\right)$$
where the product is taken over all primes $p$ dividing $n$. Basically this is for the following reason: every prime $p$ dividing $n$ eliminates $1/p$ of the numbers less than $n$ because this fraction of numbers are multiples of $p$ (if you count zero). Thus for each $p\mid n$, $(1-1/p)$ is the fraction of numbers less than $n$ (including zero) that are not multiples of $p$. Because of the Chinese Remainder Theorem, we can think of the question "am I a multiple of $p$?" as independent for each different prime. Thus the fraction of numbers less than $n$ that do not share some prime factor with $n$ is the product $\prod_{p\mid n} (1-1/p)$. Since there are $n$ numbers less than $n$ altogether (including zero), we obtain $n\prod_{p\mid n} (1-1/p)$ as the total number that are prime to $n$.
At any rate, this theorem is the key device needed to solve the problem. For example, for $\phi(n)=6$, we have
$$ 6 = 2\cdot 3 = n\prod_{p\mid n}\left(1-\frac{1}{p}\right)$$
We need the right side to have factors of only 2 and 3 and each exactly once. If we see $n$ as a product of primes $n=p_1^{k_1}p_2^{k_2}\dots$, the right side becomes
$$p_1^{k_1-1}(p_1-1)\cdot p_2^{k_2-1}(p_2-1)\cdot\dots$$
since multiplying $n$ by a factor of $(1-1/p_i) = (p_i-1)/p_i$ replaces one of the $p_i$'s with a $p_i-1$. Thus we see that for any $p$ dividing $n$, $p-1$ is a factor of $\phi(n)$, and if $p$ divides $n$ more than once, $p$ is also a factor.
We need this product to be exactly six.
So, how can this happen? For every $p$ dividing $n$, $p-1$ is a factor of $\phi(n)$, which shows that if $p>7$, then $\phi(n)\geq p-1 > 7-1=6$. So if we want $\phi(n)=6$ then $n$ cannot have any prime factors bigger than $7$.
Say $7$ is a factor of $n$. Then by the above, $7-1=6$ is a factor of $\phi(n)$. This is already the answer we want, so we can't let any other factors of $n$ contribute factors to $\phi(n)$. One solution is therefore to take $7=n$, and $\phi(7)=6$. Another is to take $n = 7\cdot 2 = 14$, because a factor of $2-1=1$ won't be a problem. But putting into $n$ another factor of $2$, or any other prime $\neq 2$, would contribute another factor to $\phi(n)$ and it would be too big. So far we have two solutions, $n=7,14$; and if we want to include the factor $7$, that's it.
But we could also avoid $7$. We must also avoid $5$, because $5$ would contribute $5-1=4$ as a factor of $\phi(n)$, and $4$ doesn't divide $6$. Thus we are left with $2$ and $3$ as possible factors. We will not get $3$ to come out as a factor of $\phi(n)$ unless we include $3$ at least twice, to get $3(3-1)$, and this is already six. Thus including $3$ more than twice will make $\phi(n)$ too big; but $3^2 = 9$ is a solution: $\phi(9)= 3(3-1)=6$. And again, we can throw in one $2$ to get $\phi(18)=6$ as well, because $2-1=1$ won't change anything, but any more factors of $2$ would contribute a $2$ to $\phi(n)$, and this would be too big. Thus $9$ and $18$ are the only other solutions, and $7,9,14,18$ is a complete list.
Similar methods work in general.
A: The general idea here is to use the prime factorizations of $n$ and $m$. For you particular example, suppose
$$
n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}
$$
where 
$$
p_1 < \dots < p_k
$$ 
are primes, and $1 \leq a_i$ for each $i$. Then we suppose $\phi(n) = 6$. We know that $\phi$ is a multiplicative function, and presumably you have seen how to compute $\phi$ for prime powers. We can use this to see that
$$
6 = \phi(n) = p_1^{a_1 - 1}(p_1 -1) \cdots p_k^{a_k - 1}(p_k -1).
$$
This tells us already that the values of $p_1, \dots, p_k$ can't be "too big". In particular, we must have $p_k \leq 7$, because otherwise $p_k - 1$ cannot be a divisor of $6$. If $p_k = 6$, it is clear that $n$ must equal $7$ or $14$. Otherwise $p_k \leq 3$, so $k \leq 2$. 
Suppose $k = 2$, so that $p_1 = 2$, $p_2 = 3$. Then $6 = 2^{a_1 -1} \cdot 3^{a_2 -1} \cdot 2 = 2^{a_1}3^{a_2 - 1}$. What can $a_1$ and $a_2$ be in this case?
Otherwise $k = 1$. So either $p_1 = 2$ or $p_2 = 3$. Try examining each case to see which can possibly work.
Once you have discovered the possible primes $p_1, \dots, p_k$ and the possible exponents $a_1, \dots, a_k$, this will tell you all possible values of $n$ such that $\phi(n) = 6$. 
