Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2010/ia/paper-4/1e/b/solution
Past exam of the mathematics course of the University of Cambridge 2010 ia Paper 4 1E b Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-14
The modular inverse of modulo is , so the second modular congruence is . The third means , equivalently . Cancelling this common factor changes the modulus; it gives .
The first three conditions consequently combine to and odd, hence for an integer . The last condition becomesAs , multiplying by the modular inverse gives . ThusThe Chinese remainder theorem states that modular congruences with pairwise coprime moduli have a unique solution modulo their product. Here those moduli are , with product . The derivation proves necessity, and substitution gives , , and , proving sufficiency for the whole displayed class.
New to topics? Read the docs here!