The answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean algorithm.
a. 8−1mod17=817−2mod17=815mod17=15mod17
b. 5−1mod23=523−2mod23=521mod23=14mod23
c. 60−1mod101=60101−2mod101=6099mod101=32mod101
d. 22−1mod211=22211−2mod211=22209mod211=48mod211
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
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}
No comments:
Post a Comment