Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Thank you for fixing the link, Moron. –  yunone Sep 28 '10 at 22:22
    
Interesting question... –  Aryabhata Sep 28 '10 at 23:22
add comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
Thank you, Qiaochu, this answer was very straightforward and easy to understand. –  yunone Sep 29 '10 at 10:41
add comment

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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