# Generalizing values which Euler's-totient function does not take

I was reading about Euler's totient function on wikipedia, and it eventually led me to this book on google:

Anyway, the books lists many assertions without proof, only references which I can't find. One I could not solve for myself said that not all even numbers are values of $\phi(n)$. The sequence of even non-values of $\phi(n)$ starts:

$14, 26, 34, 38, 50, 62,\dots$

After thinking about it for a while, I've made little headway. Looking at 14 specifically, I suppose if such a solution $a$ to $\phi(x)=14$ were to exist, $(a,m_i)=1$ for $1\leq i\leq 14$, for some $m_i\lt a$ and so there must also exist inverses $\overline{a_i}$ such that $\overline{a_i}a\equiv 1 \pmod {m_i}$ for each $i$. I'm looking for some contradiction, possibly of the Chinese Remainder Theorem, to show such $a$ cannot exist.

Is there some way to generalize which values are not taken by $\phi$, or at least explain why this is the case? I was hoping to see why $14$ is the least such integer such that this is true, but values $1$ to $13$ must be indeed taken. I suppose this would also explain why 26 is the next such value that is not taken, while $15$ to $25$ are.

-
Thank you for fixing the link, Moron. – yunone Sep 28 '10 at 22:22
Interesting question... – Aryabhata Sep 28 '10 at 23:22

It's just casework on the prime factorization of $n$. If $\phi(n) = 14$ then $n$ can't be divisible by any primes larger than $7$ (because $p-1$ cannot divide $14$ for such primes), and it can't be divisible by any of $5, 7$ because $4, 6$ don't divide $14$. So it can only be divisible by $2$ or $3$. Since $14$ is not divisible by $3$, $3$ can only divide $n$ at most once, so $n$ is of the form $2^k 3$. But then $\phi(n) = 2^k$; contradiction.

Similarly, if $\phi(n) = 26$ then $n$ can't be divisible by any primes larger than $13$, and it can't be divisible by any of $5, 7, 11, 13$ because $4, 6, 10, 12$ don't divide $26$. So it can only be divisible by $2$ or $3$, and then the same argument as above works.

For any particular potential value of $\phi(n)$ a similar, but longer, argument should work; in particular it should be possible to test in finite time whether a particular candidate works.

-
Thank you, Qiaochu, this answer was very straightforward and easy to understand. – yunone Sep 29 '10 at 10:41

From the comments to A005277 :

If p is prime then the following two statements are true. I. 2p is in the sequence iff 2p+1 is composite (p is not a Sophie Germain prime). II. 4p is in the sequence iff 2p+1 and 4p+1 are composite. - Farideh Firoozbakht (mymontain(AT)yahoo.com), Dec 30 2005

This covers most of your cases, 50 is covered by the next comment.

-
In general, when you encounter some sequence of integers in your work, it is always a good idea to look first at OEIS; the refs there usually provide interesting leads. – J. M. Sep 29 '10 at 1:20
Thanks for pointing out this site, it seems very useful and good for future reference. – yunone Sep 29 '10 at 10:42