中國剩餘的定理,,,,( 進階 )

Theorem statement
The original form of the theorem, contained in a third-century CE book by Chinese mathematician Sun Tzu and later republished in a 1247 book by Qin Jiushao, is a statement about simultaneous congruences (see modular arithmetic).
Suppose n1, n2, …, nk are integers which are pairwise coprime. Then, for any given integers a1,a2, …, ak, there exists an integer x solving the system of simultaneous congruences


圖片參考：http://upload.wikimedia.org/math/0/f/e/0fe8715d60ea676adcc593561ec34b99.png


圖片參考：http://upload.wikimedia.org/math/d/f/a/dfa2b960d974e1157af884f484c3c61c.png


圖片參考：http://upload.wikimedia.org/math/0/e/1/0e1a153dd47110c604ec2df04d2eb774.png


圖片參考：http://upload.wikimedia.org/math/8/9/0/8903a25dd74613cf96b756e86a567f11.png

Furthermore, all solutions x to this system are congruent modulo the product N = n1n2…nk.
Sometimes, the simultaneous congruences can be solved even if the nis are not pairwise coprime. A solution x exists if and only if:


圖片參考：http://upload.wikimedia.org/math/8/2/c/82c836223302ea999989259adf4cfc41.png

All solutions x are then congruent modulo the least common multiple of the ni.
Versions of the Chinese remainder theorem were also known to Brahmagupta, and appear in Fibonacci's Liber Abaci (1202).

[edit] A constructive algorithm to find the solution
This algorithm only treats the situations where the ni's are coprime. The method of successive substitution can often yield solutions to simultaneous congruences, even when the moduli are not pairwise coprime.
Suppose, as above, that a solution is needed to the system of congruences:


圖片參考：http://upload.wikimedia.org/math/a/5/d/a5dee55ec39dbe7d4d27a3fcb9b7991a.png

Again, to begin, the product N = n1n2…nk is defined. Then a solution x can be found as follows.
For each i the integers ni and N/ni are coprime. Using the extended Euclidean algorithm we can therefore find integers ri and si such that ri ni + si N/ni = 1. Then, choosing the label ei = si N/ni, the above expression becomes:


圖片參考：http://upload.wikimedia.org/math/e/d/8/ed849a11aa3063572b33504a7891fce0.png

Consider ei. The above equation guarantees that its remainder, when divided by ni, must be 1. On the other hand, since it is formed as si N/ni, the presence of N guarantees that it's evenly divisible by any nj so long as j ≠ i.


圖片參考：http://upload.wikimedia.org/math/9/f/7/9f75407c9bf00ff00be37507d73ab745.png

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


圖片參考：http://upload.wikimedia.org/math/b/c/e/bce6fbc96b2941a0749e341a6e1040a1.png

For example, consider the problem of finding an integer x such that


圖片參考：http://upload.wikimedia.org/math/1/3/9/139ebbb04538bf66cc09ae13cd719ab8.png


圖片參考：http://upload.wikimedia.org/math/b/3/c/b3c58532d18b8c1270eb4cdcb4e847c5.png


圖片參考：http://upload.wikimedia.org/math/9/9/4/994b801a574b0426e93ff5314c613247.png

Using the extended Euclidean algorithm for 3 and 4×5 = 20, we find (−13) × 3 + 2 × 20 = 1, i.e. e1 = 40. Using the Euclidean algorithm for 4 and 3×5 = 15, we get (−11) × 4 + 3 × 15 = 1. Hence, e2 = 45. Finally, using the Euclidean algorithm for 5 and 3×4 = 12, we get 5 × 5 + (−2) × 12 = 1, meaning 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 that they are all congruent to 11 modulo 60.
NOTE: There are multiple implementations of the extended Euclidean algorithm which will yield different sets of e1, e2, and e3. These sets however will produce the same solution i.e. 11 modulo 60.

[edit] Statement for principal ideal domains
For a principal ideal domain R the Chinese remainder theorem takes the following form: If u1, ..., uk are elements of R which are pairwise coprime, and u denotes the product u1...uk, then the quotient ring R/uR and the product ring R/u1R × ⋯ × R/ukR are isomorphic via the isomorphism


圖片參考：http://upload.wikimedia.org/math/f/5/6/f568de9f8da4c7468978342c6e1acf01.png

such that


圖片參考：http://upload.wikimedia.org/math/9/8/e/98ee137c614aca204150ad64160d5ebc.png

The inverse isomorphism can be constructed as follows. For each i, the elements ui and u/ui are coprime, and therefore there exist elements r and s in R with


圖片參考：http://upload.wikimedia.org/math/3/e/c/3ec533a3de42d752c176aa6ce967c825.png

Set ei = s u/ui. Then the inverse of f is the map


圖片參考：http://upload.wikimedia.org/math/7/2/b/72b1cd7798435f7ed5a2c77c2a97ff1b.png

such that


圖片參考：http://upload.wikimedia.org/math/d/4/6/d46c76dba70a3ff81e507fa450ec983c.png

Note that this statement is a straightforward generalization of the above theorem about integer congruences: the ring Z of integers is a principal ideal domain, the surjectivity of the map f shows that every system of congruences of the form


圖片參考：http://upload.wikimedia.org/math/7/8/d/78d7c8f356772a0a60d26af1058aee49.png

can be solved for x, and the injectivity of the map f shows that all the solutions x are congruent modulo u.

ok please wait