Linear congruence theorem
|
|
In modular arithmetic, the question of when a linear congruence can be solved is answered by the linear congruence theorem. If a and b are any integers and n is a positive integer, then the congruence
- ax ≡ b (mod n) (1)
has a solution x if and only if greatest common divisor (a, n) divides b.
For example, there is no integer x with
- 4x ≡ 3 (mod 6)
but there exists an integer x with
- 4x ≡ 2 (mod 6).
If the greatest common divisor d = gcd(a, n) divides b, then we can find a solution x to the congruence (1) as follows: the extended Euclidean algorithm yields integers r and s such ra + sn = d. Then x = rb/d is a solution. The other solutions are the numbers congruent to x modulo n/d.
For example, the congruence
- 12x ≡ 20 (mod 28)
has a solution since gcd(12, 28) = 4 divides 20. The extended Euclidean algorithm gives (-2)*12 + 1*28 = 4, i.e. r = -2 and s = 1. Therefore, our solution is x = -2*20/4 = -10. All other solutions are congruent to -10 modulo 7, and so they are all congruent to 4 modulo 7.
By repeatedly using the linear congruence theorem, one can also solve systems of linear congruences, as in the following example: find all numbers x such that
- 2x ≡ 2 (mod 6)
- 3x ≡ 2 (mod 7)
- 2x ≡ 4 (mod 8)
By solving the first congruence using the method explained above, we find x ≡ 1 (mod 3), which can also be written as x = 3k + 1. Substituting this into the second congruence and simplifying, we get
- 9k ≡ −1 (mod 7)
Solving this congruence yields k ≡ 3 (mod 7), or k = 7l + 3. It then follows that x = 3 (7l + 3) + 1 = 21l + 10. Substituting this into the third congruence and simplifying, we get
- 42l ≡ −16 (mod 8)
which has the solution l ≡ 0 (mod 4), or l = 4m. This yields x = 21(4m) + 10 = 84m + 10, or
- x ≡ 10 (mod 84)
which describes all solutions to the system.
See also Chinese remainder theorem.