How to find the intersection of two congruence classes 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...
 A: 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.
