Chinese remainder Theorem Motivation Find a number x that leaves a remainder of 1 when divided by 3, 2 when divided by 5 and 3 when divided by 7. So, x-l mod 3, x=2 mod 5 and x=3 mod 7 We want to solve a system of congruences to different modulChinese Remainder Theorem • Motivation: – Find a number x that leaves a remainder of 1 when divided by 3, 2 when divided by 5 and 3 when divided by 7. So, x=1 mod 3, x = 2 mod 5 and x = 3 mod 7 • We want to solve a system of congruences to different moduli