Chinese remainder theorem - pending
How do you find 'x' s.t.
x = 3 mod 11
x = 4 mod 7
x = 1 mod 5
First check that 5,7,11 are pairwise co-prime. Done.
Then we write 'x' as sum of 3 numbers in a way that 2 of them disappear when taking mod by any of 5,7,11
So x = a.7.11 + b.5.11 + c.5.7
If I do x mod 5, I will get a.7.11 mod 5 and rest 2 numbers will disappear. Same for 7 and 11.
Now I need to ensure that a.7.11 mod 5 = 1. For this we do trial and error and start with a = 1
a.77 mod 5 = a.2 mod 5 = 1 => a = 1,2 doesn't work. a = 3 works.
b.55 mod 7 = 4
=> b.6 mod 7 = 4
=> b = 3
c.35 mod 11 = c.2 mod 11 = 3 => c = 1,2,3,4,5,6 don't work. c = 7
So x = 3.77 + 165 + 245 = 231 + 410 = 641
Test 641 mod 5 = 1
641 mod 7 = 4
641 mod 11 = 3
So it works.
But there are multiple such solutions.
They are of the form:
641 + lcm(5,7,11).k = 641 + 385k
And smallest positive value would be 641 - 385 = 256
Comments
Post a Comment