Trying to figure out how to solve linear congruence by following through the sample solution to the following problem:
x≡3 (mod 7)
x≡2 (mod 5)
x≡1
(mod 3)
Let:
n1 = 7
n2=5
n3=3
N=n1⋅n2⋅n3=105
m1=Nn1=15
m2=Nn2=21
m3=Nn3=35
gcd(m1,n1) = gcd(15,7)=1=15×1−7×2 so y1=1 and x1=15
gcd(m2,n2) = gcd(21,5)=1=21×1−5×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×2−35×1≡52 (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