+0

# Number Theory

0
47
1

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.)

May 12, 2022

#1
+9457
0

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}$$.

May 12, 2022