Thursday, 18 July 2019

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





The answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean algorithm.
a. 81mod17=8172mod17=815mod17=15mod17
b. 51mod23=5232mod23=521mod23=14mod23
c. 601mod101=601012mod101=6099mod101=32mod101
d. 221mod211=222112mod211=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)2452(24)112(1)1115






521(mod23)5520525105210532259251214







6099(mod101)1099699101004964(7776)1910641296032







22209(mod211)(211)1119?This is where the superiority of Bill's approach becomes obvious


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...