Browse · MATH
Printjmc
number theory intermediate
Problem
Recall that if is a residue , then the modular inverse of is the residue for which . The table below shows the inverses of the first 9 positive residues modulo 47. \begin{array}{c|ccccccccc}
$b$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
inverse of $\,b$ & 1 & 24 & 16 & 12 & 19 & 8 & 27 & 6 & 21
\end{array}Find the modular inverse of .
Express your answer as an integer from to , inclusive.
Express your answer as an integer from to , inclusive.
Solution
We want to find the residue such that . 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 . We can multiply both sides of by the inverse of 5 to obtain Now we can multiply both sides by 27, the inverse of 7, to find Subtracting 470 from 513 does not change its residue (mod 47), so we have . Since , is the desired residue.
Remark: More generally, the approach above shows that , where denotes the modular inverse of .
Remark: More generally, the approach above shows that , where denotes the modular inverse of .
Final answer
43