The Chinese Remainder Theorem
source link: https://www.tuicool.com/articles/vE7rQjE
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
The Chinese Remainder Theorem (CRT) is very useful in cryptography and other domains. According to Wikipedia , its origin and name come from this riddle in a 3rd century book by a Chinese mathematician:
There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?
Mathematically, this is a system of linear congruences. In this post we'll go through a simple proof of the existence of a solution. It also demonstrates how to find such a solution, though check the Wikipedia link for a discussion of different methods and their relative efficiency.
We'll start with a few prerequisite lemmas needed to prove the CRT. You may want to skip them on first reading and refer back when going through the CRT proof.
Prerequisites
Lemma 1: ifand, then.
Proof: Sincewe know fromBézout's identity that there exist integers x and y such that. Multiplying both sides by b , we get:. bdx is divisible by d , and so is bay because. Therefore∎
Lemma 2: ifand, then.
Proof: Since, we know that, or. Sincewe can use Lemma 1 to conclude that. In other words,∎
Modular multiplicative inverse
A modular multiplicative inverse of an integer a w.r.t. the modulus m is the solution of the linear congruence:
Lemma 3: ifthen a has a unique modular multiplicative inverse modulo m .
Proof: Once again using Bézout's identity, we know fromthat there exist integers r and s such that. Thereforeis a multiple of m , or. So r is a multiplicative inverse of a .
Now let's see why this inverse is unique. Let's assume there are two inverses,and, soand also, which means that.
Sincewe can apply Lemma 2 to conclude that∎
Factorization and multiplying moduli
Lemma 4: ifandandthen also.
Proof: Consider the prime factorization of n .so a is a multiple of some subset of the these prime factors. The same can be said about b . But, so a and b don't have any prime factors in common. Thereforeis also a subset of the prime factors of n , and∎
The Chinese Remainder Theorem
Assumeare positive integers, pairwise coprime; that is, for any,. Letbe arbitrary integers. The system of congruences with an unknown x :
has a single solution modulo the product.
Proof: Let. Then, so eachhas a unique multiplicative inverse moduloper Lemma 3 above; let's call this inverse. Now consider:
is a multiple of everyexcept for. In other words forwe have. On the other hand, forwe have, by construction,. So for each k we have:
because all the other terms in the sum are zero. Hence x satisfies every congruence in the system.
To prove that x is unique modulo N , let's assume there are two solutions: x and y . Both solutions to the CRT should satisfy. Thereforeis a multiple offor each k . Since theseare pairwise coprime, from Lemma 4 we know thatis also a multiple of N, or∎
Corollary
Ifare pairwise coprime and, then for all integers x and a ,forif and only if.
Proof: we'll start with the if direction. Ifthis means. But that immediately means that for each i ,as well, or.
Now the only if direction. Givenfor, we can invoke the CRT using a in all congruences. The CRT tells us this system has a single solution modulo. But we know that a is a solution, so it has to be the only one ∎
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK