Chinese Remainder Theorem Reference Cheat Sheet

The Chinese Remainder Theorem is a powerful method for solving systems of congruences with different moduli. This cheat sheet helps students organize the conditions, notation, and construction steps needed to solve CRT problems accurately. It is especially useful in number theory, contest math, cryptography, and modular arithmetic applications.

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

Common Mistakes to Avoid

Forgetting to check that the moduli are pairwise coprime is wrong because the standard CRT formula requires $\gcd(m_i,m_j)=1$ for every pair.
Using $M_i=m_i$ instead of $M_i=\frac{M}{m_i}$ is wrong because each $M_i$ must include all moduli except the one for its own congruence.
Finding the inverse of the wrong number is wrong because $y_i$ must satisfy $M_i y_i \equiv 1 \pmod{m_i}$ , not $m_i y_i \equiv 1 \pmod{M_i}$ .
Stopping before reducing the final answer is wrong because the solution should be written as $x \equiv r \pmod{M}$ with $0 \le r < M$ when possible.
Assuming non-coprime systems never have solutions is wrong because they can be consistent when $a_i \equiv a_j \pmod{\gcd(m_i,m_j)}$ .

Practice Questions

1 Solve the system $x \equiv 2 \pmod{3}$ , $x \equiv 3 \pmod{5}$ , and $x \equiv 2 \pmod{7}$ .
2 Solve the system $x \equiv 1 \pmod{4}$ and $x \equiv 4 \pmod{9}$ , and write the answer modulo $36$ .
3 Find the modular inverse of $10$ modulo $17$ , then use it to solve $10x \equiv 6 \pmod{17}$ .
4 Explain why the system $x \equiv 2 \pmod{6}$ and $x \equiv 5 \pmod{9}$ has no solution, using the greatest common divisor condition.

Understanding Chinese Remainder Theorem Reference

A useful way to picture a congruence is as a position on a repeating cycle. On a clock with twelve positions, numbers separated by twelve land in the same place. A system of congruences asks for one number that lands at specified positions on several cycles at once.

Each condition removes many possible numbers. When the cycle lengths have no shared factors, their patterns combine cleanly.

The full pattern does not repeat until every cycle has returned to its starting point together. This explains why the final repeating interval is much larger than any one modulus.

The construction method works because each built term is designed to affect one condition while becoming invisible to the others. Start with the product of all moduli, then remove one modulus from that product. The remaining factor contains every other modulus, so it is a multiple of each of them.

It therefore leaves a remainder of zero for all the other conditions. It only needs adjustment for the condition left out. A modular inverse provides that adjustment.

Multiplying by the inverse turns the remaining factor into a remainder of one for its selected modulus. Multiplying once more by the required remainder creates a term that contributes exactly the needed value in one place and zero everywhere else.

Finding inverses is often the part that needs the most care. Students can use trial multiplication for small moduli, but the extended Euclidean algorithm is more reliable for larger values. That algorithm works backward from the greatest common divisor and expresses one as a combination of two numbers.

When the greatest common divisor is one, the coefficient of one number gives an inverse of the other after reducing it to the correct cycle. A negative inverse is not a problem. It can be replaced by adding the modulus until a positive representative appears.

This is one reason modular arithmetic feels different from ordinary arithmetic. Many different integers can represent the same residue.

When moduli share a factor, the restrictions may disagree before any calculation begins. Think of two bus schedules that repeat at different intervals but must meet at the same time. If one condition requires an odd number and another requires an even number, no number can satisfy both.

If they agree on the shared pattern, the system can often be simplified before solving it. The final repeat length is then based on the least common multiple rather than simply multiplying every modulus.

In school problems, check compatibility early, keep each intermediate remainder reduced, and verify the final answer in every original condition. In computing, the same ideas support calendar cycles, data reconstruction, and parts of public key cryptography.

Sign in to save

Sign in to save

Chinese Remainder Theorem Reference Cheat Sheet

Related Tools

Related Labs

Related Worksheets

Related Infographics

Study as Flashcards

Key Facts

Vocabulary

Common Mistakes to Avoid

Practice Questions

Understanding Chinese Remainder Theorem Reference