Which of the following statements is FALSE? There exists an integer $x$ such that
$1.$ $x \equiv 23$ mod $1000$ and $x \equiv 45$ mod $6789$.
$2.$ $x \equiv 23$ mod $1000$ and $x \equiv 54$ mod $6789$.
$3.$ $x \equiv 32$ mod $1000$ and $x \equiv 54$ mod $9876$.
$4.$ $x \equiv 32$ mod $1000$ and $x \equiv 44$ mod $9876$.
I observe that the first and second options are correct. Because for the first option to hold we need to find integers $X$ and $Y$ for which he equation
$$6789X-1000Y=22$$ holds. By the virtue of the fact that $6789$ and $1000$ are coprime we can say by Euclid's algorithm that there exist $m$ and $n$ such that $$6789m-1000n=1.$$ Then clearly $X=22m$ and $Y=22n$ suit our purpose.
By similar reasoning it can said that option $(2)$ is also correct. I have found trouble when I was trying to determine which of the options between $(3)$ and $(4)$ is correct. Then the rest is false and we are through. But in those cases we can't use coprime argument which has been used to determine that the first two options are indeed correct.
So how do I proceed for the remaining two cases? Please help me in doing this.
Thank you very much.
EDIT $:$
I think option $(4)$ is also correct. Because $(250,2469)=1$. so there exist $m$ and $n$ such that $$250m-2469n=1$$ Multiplying both sides by $4$ we have $$1000m-9876y=4$$ Then clearly if we take $X=3m$ and $Y=3n$ then $$1000X-9876Y=12$$ which in turn implies that there exist $X$ and $Y$ such that $$1000X+32=9876Y + 44$$ holds. So there exists some $x$ such that
$$x \equiv 32\ \mathrm {mod}\ 1000\ \mathrm {and}\ x \equiv 44\ \mathrm {mod}\ 9876.$$ Which proves that $(4)$ is also a correct option.
The first and second case clearly work out, since $6789$ and $1000$ are co prime, so one can solve the given equations simultaneously.
If $x \equiv 32 \mod 1000$ then $x$ is a multiple of $8$, since $x = 1000k + 32$ so it is a sum of multiples of $8$.
However, $9876 \equiv 4 \mod 8$, so for any $x = 9876k + 54$ , it leaves a remainder of either $2$ or $6$ when divided by $8$, so it is never a multiple of $8$, so the third case does not work out.
On the other hand, the fourth case does work out, since if $x = 1000k+32 = 9876l+44$ then one may transpose and divide by four to get $250k - 2469l = 12$, and this can be solved since $250$ and $2469$ are coprime.
Hence, $1,2,4$ are solvable while $3$ is not.
A short note
More precisely, suppose you are trying to solve two simultaneous congruences, say $x \equiv a \mod b$ and $x \equiv c \mod d$. Then, write as the conclusion, $x = a+bk = c + ld$.
Therefore, rewrite this to get $ld - bk = a-c$. That is, we want to find integers $k,l$ such that $ld - bk = a-c$.
In conclusion, the question is the following: can $a-c$ be expressed as a linear combination of $b$ and $d$? For this question, Bezout's lemma gives a very clear answer : it can, if and only if $a-c$ is a multiple of the greatest common divisor of $b$ and $d$.
Therefore, all you need to do, is to check that $a-c$ is a multiple of the greatest common divisor of $b$ and $d$!
For example, in the first two parts, $(1000,6789) = 1$, and $a-c$ is a multiple of $1$ always, so the answer is yes.
In the latter two parts, we have $(1000,9876) = 4$, so it is enough to see that $a-c$ is a multiple of $4$. In the first case, $54 - 32 = 22$ isn't a multiple of $4$, while in the second case $44-32 = 12$ is.
This short note provides a complete answer to the kind of question you have been asked. It can also be extended to three or more congruences.