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:
“Social and scientific progress are assured, sir, once our great system of postpossession payments is in operation, not the installment plan, no sir, but a system of small postpossession payments that clinch the investment. No possible rational human wish unfulfilled. A man with a salary of fifty dollars a week can start payments on a Rolls-Royce, the Waldorf-Astoria, or a troupe of trained seals if he so desires.”
—John Dos Passos (1896–1970)
“For the universe has three children, born at one time, which reappear, under different names, in every system of thought, whether they be called cause, operation, and effect; or, more poetically, Jove, Pluto, Neptune; or, theologically, the Father, the Spirit, and the Son; but which we will call here, the Knower, the Doer, and the Sayer. These stand respectively for the love of truth, for the love of good, and for the love of beauty.”
—Ralph Waldo Emerson (1803–1882)