Past exam of the mathematics course of the University of Cambridge / 2009 / ia / Paper 4 / 2E / b / Solution

The integer $137$ is prime: none of the primes $2,3,5,7,11$ below $\sqrt{137}$ divides it. Since $43\not\equiv 0(\mathrm{mod}137)$, Fermat's little theorem gives $43^{136}\equiv 1$. Therefore $43^{135}$ is the modular inverse of $43$. The extended Euclidean algorithm yieldsand back-substitution gives $1=51(43)-16(137)$. ConsequentlyIndeed, $43\cdot 51=2193=16\cdot 137+1$, directly checking the required modular inverse.