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

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.

• Do you know the Chinese remainder theorem ? – Astyx Oct 28 '16 at 19:04
• @Astyx correct me if I am wrong, but don't two numbers like that always exist so long as the remainder is a valid remainder? – The Great Duck Oct 28 '16 at 19:11
• @TheGreatDuck Assume you have two equations,the first one being mod n and second one mod m. As long as both equations imply the same one mod $gcd(n,m)$, yes, there is a solution if I am not mistaken (there even are infinetly many). – Astyx Oct 28 '16 at 19:17
• So basically if you say the remainder when x is divided by n = b and the remainder when x is divided by m = c, then there is always an x that fulfills that equation? – The Great Duck Oct 28 '16 at 22:31

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.

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

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.