The Chinese remainder theorem

The tools are Bezout’s identity and Euclid’s lemma from Bezout's identity and the extended Euclidean algorithm, and Theorems 5 and 6 of Modular inverses and linear congruences on solving ax \equiv c \pmod{n}. Each proof builds a solution (Existence proof), then shows any two solutions agree.

Lemma. If \gcd(m, n) = 1, m \mid c and n \mid c, then mn \mid c.

Proof. Bezout gives integers u, v with mu + nv = 1, so c = cmu + cnv. Write c = ns and c = mt. Then cmu = mn(su) and cnv = mn(tv), so mn divides both terms and their sum. \square

Proof of Theorem 1. Every x = a + mk with k \in \mathbb{Z} satisfies the first congruence, and every solution of it has this form. Such an x satisfies the second exactly when mk \equiv b - a \pmod{n}. Since \gcd(m, n) = 1, this has the solution k \equiv m^{-1}(b - a), so x = a + mk solves both. If x and x' are solutions, then x \equiv a \equiv x' \pmod{m} and x \equiv b \equiv x' \pmod{n}, so m and n divide x - x', and by the lemma mn \mid x - x'. Conversely, if x' = x + mnt, then x' \equiv x modulo m and modulo n, so x' is a solution. \square

Proof of Theorem 2. Suppose \gcd(M_i, m_i) > 1; then some prime p divides m_i and M_i. Since M_i is the product of the m_j with j \ne i, Euclid’s lemma gives p \mid m_j for one such j, and then p \mid \gcd(m_i, m_j) = 1, which is impossible. So y_i exists.

Fix i. For j \ne i, the factor m_i appears in M_j, so a_j M_j y_j \equiv 0 \pmod{m_i}, while a_i M_i y_i \equiv a_i \cdot 1 \pmod{m_i}. Adding, x_0 \equiv a_i \pmod{m_i}.

If x and x' are solutions, every m_i divides c = x - x'. By the lemma m_1 m_2 \mid c. The prime argument above shows \gcd(m_1 m_2, m_3) = 1, so the lemma again gives m_1 m_2 m_3 \mid c, and continuing through m_k, M \mid c. As before, anything congruent to x_0 modulo M is congruent to it modulo each m_i, so it is a solution. \square

Proof of Theorem 3. As in Theorem 1, the solutions are the x = a + mk with mk \equiv b - a \pmod{n}. By Theorem 6 of Modular inverses and linear congruences, this congruence in k has a solution if and only if \gcd(m, n) \mid b - a, which is the same as d \mid a - b.

For uniqueness, first: every common multiple c of m and n is a multiple of L. Divide, c = qL + r with 0 \le r < L. Then r = c - qL is a common multiple of m and n, and it is smaller than the least positive one, so r = 0. Now if x and x' are solutions, x - x' is a common multiple, so L \mid x - x'. Conversely x + Lt is a solution because m \mid L and n \mid L. \square

When d = 1 the lemma shows mn \mid L, and mn is itself a common multiple, so L = mn: Theorem 3 contains Theorem 1.

Proof of Theorem 4. \varphi(x) = (a, b) says exactly that x solves x \equiv a \pmod{m}, x \equiv b \pmod{n}. By Theorem 1 the solutions form one class modulo mn, with exactly one member among 0, \dots, mn - 1. So each pair has exactly one preimage. For the arithmetic: since m \mid mn, reducing x + y modulo mn first does not change its remainder modulo m; and by the addition rule of Congruence modulo n and its arithmetic, x + y \equiv (x \bmod m) + (y \bmod m) \pmod{m}. The same holds modulo n, and for products by the multiplication rule. \square

