Let $a,b \in \mathbb{Z}$, and let $m,n \in \mathbb{Z}$ satisfy $m>0$ and $n>0$. The system of congruences
paragraph
admin
\begin{align*}
x \equiv a \pmod{m}
\end{align*}
latex_env
admin
and
paragraph
admin
\begin{align*}
x \equiv b \pmod{n}
\end{align*}
latex_env
admin
has a solution $x \in \mathbb{Z}$ if and only if
paragraph
admin
\begin{align*}
a \equiv b \pmod{\gcd(m,n)}.
\end{align*}
latex_env
admin
When a solution exists, the set of all integer solutions is a single congruence class modulo $\operatorname{lcm}(m,n)$: if $x_0 \in \mathbb{Z}$ is one solution, then an integer $x \in \mathbb{Z}$ is a solution if and only if
paragraph
admin
\begin{align*}
x \equiv x_0 \pmod{\operatorname{lcm}(m,n)}.
\end{align*}