An Initiative by SAARTHI IAS
Maarg Manthan · Topic 1.8

Remainder Theorem and Chinese Remainder Theorem

Quantitative Aptitude › Number System · Topic 1.8

The remainder theorem for numbers says that the remainder of a sum, difference, product or power can be found by combining the remainders of the parts. The Chinese Remainder Theorem finds a number that leaves given remainders on division by several pairwise co-prime numbers.

Share:
Remainder Theorem and Chinese Remainder Theorem - Quantitative Aptitude - MaargX UPSC Maarg Manthan

Quick Answer

The remainder theorem for numbers says that the remainder of a sum, difference, product or power can be found by combining the remainders of the parts. The Chinese Remainder Theorem finds a number that leaves given remainders on division by several pairwise co-prime numbers.

At a Glance

  • Sum rule Add the remainders, then reduce
  • Product rule Multiply the remainders, then reduce
  • Power rule Use a short cycle or a negative remainder
  • CRT condition Divisors pairwise co-prime
  • CRT solution Unique up to the product of the divisors
  • Divisible Remainder 0

Where Does It Fit?

This topic follows Factorial Values and Number of Trailing Zeros in a Factorial and generalises Divisibility Rules for 2 to 19, where divisibility is the case of remainder zero. It leads to Fermat’s Little Theorem and Wilson’s Theorem Applications and later to the congruence-style problems in Least Number Divisible by Given Numbers Leaving a Specified Common Remainder.

How Do You Find Remainders of Sums, Products and Powers?

In short: replace each number by its remainder, do the operation, and take the remainder again.

Remainder rules

  • (a + b) mod m = ((a mod m) + (b mod m)) mod m
  • (a × b) mod m = ((a mod m) × (b mod m)) mod m
  • an mod m = (a mod m)n mod m
  • Negative remainders: a remainder of m – 1 can be written as -1. For example, 7 leaves remainder 3 on division by 4, and 3 = 4 – 1, so 7 ≡ -1 (mod 4). Then 7100 ≡ (-1)100 = 1.
  • Product example: 12 × 15 × 17 divided by 7: the remainders are 5, 1 and 3. 5 × 1 × 3 = 15, which leaves 1.
  • Power example: 2100 divided by 7: 23 = 8 leaves 1, so 299 leaves 1, and 2100 leaves 2.

What Is the Chinese Remainder Theorem?

In short: if the divisors are pairwise co-prime, there is exactly one remainder class modulo their product that satisfies all the given remainders.

  • Find the smallest N with N ≡ 2 (mod 3), N ≡ 3 (mod 5), N ≡ 2 (mod 7). Numbers satisfying the last two are 23, 58, 93, … and 23 also satisfies the first. So N = 23.
  • All solutions are 23 + 105k, since 3 × 5 × 7 = 105.
  • For N ≡ 3 (mod 4) and N ≡ 2 (mod 5), the smallest is 7, and the general solution is 7 + 20k.
Conditions Smallest N General solution
N ≡ 3 (mod 4), N ≡ 2 (mod 5) 7 7 + 20k
N ≡ 2 (mod 3), N ≡ 3 (mod 5), N ≡ 2 (mod 7) 23 23 + 105k

The method used in Least Number Divisible by Given Numbers Leaving a Specified Common Remainder is related: when the remainder is the same for all divisors, the least number is the LCM plus the remainder.

How Do You Solve Remainder Problems Quickly?

In short: reduce first, look for a pattern, and use negative remainders when they make the numbers smaller.

  • Reduce every base modulo the divisor before raising to a power.
  • Look for a power that gives remainder 1 or -1.
  • For 1717 divided by 18, write 17 ≡ -1, so the remainder of (-1)17 is -1, which is 17.
  • For 7100 divided by 4, 7 ≡ -1, so the remainder is (-1)100 = 1. A second check: 7 ≡ 3 and 32 = 9 leaves 1, so every even power of 7 leaves 1.

Solved Examples

Example 1

Question: Find the remainder when 12 × 15 × 17 is divided by 7.

  1. 12 leaves 5, 15 leaves 1, 17 leaves 3 on division by 7.
  2. Multiply the remainders: 5 × 1 × 3 = 15.
  3. 15 divided by 7 leaves 1.

Answer: 1.

Example 2

Question: Find the remainder when 2100 is divided by 7.

  1. 23 = 8 leaves remainder 1.
  2. 100 = 3 × 33 + 1, so 2100 leaves the same remainder as 21.
  3. The remainder is 2.

Answer: 2.

Example 3

Question: Find the smallest positive number that leaves remainders 2, 3, 2 when divided by 3, 5, 7.

  1. Numbers leaving 3 on division by 5: 3, 8, 13, 18, 23, …
  2. Among these, those leaving 2 on division by 7: 23 (23 = 3 × 7 + 2).
  3. Check 23 on division by 3: 23 = 3 × 7 + 2.

Answer: 23.

Example 4

Question: Find the smallest N that leaves remainder 3 on division by 4 and remainder 2 on division by 5.

  1. Numbers leaving 2 on division by 5: 2, 7, 12, 17, …
  2. Test each on division by 4: 2 leaves 2, 7 leaves 3.
  3. So N = 7, and the general solution is 7 + 20k.

