Given that 13^(-1) = 29 (mod 47), find \(17\)^(-1) (mod 47), as a residue modulo 47. (Give a number between 0 and 46, inclusive.)
+9519 Note that \(13 + 2(17) = 47\).
Multiply both sides by 29 gives
\(13 \times 29 + 2 \times 17 \times 29 = 47 \times 29 \equiv 0 \pmod{47}\\ 1 + 17 \times (2 \times 29) \equiv 0 \pmod {47}\\ 17 \times (-2\times 29) \equiv 1\pmod{47}\\ 17 \times (-58) \equiv 1 \pmod{47}\\ 17 \times 36 \equiv 1 \pmod{47} \)
Therefore, by definition of modular inverse, \(17^{-1} \equiv 36 \pmod{47}\).
