Problem:
Let
P(m)=2mβ+4m2β+8m4β+8m8β.
How many of the values P(2022),P(2023),P(2024), and P(2025) are integers?
Answer Choices:
A. 0
B. 1
C. 2
D. 3
E. 4
Solution:
Let Q(m)=8P(m)=4m+2m2+m4+m8. Because the coefficients of Q are integers, it follows that if aβ‘b(mod8), then Q(a)β‘Q(b)(mod8). It suffices to show that the 8 numbers Q(β3),Q(β2),Q(β1),β¦,Q(4) are all divisible by 8 . If m is even, then each of the monomials of Q(m) is divisible by 8 . If m=Β±1, then Q(m)=Β±4+4β‘0(mod8). If m=Β±3, then m2=9β‘1(mod8), which implies that m4β‘1(mod8), and so also that m8β‘1(mod8). Hence Q(Β±3)β‘Β±12+2+1+1β‘0(mod8).
Therefore 8P(m) is divisible by 8 for all integers m, which implies that P(m) is an integer for all m. In particular, all (E)4β of the given values of P(m) are integers.
OR
Let Q(m) be defined as in the first solution, and note that Q(m) is divisible by 8 if m is even. To treat odd m, write
Q(m)β=8m+4(m2βm)+2m2(m2β1)+m4(m4β1)=8m+4m(mβ1)+2m2(m+1)(mβ1)+m4(m2+1)(m+1)(mβ1)β
and note that because m+1,mβ1, and m2+1 are all even, each term has at least three factors of 2 . The solution concludes as above.
OR
Another way to see that Q(m) is divisible by 8 when m is odd in the second solution is to apply more general facts from number theory. Fermat's Little Theorem asserts that if p is prime, then apβ‘a (modp) for all integers a. In particular, m2β‘m(mod2). Euler's Totient Theorem asserts that if gcd(a,q)=1, then aΟ(q)β‘1(modq), where Ο(q) is the number of positive integers less than q that are relatively prime to q. Because Ο(4)=2, it follows that m2β‘1(mod4) when m is odd. Also, Ο(8)=4, so m4β‘1(mod8) if m is odd.
Note: Suppose that a necklace is to be made by placing n beads, equally spaced, on a circular ring. Each bead can be any one of m 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
n1βdβ£nββΟ(dnβ)md
He acknowledged its prior discovery by another soldier, Monsieur le Colonel Charles Paul Narcisse Moreau. Thus P(m) counts the number of necklaces with n=8 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