Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2016/ia/paper-4/1e/solution
Past exam of the mathematics course of the University of Cambridge 2016 ia Paper 4 1E Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-06
The extended Euclidean algorithm givesBack-substituting in these equations produces the Bezout identityThus one integer solution is . In fact, subtracting this Bezout identity from any other solution and using that and are coprime integers gives all solutions: , , where .
For the modular arithmetic calculation, is a prime number and is coprime to it, so Fermat little theorem gives . Since , and the preceding Bezout identity identifies as the modular multiplicative inverse of , we obtainConsequently the least positive representative is .
New to topics? Read the docs here!