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

congruenceselementary-number-theory

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.

Best Answer

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.

Related Question