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)
4 Answers
For any number $A$, it's modular inverse is any such number such that when you multiply this number by $A$ (or if you multiply $A$ by this number) you get $1$. That is
$$A\cdot A^{-1} = A^{-1}\cdot A = 1 \pmod{c}$$
For example,
$$3\cdot5 = 1 \pmod7$$
Thus $5$ is the modular inverse of $3$, and $3$ is the modular inverse of $5$ (specifically for $\mod7$). A systematic way to determine a number's inverse exists (and usually involves Euclid's algorithm).
The notation $A^{-1}$ is only a formal notation for the inverse of $A$.
Consider for example the case of $C = 5$ and $A = 3$. Then $2 \cdot 3 \mod 5 = 1$, so $2$ is the modular inverse of $3$ modulo $5$.
For small moduli it is easy to find the modular inverse of a number by brute-force. For larger numbers, the extended euclidean algorithm is an effective way to calculate the modular inverse of a number.
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$?)
I think that the main problem here is with the word "the" modular inverse suggesting uniquness. For a number $a$ if there exist a modular inverse, that is $b$ such that $ab\equiv 1 (mod$ $c)$, then there are infinite modular inverses. The usual practice is to demend that $0\leq b\leq |c|$. Then, if a modular inverse exists then it is unique.
