# 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$.

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.

• You're welcome. Don't forget to multiply only relatively prime numbers in your function $\varphi(n)$ since I had forgotten to mention that and since this example doesn't include that possibility.In this example if we imagined that $\varphi(2^3)=1$ works , we shouldn't consider following variation: $\varphi(7^2)*\varphi(2)*\varphi(2^3)$ because $2$ and $8$ are not relatively prime. Just to mention that $\varphi(2^3)$ is not $1$ , this was just covering all the possible cases. – Kenkar Apr 29 '18 at 15:30
Writing $\varphi(3^\beta)=3^\beta-3^{\beta-1}$ is not correct when $\beta=0$. That is why you are missing $49,98$.