I was reading about Euler's totient function on wikipedia, and it eventually led me to this book on google:
Page 74 of the book, Prime numbers: the most mysterious figures in math
By David G. Wells.
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.
Best Answer
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.