Threading Thirty-One and Seventy-Three

Find whole numbers $m$ and $n$, allowing them to be negative, so that $$31m + 73n = 1.$$

Solution

Run Euclid’s algorithm on the two numbers, then unwind it. Dividing repeatedly, $$73 = 2 \cdot 31 + 11, \quad 31 = 2 \cdot 11 + 9, \quad 11 = 1 \cdot 9 + 2, \quad 9 = 4 \cdot 2 + 1,$$ which confirms the two numbers share no common factor, so a solution exists. Now read the chain backwards, expressing the final remainder $1$ in terms of earlier ones: $$1 = 9 - 4 \cdot 2 = 5 \cdot 9 - 4 \cdot 11 = 5 \cdot 31 - 14 \cdot 11 = 33 \cdot 31 - 14 \cdot 73.$$ So $m = 33$, $n = -14$, and indeed $31 \cdot 33 - 73 \cdot 14 = 1023 - 1022 = 1$. Every solution has the form $m = 33 + 73t$, $n = -14 - 31t$ for a whole number $t$, since one can shift a multiple of $73 \cdot 31$ between the two terms.