CodeChef Logo CodeChef Logo
Courses

Programming and DSA

Learn to think like a programmer. Develop your problem-solving skills with essential data structures and algorithms.

Career Paths

From beginner to job-ready. Explore our curated career paths designed to help you succeed in the tech industry.

Other Courses

Programming and DSA

Explore courses

Catalogue

Programming and DSA

Learn to think like a programmer. Develop your problem-solving skills with essential data structures and algorithms.

Career Paths

From beginner to job-ready. Explore our curated career paths designed to help you succeed in the tech industry.

Other Courses

Explore courses
Practice Compete Compiler
Upgrade to Pro
Courses

Programming and DSA

Learn to think like a programmer. Develop your problem-solving skills with essential data structures and algorithms.

Career Paths

From beginner to job-ready. Explore our curated career paths designed to help you succeed in the tech industry.

Other Courses

Programming and DSA

Explore courses

Catalogue

Programming and DSA

Learn to think like a programmer. Develop your problem-solving skills with essential data structures and algorithms.

Career Paths

From beginner to job-ready. Explore our curated career paths designed to help you succeed in the tech industry.

Other Courses

Explore courses
Practice Compete Compiler
Home » Wiki » Very brief tutorial for Chinese Remainder Theorem

Very brief tutorial for Chinese Remainder Theorem

You can learn CRT mostly from it's wikipedia article.

Break General modulo into prime power modulo's
A summary: Basically when we have to compute something modulo n where n is not prime, according to this theorem, we can break this kind of questions into cases where the number by which you are taking modulo's is a prime power.

This can be done by write n in its prime representation n = p1q1. . . pkqk

Compute modulo p^k by usual methods
Many times we can use standard tricks to find answer modulo p^k.

Merge those answers
After getting modulo p^k answers, we can merge them using CRT. For that see the example given in the wikipedia page.

Short Example
Compute a^b % n assume a = 4 and n = 6.
Write n = 6 = 2 * 3
Compute a^b % 2 = 0
Compute a^b % 3 = 1
Now merge them using CRT. See the formula given in the wikipedia to merge it.

Details of Merging
Assume we want to find a % n.
Let n = p1 * p2.
Find a % p1 and a % p2. Call a % p1 = x1
Call a % p2 = x2; For finding a % n. We can do following.
Write a % n = x1 * alpha1 + x2 * alpha2; (Proof is very simple).
where alpha1 is such that
alpha1 = 1 mod p1
and alpha1 = 0 mod p2

Similarly define alpha2
where alpha1 is such that
alpha2 = 0 mod p1
and alpha2 = 1 mod p2

So basically find alpha1, alpha2. For finding these, you need to solve two equations of two variables. That can be done by simplifying the equations written above.

Finally your answer will x1 * alpha1 + x2 * alpha2.

Sample Implementation
See the following code

Workden, MNR PRIDE, 14, HAL Old Airport Rd, Domlur I Stage, 1st Stage, DOMLUR, Bengaluru, Karnataka 560071 [email protected] +91 95911 47880
Find us online

ROADMAPS

Learn Python
Learn Java
Learn C
Learn C++
Data structures and Algorithms
Competitive Programming
More Roadmaps

CAREER PATHS

React JS Developer
SQL for Data Analysis
Frontend Developer
Java Backend Developer
Data Analysis using Python
Python Backend Developer
C++ Developer

COMPILERS

HTML online compiler
C++ online compiler
C online compiler
Java online compiler
Python online compiler
SQL online compiler
JavaScript online compiler
React online compiler
More compilers

COMPANY

About us
For colleges
Coding Contests
Blogs
Contact us
Privacy Policy

© 2025 CodeChef Inc. All rights reserved.

We use cookies to improve your experience and for analytical purposes. Read our Privacy Policy and Terms to know more. You consent to our cookies if you continue to use our website.