Show that there exists an integer $x$ such that $x\equiv 23 \mod 1000$ and $x\equiv 45 \mod 6789$

Question

Show that there exists an integer $x$ such that $x\equiv 23 \mod 1000$ and $x\equiv 45 \mod 6789$

I am unable to understand how to find such an integer .I tried using some examples like $7023,8023,9023..$ but none are satisfying the second equation.Also solutions of the second one don't satisfy the first one.

Is the problem a correct one?Please help.

Answer 1

4,087,023 = 4,087 * 1,000 + 23
4,087,023 = 602 * 6,789 + 45
Therefore a solution exists.

Answer 2

First find an integer $x_1$ such that $x_1 \equiv 1 [1000]$ and $x_1 \equiv 0[6789]$.

Such an integer exists because $1000 = 2^3 \times 5^3$ and neither 2 or 5 (which are prime) divide 6789, thus 1000 and 6789 are coprime and therefore there exists a Bézout identity $1000 u + 6789 v = 1$ (with u and v integers). it is easy to check that $6789 v$ is a solution.

Similiarily find $x_2$ such that $x_2 \equiv 0 [1000]$ and $x_2 \equiv 1[6789]$ ($1000u$ fits here).

Now check $x = 23x_1 + 45 x_2$ is solution to your equation.

Answer 3

You can write $x=1000N+23$ and $x=6789M+45$ for some integers M and N. Then we seek integer solutions to

$6789M-1000N=22$.

A solution to this equation exists since we can use Euclid's algorithm to find integers $n,m $ so that

$6789m-1000n=1$,

thanks to the fact that 6789 and 1000 are comprime. Then $M=22m $ and $N=22n $. You can calculate these numbers by Euclid's algorithm.