2
$\begingroup$

Hi Mathematics Stack Exchange community!

I have a question. I want to know how one would go about taking an intersection of two congruence classes. Are there any well known methods to do it?

i.e. $$\overline{2}_3 \cap \overline{1}_4=\overline{5}_{12}$$ $$\{3n+2|n\in \mathbb Z\}\cap\{4n+1|n\in \mathbb Z\}=\{12n+5|n\in \mathbb Z\}$$ $$\{\ldots, -7,-4,-1,2,5,8,\ldots\}\cap\{\ldots, -7, -3, 1, 5,9\ldots\}=\{\ldots,-19, -7,5,17,\ldots\}$$


I found a way to do it by myself but when I tried to google about intersections of congruence classes, I found only one site which wasn't even about the thing I was after. Is it just assumed that you have to be able to find the intersection by yourself? I'm not yet in uni and I haven't taken any courses in modular arithmetic so I don't know, what is taught and what is not...

$\endgroup$
2
$\begingroup$

This is a great question!

This has been considered, and there is a key phrase to look for: "The Chinese Remainder Theorem." (With this phrase and MSE/your favorite search engine, you can find very many examples and exposition).

Let's clarify a bit. To find the intersection of the congruence classes $2_3$ and $1_4$ is equivalent to finding those $x$ which simultaneously satisfy $$ \begin{align} x &\equiv 2 \pmod 3 \\ x &\equiv 1 \pmod 4 \end{align}.\tag{1}$$ The Chinese Remainder Theorem asserts that since $3$ and $4$ are relatively prime, the set of such $x$ can be described as a single congruence class mod $3\cdot 4 = 12$, or rather that the set of $x$ satisfying $(1)$ is the set of $x$ satisfying $x \equiv a \pmod{12}$ for some $a$. As $5$ is one such element, this means that the set of $x$ satisfying $(1)$ consists exactly of those $x$ with $x \equiv 5 \pmod {12}$.

There are variants of the Chinese Remainder Theorem when the moduli are not relatively prime, in which case the result is a bit more complicated to state. And there are many ways to quickly compute the congruence classes of the final sets --- these can all be found by looking up some problems on the Chinese Remainder Theorem.

$\endgroup$
  • $\begingroup$ Wow, thanks! I've heard of the theorem but never knew that it would be so useful. The name sounds like it would only be applicable in some special cases : D. I'll take a deeper look into it. $\endgroup$ – Miksu Mar 24 '17 at 5:50

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.