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:
“While the system of holding people in hostage is as old as the oldest war, a fresher note is introduced when a tyrannic state is at war with its own subjects and may hold any citizen in hostage with no law to restrain it.”
—Vladimir Nabokov (1899–1977)
“In a universe that is all gradations of matter, from gross to fine to finer, so that we end up with everything we are composed of in a lattice, a grid, a mesh, a mist, where particles or movements so small we cannot observe them are held in a strict and accurate web, that is nevertheless nonexistent to the eyes we use for ordinary living—in this system of fine and finer, where then is the substance of a thought?”
—Doris Lessing (b. 1919)