Monday 19 January 2015

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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...