Number of integers in an interval satisfying two linear congruences.

Question

Suppose I have an interval $I \subset \mathbb{R}$. Suppose I have two linear congruences $x \equiv a \pmod {N_1}$ and $x \equiv b \pmod{N_2}$. I am wondering what are the number of integers in the interval that satisfy these congruences? When $N_1$ and $N_2$ are coprime it is $$ \frac{|I|}{N_1 N_2} + O(1). $$ I was wondering what can we say when $N_1$ and $N_2$ are not coprime. Any input is appreciated. Thank you.

Answer 1

If $N_1$ and $N_2$ are not coprime, the congruences can only be satisfied for certain values of $a$ and $b$. For instance, $x\equiv0\bmod6$ and $x\equiv1\bmod10$ cannot be simultaneously satified. A fraction $\frac1{\gcd(N_1,N_2)}$ of the pairs of residues modulo $N_1$ and $N_2$ yields simultaneously satisfiable congruences, and for such pairs, the number of integers in $I$ that satisfy these congruences is

$$ \frac{|I|}{\operatorname{lcm}(N_1,N_2)}+O(1)\;. $$

Incidentally, if you uniformly randomly select a pair of residues, the expected number of integers in $I$ that satisfy the resulting congruences is

$$ \frac1{\gcd(N_1,N_2)}\cdot\frac{|I|}{\operatorname{lcm}(N_1,N_2)}+O(1)=\frac{|I|}{N_1N_2}+O(1)\;, $$

the same as for coprime $N_1$ and $N_2$.