# 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 .