Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2016/ia/paper-4/1e/solution

The extended Euclidean algorithm gives
Back-substituting in these equations produces the Bezout identity
Thus 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 obtain
Consequently the least positive representative is .

New to topics? Read the docs here!