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:
“A child is born with the potential ability to learn Chinese or Swahili, play a kazoo, climb a tree, make a strudel or a birdhouse, take pleasure in finding the coordinates of a star. Genetic inheritance determines a child’s abilities and weaknesses. But those who raise a child call forth from that matrix the traits and talents they consider important.”
—Emilie Buchwald (20th century)
“Disillusionment in living is finding that no one can really ever be agreeing with you completely in anything.”
—Gertrude Stein (1874–1946)
“There is a lot of talk now about metal detectors and gun control. Both are good things. But they are no more a solution than forks and spoons are a solution to world hunger.”
—Anna Quindlen (b. 1953)
“Justice begins with the recognition of the necessity of sharing. The oldest law is that which regulates it, and this is still the most important law today and, as such, has remained the basic concern of all movements which have at heart the community of human activities and of human existence in general.”
—Elias Canetti (b. 1905)
“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)