1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you! Your answer has been really helpful! $\endgroup$ – Collapse Apr 13 '18 at 23:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Kenkar Apr 29 '18 at 15:30
1
$\begingroup$

Writing $\varphi(3^\beta)=3^\beta-3^{\beta-1}$ is not correct when $\beta=0$. That is why you are missing $49,98$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.