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)
“Well, it is a good experience, to divest oneself of some tested ideals, some old standbys,
And even finding nothing to put in their place is a good experience,
Preparing one, as it does, for the consternation that is to come.”
—John Ashbery (b. 1927)
“All the followers of science are fully persuaded that the processes of investigation, if only pushed far enough, will give one certain solution to each question to which they can be applied.... This great law is embodied in the conception of truth and reality. The opinion which is fated to be ultimately agreed to by all who investigate is what we mean by the truth, and the object represented in this opinion is the real.”
—Charles Sanders Peirce (1839–1914)
“Insecurity, commonly regarded as a weakness in normal people, is the basic tool of the actor’s trade.”
—Miranda Richardson (b. 1958)
“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)