0
$\begingroup$

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

enter image description here

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)

$\endgroup$
  • $\begingroup$ $A^{-1}$ is simply the notation for modular inverse. The first bullet point tells you notation; the second bullet point tells you the definition; the third tells you which numbers have inverses. $\endgroup$ – Akiva Weinberger Aug 14 '15 at 11:21
1
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 inveses. The usual practice is to demend that $0\leq b\leq |c|$. Then, if a modular inverse exists then it is unique.

$\endgroup$
1
$\begingroup$

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$?)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.