2
$\begingroup$

I was just getting my hands dirty solving some equations of the form $x=\phi(n)$ where $\phi(n)$ is Euler totient function. I know that $\phi(n)$ is even for $n\geq 3$. However, I am wondering that:

Can all even integers $x$ be expressed as $\phi(n)$ where $n$ is an integer?

I start doing some research, the first even number appears to hove no solution is $14$. According to this page, there is no solution to the equation $14=\phi(n)$ for $n\leq 500$. But does it have a solution for $n>500$?

Moreover, what can you say about the above statement?

$\endgroup$
2
$\begingroup$

To see that $\varphi(n)=14$ has no solution, consider the possible prime factorization of $n$. If a prime $p>15$ divided $n$, then $p-1$ would divide $14$, a contradiction. So $n$ can only be divisible by $2,3,5,7,11,13$. Easy to eliminate $7,11,13$, so $n=2^a3^b5^c$. But $7$ clearly doesn't divide $\varphi(2^a3^b5^c)$, and we are done.

To see that there are infinitely many $m$ for which $\varphi(n)=m$ has no solution, consider $m$ of the form $2p$ where $p$ is an odd prime, such that $2p+1$ is not prime (it's enough that $p\equiv 1 \pmod 3$, say). Suppose that $\varphi(n)=2p$, and let $q$ be a prime dividing $n$. Now $(q-1)\,|\,2p\implies (q-1)\in \{1,2,p,2p\}$ Thus $q\in \{2,3\}$. Easy to see that this is impossible.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for this detailed answer. $\endgroup$ – Maged Saeed Nov 3 '18 at 11:32
  • 1
    $\begingroup$ No problem. I edited my post to sketch a proof that that there are infinitely many such. $\endgroup$ – lulu Nov 3 '18 at 11:44
2
$\begingroup$

14 is not $\varphi(n)$ for any $n$. Such numbers are called nontotients, there are infinitely many of them and they are given by OEIS A005277.

To show the infinitude of nontotients, consider the primes $p=10n+7$, which are themselves infinite by Dirichlet's theorem on arithmetic progressions. Then $2p+1$ is composite, being divisible by 5, and by a comment by Firoozbakht on the OEIS page $2p$ is a nontotient. In particular, 14 is the first nontotient corresponding to a $10n+7$ prime.

| cite | improve this answer | |
$\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.