Using Fermat's Little Theorem or Euler's Theorem to find the Multiplicative Inverse -- Need some help understanding the solutions here.

Question

The answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean algorithm.
a. $8^{-1}\bmod17=8^{17-2}\bmod17=8^{15}\bmod17=15\bmod17$
b. $5^{-1}\bmod23=5^{23-2}\bmod23=5^{21}\bmod23=14\bmod23$
c. $60^{-1}\bmod101=60^{101-2}\bmod101=60^{99}\bmod101=32\bmod101$
d. $22^{-1}\bmod211=22^{211-2}\bmod211=22^{209}\bmod211=48\bmod211$

The above is using Fermat's little theorem to find the multiplicative inverse of some modular functions. However, there is a final step just before arriving at the answer that I do not understand how to solve, except to solve it by factoring. Factoring takes a very long time.

Basically, I don't see how the answers move from the third step to the fourth step aside from arriving at the answer by factoring. There has to be a better way using Fermat's Theorem or Euler's Theorem.

Answer 1

Bill's way seems great. Here's another approach (with the goal of finding easily reducible powers)

\begin{align} 8^{15}\pmod {17} &\equiv 2^{45}\\ &\equiv 2\cdot (2^{4})^{11}\\ &\equiv 2\cdot (-1)^{11} \tag{$16 \equiv -1$}\\ &\equiv 15 \tag{$15 \equiv -2$} \end{align}

---

\begin{align} 5^{21}\pmod {23} &\equiv 5\cdot 5^{20}\\ &\equiv 5\cdot 25^{10}\\ &\equiv 5\cdot 2^{10} \tag{$25 \equiv 2$}\\ &\equiv 5\cdot 32^2\\ &\equiv 5\cdot 9^2 \tag{$32 \equiv 9$}\\ &\equiv 5\cdot 12 \tag{$81 \equiv 12$}\\ &\equiv 14 \tag{$60 \equiv 14$} \end{align}

---

\begin{align} 60^{99}\pmod {101} &\equiv 10^{99}&\cdot 6^{99}\\ &\equiv 10\cdot 100^{49}&\cdot 6^4 \cdot (7776)^{19}\\ &\equiv -10&\cdot -6^4\\ &\equiv 12960\\ &\equiv 32 \end{align}

---

\begin{align} 22^{209}\pmod {211} &\equiv (2\cdot11)^{11\cdot19}\\ &\equiv ?\\ &\text{This is where the superiority of Bill's approach becomes obvious} \end{align}

Answer 2

The excerpt does not indicate how they compute the power in $\, a^{\large p−2}\equiv a^{\large −1}\pmod{\! p}.\,$ One common method is to use powering by repeated squaring. You remark "but this is very time consuming. I am looking for a better way". For manual computations it is often easier to use Gauss's algorithm or other convenient variations of the extended Euclidean algorithm. Here that takes under a minute of purely mental arithmetic as below.

$\bmod 17\!:\ \ \ \ \ \ \dfrac{1}8\equiv \dfrac{2}{16}\equiv \dfrac{2}{-1}\equiv -2 $ $\ \left[\,\rm or\ \ \ \dfrac{1}8\equiv \dfrac{-16}{8},\ \ {\rm or}\,\ \ \dfrac{1}8\equiv \dfrac{18}{-9}\,\right]$

$\bmod 23\!:\ \ \ \ \ \, \dfrac{1}5\equiv \dfrac{5}{25}\equiv \dfrac{5}{2}\equiv\dfrac{28}2\equiv 14 $ $\, \left[\,\rm or\ \ \ \dfrac{1}5\equiv\dfrac{4}{20}\equiv\dfrac{4}{-3}\equiv\dfrac{27}{-3} \right]$

$\bmod 101\!:\,\ \dfrac{1}{60}\equiv \dfrac{2}{120}\equiv \dfrac{2}{19}\equiv\dfrac{10}{95}\equiv\dfrac{10}{-6}\equiv\dfrac{-5}3\equiv\dfrac{96}3\equiv 32$

$\bmod 211\!:\,\ \dfrac{1}{22}\equiv \dfrac{10}{220}\equiv \dfrac{10}{9}\equiv \dfrac{-201}3\:\dfrac{1}3\equiv\dfrac{-67}{3}\equiv\dfrac{144}3\equiv 48$

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

Answer 3

I think you'll find there not many ( but still some) faster ways. Factoring such low exponents, isn't all that hard. Every product of same parity numbers, is a difference of perfect squares (which algebraically factors).(15=3*5;21=3*7;99=3*3*11;209=11*19)

You,could also express the exponents as sums. (15=5+5+5;21=7+7+7;99=33+33+33;209=19+19+19+19+19+19+19+19+19+19+19)

repeated squaring, and negation if over halfway(and done carefully to obey certain rules), keeps the numbers you are dealing with smaller.

with small numbers, you could potentially use more methods as shown by Bill.

EDIT for the first turn it into $2^{45}\equiv 2^{13}\bmod 17$, second is $-(3)^{20}2^{21} \bmod 23$, I think, third is equivalent to $2^{98}3^{99}5^{99}\bmod 101$ which can be made even better, fourth can be made into $-(2)^{206}5^{208}\bmod 211$