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

    “What Romantic terminology called genius or talent or inspiration is nothing other than finding the right road empirically, following one’s nose, taking shortcuts.”
    —Italo Calvino (1923–1985)

    “One of the many reasons for the bewildering and tragic character of human existence is the fact that social organization is at once necessary and fatal. Men are forever creating such organizations for their own convenience and forever finding themselves the victims of their home-made monsters.”
    —Aldous Huxley (1894–1963)

    “Give a scientist a problem and he will probably provide a solution; historians and sociologists, by contrast, can offer only opinions. Ask a dozen chemists the composition of an organic compound such as methane, and within a short time all twelve will have come up with the same solution of CH4. Ask, however, a dozen economists or sociologists to provide policies to reduce unemployment or the level of crime and twelve widely differing opinions are likely to be offered.”
    —Derek Gjertsen, British scientist, author. Science and Philosophy: Past and Present, ch. 3, Penguin (1989)

    “Mental health depends upon the maintenance of a balance within the personality between the basic human urges and egocentric wishes on the one hand and the demands of conscience and society on the other hand.”
    —Selma H. Fraiberg (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)