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)
“Few white citizens are acquainted with blacks other than those projected by the media and the so—called educational system, which is nothing more than a system of rewards and punishments based upon one’s ability to pledge loyalty oaths to Anglo culture. The media and the “educational system” are the prime sources of racism in the United States.”
—Ishmael Reed (b. 1938)