Determine the multiplicative inverse of the following numbers by using Fermat’s Little Theorem. Give your answer as the least non-negative residue.
(a) $5 \pmod {11}$
(b) $9 \pmod {23}$
(c) $2 \pmod {37}$
(d) $5 \pmod {41}$
For integer $a$ and prime $p$, where $p \not \mid a$, we have
$$ a^{p-1} \equiv 1 \pmod p \; \implies \; a(a^{p-2}) \equiv 1 \pmod p \; \implies \; a^{-1} \equiv a^{p-2} \pmod p $$
(a) Here 11 is prime, and does not divide 5, and so
$ 5^{-1} \equiv 5^{9} \pmod {11} $
Using $5^3 \equiv 125 \equiv 4 \pmod {11}$, we have
$ 5^{-1} \equiv (5^{3})^3 \equiv 4^3 \equiv 64 \pmod {11} $
$ 5^{-1} \equiv 9 \pmod {11} $
(b) Here 23 is prime, and does not divide 9, and so
$ 9^{-1} \equiv 9^{21} \pmod {23} $
Using $9^7 \equiv 4782969 \equiv 4 \pmod {23}$, we have
$ 9^{-1} \equiv (9^{7})^3 \equiv 64 \pmod {23} $
$ 9^{-1} \equiv 18 \pmod {23} $
(c) Here 37 is prime, and does not divide 2, and so
$ 2^{-1} \equiv 2^{35} \pmod {37} $
Using $2^7 \equiv 128 \equiv 17 \pmod {37}$, we have
$ 2^{-1} \equiv (2^{7})^5 \equiv 17^5 \pmod {37} $
Using $17^2 \equiv 289 \equiv 30 \pmod {37}$, we have
$ 2^{-1} \equiv (17^2)^2 \times 17 \equiv 30^2 \times 17 \equiv 15300 \pmod {37} $
$ 2^{-1} \equiv 19 \pmod {37} $
(d) Here 41 is prime, and does not divide 5, and so
$ 5^{-1} \equiv 5^{39} \pmod {41}$
Using $5^{13} \equiv 1220703125 \equiv 39 \pmod {41}$, we have
$ 5^{-1} \equiv (5^{13})^3 \equiv 39^3 \equiv 59319 \pmod {41}$
$ 5^{-1} \equiv 33 \pmod {41} $