1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Do you know the Chinese remainder theorem ? $\endgroup$ – Astyx Oct 28 '16 at 19:04
  • $\begingroup$ @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? $\endgroup$ – The Great Duck Oct 28 '16 at 19:11
  • $\begingroup$ @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). $\endgroup$ – Astyx Oct 28 '16 at 19:17
  • $\begingroup$ 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? $\endgroup$ – The Great Duck Oct 28 '16 at 22:31
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.