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
  • 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. Python Labs
  2. /A solver for the Chinese remainder theorem
MathematicsMediumHigh School (11–12)Number Theory

A solver for the Chinese remainder theorem

You will write a solver for two congruences, with moduli that may share a factor. It must also say when there is no solution.

The idea. Write x=a+mtx = a + mtx=a+mt and put it into x≡b(modn)x \equiv b \pmod nx≡b(modn). This gives mt≡b−a(modn)mt \equiv b - a \pmod nmt≡b−a(modn), a linear congruence for ttt. It is solvable when g=gcd⁡(m,n)g = \gcd(m, n)g=gcd(m,n) divides b−ab - ab−a, and the answer is unique modulo lcm⁡(m,n)\operatorname{lcm}(m, n)lcm(m,n).

Your tasks.

  1. Finish inverse(a, m). Return the inverse of aaa modulo mmm by trying 1,2,…,m−11, 2, \dots, m - 11,2,…,m−1, or None if there is none.
  2. Finish solve_pair(a, m, b, n). Return the pair (x, L) where L is the lcm of mmm and nnn and 0≤x<L0 \le x < L0≤x<L, or None when there is no solution.
  3. Finish sunzi(). Use solve_pair twice to solve x≡2(mod3)x \equiv 2 \pmod 3x≡2(mod3), x≡3(mod5)x \equiv 3 \pmod 5x≡3(mod5), x≡2(mod7)x \equiv 2 \pmod 7x≡2(mod7), and return x.

Run it first, just as it is. The checker at the end prints FAIL for each task. Then do the tasks one at a time, and run the program again after each one. A Hint appears under every check that still fails.

When every line says PASS, solve the eggs problem: one left over for 2,3,4,5,62, 3, 4, 5, 62,3,4,5,6 and none left for 777. Two calls of solve_pair are enough.

StemPy LabContributed by StemPy Lab
python
Loading Python runtime…

A worked solution

Run your code once to unlock the worked solution.

Have you tried it?

Do the tasks in the editor first, and run the checker after each one. Its hints help when a check fails. When you are ready, compare your code with this solution.

Log in to save
← All Labs
← Fast powers modulo mEuler's totient two ways →
More onNumber Theory

Discussion (0)

Log in to join the discussion.

Loading…

More labs on this topic

  1. Pythagorean triples by formula and by searchMedium
  2. Every solution of a linear equationMedium
  3. Orders, primitive roots and WilsonMedium
  4. Euler's totient two waysMedium
  5. Fast powers modulo mMedium
All labs on this topic →