Any relationship between $a\bmod b$ and $a\bmod c$?

2.3k Views Asked by At

Let's say we have $a\equiv x\pmod b$ and $a\equiv y\pmod c$. Is there any way to find the relationship between $x$ and $y$ for nontrivial (a>b and/or a>c) moduli?

How about a specific example, such as

$a\equiv x\pmod b$ vs $a\equiv y\pmod{2b}$,

or

$a\equiv x\pmod b$ vs $a\equiv y\pmod{2b-1}$.

1

There are 1 best solutions below

0
On

One can readily generalize your example from $2$ to an arbitrary positive integer $k$. It follows immediately from the definition that $$a \equiv y \pmod {(k b)} \qquad \textrm{implies} \qquad a \equiv y \pmod b$$ for any integer $k$. The converse does not hold in general, but $$a \equiv y \pmod b \qquad \textrm{implies} \qquad a \equiv y + \ell b \pmod {(kb)}$$ for some integer $\ell$ (in fact, a unique integer in $\{0, \ldots, k - 1\}$).

On the other hand, $b$ and $k b - 1$ are coprime for any positive integer $b$ (excluding the trivial case $b = k = 1$), so the Chinese Remainder Theorem tells us that for any remainders $m$ and $n$ we can find an integer $a$ such that $$a \equiv m \pmod b \qquad \textrm{and} \qquad a \equiv n \pmod {(k b - 1)} .$$ In this sense there is no relation between residues modulo $b$ and $k b - 1$. Conversely, however, given coprime $b, c$ we can use the residue classes of an integer $a$ modulo those numbers to determine the residue class modulo $bc$.