I realize that this question has been asked before; please just bear with me. I looked across the Internet on here, Khan Academy, and many other sites in order to understand what an inverse mod is and how to calculate it.
The closest explanation I got is
However, I can't for the life of me figure out how we get the equation in the second bullet point. I tried testing it out in Python programming language by representing ^ as both xor and "to the power of" symbol ** (example for those who have not used it: 2 ** 4 = 16) and replacing mod with % (modulo).
To anyone who knows, please explain exactly what a modular inverse is and how to solve it.
As someone said, I should probably tell why I am saying "the" modular inverse. I came across this while doing Problem 451 of Project Euler and am trying to find greatest modular inverse (if I have function l(n) then the modular inverse I am calculating must be less than n-1)
Best Answer
For example, we have: $$7\times14\equiv1\pmod{97}$$ Thus, by definition, we have the following: \begin{align} 7&\equiv14^{-1}\pmod{97}\\ 14&\equiv7^{-1}\phantom1\pmod{97} \end{align} Can you explain why $23^{-1}\equiv38\pmod{97}$?
Every number has an inverse mod $97$ (except for $0\equiv97$). Why? It turns out that $a$ has an inverse mod $b$ iff $a$ and $b$ are coprime. Since $97$ is prime, everything has an inverse modulo it.
(What numbers have inverses mod $10$? What are their inverses? Why doesn't $2$ have an inverse mod $10$?)