Complete proof of Chinese Remainder Theorem

-


Statement:

If we take t number of integers a1,a2,a3,…,at  and   m1,m2,m3,…,mt  be coprime (i.e gcd of two numbers is 1) then there is a number x with the property that, 
x ยบ ai (mod mi)   1 £ i £ t   ......(1)
The number x is unique in the following sense: 
Let M be the product of all the mi¢s, 
M = m1.m2...mt 
and y satisfies the system of congruences (1). Then, 
y ยบ x ( mod M)  

Proof:

We will use induction to prove this,
           For x=a1         here x is unique so, the result is true For t=1,

Now, by the induction hypothesis,
we assume it to be true for t=k  

We will proof if the result is true for t=k+1 

Consider the system of congruences, x ยบ a1 (mod m1 ) 
x ยบ a2 (mod m2 ) 
.                           
.                           
.                           
x ยบ ak (mod mk ) 
      x ยบ ak+1 (mod mk+1 ) 

Where the modulus is relatively prime to each other.
By induction, there is a number x¢ satisfying the first k congruences. Note that the product of m1,m2,…, mk and mk+1 are coprime i.e.,
 
gcd( mr , mk+1)=1 , 

where  mr is the product m1.m2.m3….. mk. 

Otherwise, there would be a common prime factor p. Since p divides mr it must divide one of the factors say mj where 1 £ j £ k. then,
1  p £ gcd( mj , mk+1). 

This contradicts the assumption that moduli are coprime. 

Since m1,m2,m3,…..,mk and mk+1 are coprime there exist integers u and v such that, 

u.m2.m3….. mk +v. mk+1=1
 
Multiplying both sides by ( ak+1-x¢), we get, 

( ak+1-x¢).u.m2.m3….. mk+( ak+1-x¢).v. mk+1=( ak+1-x¢) 

Taking u¢¢= u.( ak+1-x¢) and v¢¢= -v.( ak+1-x¢) 
It gives,  
x¢+u¢¢.m1.m2….. mk = ak+1+v¢¢.mk+1 
Let’s denote x¢¢=x¢+u¢¢.m1.m2….. mk this gives us, 
x¢¢= ak+1+v¢¢ mk+1 

Rewriting the equivalence equation as 
x¢¢= ak+1 ยบ (mod mk+1)
Since,                x¢ ยบ ai(mod mi)    ,1 £ i £ k                          
Thus,               x¢¢ ยบ x¢ ยบ ai(mod mi)    ,1 £ i £ k                
 
The induction step is completed as x¢¢ satisfies all of the original k+1congruences since the first congruence follows by the definition of x¢ ¢and the second is due to the choice of  x¢. To prove uniqueness, consider two numbers x1 and x2 satisfying (1). 

Thus,             x1 ยบ x2(mod mi) ,i=1,2,...,t  
                 
from which the relation x1 ยบ x2(mod M) immediately follows, by the definition of congruence and by our assumption that these are coprime.
 
This completes the proof.

     
Hey there, This is Hifza Siddiqui, an aspiring Mathematician pursuing masters from the University of Mumbai. I'm writing this blog to share the knowledge and the way I understand mathematics. I hope it helps you to get a better insight. My blog's frequency will be twice per week.

Comments

Post a Comment

Please do not enter spam link in the comment box

Recent blogs

Topology

-
Image
    What is topology ? What is topology used for? Topology is a branch of mathematics that deals with the properties of an object that are invariant ( do not change ) under continuous deformations like stretching, crushing, coiling. However, shredding or gluing is not allowed.  It also gives the spatial relation of the elements of a set. In simple words, two objects ( spaces ) that can be deformed into each other are topologically isomorphic.   cube turning into dodecahedron by  Tomruen   For example,   A cube can be deformed into a sphere without breaking it, square into a circle, coffee cup into a torus ( doughnut) , double doughnut into a kettle, and scissor.  Fun Fact: It is said that topologists cannot distinguish between a coffee mug and a doughnut. Types of Topology Applications of topology: In mathematics: It is used in various fields of mathematics such as number theory, differential equations, dynamical systems, knot theory and Ri...
Read more

Integration = Area under the curve?

-
Image
What is the concept of integration ?  What is the purpose of integration ?  Why does integrating give you area under the curve? Integration, also known as  anti-derivative   of a function, gives the area under the curve of the function.  Most of you already know all this thing but did  you  ever wonder  why integration gives you area under the curve?  How does it work actually? Well, the answer is quite simple and basic. We will take some polynomials as examples and the integration rule for a polynomial term of an arbitrary degree n " $ax^n $  " is given by \[\int ax^n dx=\frac{ax^{n+1}}{n+1}+C\]
Read more

Types of Topology

-
Image
Types of Topology        General or point-set Topology: It generalizes the basic concepts such as connectedness, continuity, compactness by using definitions from set theory and lays the foundation for the other branches. Changing the topology can change which functions are continuous and which subsets are connected or compact. Topological spaces have metric spaces as an important class as they simplify many proofs.           Algebraic Topology: It associates the algebraic objects with topology . In this algebraic structures are used as tools to study the variations of geometric objects. The basic idea is to consider two spaces to be identical if they have the same shape. Sometimes, the topologically isomorphic shapes seem different geometrically, like a cuboid and sphere but their algebraic properties are similar, so it becomes easier to study it by converting these problems to algebraic ones.     It gives the con...
Read more

Examples based on Chinese Remainder Theorem

-
Image
Steps to solve the system of congruences : Step 1: Take the congruence with the largest modulus  x   a n  (mod m n )  then rearrange it as, x=m n k+a n      where k is an integer. Step 2: Substitute x into the 2 nd  largest modulus m n k+a n   a n-1  (mod m n-1 ) then solve the  congruence k   h (mod m n - 1 ). Step 3: Rewrite the congruence as k= m n-1 d+h and substitute it in x. Step 4: Substitute the solve equation of x in the next largest modulus then solve the congruence. Step 5: Repeat the above steps until the solution arrives.                    
Read more

Chinese Remainder Theorem

-
How do you solve Chinese Remainder Theorem? How do you solve a system of congruence? How can CRT be used to speed up RSA decryption? Chinese Remainder Theorem (C.R.T) , given by Sun Zi, is one of the brilliant concepts in mathematics, it represents Horace's quote beautifully,  omne tulit punctum qui miscuit utile dulci (he gains everyone’s approval who mixes the pleasant with the useful).   In number theory, the C.R.T . gives us the unique remainder from the simultaneous linear congruences by solving the congruences using th e Euclidean division where the divisors are coprime. Statement: If we take t number of integers a 1 ,a 2 ,a 3 ,…,a t  and m 1 ,m 2 ,m 3 ,…,m t  be coprime (i.e gcd of two numbers is 1) then there is a number x with the property that,   x  ยบ  a i  (mod m i )     1  £  i  £  t      .......(1) The number x is unique in the following sense:   Let M be the product of all ...
Read more

Riemann Sums and Integral

-
Image
Riemann sums and Integral was introduced by a German Mathematician Bernhard Riemann . What are Riemann sums?  How do you convert integrals to Riemann sums?  How do you calculate Riemann integral ?  Its argument arose when we want to find the area under the curve of a function. Imagine that you are given a rectangle or any other polygon or a function how will you calculate the area under the curve ?    Riemann sums (RS) is there to help you. I t is used to approximate the area under the curve of a function by adding shapes like rectangle, trapezoid, etc . But the question here is how can we make these rectangles? There are three choices when it comes to making rectangles to approximate the area.
Read more