how comes $s=4$ and $t=3$ for $4=7s-8t$

Question

i am given these two problems:

$x\equiv 1 (\bmod 7 )$ and $x \equiv 5( \bmod 18)$

I tried this way:

$x\equiv 1 (\bmod 7 )$ is basically $x = 1 + 7s$ and $x\equiv 5 (\bmod 18 )$ is $x=5+18t$

then substituted x: $4 = 7s - 8t$

Now i am asked to use extended euclidean algorithm to solve this equation for $s$ and $t$ so that i can find $x$.

i tried this:

but i am getting $s=1$ and $t=-1$. what am i doing wrong? please help. the answer in the textbook is: $s=4$ and $t=3$

Answer 1

You have solved $1=gcd(7,8)=7s-8t$ correctly with $s=1$ and $t=-1$, because $-7+8=1$. Multiplying by $4$ we obtain $4=-4\cdot 7+4\cdot 8$. But this does not solve your simultaneous congruences for $x$ (and $s=4, t=3$ also do not solve it). Check the webpage for the Chinese remainder Theorem, http://en.wikipedia.org/wiki/Chinese_remainder_theorem, to see how the extended Euclidean algorithm yields the solution $x=113$, which is unique up to multiples of $7\cdot 18=126$. So $s=16$ and $t=6$.