Given two natural numbers m and n with greatest common divisor 1, there is a simultaneous solution
to the congruences x ≡ a (mod m) and x ≡ b (mod n) and this solution is unique (mod mn).
Suppose n1, ..., nk are integers which are pairwise coprime (meaning gcd (ni, nj) = 1 whenever i ≠ j). Then, for any given integers a1, ..., ak, there exists an integer x solving the system of simultaneous congruences
Furthermore, all solutions x to this system are congruent modulo the product n = n1...nk.
A solution x can be found as follows. For each i the integers ni and n/ni are coprime, and using the extended Euclidean algorithm we can find integers r and s such that r ni + s n/ni = 1. If we set ei = s n/ni, then we have
for j ≠ i.
One solution to the system of simultaneous congruences is therefore
For example, consider the problem of finding an integer x such that
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 + 2 × (-24) = 167. All other solutions are congruent to 167 modulo 60, which means that they are all congruent to 47 modulo 60.
Sometimes, the simultaneous congruences can be solved even if the ni's are not pairwise coprime. The precise criterion is as follows: a solution x exists if and only if ai ≡ aj (mod gcd(ni, nj)) for all i and j. All solutions x are congruent modulo the least common multiple of the ni.
The method of successive substitution can often yield solutions to simultaneous congruences, even when the moduli are not pairwise coprime.
Can understand anot? HAHAHA.
chinese maths standard is quite high.
I suddenly have the urge to learn alot of things
