Notes

The Chinese remainder theorem is a theorem which gives a unique solution to simultaneous linear congruences with coprime moduli. In its basic form, the Chinese remainder theorem will determine a number p



p that, when divided by some given divisors, leaves given remainders.



Chinese Remainder Theorem

Given pairwise coprime positive integers n_1, n_2.......... n_k​ and arbitrary integers a_1, a_2, .......... a_k the system of simultaneous congruences

x≡a1 (mod n1​)



x≡a2 ​(mod n2)



⋮



x≡ak ​(mod nk​)

​

has a solution, and the solution is unique modulo N=n1​n2​⋯nk.

The following is a general construction to find a solution to a system of congruences using the Chinese remainder theorem:

Compute N=n1​×n2​×⋯×nk
For each i=1,2,…,k, compute
yi​=N/ni=n1​n2⋯ni−1 ni+1​⋯nk​.



​3.For each i=1,2,…,k, compute zi≡yi^−1mod ni​ using Euclid's extended algorithm (zi exists since n1​,n2​,…,nk are pairwise coprime).

4.The integer x=∑i=1k ai​ yi​ zi is a solution to the system of congruences, and x mod N is the unique solution modulo N.



PROOF

To see why x

x is a solution, for each i=1,2,…,k, we have

x ≡(a1 y1 z1​+a2 y2 ​z2+⋯+ak yk zk​) (modni)

≡ai yi ​zi (modni​),

≡ai ​(modni​)



Now, suppose there are two solutions u

u and v to the system of congruences. Then n1 ​∣(u−v),n2 ​∣(u−v),…,nk ​∣(u−v), and since n1,n2​,…,nk are relatively prime, we have that n1 n2​⋯nk divides u−v, or

u≡v(mod n1 n2​⋯nk​).

Thus, the solution is unique modulo n1 n2​⋯nk.



​------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

By using Chinese remainder theorem,

x ≡ 49^19 mod 100

100 = 25 * 4

x ≡ 49^19 mod 25

x ≡ 49^19 mod 4

( 49 )^19 = ( -1 )^19 mod 25

-1 mod 25

( 49 )^19 = ( 1 )^19 mod 4

1 mod 4

x ≡ ( ( -1 ) ( 4 ) ( 19 ) ) + ( ( 1 ) ( 25 ) ( 1 ) )

x ≡ -51 mod 100

x ≡ 49 mod 100

Hence, the last two digits of 49^19 is 49