Problem:
One of the following numbers is not divisible by any prime number less than 10 . Which is it?
Answer Choices:
A. 2606−1
B. 2606+1
C. 2607−1
D. 2607+1
E. 2607+3607
Solution:
Recall that if n is an integer greater than 1 , then an−bn factors as
(a−b)(an−1+an−2b1+an−3b2+⋯+a1bn−2+bn−1)(*)
and, furthermore, if n is odd, then an+bn factors as
(a+b)(an−1−an−2b1+an−3b2−⋯−a1bn−2+bn−1).
For (A), observe that 2606−1=(23)202−(13)202, so 2606−1 is divisible by 7=23−1 by (*). For (E), it follows from (†) that 2607+3607 is divisible by 5 . For (B), because the units digits of successive powers of 2 cycle in groups of 4 , the units digit of 2606 is 4 . Therefore 2606+1 is divisible by 5 . For (D), note that because 26≡1(mod3), it follows that 2606=(26)101≡1101≡1 (mod3). Therefore 2607+1≡2⋅1+1≡0(mod3), so 2607+1 is divisible by 3 .
Because it is given that one of the answer choices is not divisible by any prime number less than 10 , the correct choice must be (C). It can be verified, using the methods discussed above, that none of 2,3,5, or 7 divides (C)2607−1.
Note: In fact, 2607−1 is the 14th Mersenne prime, proven to be prime in 1952.
The problems on this page are the property of the MAA's American Mathematics Competitions