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)

    “The ex-Presidential situation has its advantages, but with them are certain drawbacks. The correspondence is large. The meritorious demands on one are large. More independent out than in place, but still something of the bondage of the place that was willingly left. On the whole, however, I find many reasons to be content.”
    —Rutherford Birchard Hayes (1822–1893)

    “To the questions of the officiously meddling police Falter replied absently and tersely; but, when he finally grew tired of this pestering, he pointed out that, having accidentally solved “the riddle of the universe,” he had yielded to artful exhortation and shared that solution with his inquisitive interlocutor, whereupon the latter had died of astonishment.”
    —Vladimir Nabokov (1899–1977)