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:
“Love has its own instinct, finding the way to the heart, as the feeblest insect finds the way to its flower, with a will which nothing can dismay nor turn aside.”
—Honoré De Balzac (1799–1850)
“With two sons born eighteen months apart, I operated mainly on automatic pilot through the ceaseless activity of their early childhood. I remember opening the refrigerator late one night and finding a roll of aluminum foil next to a pair of small red tennies. Certain that I was responsible for the refrigerated shoes, I quickly closed the door and ran upstairs to make sure I had put the babies in their cribs instead of the linen closet.”
—Mary Kay Blakely (20th century)
“Coming out, all the way out, is offered more and more as the political solution to our oppression. The argument goes that, if people could see just how many of us there are, some in very important places, the negative stereotype would vanish overnight. ...It is far more realistic to suppose that, if the tenth of the population that is gay became visible tomorrow, the panic of the majority of people would inspire repressive legislation of a sort that would shock even the pessimists among us.”
—Jane Rule (b. 1931)
“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)
“‘Tis no extravagant arithmetic to say, that for every ten jokes,—thou hast got an hundred enemies; and till thou hast gone on, and raised a swarm of wasps about thine ears, and art half stung to death by them, thou wilt never be convinced it is so.”
—Laurence Sterne (1713–1768)