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:

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

    “Let us begin to understand the argument.
    There is a solution to everything: Science.”
    —Allen Tate (1899–1979)

    “When you realize how hard it is to know the truth about yourself, you understand that even the most exhaustive and well-meaning autobiography, determined to tell the truth, represents, at best, a guess. There have been times in my life when I felt incredibly happy. Life was full. I seemed productive. Then I thought,”Am I really happy or am I merely masking a deep depression with frantic activity?” If I don’t know such basic things about myself, who does?”
    —Phyllis Rose (b. 1942)

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