Finding The Solution With Basic Algebra and Modular Arithmetic
For example, consider the problem of finding an integer x such that
A brute-force approach converts these congruences into sets and writes the elements out to the product of 3×4×5 = 60 (the solutions modulo 60 for each congruence):
- x ∈ {2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, …}
- x ∈ {3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, …}
- x ∈ {1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56, …}.
To find an x that satisfies all three congruences, intersect the three sets to get:
- x ∈ {11, …}.
Which can be expressed as
Another way to find a solution is with basic algebra, modular arithmetic, and stepwise substitution.
We start by translating these equivalences into equations for some t, s, and u:
- Equation 1: x = 2 + 3 × t (mod 3)
- Equation 2: x = 3 + 4 × s (mod 4)
- Equation 3: x = 1 + 5 × u (mod 5).
Start by substituting the x from equation 1 into equivalence 2: 2 + 3 × t = 3 (mod 4), hence 3 × t = 1 (mod 4), or t = (1/3) (mod 4) = 3 (mod 4), meaning that t = 3 + 4 × s for integer s.
Plug t into equation 1: x = 2 + 3 × t (mod 3) = 2 + 3 × (3 + 4 × s) (mod 3) = 11 + 12 × s (mod 3).
Plug this x into equivalence 3: 11 + 12 × s = 1 (mod 5). Casting out 5s, we get 1 + 2 × s = 1 (mod 5), or 2 × s = 0 (mod 5), meaning that s = 0 + 5 × u for integer u.
Finally, x = 11 + 12 × s = 11 + 12 × (5 × u) = 11 + (60 × u). Since 60 = lcm(3, 4, 5), we have solutions 11, 71, 131, 191, …
Read more about this topic: Chinese Remainder Theorem
Famous quotes containing the words finding the, finding, solution, basic, algebra and/or arithmetic:
“One of the many reasons for the bewildering and tragic character of human existence is the fact that social organization is at once necessary and fatal. Men are forever creating such organizations for their own convenience and forever finding themselves the victims of their home-made monsters.”
—Aldous Huxley (1894–1963)
“As one delves deeper and deeper into Etiquette, disquieting thoughts come. That old Is- It-Worth-It Blues starts up again softly, perhaps, but plainly. Those who have mastered etiquette, who are entirely, impeccably right, would seem to arrive at a point of exquisite dullness. The letters and the conversations of the correct, as quoted by Mrs. Post, seem scarcely worth the striving for. The rules for finding topics of conversation fall damply on the spirit.”
—Dorothy Parker (1893–1967)
“Who shall forbid a wise skepticism, seeing that there is no practical question on which any thing more than an approximate solution can be had? Is not marriage an open question, when it is alleged, from the beginning of the world, that such as are in the institution wish to get out, and such as are out wish to get in?”
—Ralph Waldo Emerson (1803–1882)
“The basic essential of a great actor is that he loves himself in acting.”
—Charlie Chaplin (1889–1977)
“Poetry has become the higher algebra of metaphors.”
—José Ortega Y Gasset (1883–1955)
“Under the dominion of an idea, which possesses the minds of multitudes, as civil freedom, or the religious sentiment, the power of persons are no longer subjects of calculation. A nation of men unanimously bent on freedom, or conquest, can easily confound the arithmetic of statists, and achieve extravagant actions, out of all proportion to their means; as, the Greeks, the Saracens, the Swiss, the Americans, and the French have done.”
—Ralph Waldo Emerson (1803–1882)