The Mysterious Remainder
A number N leaves a remainder of 5 when divided by 7, a remainder of 3 when divided by 5, and a remainder of 2 when divided by 3. A student claims that the smallest positive integer satisfying these conditions is 68. However, another student argues that there are infinitely many such numbers and that the smallest positive one is actually less than 68. The teacher asks you to analyze the situation and determine the correct smallest positive integer, and to explain the pattern of all solutions.
1. Find the smallest positive integer N that satisfies the given system of congruences. Show your method clearly.
Read the worked answer
We need to solve the system: [ \begin{cases} N \equiv 5 \pmod{7} \ N \equiv 3 \pmod{5} \ N \equiv 2 \pmod{3} \end{cases} ] We can solve step by step. First, combine the first two congruences. Let (N = 7k + 5). Then (7k + 5 \equiv 3 \pmod{5}), so (7k \equiv -2 \equiv 3 \pmod{5}). Since (7 \equiv 2 \pmod{5}), we have (2k \equiv 3 \pmod{5}). Multiply both sides by 3 (the inverse of 2 mod 5): (k \equiv 9 \equiv 4 \pmod{5}). So (k = 5m + 4). Then (N = 7(5m+4) + 5 = 35m + 33). So (N \equiv 33 \pmod{35}).
Now combine with the third congruence: (N \equiv 2 \pmod{3}). We have (N = 35m + 33). Modulo 3: (35 \equiv 2), (33 \equiv 0), so (2m \equiv 2 \pmod{3}), hence (m \equiv 1 \pmod{3}). Thus (m = 3t + 1). Then (N = 35(3t+1) + 33 = 105t + 68). So the general solution is (N \equiv 68 \pmod{105}). The smallest positive integer is 68.
Therefore, the first student is correct: the smallest positive integer is 68. The second student is incorrect about the smallest being less than 68.
2. Explain why the solutions form an arithmetic progression and find the 5th smallest positive integer solution.
Read the worked answer
From the solution above, all integers satisfying the system are of the form (N = 68 + 105t) for integer (t). This is an arithmetic progression with common difference 105 (the least common multiple of 7, 5, and 3). The positive solutions occur when (t \ge 0) (since for (t = -1), (N = -37) is negative). Thus the positive solutions are (68, 173, 278, 383, 488, \ldots). The 5th smallest positive integer is (68 + 4 \cdot 105 = 68 + 420 = 488).
In general, the Chinese Remainder Theorem guarantees a unique solution modulo the product of the moduli when they are pairwise coprime, which they are here (7, 5, 3). Hence the solutions form an arithmetic progression with difference equal to the product 105.