Congruences

Find the least positive four-digit solution to the following system of congruences.

 

7x = 21 (mod 14)

2x + 18 = 16 (mod 9)

 

7x=21 mod14

x=3 mod14

x=14p+3

 

2x+18=16 mod9

2x=-2  mod9

x=-1    mod9

x=9q-1

 

9q-1 = 14p+3

9q - 14p = 4

-------------------------

9=-1*(-14) - 5

-14=  3(-5)+1

 

-14 - 3(-5) = 1

-14 - 3 [9+1*(-14)] = 1

(-14) - 3*9 -3(-14) = 1

-2(-14) -3(9) = 1

9(-3) -14(-2)=1

9(-12) -14(-8)=4

 

9(-12+14g) - 14(-8+9g) = 4

so

q =-12+14g             and    p =-8+9g

x = 9q-1                  and     x= 14p+3

x= 9(-12+14g)-1     and     x= 14(-8+9g)+3

x= -109 +9*14g      and     x = -109 + 14*9g      they are the same so it is right.

x= -109 +126g

 

I want the smallest 4 digit value of x

-109+126g>1000

126g > 1109

g > 8.8

g=9

 

x = -109+126*9

x= 1025