1. x \equiv 83 \pmod{88}. x = 3 + 8k gives 8k \equiv 3 \pmod{11}; 8 \cdot 7 = 56 \equiv 1, so k \equiv 21 \equiv 10 and x = 83. Check: 83 = 10 \cdot 8 + 3 = 7 \cdot 11 + 6.
2. x \equiv 46 \pmod{84}. x = 4 + 7k gives 7k \equiv 6 \pmod{12}; 7 \cdot 7 = 49 \equiv 1, so k \equiv 42 \equiv 6 and x = 46. Check: 46 = 6 \cdot 7 + 4 = 3 \cdot 12 + 10.
3. x \equiv 111 \pmod{140}. M_1 = 35 \equiv 3 \pmod{4}, y_1 = 3; M_2 = 28 \equiv 3 \pmod{5}, y_2 = 2; M_3 = 20 \equiv 6 \pmod{7}, y_3 = 6. Then x_0 = 3 \cdot 35 \cdot 3 + 28 \cdot 2 + 6 \cdot 20 \cdot 6, which is 315 + 56 + 720 = 1{,}091, and 1{,}091 = 7 \cdot 140 + 111.
4. x \equiv 119 \pmod{390}. The first two say x \equiv -1 modulo 6 and 5, so x \equiv -1 \equiv 29 \pmod{30} by Theorem 1. Then 29 + 30j \equiv 2 \pmod{13} gives 3 + 4j \equiv 2, 4j \equiv 12, j \equiv 3, and x = 119. Check: 119 = 9 \cdot 13 + 2.
5. e_1 = 10, e_2 = 81, x \equiv 34 \pmod{90}. 10 \equiv 1 \pmod{9}, and 81 = 9^2 ends in 1. Then x = 7e_1 + 4e_2 = 394, and 394 \equiv 34 \pmod{90}.
6. Days 76, 202, 328, \dots, every 126 days. x \equiv 6 \pmod{14}, x \equiv 4 \pmod{9}: x = 4 + 9k, 9k \equiv 2 \pmod{14}, 9 \cdot 11 = 99 \equiv 1, so k \equiv 22 \equiv 8 and x = 76 = 5 \cdot 14 + 6.
7. Day 235, then every 840 days. Both come on days x \equiv 115 \pmod{120}; Saturday is x \equiv 4 \pmod{7}. With x = 115 + 120j and 115 \equiv 3, 120 \equiv 1 \pmod{7}: 3 + j \equiv 4, j \equiv 1, x = 235 = 33 \cdot 7 + 4. Since \gcd(120, 7) = 1, the period is 840.
8. x \equiv a \pmod{mn}. The integer a is a solution, and by Theorem 1 the solutions are exactly the integers congruent to one solution modulo mn.
9. Proof. By Theorem 1 the solutions are one class modulo mn. Two of c, c + 1, \dots, c + mn - 1 differ by less than mn, so at most one lies in the class; and their remainders modulo mn are all mn remainders, so one does. \square
10. Reduced modulo 5, the second gives x \equiv 3 and the third x \equiv 4. Theorem 2 needs the moduli pairwise coprime, and \gcd(10, 15) = 5 (also \gcd(6, 10) = 2, \gcd(6, 15) = 3), though no prime divides all three.
11. Proof. Since nv = 1 - mu \equiv 1 \pmod{m} and bmu \equiv 0 \pmod{m}, x \equiv a \cdot 1 + 0 = a \pmod{m}. Likewise mu = 1 - nv \equiv 1 \pmod{n} and anv \equiv 0 \pmod{n}, so x \equiv b \pmod{n}. \square
12. x \equiv 21 \pmod{24}. d = 4 \mid 5 - 9. x = 5 + 8k: 8k \equiv 4 \pmod{12}, so 2k \equiv 1 \pmod{3}, k \equiv 2, x = 21. Check: 21 = 2 \cdot 8 + 5 = 12 + 9.
13. First, \gcd(8, 12) = 4 and 4 \nmid 5 - 11 = -6, so Theorem 3 gives none. Second, directly: x \equiv 5 \pmod{8} gives x \equiv 1 \pmod{4}, and x \equiv 11 \pmod{12} gives x \equiv 3 \pmod{4}.
14. x \equiv 67 \pmod{90}. d = 2 \mid 7 - 13, L = 90. x = 7 + 10k: 10k \equiv 6 \pmod{18}, so 5k \equiv 3 \pmod{9}; 5 \cdot 2 = 10 \equiv 1, so k \equiv 6 and x = 67 = 3 \cdot 18 + 13.
15. b = 1, 4, 7, 10, 13, 16, 19; for b = 10, x \equiv 94 \pmod{105}. \gcd(15, 21) = 3 must divide 4 - b, so b \equiv 1 \pmod{3}. For b = 10: x = 4 + 15k, 15k \equiv 6 \pmod{21}, 5k \equiv 2 \pmod{7}, k \equiv 3 \cdot 2 = 6, x = 94 = 4 \cdot 21 + 10.
16. \varphi(7) = (3, 2), \varphi(13) = (1, 3); (3, 0) comes from 15 and (2, 4) from 14. Among the multiples of 5 below 20, only 15 \equiv 3 \pmod{4}; among 4, 9, 14, 19, only 14 \equiv 2 \pmod{4}.
17. 76. Modulo 7: 58 \equiv 2, 73 \equiv 3, product \equiv 6 \equiv -1. Modulo 11: 58 \equiv 3, 73 \equiv 7, product 21 \equiv 10 \equiv -1. So the product is \equiv -1 \equiv 76 \pmod{77}. Check: 58 \cdot 73 = 4{,}234 = 55 \cdot 77 - 1.
18. x = 0, 1, 6, 10, 15, 16, 21, 25. Since 30 = 2 \cdot 3 \cdot 5, the condition holds modulo 30 exactly when it holds modulo each prime, and p \mid x(x - 1) means x \equiv 0 or 1 \pmod{p}. The 2^3 = 8 choices give one x each by Theorem 2; for example (0, 0, 1) gives 6 and (1, 0, 0) gives 15.
19. Days 29, 65, 101, \dots, every 36 days; with day 8, never. x \equiv 5 \pmod{12}, x \equiv 11 \pmod{18}: d = 6 \mid -6, and x = 5 + 12k, 12k \equiv 6 \pmod{18}, 2k \equiv 1 \pmod{3}, k \equiv 2, x = 29 = 18 + 11. With x \equiv 8 \pmod{18}, 6 \nmid 5 - 8 = -3.
20. Proof. Let c = mn/d = m \cdot \tfrac{n}{d} = n \cdot \tfrac{m}{d}. It is a common multiple of m and n, and 0 < c < mn since d > 1. So \varphi(c) = (0, 0) = \varphi(0) with c \ne 0 in \mathbb{Z}_{mn}, and \varphi is not one-to-one. Both sets have mn elements, so the image of \varphi has fewer than mn elements, and some pair is missed. \square
21. Proof. By Theorem 1 of Modular inverses and linear congruences, x is a unit modulo k exactly when \gcd(x, k) = 1. If a prime divides x and mn, Euclid’s lemma puts it in m or n; conversely a prime dividing x and m (or n) divides mn. So \gcd(x, mn) = 1 if and only if \gcd(x, m) = 1 and \gcd(x, n) = 1. \square Modulo 5 there are 4 units and modulo 7 there are 6; by Theorem 4 the units modulo 35 correspond to pairs, so there are 4 \cdot 6 = 24.
22. After t steps the walk is at \varphi(t) = (t \bmod m, t \bmod n). It is first back at (0, 0) when m \mid t and n \mid t, at t = \operatorname{lcm}(m, n), and before that no cell repeats, since a repeat at steps s < t would put (0, 0) at step t - s. For 3 and 4 the lcm is 12, every cell; for 4 and 6 it is 12 of the 24.