Solving $\phi(n)=84$ Ok, I really need some help understanding this because either my brain isn't working at the moment or I'm breaking math and I have a striking suspicion that one of those is more likely.
Anyways, here's my process. WolframAlpha tells me there are 12 integer solutions, they are all $^+_-n$ so let's say there are 6 of them. They are as follows: $129, 147, 172, 196, 258, 294$
Ok, so here's how I attempted to solve it. $n$ looks like this ${\prod_{i=1}^kp_i^{\alpha_i}}$. And $\phi(n)=n\prod_{p\vert n}(1-\frac{1}{p})$. So I plug $n$ in and get an equation like this:
$\prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)=84$
Now, solving for $n$ SHOULD be equivalent to solving for $p_i, \alpha_i$, right?
So, I started going through possible values of $k$ and I'm interested in the case of $k=2$.
This means that $n$ has two prime factors, so it looks like $p_1^{\alpha_1}p_2^{\alpha_2}$, and the equation is:
$p_1^{\alpha_1-1}(p_1-1)p_2^{\alpha_2-1}(p_2-1)=84$
Ok. Here's my issue. Factoring $84$, we get $2\times2\times3\times7$
So I try to see a pattern. The first solution I came up with is $p_1=7, \alpha_1=2, p_2=2, \alpha_2=2$. Then I followed the same logic that led me to that solution but didn't find any more so I concluded that the other solutions must be as higher values of $k$. But then I factored $172$ and saw that it also had only two primes. It also fits the pattern. So I realized that I could get ones in that product as a result of $p^0$ and following that pattern, filling in the remaining factors, I found the $129$ solution.
No more, the next one must be at $k=3$. NOPE. $147$ also factors into only 2 primes. So now I'm really at a miss. Is there a more effective way to iterate over all of these combinations?
 A: Look at 7. Two possibilities:


*

*$7|(p-1)$ with $p|n$:
hence $p = 14k+1 \in \{ 29, 43\}$ (the others are too big). 

*If $p=29$, $\phi(n) = 28\times 3 = (29-1)(3)$. 3 has to be some $(p-1)p^{a-1}$ but $p=4$ is not prime.

*If $p=43$, you have the solution $\phi(n) = 42\times 2\implies n = 43\times 3$ or
$n = 43\times 2^2$.

*Otherwise: $7|n$. $\phi(n) = 6\times 7\times 2\implies n= 7^2\times 3$ or $n= 7^2\times 2^2$.


I have used that $\phi(n) = 2\implies n\in\{3,4\}$.
A: Here is a technique you can use to solve these kinds of problems that doesn't need much intuition. Firstly, you need a lemma.
Lemma: If $n$ is odd, then $\phi(n) =\phi(2n)$.
If the prime factorisation of $n$ is $n = \prod_{i=1}^m p_i^{\alpha_i}$, then $\phi(n) = \prod_{i=1}^m p_i^{\alpha_i-1}(p_i-1)$. So $p_i - 1 \mid 84$. Listing out factors of 84, the possible values $p_i-1$ can take are:
$$p_i-1 = 1,2,4,6,7,12,14,21,42,84.$$
Then,
$$p_i = 2,3,5,7,8,13,15,22,43,85,$$ of which $8,15,22,85$ are not prime. So possible values of $p_i$ can take are:
$$p_i = 2,3,5,7,13,43.$$
Now condition on the highest prime occurring in the prime factorisation of $n$.
$43$ is the highest prime dividing $n$: Then $\phi(n) = 42*a, a=2$. Then we only need to hunt for something to contribute a factor of $2$ for $\phi(n)$. This can come from $2^2$ or $3$. This gives $n = 43*3$ or $n=43*2^2$ respectively. With the lemma, $\phi(2*43*3)=\phi(3*43)$. This gives $3$ solutions, $n= 129,258,172$.
$13$ is the highest prime dividing $n$. $\phi(n) = 12 *a , a=7$. We need to hunt for a term contributing $7$. $7$ can either come from one of the $p_i-1$'s or $p_i$'s. It is the latter because $p_i-1 = 7 \implies p_i = 8$, which is not prime. Yet, having $7 \mid n$ would imply $6 *12 \mid \phi(n)$, contradiction. So $13$ cannot be the highest prime dividing $n$.
$7$ is the highest prime dividing $n$. $\phi(n) = 6*a, a=14$. We need to hunt for a term contributing $14$. Yet all primes dividing $n$ are going to be smaller than $7$ already, so the only option for $\phi(n)$ to incur a factor of $7$ would be for the power of $7$ in the prime factorisation of $n$ to be $\geq 2$. We can further see that it has to be exactly $2$. This means that $7^2 \mid n$ and $\phi(n) = 7*6*a, a=2$. We still need a factor of $2$, which would come from $3$ or $2^2$. So $n = 7^2 * 3$ or $n = 7^2 * 2^2$. From the lemma, $n = 2*7^2 *3$ is a viable option as well. So $n = 147,294, 196$.
$5$ is the highest prime dividing $n$. Then we need to hunt for a term contributing $21$. Yet this implies $7 \mid n$, but now the primes are too `small' to contribute a $7$, contradiction.
Similarly, for $3$ and $2$ being the highest prime dividing $n$, it will always imply that $7 \mid n$. So there are no more answers.
