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


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

  • 1
    $\begingroup$ 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? $\endgroup$ – Mark Bennet Oct 2 '18 at 19:52
  • $\begingroup$ 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. $\endgroup$ – Tejas Rao Oct 2 '18 at 19:57

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


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.