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:

    “Work is a responsibility most adults assume, a burden at times, a complication, but also a challenge that, like children, requires enormous energy and that holds the potential for qualitative, as well as quantitative, rewards. Isn’t this the only constructive perspective for women who have no choice but to work? And isn’t it a more healthy attitude for women writhing with guilt because they choose to compound the challenges of motherhood with work they enjoy?”
    —Melinda M. Marshall (20th century)

    “Is not disease the rule of existence? There is not a lily pad floating on the river but has been riddled by insects. Almost every shrub and tree has its gall, oftentimes esteemed its chief ornament and hardly to be distinguished from the fruit. If misery loves company, misery has company enough. Now, at midsummer, find me a perfect leaf or fruit.”
    —Henry David Thoreau (1817–1862)

    “All the followers of science are fully persuaded that the processes of investigation, if only pushed far enough, will give one certain solution to each question to which they can be applied.... This great law is embodied in the conception of truth and reality. The opinion which is fated to be ultimately agreed to by all who investigate is what we mean by the truth, and the object represented in this opinion is the real.”
    —Charles Sanders Peirce (1839–1914)