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:

    “Friendship among nations, as among individuals, calls for constructive efforts to muster the forces of humanity in order that an atmosphere of close understanding and cooperation may be cultivated.”
    —Franklin D. Roosevelt (1882–1945)

    “Our ability to fall in love requires enough comfort with our masculinity to join it with someone’s femininity and feel enhanced. . . . If our mother made us feel secure and proud in our masculinity, then we want to find that again in our wife. If we are really comfortable with our mother, we can even marry a woman who is a friend rather than an adversary, and form a true partnership.”
    —Frank Pittman (20th century)

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