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:
“What affects men sharply about a foreign nation is not so much finding or not finding familiar things; it is rather not finding them in the familiar place.”
—Gilbert Keith Chesterton (1874–1936)
“The great problem of American life [is] the riddle of authority: the difficulty of finding a way, within a liberal and individualistic social order, of living in harmonious and consecrated submission to something larger than oneself.... A yearning for self-transcendence and submission to authority [is] as deeply rooted as the lure of individual liberation.”
—Wilfred M. McClay, educator, author. The Masterless: Self and Society in Modern America, p. 4, University of North Carolina Press (1994)
“What is history? Its beginning is that of the centuries of systematic work devoted to the solution of the enigma of death, so that death itself may eventually be overcome. That is why people write symphonies, and why they discover mathematical infinity and electromagnetic waves.”
—Boris Pasternak (1890–1960)
“The “universal moments” of child rearing are in fact nothing less than a confrontation with the most basic problems of living in society: a facing through one’s children of all the conflicts inherent in human relationships, a clarification of issues that were unresolved in one’s own growing up. The experience of child rearing not only can strengthen one as an individual but also presents the opportunity to shape human relationships of the future.”
—Elaine Heffner (20th century)
“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)