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)
815(mod17)≡245≡2⋅(24)11≡2⋅(−1)11≡15
521(mod23)≡5⋅520≡5⋅2510≡5⋅210≡5⋅322≡5⋅92≡5⋅12≡14
6099(mod101)≡1099⋅699≡10⋅10049⋅64⋅(7776)19≡−10⋅−64≡12960≡32
22209(mod211)≡(2⋅11)11⋅19≡?This is where the superiority of Bill's approach becomes obvious
No comments:
Post a Comment