Thursday, November 12, 2015

modular arithmetic - Solving simultaneous congruences



Trying to figure out how to solve linear congruence by following through the sample solution to the following problem:





x3 (mod 7)
x2 (mod 5)
x1
(mod 3)




Let:
n1 = 7
n2=5
n3=3



N=n1n2n3=105



m1=Nn1=15

m2=Nn2=21

m3=Nn3=35




gcd(m1,n1) = gcd(15,7)=1=15×17×2 so y1=1 and x1=15
gcd(m2,n2) = gcd(21,5)=1=21×15×4 so y2=1 and x2=21
gcd(m3,n3) = gcd(35,3)=1=35×1+3×12 so y3=1 and x3=35



I understand up to this point, but the next line I don't get:



So x=15×3+21×235×152 (mod 105)



Where is the ×3, ×2, ×1 from? Is it just because there are 3 terms, so it starts from 3 then 2 then 1? And where is the 52 coming from?


Answer



Although Bill Cook's answer is completely, 100% correct (and based on the proof of the Chinese Remainder Theorem), one can also work with the congruences successively; we know from the CRT that a solution exists.




Starting from x\equiv 3\pmod{7}, this means that x is of the form x=7k+3 for some integer k. Substituting into the second congruence, we get
7k+3 \equiv 2\pmod{5}.
Since 7\equiv 2\pmod{5}, and 3\equiv -2\pmod{5}, this is equivalent to 2k-2\equiv 2\pmod{5}. Dividing through by 2 (which we can do since \gcd(2,5)=1) we get k-1\equiv 1\pmod{5}, or k\equiv 2\pmod{5}. That is, k is of the form k=5r+2 for some integer r.



Plugging this into x=7k+3 we have x=7(5r+2)+3 = 35r + 17.



Then plugging this into the third (and last) congruence, we get
35r + 17\equiv 1\pmod{3}.
Now, 35\equiv -1\pmod{3}, 17\equiv -1\pmod{3}, so this is the same as -r-1\equiv 1\pmod{3}, or r\equiv -2\equiv 1\pmod{3}. That is, r is of the form 3t+1. Plugging that into x we get

x = 35r+17 = 35(3t+1)+17 = 105t + 52,
so that means that x is of the form x=52+105t for some integer t; that is, x\equiv 52\pmod{105} is the unique solution modulo 3\times5\times 7.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...