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 = 3
k + 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 = 7
l + 3. It then follows that
x = 3 (7
l + 3) + 1 = 21
l + 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 = 4
m. This yields
x = 21(4
m) + 10 = 84
m + 10, or
- x ≡ 10 (mod 84)
which describes all solutions to the system .
