Notes - The Chinese Remainder Theorem

The following are notes from Introduction to Cryptography with Coding Theory.

• Chinese remainder theorem is used to break a congruence mod n into a system of congruences mod factors of n
• Example
• Number satisfies x≡ 25(mod 42)
• means we can write x = 25 + 42k (k is some integer)
• we can rewrite 42 as 7*6
• x = 25 + 7(6k)
• x = 25 + 6(7k)
• Chinese Remainder Theorem
• suppose gcd(m,n) = 1. If an integer c is a multiple of both m and n, then c is a multiple of mn. given integers a and b there exists exactly one solution x (mod mn)to the simultaneous congruences
• x ≡ a (mod m)
• x ≡ a (mod m)
• x ≡ b (mod n)
• Lemma
• Let m,n be integers with gcd(m,n) = 1
• if an integer c is a multiple of both m and n, then c is a multiple of mn
• Example
• Solve x ≡ 3 (mod 7), x ≡ 5 (mod 15)
• 7*15 = 105
• list congruences
• 5,20,35,50,65,80
• 3,10,17,24,31,38,45,52,59,66,73,80
• x ≡ 80 mod 105
• solve
• nk ≡ a - b (mod m)
• k ≡ (a - b)i (mod m) [i is the multiplicative inverse of n]

Back to ToC