Chinese Remainder Theorem - Finding The Solution With Basic Algebra and Modular Arithmetic

Finding The Solution With Basic Algebra and Modular Arithmetic

For example, consider the problem of finding an integer x such that

\begin{align} x &\equiv 2 \pmod{3}\\ x &\equiv 3 \pmod{4}\\ x &\equiv 1 \pmod{5}. \end{align}

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, solution, basic, algebra and/or arithmetic:

    “One way to think about play, is as the process of finding new combinations for known things—combinations that may yield new forms of expression, new inventions, new discoveries, and new solutions....It’s exactly what children’s play seems to be about and explains why so many people have come to think that children’s play is so important a part of childhood—and beyond.”
    —Fred Rogers (20th century)

    “To the questions of the officiously meddling police Falter replied absently and tersely; but, when he finally grew tired of this pestering, he pointed out that, having accidentally solved “the riddle of the universe,” he had yielded to artful exhortation and shared that solution with his inquisitive interlocutor, whereupon the latter had died of astonishment.”
    —Vladimir Nabokov (1899–1977)

    “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)