1
$\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$
1
  • 1
    $\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$ Aug 14, 2015 at 11:21

4 Answers 4

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .