Monday, April 11, 2016

Chinese Remainder Theorem Explanation

I'm reading through a brief example of the Chinese remainder theorem and am having difficulty understand the process they are going through.



Consider two primes p and q. For an arbitrary a < p and b < q, there exists a unique y less than p × q such that y ≡ a (mod p) and y ≡ b (mod q).



Consider p=5 and q=7. Consider a=4 and b=3,there exists a unique y less than 35 such that y ≡ 4 (mod 5) and y ≡ 3 (mod 7), that is y = 24.



Method:



Use Euclids algorithm to compute the smallest u such that u × q ≡ 1 ( mod p), it gives 7×u≡1(mod5) ≡ u = 3




Compute y=(((a−b)×u)modp)×q+b,it gives y=(((4−3)×3)mod 5)×7+3 = (3 mod 5)×7+3 = 3×7+3 = 24



I'm having quite a lot of trouble trying to find out what is going on here and how the method utilises Euclid's algorithm. Can anybody please help and explain it better and simpler? Thank you!

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...