Chinese Remainder Theorem by Hin Chi Lee (12JLG)
The Chinese Remainder Theorem allows solving of a system of simultaneous linear congruences involving modulo operations. It has first been discovered by the Chinese mathematician Sunzi. The theorem is commonly used when dealing with large integers in computers or sometimes serves calculations in astronomical purposes. We denote that “x divided by n leaves a remainder of a” as ≡ This is known as the modulo operation. Eg. 9 divided by 4 leaves a remainder of 1, hence this identity can be denoted by the following: 9 ≡ 1 4 It states that given a set of simultaneous congruences where are pairwise co-prime 1 for = 1, 2, … , ≡ 1 1 ≡ 2 2 : ≡ can be solved by the following sequence: = 1 1 1 + 2 2 2 + ⋯+ where = 1 2 … and 1 ∙ 𝑀 𝑖 = 1 2
Proof of existence of solution
For any system of linear congruences,
= 1 = 2
1 2 …
=
If we define:
=
Since are pairwise co-prime, we know that the greatest common divisor of and is 1. Bezout’s identity state that “ for any nonzero integers 1 and 2 , of which the great common divisor is d, there exists integers 1 and 2 such that 1 1 + 2 2 = d” . In this case: + = 1 Where and are integers. The solution of x can be given by:
≡ ∑
=1
Since
is a multiple of for all values of ≠ , we obtain for every value: ≡ ≡ (1 − ) ≡ 3
1 Pairwise Co-prime: Every pair of numbers within the set have 1 as their greatest common divisor 2 http://mathworld.wolfram.com/ChineseRemainderTheorem.html 3 https://pdfs.semanticscholar.org/19c5/08c974a0da5f7212f1b71a4b41f40ae33688.pdf
Made with FlippingBook - professional solution for displaying marketing and sales documents online