Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

Problem

Find the least positive four-digit solution to the following system of congruences.
Solution
Divide the first congruence by 7, remembering to divide 14 by as well. We find that the first congruence is equivalent to . Subtracting 13 from both sides and multiplying both sides by 5 (which is the modular inverse of 2, modulo 9) gives for the second congruence. Finally, adding to both sides in the third congruence and multiplying by 17 (which is the modular inverse of 3, modulo 25) gives . So we want to solve Let's first find a simultaneous solution for the second and third congruences. We begin checking numbers which are 17 more than a multiple of 25, and we quickly find that 42 is congruent to 17 (mod 25) and 6 (mod 9). Since 42 does not satisfy the first congruence we look to the next solution . Now we have found a solution for the system, so we can appeal to the Chinese Remainder Theorem to conclude that the general solution of the system is , where 450 is obtained by taking the least common multiple of 2, 9, and 25. So the least four-digit solution is .
Final answer
1167