A Modular Diophantine Equation

Question

$a = (N \bmod c)\bmod d$

$b = (N \bmod d)\bmod c$

That is $a$ and $c$ is remainder of $N$ when divided by $c$ and $d$ in different order.

What can we say about $N$ if $a,b,c,d$ are known and $N < cd$?

Answer 1

Without loss of generality, assume that $c<d$. Moreover assume that $x \bmod n$ denotes the unique representative in $[0,n-1]$.

The first remark is that $a=N \bmod c$, because (since $c<d$) this value is already reduced modulo $d$. For the other reduction, we only know that $N \bmod d=b+tc$, where $$0\leq t \leq \frac{(d-1)-b}{c}.$$

Now, from $N \bmod c$ and $N \bmod d$ you can easily reconstruct $N$ using the CRT (since $0\leq N <cd$).

In addition, if $N_t$ denotes the solution obtained for some acceptable value of $t$, we have $N_t=N_0+tc$.

---

Here is an example, take $c=11$, $d=101$, $a=2$ and $b=3$. Since $(d-4)/c\approx 8.8$, we have $t\in [0;8]$. This yields the following set of solutions: $$ S=\{508,519,530,541,552,563,574,585,596\} $$