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 the m i ¢ s, M = m 1 .m 2 ...m t and y satisfies the system of congruences (1). Then, y º x ( mod M) Proof: We will use induction to prove this, For x=a 1 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 º a 1 (mod m 1 ) x º a 2 (mod m 2 ) ...
Comments