Problem:
Ms. Math's kindergarten class has 16 registered students. The classroom has a very large number, N, of play blocks which satisfies the conditions:
(a) If 16,15, or 14 students are present in the class, then in each case all the blocks can be distributed in equal numbers to each student, and
(b) There are three integers 0<x<y<z<14 such that when x,y, or z students are present and the blocks are distributed in equal numbers to each student, there are exactly three blocks left over.
Find the sum of the distinct prime divisors of the least possible value of N satisfying the above conditions.
Solution:
Because N is divisible by 16,15, and 14, it must be a multiple of lcm(14,15,16)=1680. Let N=1680m, for some positive integer m.
The number of students present must be a whole number no greater than 16. Of these, only 9,11, and 13 are not factors of 1680=24⋅31⋅51⋅71. Therefore x=9,y=11, and z=13. Note that 1680≡3(mod13). Because 1680 and 13 are relatively prime, 1680 m will have a remainder of 3 when divided by 13 if and only if m≡1(mod13). In turn, 1680≡8(mod11),11 and 1680 are relatively prime, and the least residues mod11 of the multiples of 1680 are 8,5,2,10,7,4,1,9,6,3, and 0, repeating. Therefore 1680m will have a remainder of 3 when divided by 11 if and only if m≡10(mod11). Lastly, 1680≡6(mod9), and the least residues mod9 of the multiples of 1680 are 6,3, and 0, repeating, so 1680m will have a remainder of 3 when divided by 9 if and only if m≡2 (mod3).
The Chinese Remainder Theorem shows that the three congruences above have a unique solution. To find it, let m=1+13i, for some nonnegative integer i. Then 13i+1≡10(mod11),13i≡9≡−13(mod11),i≡−1(mod11),i=−1+11j for some nonnegative integer j, and m=1+13(−1+11j)=−12+143j.
In turn, 143j−12≡2(mod3),143j≡14≡143(mod3),j≡1(mod3),j= 1+3k for some nonnegative integer k, and m=−12+143(1+3k)=131+429k.
Therefore N is of the form 1680(131+429k) for some nonnegative integer k, so the least possible value of N=1680⋅131=24⋅31⋅51⋅71⋅131. The requested sum is 2+3+5+7+131=148.
OR
Because 1680 m is congruent to 3mod9,mod11, and mod13, the product 9⋅11⋅13=1287 must divide 1680m−3 or, for some integer n,1680m=1287n+3 or 560m=429n+1. The Euclidean Algorithm can now be used to show m=131 and n=171, and the result follows as above.
The problems on this page are the property of the MAA's American Mathematics Competitions