Chinese Remainder Theorem

By RCM, IITian · October 6, 2026 · Updated October 19, 2026 · 35 min study · Mathematics

Also in: RMO Number Theory Congruences & Orders

Mathematics IOQM RMO Congruences Congruences & Orders

The Chinese Remainder Theorem is very important in Number Theory for examinations such as IOQM, RMO and other Olympiad examinations. The Chinese Remainder Theorem helps in simultaneous equations involving congruences. The simultaneous equations involving the congruences cannot be solved easily using ordinary algebraic methods. To solve them, it is required to have clear conceptual clarity on using the Chinese Remainder Theorem. Here, we will be solving a typical problem involving the Chinese Remainder Theorem and the concepts involved in it.

Chinese Remainder Theorem – Problem 1

Solve for x if,

$\begin{matrix} x \equiv 7 (\mod 11) \\ x \equiv 11 (\mod 13) \\ x \equiv 17 (\mod 23) \end{matrix}$

Solution :

Given that $\begin{matrix} x \equiv 7 (\mod 11) \\ x \equiv 11 (\mod 13) \\ x \equiv 17 (\mod 23) \end{matrix}$

We have to find the value of x such that it satisfies all the above equations. The congruences are of mod11, mod 13 and mod 23.

Hence to satisfy all the above congruence modulo equations, we are required to find x such that ,

$x \equiv A (\mod M)$

Where M is the product of all above congruence modulo given.

$x \equiv (r_{1} M_{1} a_{1} + r_{2} M_{2} a_{2} + r_{3} M_{3} a_{3})(\mod M)$

Let,

$M = r_{1} r_{2} r_{3} = 11 \times 13 \times 23 = 3289$

$A = r_{1} M_{1} a_{1} + r_{2} M_{2} a_{2} + r_{3} M_{3} a_{3}$

$M_{1} = \frac{M}{r_{1}} = \frac{3289}{11} = 299$

$M_{2} = \frac{M}{r_{2}} = \frac{3289}{13} = 253$

$M_{3} = \frac{M}{r_{3}} = \frac{3289}{23} = 143$

From above , the only unknowns in above are $r_{1}, r_{2}, r_{3}$ .

These values can be found out by solving the simultaneous congruences,

$M_{1} a_{1} \equiv 1 \mod (r_{1})$

$M_{2} a_{2} \equiv 1 \mod (r_{2})$

$M_{3} a_{3} \equiv 1 \mod (r_{3})$

The above requires solving,

$299 a_{1} \equiv 1 \mod (11)$

$253 a_{2} \equiv 1 \mod (13)$

$143 a_{3} \equiv 1 \mod (23)$

Application of Chinese Remainder Theorem

299=297+2=27X11+2. Hence,

$299 \equiv 2 (\mod 11)$ , comparing it with,

$299 a_{1} \equiv 1 \mod (11)$ , we get,

$2 a_{1} = 11 + 1 = 12 \Rightarrow a_{1} = 6$

Similarly from $253 a_{2} \equiv 1 \mod (13)$ and $143 a_{3} \equiv 1 \mod (23)$

$a_{2} = 11, a_{3} = 14$

By substituting all above values in $x \equiv (r_{1} M_{1} a_{1} + r_{2} M_{2} a_{2} + r_{3} M_{3} a_{3})(\mod M)$ , we get,

$x \equiv (7.299.6 + 11.253.11 + 17.143.14)(\mod 3289)$ . Hence,

$x \equiv 77205 (\mod 3289)$

$77205 = 23 \times 3289 + 1558$ , Hence,

Final answer for x is given by,

x
≡
1558
(
mod
3289
)

Conclusion

Thus, the above system of congruences could be solved using the following topics and concepts:
1 Chinese Remainder Theorem
2 Pair wise co prime integers
3 Modular arithmetic
4 Modular multiplicative inverse
5 Linear congruences solutions
6 Substitution/ Elimination of congruence
For any clarifications on the above topic and solution, write to us at : https://mathsnscience.com/contact/
For the video solution, please visit the channel run by the same person as this site.
YouTube Channel Name : maths&science by iitian

Channel link : https://www.youtube.com/@mathsciencebyiitian

The thumbnail image of the video is

Best of luck to every one.

Chinese Remainder Theorem

Chinese Remainder Theorem – Problem 1

Solution :

Application of Chinese Remainder Theorem

Conclusion

Leave a comment Cancel reply

Related Articles & Resources

Exponential Equations | Quadratic Functions | Algebra – Can you solve it?

Greatest Integer Function | Quadratic equation -1

Diophantine Equations – Can you solve this?-1