Problem:
Ethan writes down five congruences:
xβ‘0(mod2),xβ‘0(mod3),xβ‘1(mod4),xβ‘5(mod6),xβ‘7(mod12).
How many positive integers less than or equal to 2026 satisfy at least one of these five congruences?
Answer Choices:
A. 1688
B. 1856
C. 1857
D. 2025
E. 2026
Solution:
All five moduli divide 12, so whether x satisfies each congruence depends only on xmod12. We list the residues mod 12 covered by each congruence:
xβ‘0(mod2)xβ‘0(mod3)xβ‘1(mod4)xβ‘5(mod6)xβ‘7(mod12)β:0, 2, 4, 6, 8, 10:0, 3, 6, 9:1, 5, 9:5, 11:7β
Together these cover
0,1,2,3,4,5,6,7,8,9,10,11,
which is every residue mod 12. So every integer satisfies at least one of the congruences, and the answer is all (E) 2026 positive integers up to 2026.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions