# Conditions for congruences

It is well known that $\exists x \in \mathbb{N}$ such that $$x \equiv a_1 \mod b_1$$ $$x \equiv a_2 \mod b_2$$ if and only if $a_1 \equiv a_2 \mod \text{gcd}(b_1, b_2)$.

Is there such a simple condition for the following system? $$x \equiv a_1 \mod b_1$$ $$x \not\equiv a_2 \mod b_2$$

• Yes. x satisfies the second set of relations iff the subset {a_2 + nb_2} as n ranges over all natural numbers does not contain the subset {a_1 + nb_1} of the naturals, again with n ranging over all natural numbers. I leave it to you to rephrase it in algebraic form. Gerhard "Ask Me About System Design" Paseman, 2011.05.24 – Gerhard Paseman May 24 '11 at 23:29

If $b_2$ divides $b_1$ then an obvious necessary and sufficient condition is that $a_1\not\equiv a_2\ \mathrm{mod}\ b_2$.
If $b_2$ does not divide $b_1$ then $\gcd(b_1,b_2)$ is a proper divisor of $b_2$, so there are at least two residue classes $y\ \mathrm{mod}\ b_2$ such that $y\equiv a_1\ \mathrm{mod}\ \gcd(b_1,b_2)$. Pick one that satisfies $y\not\equiv a_2\ \mathrm{mod}\ b_2$, then by the criterion you quote there is an $x$ satisfying $x\equiv a_1\ \mathrm{mod}\ b_1$ and $x\equiv y\ \mathrm{mod}\ b_2$. This $x$ solves the second system.
To summarize, the second system has a solution unless $b_2\mid b_1$ and $a_1\equiv a_2\ \mathrm{mod}\ b_2$.
• @Gustav: If $b_1=1$ or $b_2=1$ then there is no solution. If $b_1=b_2=2$ and $a_1\not\equiv a_2\ \mathrm{mod}\ 2$ then there is no solution. In all other cases there is a solution because if $b_1=b_2=b>2$ you can choose $x\not\equiv a_1,a_2\ \mathrm{mod}\ b$, and if $b_2>b_1>1$ (say) then you can apply the second paragraph of my original response to $a_1+1$ in place of $a_1$. – GH from MO May 25 '11 at 3:15