Past exam of the mathematics course of the University of Cambridge / 2009 / ia / Paper 4 / 2E (Numbers and Sets)

Eliminate $x$ by twice the first modular congruence minus three times the second. This givesThe modular inverse of $3$ is $16$, because $3\cdot 16=48\equiv 1$. Hence $y\equiv 16\cdot 13\equiv 20$. Substitution into the second modular congruence gives $6x\equiv 14-7(20)\equiv 15$, and $6^{-1}\equiv 8$, so $x\equiv 8\cdot 15\equiv 26$. ThusIn particular, $(x,y)=(26,20)$ works: $9(26)+12(20)=474=10(47)+4$ and $6(26)+7(20)=296=6(47)+14$. The elimination is reversible because $3$ and $6$ have modular inverses, so the displayed classes contain all solutions.

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.