Chinese Remainder Theorem

[vokoyo]

Dear

How to solve the CRT for cryptography as below -

(1) Find x such that

x = 2(mod3)
x = 5(mod9)
x = 7(mod11)

(2) Find x such that

x = 2(mod3)
x = 4(mod7)
x = 5(mod11)

(3) Find x such that x^2= 26(mod77)

(4) Find x such that x^2 = 38(mod77)

Please help me by provide your advice and suggestion

Prayerfully



Tron Orino Yeong
tcynotebook@yahoo.com
0916643858

[HallsofIvy]

Strictly speaking the "Chinese remainder theorem" does not apply to the first problem. The "Chinese remainder theorem" says that a set of equations of the form "x= b (mod n)" has a solution if the "n"s are relatively prime. In your first problem, 3 and 9 are not relatively prime. There may or many not be a solution.

If x= 5 (mod 9) then x= 9i+ 5 for any integer I. Then, since 9 is a multiple of 3, x= 3(3i)+ 3+ 2= 3(3i+1)+ 2 so any solution of x= 5 (mod 9) is also a solution of x= 3 (mod 3). So, in this case there is a solution but notice that if the equation were x= a (mod 3) for a= 0 or 1, there would not.

Since x= 9i+ 5= 7 (mod 11), 9i= 2 (mod 11). That is, 9i= 2+ 11j for some integer j. That is the Diophantine equation 9i- 11j= 2. An obvious solution is i= -1, j= -1, since 9(-1)- 11(-1)= -9+ 11= 2. But it is also true that i= -1+ 11k, j= -1+ 9k is a solution for any k: 9(-1+ 11k)- 11(-1+ 9k)= -9+ 99k+ 11- 99k= 2 for all k. So i= -1+ 11k which can also be written i= 10+ 11m with m= k- 1.

So x= 9i+ 5= 9(10+ 11m)+ 5= 95+ 99m.

The three equations are all satisfied by x= 95+ 99m for m any integer.
Check:
x= 95+ 99m= 3(31)+ 2+ 3(33m)= 2 (mod 3)
x= 95+ 99m= 3(30)+ 5+ 9(11m)= 5 (mod 9)
x= 95+ 99m= 8(11)+ 7+ 11(9m)= 7 (mod 11).

The second problem is much the same (except that 3, 7, and 11 are relatively prime so the "Chinese remainder theorem does apply).

[Guest]

Since this has been sitting here for a while, here is how to solve the second set of equations.

x= 2(mod 3) is equivalent to x= 2+ 3i for some integer i. Then x= 2+ 3i= 4 (mod 7) is the same as 3i= 2 (mod 7). We can write that as 3i= 2+ 7j for some integer, j. That is the same as 3i- 7j= 2. I notice immediately that 7- 2(3)= 1 so that 2(7)- 4(3)= 3(-4)- 7(-2)= 2. That means that i= -4 (mod 7) which is the same as i= 7- 4= 3 (mod 7). So i= 3+ 7j for some integer j and then x= 2+ 3i= 2+ 3(3+ 7j)= 11+ 21j.
(It is a good idea to check that 11= 3(3)+ 2 and 11= 7+ 4 so 11 is equal to 2 (mod 3) and 4 (mod 7).)\

Now, x= 11+ 21j= 5 (mod 11) is the same as 21j= 5- 11= -6= 5 (mod 11). 21= 11+ 10 so 21j= 10j= 5 (mod 11). That is, 10j= 5+ 11k for some integer k. 10j- 11k= 5. Again, 11- 10= 1 so 10(-5)- 11(-5)= 5. j= -5= 6 (mod 11). j= 6+ 11k so x= 11+ 21(6+ 11k)= 137+ 231k.

Final check: 137= 45(3)+ 2= 2 (mod 3), 137= 19(7)+ 4= 4 (mod 7), and 137= 12(11)+ 5= 5 (mod 11).