Find all integers x with absolute value x less than 100 that satisfy the following system of linear congruencies.
13x== 1 (mod2)
3x== 7 (mod5)
5x== 11 (mod3)
1st congruence 13x== 1 (mod2)
13x== 1 (mod2) equals 12x + x == 1 (mod2) equals 0 + x == 1 (mod2) equals x == 1 (mod2)
i.e. x1 = 1,3,5,7,9,11,... (all odd numbers) x1 = 1 + 2r, r = 0,1,2,...
2nd congruence 3x== 7 (mod5)
3x== 7 (mod5) equals 3x== 12 (mod5) equals x== 4 (mod5)
i.e. x2 = 4,9,14,19,24,29,... x2 = 4 + 5s, s = 0,1,2,...
3rd congruence 5x== 11 (mod3)
5x== 11 (mod3) equals 5x== 20 (mod3) equals x== 4 (mod3) equals x== 1 (mod3)
i.e. x3 = 1,4,7,10,13,16,19,... x3 = 1 + 3t, t = 0,1,2,...
The elements of {x1} have a common difference of 2.
The elements of {x2} have a common difference of 5.
So, elements common to both {x1} and {x2} will have a common difference of 10 (10 = 2*5)
1st element common to both {x1} and {x2} is 9.
So {x4} = 9 + 10p, p = 0,1,2,... {x4} = {x: x e {x1} & x e {x2}}
The elements of {x4} have a common difference of 10.
The elements of {x3} have a common difference of 3.
So, elements common to both {x4} and {x3} will have a common difference of 30 (30 = 2*5*3)
1st element common to both {x4} and {x3} is 19.
So {x5} = 19 + 30q, q = 0,1,2,... {x5} = {x: x e {x4} & x e {x3}}
So elements of {x5} where x < 100 are: x = 19,49, 79