HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
  1. Notes
  2. /Congruences and the Chinese Remainder Theorem: Quick Revision
Mathematics

Congruences and the Chinese Remainder Theorem: Quick Revision

A brief note on congruences: the rules, cancelling with the gcd, remainders of large powers, divisibility tests, linear congruences and inverses, and the Chinese remainder theorem, with practice, a program and questions.

StemPy LabWritten by StemPy Lab
Log in to save

A brief note on Congruences and the Chinese Remainder Theorem. Read it before a test. Try each question at the end before you open its answer.

Congruences

  • Meaning: a≡b(modm)a \equiv b \pmod ma≡b(modm) when m∣a−bm \mid a - bm∣a−b, that is, the same remainder on division by mmm.
  • Rules: add, subtract, multiply and take powers on both sides; any polynomial with integer coefficients keeps the congruence.
  • Cancelling: from ac≡bc(modm)ac \equiv bc \pmod mac≡bc(modm) you get a≡b(modm/gcd⁡(c,m))a \equiv b \pmod{m/\gcd(c, m)}a≡b(modm/gcd(c,m)).
  • Large powers: find a small power ak≡±1a^k \equiv \pm 1ak≡±1 and cut the exponent by kkk.
  • Squares: 000 or 111 modulo 444; 000, 111 or 444 modulo 888.

Linear congruences

  • Solvable: ax≡b(modm)ax \equiv b \pmod max≡b(modm) exactly when d=gcd⁡(a,m)d = \gcd(a, m)d=gcd(a,m) divides bbb; then ddd solutions modulo mmm.
  • Method: divide aaa, bbb and mmm by ddd, then multiply by the inverse.
  • Inverse: exists exactly when gcd⁡(a,m)=1\gcd(a, m) = 1gcd(a,m)=1; the extended Euclidean algorithm finds it.

The Chinese remainder theorem

  • Pairwise coprime moduli: exactly one solution modulo the product.
  • Lifting: x=a1+m1tx = a_1 + m_1 tx=a1​+m1​t, then reduce modulo the next modulus.
  • Shared factor: solvable when gcd⁡(m,n)∣a−b\gcd(m, n) \mid a - bgcd(m,n)∣a−b, unique modulo the lcm.
  • Counting: the number of solutions modulo m1m2m_1 m_2m1​m2​ is the product of the counts.

A worked example

Find xxx with x≡4(mod5)x \equiv 4 \pmod 5x≡4(mod5) and x≡5(mod9)x \equiv 5 \pmod 9x≡5(mod9).

  1. Lift. x=5+9tx = 5 + 9tx=5+9t, and 5+9t≡4(mod5)5 + 9t \equiv 4 \pmod 55+9t≡4(mod5) gives 4t≡44t \equiv 44t≡4, so t≡1t \equiv 1t≡1.
  2. Answer. x=14x = 14x=14, unique modulo 454545.
  3. Check. 14=2×5+4=9+514 = 2 \times 5 + 4 = 9 + 514=2×5+4=9+5.

Practice with new numbers

A program to try

The program checks a power, an inverse and a small system.

Read it first. Then run it. Does each line agree with the rules above?

1. Change the system to x≡2(mod6)x \equiv 2 \pmod 6x≡2(mod6) and x≡1(mod4)x \equiv 1 \pmod 4x≡1(mod4). Why is the list empty?

Mistakes to avoid

  • Cancelling a factor that shares a factor with the modulus.
  • Reducing an exponent modulo mmm. Only the base is reduced modulo mmm.
  • One solution when there are gcd⁡(a,m)\gcd(a, m)gcd(a,m) of them.
  • Using the theorem with moduli that share a factor without checking that the remainders agree.

Check yourself

  1. Find the remainder of 21002^{100}2100 on division by 111111.
  1. Solve 7x≡1(mod26)7x \equiv 1 \pmod{26}7x≡1(mod26).
  1. Solve x≡1(mod4)x \equiv 1 \pmod 4x≡1(mod4) and x≡3(mod5)x \equiv 3 \pmod 5x≡3(mod5).
  1. How many solutions has 4x≡6(mod10)4x \equiv 6 \pmod{10}4x≡6(mod10) from 000 to 999?

Sources

  • David M. Burton, Elementary Number Theory, Chapter 4, The Theory of Congruences.
← All Notes
← Factorials, Irrational Numbers, Digits and the Floor Function: Quick RevisionFermat, Euler and Wilson: Quick Revision →
More onNumber Theory

Discussion (0)

Log in to join the discussion.

Loading…

On this page

  1. Congruences
  2. Linear congruences
  3. The Chinese remainder theorem
  4. A worked example
  5. Practice with new numbers
  6. A program to try
  7. Mistakes to avoid
  8. Check yourself
  9. Sources

Goes with the lesson

  1. The Chinese remainder theoremCongruences and the Chinese Remainder Theorem

More notes on this topic

  1. Diophantine Equations and Pythagorean Triples: Quick Revision
  2. Fermat, Euler and Wilson: Quick Revision
  3. Factorials, Irrational Numbers, Digits and the Floor Function: Quick Revision
  4. Common Factors, the Euclidean Algorithm and Divisors: Quick Revision
  5. Division, Divisibility Rules and Primes: Quick Revision
All notes on this topic →