Chinese Maths

Chinese Remainder Theorem

---

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 n₁, ..., n_k are integers which are pairwise coprime (meaning gcd (n_i, n_j) = 1 whenever i ≠ j). Then, for any given integers a₁, ..., a_k, there exists an integer x solving the system of simultaneous congruences

Furthermore, all solutions x to this system are congruent modulo the product n = n₁...n_k.

A solution x can be found as follows. For each i the integers n_i and n/n_i are coprime, and using the extended Euclidean algorithm we can find integers r and s such that r n_i + s n/n_i = 1. If we set e_i = s n/n_i, 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. e₁ = 40. Using the Euclidean algorithm for 4 and 3×5 = 15, we get (-11) × 4 + 3 × 15 = 1. Hence, e₂ = 45. Finally, using the Euclidean algorithm for 5 and 3×4 = 12, we get 5 × 5 + (-2) × 12 = 1, meaning e₃ = -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 n_i's are not pairwise coprime. The precise criterion is as follows: a solution x exists if and only if a_i ≡ a_j (mod gcd(n_i, n_j)) for all i and j. All solutions x are congruent modulo the least common multiple of the n_i.

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

like yoga, dancing, french, jap, latin, chinese maths, world history and so much more..!!
adrenaline rush mad .. but seriously, I wanna learn =(