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$$

  • $\begingroup$ 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 $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ Great answer, do you know what happens when it's \not\equiv in both congruences? $\endgroup$ – Gustav May 25 '11 at 2:16
  • $\begingroup$ @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$. $\endgroup$ – GH from MO May 25 '11 at 3:15
  • $\begingroup$ If you view the congruence condition as defining a set, you may be able to visualize this more easily for two or more conditions as belonging or not belonging to some nice Boolean combination of the sets. Gerhard "Ask Me About System Design" Paseman, 2011.05.25 $\endgroup$ – Gerhard Paseman May 26 '11 at 0:16

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.