Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

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.
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 .
Final answer
43