Chinese Remainder Theorem Reference Cheat Sheet

Key Facts

• A congruence $x \equiv a \pmod{m}$ means that $m$ divides $x-a$, or $m \mid x-a$.
• The Chinese Remainder Theorem applies directly when the moduli $m_1,m_2,\ldots,m_k$ are pairwise coprime, meaning $\gcd(m_i,m_j)=1$ for $i \ne j$.
• If the moduli are pairwise coprime, the system $x \equiv a_i \pmod{m_i}$ has one unique solution modulo $M=m_1m_2\cdots m_k$.
• For each congruence, define $M_i=\frac{M}{m_i}$, where $M=m_1m_2\cdots m_k$.
• The modular inverse $y_i$ is chosen so that $M_i y_i \equiv 1 \pmod{m_i}$.
• A CRT solution is $x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$.
• For two congruences $x \equiv a \pmod{m}$ and $x \equiv b \pmod{n}$ with $\gcd(m,n)=1$, the solution is unique modulo $mn$.
• If moduli are not coprime, a solution exists only when $a_i \equiv a_j \pmod{\gcd(m_i,m_j)}$ for every pair of congruences.

Vocabulary

Congruence

A statement such as $x \equiv a \pmod{m}$ saying that $x$ and $a$ have the same remainder when divided by $m$.

Modulus

The positive integer $m$ in $x \equiv a \pmod{m}$ that determines the remainder system being used.

Pairwise coprime

A set of integers is pairwise coprime when every two different integers in the set have greatest common divisor $1$.

Modular inverse

The modular inverse of $a$ modulo $m$ is a number $a^{-1}$ such that $aa^{-1} \equiv 1 \pmod{m}$.

Residue class

A residue class modulo $m$ is the set of all integers congruent to the same remainder modulo $m$.

Unique modulo $M$

A solution is unique modulo $M$ when all solutions differ from it by a multiple of $M$.