Linear Congruence Theorem - System of Linear Congruences

System of Linear Congruences

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.

Read more about this topic:  Linear Congruence Theorem

Famous quotes containing the words system of and/or system:

    Each generation’s job is to question what parents accept on faith, to explore possibilities, and adapt the last generation’s system of values for a new age.
    Frank Pittman (20th century)

    I confidently predict the collapse of capitalism and the beginning of history. Something will go wrong in the machinery that converts money into money, the banking system will collapse totally, and we will be left having to barter to stay alive. Those who can dig in their garden will have a better chance than the rest. I’ll be all right; I’ve got a few veg.
    Margaret Drabble (b. 1939)