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:

    It would be enough for me to have the system of a jury of twelve versus the system of one judge as a basis for preferring the U.S. to the Soviet Union.... I would prefer the country you can leave to the country you cannot.
    Joseph Brodsky (b. 1940)

    We are now going through a period of demolition. In morals, in social life, in politics, in medicine, and in religion there is a universal upturning of foundations. But the day of reconstruction seems to be looming, and now the grand question is: Are there any sure and universal principles that will evolve a harmonious system in which we shall all agree?
    Catherine E. Beecher (1800–1878)