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:

    “As a father I had some trouble finding the words to separate the person from the deed. Usually, when one of my sons broke the rules or a window, I was too angry to speak calmly and objectively. My own solution was to express my feelings, but in an exaggerated, humorous way: “You do that again and you will be grounded so long they will call you Rip Van Winkle II,” or “If I hear that word again, I’m going to braid your tongue.””
    —David Elkind (20th century)

    “Primitive peoples tried to annul death by portraying the human body—we do it by finding substitutes for the human body. Technology instead of mysticism!”
    —Max Frisch (1911–1991)

    “Any solution to a problem changes the problem.”
    —R.W. (Richard William)

    “Our basic ideas about how to parent are encrusted with deeply felt emotions and many myths. One of the myths of parenting is that it is always fun and games, joy and delight. Everyone who has been a parent will testify that it is also anxiety, strife, frustration, and even hostility. Thus most major parenting- education formats deal with parental emotions and attitudes and, to a greater or lesser extent, advocate that the emotional component is more important than the knowledge.”
    —Bettye M. Caldwell (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)