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:

    “It makes little sense to spend a month teaching decimal fractions to fourth-grade pupils when they can be taught in a week, and better understood and retained, by sixth-grade students. Child-centeredness does not mean lack of rigor or standards; it does mean finding the best match between curricula and children’s developing interests and abilities.”
    —David Elkind (20th century)

    “To have no son, no wife,
    No house or land still seemed quite natural.
    Only a numbness registered the shock
    Of finding out how much had gone of life,
    How widely from the others.”
    —Philip Larkin (1922–1986)

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

    “The basic idea which runs right through modern history and modern liberalism is that the public has got to be marginalized. The general public are viewed as no more than ignorant and meddlesome outsiders, a bewildered herd.”
    —Noam Chomsky (b. 1928)

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