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)
“[Madness] is the jail we could all end up in. And we know it. And watch our step. For a lifetime. We behave. A fantastic and entire system of social control, by the threat of example as effective over the general population as detention centers in dictatorships, the image of the madhouse floats through every mind for the course of its lifetime.”
—Kate Millett (b. 1934)