Question

find all integers x with asolute value x less than 100 that satisfy the following system of linear congruences

13x== 1 (mod2)

3x== 7 (mod5

5x== 11 (mod3

Answer 1

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