System of congruences
We now focus on the solution of a system of conguences. We look for a simultaneous solution for all congruences in the system. Let
x ≡ 2 (mod 3);
x ≡ 3 (mod 5);
x ≡ 2 (mod 7).
The first congruence means x = 2, 5, 8, 11, 14, 17, 20, 23, 26, ..., are possible solutions; the second congruence yields x = 3, 8, 13, 18, 23, 28, 33, 38, ... ; and the third produces x = 2, 9, 16, 23, 30, 37, 44, ... . Since 23 appears on all three lists, x = 23 is the solution of the system. Moreover, if you were to extend each of these lists as far as 100, you would see that 23 is the only number that is common to all three lists, that is, 23 is the unique solution to this system of congruences modulo 105.
4.8.1 Lemma. Let m and n be relatively prime and a and b integers. There exists an integer x that satisfies the system of congruences
x ≡ a (mod m)
x ≡ b (mod n).
Furthermore, any two solutions x and y are congruent modulo mn.
Proof. Suppose (m, n) = 1. Let x be a solution to the first congruence in the system. Thus x = a + mk for some integer k, and this k must be such that
a + mk ≡ b (mod n)
or
mk ≡ b − a (mod n).
Since (m, n) = 1, (Proposition 4.6.4) guarantees the existence of such an integer k, and x = a + mk satisfies the system.
Uniqueness. Now let y be another solution to the system of congruences; that is,
y ≡ a (mod m)
y ≡ b (mod n).
Owning to transitivity of modulo operation
x ≡ y (mod m)
x ≡ y (mod n).
and
m| x − y and n | x − y
Then
mn | x−y
So x ≡ y (mod mn).□
4.8.2 Example Since (7, 5) = 1, we use Lemma 4.8.1 to solve the system of congruences
x≡ 5 (mod 7)
x ≡ 3 (mod 5).
From the first congruence we write x = 5 + 7k for some integer k and substitute this expression for x into the second congruence.
5 + 7k ≡ 3 (mod 5)
or
7k ≡ −2 (mod 5)
⇒ 2k ≡ −2 (mod 5)
⇒ k ≡ −1 (mod 5)
⇒ k ≡ 4 (mod 5).
since (2, 5) = 1 there exists such integer k
Thus x = 5+7(4+5j) ⟶ x = 33 + 35j ⟶ and x ≡ 33 (mod 7 ⋅ 5 = 35) gives all solutions to the system of congruences.
We now study how a system can be transformed into another.
Lemma 4.8.3. Let
a1x ≡ b1 mod n1
a2x ≡ b2 mod n2 (4.5)
...
asx ≡ b3 mod ns
with (ni,nj) = 1, for i ≠ j, will suppose also that (ni,nj) = 1, for i ≠ j in which every congruence admits solutions. This system can be equally represented (in the sense, they both admits the same solutions), as
x ≡ c1 mod n'1
x ≡ c2 mod n'2 (4.6)
...
x ≡ c3 mod ns
with (n'i,n'j) = 1, for i ≠ j.
Proof. System 4.5 is solvable if for every k = 1,...,s, dk = gcd(ak,nk)|bk (Proposition 4.6.4). In this case, it is possible to divide the k-th congruence by dk, obtaining the new system equivalent to the first
a'1x ≡ b'1 mod n'1
a'2x ≡ b'2 mod n'2 (4.5')
...
a'sx ≡ b'3 mod n's
where ak' = ak/dk, bk' = bk/dk and nk' = nk/dk and with the condition (n'i,n'j) = 1, for i ≠ j still holding. Now by noting that for each congruence of the system k = 1,...,s we have that (a'k,n'k) = 1, by Corollary 4.21 the system admits a unique solution ck modulo n'k. For this we can replace the system 4.5' with 4.6. Thus we proved that any system of the form 4.5 can be reduced to one of the form 4.5'. □
4.8.3 Example In systems such as x ≡ 1 mod 6, x ≡ 2 mod 3, even if each single congruence is solvable, the system has no solutions. Solving the first congruence gives x = 6k + 1 and substituting that into the second gives 6k + 1 ≡ 2 (mod 3) that is 6k ≡ 1 (mod 3) this system has no solutions, since 3 = gcd(3,6) does not divide 1.