Modular Inverse Finding
Recall that if $ b $ is a residue $ \pmod{m} $, then the modular inverse of $ b $ is the residue $ c $ for which $ bc \equiv 1\pmod{m} $. The table below shows the inverses of the first 9 positive residues modulo 47. \begin{array}{c|ccccccccc}
\text{$ b $} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
\text{inverse of $ \,b $} & 1 & 24 & 16 & 12 & 19 & 8 & 27 & 6 & 21
\end{array}Find the modular inverse of $ 35\pmod{47} $.
Express your answer as an integer from $ 0 $ to $ 46 $, inclusive.
- 1
- 2
- 3
- +
- 4
- 5
- 6
- -
- 7
- 8
- 9
- $\frac{a}{b}$
- .
- 0
- =
- %
- $a^n$
- $a^{\circ}$
- $a_n$
- $\sqrt{}$
- $\sqrt[n]{}$
- $\pi$
- $\ln{}$
- $\log$
- $\theta$
- $\sin{}$
- $\cos{}$
- $\tan{}$
- $($
- $)$
- $[$
- $]$
- $\cap$
- $\cup$
- $,$
- $\infty$
Solution
We want to find the residue $ c $ such that $ 35c \equiv 1 \pmod{47} $. Recall that, since 35 is relatively prime to 47, this inverse exists and is unique. To make use of the table we are given, we notice that $ 35 = 5\cdot 7 $. We can multiply both sides of $ 35c \equiv 1\pmod{47} $ by the inverse of 5 to obtain \begin{align*}
19\cdot 5 \cdot 7 \cdot c &\equiv 19\cdot 1 \pmod{47} \implies \\
(19\cdot 5) \cdot 7 \cdot c &\equiv 19 \pmod{47} \implies \\
1 \cdot 7 \cdot c &\equiv 19 \pmod{47}.\\\end{align*}
Now we can multiply both sides by 27, the inverse of 7, to find \begin{align*}
27\cdot 7 \cdot c &\equiv 27\cdot 19 \pmod{47} \implies \\
c &\equiv 513 \pmod{47}.\end{align*}
Subtracting 470 from 513 does not change its residue (mod 47), so we have $ c\equiv 43\pmod{47} $. Since $ 0\leq 43 < 47 $, $ \boxed{43} $ is the desired residue.
Remark: More generally, the approach above shows that $ (ab)^{-1}=b^{-1}a^{-1} $, where $ b^{-1} $ denotes the modular inverse of $ b $.
Freeflows