Chinese Remainder Theorem - A Constructive Algorithm To Find The Solution

A Constructive Algorithm To Find The Solution

The following algorithm only applies if the 's are pairwise coprime. (For simultaneous congruences when the moduli are not pairwise coprime, the method of successive substitution can often yield solutions.)

Suppose, as above, that a solution is required for the system of congruences:

Again, to begin, the product is defined. Then a solution x can be found as follows.

For each i the integers and are coprime. Using the extended Euclidean algorithm we can find integers and such that . Then, choosing the label, the above expression becomes:

Consider . The above equation guarantees that its remainder, when divided by, must be 1. On the other hand, since it is formed as, the presence of N guarantees a remainder of zero when divided by any when .

Because of this, and the multiplication rules allowed in congruences, one solution to the system of simultaneous congruences is:

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}

Using the extended Euclidean algorithm, for x modulo 3 and 20, we find (−13) × 3 + 2 × 20 = 1, i.e. e1 = 40. For x modulo 4 and 15, we get (−11) × 4 + 3 × 15 = 1, i.e. e2 = 45. Finally, for x modulo 5 and 12, we get 5 × 5 + (−2) × 12 = 1, i.e. e3 = −24. A solution x is therefore 2 × 40 + 3 × 45 + 1 × (−24) = 191. All other solutions are congruent to 191 modulo 60, which means they are all congruent to 11 modulo 60.

Note: There are multiple implementations of the extended Euclidean algorithm which will yield different sets of, and . These sets however will produce the same solution; i.e., (−20)2 + (−15)3 + (−24)1 = −109 = 11 modulo 60.

Read more about this topic:  Chinese Remainder Theorem

Famous quotes containing the words constructive, find and/or solution:

    “Euphemisms are not, as many young people think, useless verbiage for that which can and should be said bluntly; they are like secret agents on a delicate mission, they must airily pass by a stinking mess with barely so much as a nod of the head, make their point of constructive criticism and continue on in calm forbearance. Euphemisms are unpleasant truths wearing diplomatic cologne.”
    —Quentin Crisp (b. 1908)

    “Hast ever ben in Omaha
    Where rolls the dark Missouri down,
    Where four strong horses scarce can draw
    An empty wagon through the town?
    Where sand is blown from every mound
    To fill your eyes and ears and throat;
    Where all the steamboats are aground,
    And all the houses are afloat?...
    If not, take heed to what I say,
    You’ll find it just as I have found it;
    And if it lies upon your way
    For God’s sake, reader, go around it!”
    —For the State of Nebraska, U.S. public relief program (1935-1943)

    “The truth of the thoughts that are here set forth seems to me unassailable and definitive. I therefore believe myself to have found, on all essential points, the final solution of the problems. And if I am not mistaken in this belief, then the second thing in which the value of this work consists is that it shows how little is achieved when these problems are solved.”
    —Ludwig Wittgenstein (1889–1951)