Problem:
Let
How many of the values , and are integers?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Let . Because the coefficients of are integers, it follows that if , then . It suffices to show that the 8 numbers are all divisible by 8 . If is even, then each of the monomials of is divisible by 8 . If , then . If , then , which implies that , and so also that . Hence .
Therefore is divisible by 8 for all integers , which implies that is an integer for all . In particular, all of the given values of are integers.
Let be defined as in the first solution, and note that is divisible by 8 if is even. To treat odd , write
and note that because , and are all even, each term has at least three factors of 2 . The solution concludes as above.
Another way to see that is divisible by 8 when is odd in the second solution is to apply more general facts from number theory. Fermat's Little Theorem asserts that if is prime, then for all integers . In particular, . Euler's Totient Theorem asserts that if , then , where is the number of positive integers less than that are relatively prime to . Because , it follows that when is odd. Also, , so if is odd.
Note: Suppose that a necklace is to be made by placing beads, equally spaced, on a circular ring. Each bead can be any one of different colors. Two necklaces are regarded as being the same if they differ only by rotation. In 1892 Captain Percy Alexander MacMahon showed that the number of such necklaces is
He acknowledged its prior discovery by another soldier, Monsieur le Colonel Charles Paul Narcisse Moreau. Thus counts the number of necklaces with beads and therefore must be an integer. This is discussed in Concrete Mathematics by Graham, Knuth, and Patashnik.
The problems on this page are the property of the MAA's American Mathematics Competitions