Euler totient function equation: $\varphi(n)=42$ I was trying to solve an Euler totient equation, specifically $\varphi(n)=42$
My attempt:
If we denote $n=p_{1}^{k_1}\cdot ...\cdot p_{n}^{k_n}$ then we know that $\varphi(n) = \prod_i{p_i^{k_i-1}(p_i - 1)}$.
Threfore $p_i-1 \vert \varphi(n)=42=2^13^17^1$
Obviously then $p_i\in \{2,3,4,7,8,15,22,43 \}$ 
Only valid choices are obviously $2,3,7,43$ since the others aren't prime. We know that $2\vert 42,3\vert 42,7\vert 42$ so let's observe $43$ separately.
First, consider that $n=43\cdot m$, where $\gcd(m,43)=1$. Now we have
$42 = \varphi(n) = \varphi(43)\varphi(m)= 42\varphi(m) $. Therefore $m=1,2$, so the solutions for $n$ are $43$ and $86$.
Second, consider that $43$ is not a divisor of $n$. So we can write $n$ as $2^{\alpha}3^{\beta}7^{\gamma}$ where $\alpha \leq 2, \beta \leq 2, \gamma \leq 2$. (coming from $p_i^{k_i-1}\vert42$).
But now $42 = \varphi(n)=\varphi(2^{\alpha})\varphi(3^{\beta})\varphi(7^{\gamma}) = (2^{\alpha}-2^{\alpha-1})(3^{\beta}-3^{\beta-1})(7^{\gamma}-7^{\gamma-1}) = 2^{\alpha+1}3^{\beta}7^{\gamma-1}$
So: $\alpha = 0, \beta = 1, \gamma = 2$.
But that doesn't make any sense, because $\varphi(147) \neq 42$ and I'm missing two solutions: $49$ and $98$.
Thanks in advance!
 A: Hopefully this approach will help you solving these kinds of problems.
You have already determined all of the needed primes, so I will skip that part.
Now determine the highest possible power of each prime that will form the wanted $n$ along with the fact that, as you have written ,$\varphi(n) = \prod_i{p_i^{k_i-1}(p_i - 1)}$.
So we got:
$2^a => a\leqslant2$,  since $2^2\nmid 42$
$3^b => b\leqslant2$, since $3^2\nmid 42$
$7^c => c\leqslant2$, since $7^2\nmid 42$
$43^d => d\leqslant1$, since $43\nmid 42$.
Now write down all the possible $\varphi(k)$ using $\varphi(n)= n\prod_{p\vert n}{(1-\frac{1}{p})}$ where $p$ is prime:
$\varphi(2)=1,\varphi(2^2)=2,\varphi(3)=2,\varphi(3^2)=6,\varphi(7)=6,\varphi(7^2)=42,\varphi(43)=42$.
All you need to do now is to find all the possible combinations that will form $42$:
$\varphi(7^2)$ , $\varphi(7^2)*\varphi(2)$ , $\varphi(43)$ , $\varphi(43)*\varphi(2)$.
So $n=49,98,43,86$, since $\varphi(n)$ is multiplicative.
A: Writing $\varphi(3^\beta)=3^\beta-3^{\beta-1}$ is not correct when $\beta=0$.  That is why you are missing $49,98$.
