Encyclopedia > Linear congruence theorem

  Article Content

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
axb (mod n)      (1)
has a solution x if and only if gcd(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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
U.S. presidential election, 1804

... elections: 1792, 1796, 1800, 1804, 1808, 1812, 1816 Source: U.S. Office of the Federal R ...

 
 
 
This page was created in 35 ms