Answer: 7.

Example 5

Question: Find the remainder when 1717 is divided by 18.

  1. 17 leaves remainder 17 on division by 18, which is -1.
  2. (-1)17 = -1.
  3. A remainder of -1 corresponds to 18 – 1 = 17.

Answer: 17.

Shortcuts and Tricks

  • Reduce each factor modulo the divisor before multiplying.
  • Use -1 for a remainder of m – 1, so that powers become +1 or -1.
  • Look for the smallest power with remainder 1, then divide the exponent by that power.
  • For CRT, list numbers meeting the largest modulus first, since they are fewer.
  • The CRT solution repeats after the product of the pairwise co-prime moduli.

Common Mistakes

  • Adding remainders without reducing the sum again.
  • Giving a negative number as the final remainder instead of adding the divisor.
  • Using CRT when the divisors are not pairwise co-prime.
  • Reducing the exponent modulo the divisor instead of modulo the cycle length.
  • Forgetting that the CRT solution is a set of numbers, not a single number.

Practice Questions

  1. What is the remainder when 7100 is divided by 4?
  2. What is the remainder when 100 × 101 × 102 is divided by 7?
  3. What is the remainder when 550 is divided by 6?
  4. Find the smallest number leaving remainders 1 and 2 when divided by 3 and 4.
  5. What is the remainder when 210 is divided by 11?

Answers: 1) 1; 2) 3, since the remainders are 2, 3, 4 and 2 × 3 × 4 = 24 leaves 3; 3) 1; 4) 10; 5) 1.

Why Is This Topic Important?

  • Wide use Remainders appear in factorials, powers and calendar-style questions.
  • Concept Teaches how to reduce large numbers to small ones.
  • Link Prepares Fermat’s theorem in Fermat’s Little Theorem and Wilson’s Theorem Applications.
  • Link Used for the cycle questions in Cyclicity of Numbers in Finding Unit Digits.

What Comes Next?

The next topic is Fermat’s Little Theorem and Wilson’s Theorem Applications, which gives two shortcuts for remainders with prime divisors.

Key Terms and Formulas

  • Remainder What is left after division
  • Congruence a ≡ b (mod m) means m divides a – b
  • Modulus The divisor m
  • Pairwise co-prime Every pair of divisors has HCF 1
  • Negative remainder A remainder written as r – m
  • Residue class All numbers with the same remainder

Exam Corner

Points to Remember

  • Remainders can be added and multiplied before the final reduction.
  • A remainder of m – 1 equals -1 modulo m.
  • CRT needs pairwise co-prime moduli.
  • The CRT solution repeats after the product of the moduli.
  • Remainder 0 means divisible.

Do Not Confuse With

  • Remainder vs quotient The remainder is what is left; the quotient is how many times.
  • Divisible vs remainder 1 Divisible means remainder 0.
  • Negative remainder vs true remainder Add the divisor to turn -1 into m – 1.
  • CRT vs LCM CRT finds a number; LCM finds a common multiple.

Memory Hook

Reduce, combine, reduce again; and for co-prime moduli, search the largest first.

GS Relevance

Remainder questions appear in SSC CGL and CAT in many forms: products, powers, factorials and linked divisors.

Frequently Asked Questions

What is the remainder theorem for numbers?

The remainder theorem for numbers states that the remainder of a sum, difference, product or power can be found from the remainders of its parts. You replace each number by its remainder, perform the operation, and take the remainder again. For example, the remainder of 12 times 15 times 17 on division by 7 is 1.

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem says that if the divisors are pairwise co-prime, there is exactly one remainder class modulo their product that leaves the given remainders on division by each divisor. For remainders 2, 3 and 2 on division by 3, 5 and 7, the smallest number is 23.

How do you find the remainder of a large power?

To find the remainder of a large power, reduce the base modulo the divisor and look for a power that leaves remainder 1 or negative 1. Then divide the exponent by that power length. For example, 2 cubed leaves remainder 1 on division by 7, so 2 to the power 100 leaves the same remainder as 2.

What is a negative remainder?

A negative remainder is a remainder written as the actual remainder minus the divisor, such as negative 1 in place of m minus 1. It makes powers easier, because negative 1 raised to an odd power is negative 1 and to an even power is 1. Add the divisor at the end to get a standard remainder.

When can the Chinese Remainder Theorem be used?

The Chinese Remainder Theorem can be used only when the divisors are pairwise co-prime, meaning every pair of divisors has highest common factor 1. If two divisors share a factor, a solution may not exist or may not be unique, and a separate check of the remainders is required.

PYQ Practice — Statement Analysis

1 The remainder when 2100 is divided by 7 is 2.
True

23 leaves 1, and 100 leaves remainder 1 on division by 3.

2 The smallest number leaving remainders 2, 3, 2 on division by 3, 5, 7 is 23.
True

23 = 3 × 7 + 2, 4 × 5 + 3 and 7 × 3 + 2.

3 The Chinese Remainder Theorem applies to any set of divisors.
False

The divisors must be pairwise co-prime.

4 The remainder when 1717 is divided by 18 is 17.
True

17 ≡ -1, so the power is -1, which equals 17.

Share: