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
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. Isnt this the only constructive perspective for women who have no choice but to work? And isnt 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)
“A man without a will thats strong wont find himself at peace for long.”
—Chinese proverb.
Rhyme.
“Let us begin to understand the argument.
There is a solution to everything: Science.”
—Allen Tate (18991979)