# Any relationship between $a\mod b$ and $a\mod c$?

Let's say we have $$a\equiv x\mod b$$ and $$a\equiv y\mod 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\mod b$$ vs $$a\equiv y\mod 2b$$,

or

$$a\equiv x\mod b$$ vs $$a\equiv y\mod 2b-1$$.

• Note that $x$ and $y$ are not uniquely defined as integers, but are representatives of equivalence classes (as you have stated the problem) - perhaps you want the least non-negative residue? – Mark Bennet Oct 2 '18 at 19:52
• Sorry for the flippant description. The relationship between the equivalence classes is indeed what I am going for (I mean to say that determining any element in the equivalence class will do). Least non-negative residue would be great if you could do so. – Tejas Rao Oct 2 '18 at 19:57

## 1 Answer

For any integer $$k \neq -1, 0, 1$$ $$a \equiv y \pmod {(k b)} \qquad \textrm{implies} \qquad a \equiv y \pmod b,$$ but the converse does not hold in general. On the other hand $$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 integers $$k, b$$ such that $$b \neq 0$$, $$(k, b) \neq (\pm 1, \pm 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 {(2 b - 1)} .$$ In this sense there is no relation between residues modulo $$b$$ and $$k b - 1$$. Conversely, however, given coprime $$p, q$$ we can use the residue classes modulo those numbers to determine the residue class modulo $$pq$$.