Determine $x$ if $x = 4 \mod 17$ and $x = 3 \mod 11$.

Question

Given $x =4\mod 17$ and $x = 3\mod 11$, determine $x$.

I know that $\gcd(17,11)= 1$. I was hoping to use this to determine $x$.

Answer 1

From the second congruence,

$x = 11k + 3, k \in \mathbb{Z}$

Substitute into first congruence,

$11k + 3 = 4 \pmod{17}$

$11k = 1 \pmod{17}$

$k \equiv 11^{-1}\pmod{17}$

Solving for the inverse using the Extended Euclidean Algorithm, we get:

$k \equiv 14 \pmod{17}$

or $k = 17m + 14, m \in \mathbb{Z}$

Hence $x = 11(17m + 14) + 3 = 187m + 157$

giving the solution $x \equiv 157 \pmod{187}$.

Answer 2

The two congruences are equivalent to $$x=4+17n=3+11m$$ We solve the equation $$11m-17n=1$$ of which a particular solution is $(m,n)=(31,20)$ hence all the solutions are given by $$\begin{cases}m=31+17t\\n=20+11t\end{cases}$$

Thus all the solutions $x$ are given by$$x=4+17(20+11t)=344+187t=\color{red}{157+187t}$$ where $t$ is an arbitrary integer the minimun positive being $157$ corresponding to $t=0$.