Calculating the Modular Multiplicative Inverse without all those strange looking symbols
Solution 1:
"Particularly, I had a hard time knowing why the (mod m) was off to the right and separate, and I am still not sure what the triple-lined equals symbol is all about."
The notation $(57 \equiv 62) \pmod 5$ means $57$ and $62$ are congruent to each other modulo $5$, i.e. they both leave the same remainder on division by $5$. See Modular arithmetic. That notation was introduced by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae published in 1801, and has been standard since that time.
Later when computer programmers started doing modular arithmetic, they introduced a new notation: $57 \bmod 5$ means the remainder when $57$ is divided by $5$.
Just remember which notation is which and don't confuse them with each other.
The Wikipedia article might benefit from a concrete example or two.
Alright, suppose you want the inverse of $322$ when the modulus is the prime number $701$. Since $701$ is prime, the gcd of $701$ and any number that is not a multiple of $701$ is $1$. We will see that this implies there is a solution to the Diophantine equation $701x+322y=1$ (and if the gcd were something other than $1$, there would be a solution if instead of "$=1$" we put "$=\text{whatever that other number is}$").
So apply the Euclidean algorithm, but remember the quotients. Divide $701$ by $322$; get a quotient of $2$ and a remainder of $57$: $$ 701-2\cdot322 = [57]. $$ In Euclid's algorithm, we would next divide $322$ by $57$, getting a quotient of $5$ and a remainder of $37$: $$ 322 - 5\cdot [57] = [37]. $$ Then divide 57 by 37, getting a quotient of $1$ and a remainder of $20$: $$ [57] - 1\cdot[37] = [20]. $$ Divide 37 by 20, getting a quotient of $1$ and a remainder of $17$: $$ [37]-1\cdot[20] = [17]. $$ Divide $20$ by $17$, getting a quotient of 1 and a remainder of $3$: $$ [20]-1\cdot[17]=[3]. $$ Divide $17$ by $3$, getting a quotient of $5$ and a remainder of $2$: $$ [17]-5\cdot[3]=[2]. $$ Divide $3$ by $2$, getting a quotient of $1$ and a remainder of $1$: $$ [3] -1\cdot[2]=[1]. $$ So according to Euclid's algorithm, the gcd is $1$, and if that is all we wanted, we'd have needed only the remainders and not the quotients. But now we use the results above it solve $701x+322y=1$. This will imply that $(322y\equiv1)\pmod {701}$, i.e. the multiplicative inverse of 322 is $y$, when the modulus is $701$.
I've put square brackets around the numbers found to be REMAINDERS but NOT around the QUOTIENTS.
In place of the remainder $2$, in the last line, put the expression found to be equal to $2$ in the line before it: $$ \begin{align} [3]-1\cdot[2] & = [1] \\ {[}3{]}-1([17]-5\cdot[3]) & = [1] \end{align} $$ Simplify, getting linear combination of REMAINDERS: $$ 6[3]-1[17] =1. $$ Now in place of the remainder $3$, put the expression found to be equal to it: $$ 6([20]-1[17])-1[17] = 1. $$ Simplify, getting linear combination of REMAINDERS: $$ 6[20]-7[17] = 1. $$ Now in place of the remainder $17$, put the expression found to be equal to it: $$ 6[20] - 7([37]-1[20])=1. $$ Simplify, getting linear combination of REMAINDERS: $$ 13[20]-7[37]=1. $$ Now in place of the remainder $20$, put the expression found to be equal to it: $$ 13([57]-1[37])-7[37]=1. $$ Simplify, getting linear combination of REMAINDERS: $$ 13[57]-20[37]=1. $$ Now in place of the remainder $37$, put the expression found to be equal to it: $$ 13[57]-20(322-5[57])=1. $$ Simplify, getting linear combination of REMAINDERS: $$ 113[57]-20[322]=1. $$ Now in place of the remainder $57,$ put the expression found to be equal to it: $$ 113([701]-2[322])-20[322]=1. $$ Simplify, getting linear combination of REMAINDERS: $$ 113[701]-246[322]=1. $$ THEREFORE $(-246\cdot322\equiv1) \pmod{701}$.
Or in other words $(455\cdot322 \equiv1)\pmod{701}$.
So modulo $701$, the multiplicative inverse of $322$ is $455$.
Solution 2:
Here's old JS code I had for computing the modular inverse of a with respect to the modulus m, based on a modification of the usual Euclidean algorithm. I must admit that I've forgotten the provenance of this algorithm, so I'd appreciate if somebody could point me to where this modification first appeared:
function modinv(a,m) {
var v = 1;
var d = a;
var u = (a == 1);
var t = 1-u;
if (t == 1) {
var c = m % a;
u = Math.floor(m/a);
while (c != 1 && t == 1) {
var q = Math.floor(d/c);
d = d % c;
v = v + q*u;
t = (d != 1);
if (t == 1) {
q = Math.floor(c/d);
c = c % d;
u = u + q*v;
}
}
u = v*(1 - t) + t*(m - u);
}
return u;
}
Solution 3:
Consider the element $a \in \mathbb{Z}/m\mathbb{Z}$. It is not hard to show that $a^{-1}$ exists in $\mathbb{Z}/m\mathbb{Z}$ if and only if the gcd of $a$ and $m$ is 1, that is, $a$ and $m$ are coprime. Using Euler's theorem (also sometimes called Fermat's theorem), $a^{\varphi(m)} \equiv 1 \pmod{m}$ for all $a$ coprime to $m$ where $\varphi(m)$ is Euler's totient function. Therefore $$a^{-1} \equiv a^{\varphi(m) - 1} \pmod{m}.$$
So I guess an pseudo-algorithm for computing the inverse of $a \in \mathbb{Z}/m\mathbb{Z}$ could be:
- Compute the gcd of $a$ and $m$. If this is not equal to 1, exit. Else continue.
- Compute $\varphi(m)$. One way is to count the number of integers less than $m$, relatively prime to $m$, another way is to use $m$'s prime factorization. There are other much faster ways I think, but these two methods are the most obvious ones.
- Compute $a^{\varphi(m) - 1}$.
- Reduce mod $m$.
- Repeat Step 4 until the result is in $\{0, 1, \ldots, m - 1\}$.
Solution 4:
One need not understand congruence arithmetic to understand the extended Euclidean algorithm as applied to computing modular inverses. By Bezout's Identity there are integers $\rm\:x,y\:$ such that $\rm\:m\ x + n\ y\:=\:gcd(m,n) = 1\:,\:$ i.e. $\rm\ n\ y = 1 - m \ x\:.\:$ So, mod $\rm\:m\!:\ n\ y = 1\ \Rightarrow\ y = 1/n\:.\:$ To compute $\rm\:x,y\:$ one may use an extended form of the Euclidean algorithm that is analogous to identity-augmented elimination in linear algebra, e.g. see below from one of my old posts.
For example, to solve m x + n y = gcd(m,n) one begins with
two rows [m 1 0], [n 0 1], representing the two
equations m = 1m + 0n, n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,
Here is an example: d = x(80) + y(62) proceeds as:
in equation form | in row form
---------------------+------------
80 = 1(80) + 0(62) | 80 1 0
62 = 0(80) + 1(62) | 62 0 1
row1 - row2 -> 18 = 1(80) - 1(62) | 18 1 -1
row2 - 3 row3 -> 8 = -3(80) + 4(62) | 8 -3 4
row3 - 2 row4 -> 2 = 7(80) - 9(62) | 2 7 -9
row4 - 4 row5 -> 0 = -31(80) -40(62) | 0 -31 40
Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,
row1 row2 row3 row4 row5
namely: 80, 62, 18, 8, 2 = Euclidean remainder sequence
| |
for example 62-3(18) = 8, the 2nd step in Euclidean algorithm
becomes: row2 -3 row3 = row4 on the identity-augmented matrix.
In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:
[ 7 -9] [ 80 1 0] = [2 7 -9]
[-31 40] [ 62 0 1] [0 -31 40]
row 1 is the particular solution 2 = 7(80) - 9(62)
row 2 is the homogeneous solution 0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:
n row1 + m row2 -> 2n = (7n-31m) 80 + (40m-9n) 62
The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.
Solution 5:
There is an algorithm besides the extended Euclidean algorithm that can be used to solve
$\tag 1 ax \equiv b \pmod{p} \quad \text{where } p \text{ is prime} \land p \nmid a \land p \nmid b$
An outline for the algorithm's logic was given here.
Here is a Python program that calculates $3789 x \equiv 1234 \pmod{7919}$; it ends with
$\tag {ANS} 3789 x \equiv 1234 \pmod{7919} \; \text{ iff } \; x \equiv 4498 \pmod{7919}$
We take the output of the program and paste it into our Latex interpreter:
Multiply by $ 2 $:
$\quad 7578 x \equiv 2468 \pmod{7919}$
$\quad -341 x \equiv 2468 \pmod{7919}$
$\quad 341 x \equiv 5451 \pmod{7919}$
Multiply by $ 23 $:
$\quad 7843 x \equiv 125373 \pmod{7919}$
$\quad -76 x \equiv 6588 \pmod{7919}$
$\quad 76 x \equiv 1331 \pmod{7919}$
Multiply by $ 104 $:
$\quad 7904 x \equiv 138424 \pmod{7919}$
$\quad -15 x \equiv 3801 \pmod{7919}$
$\quad 15 x \equiv 4118 \pmod{7919}$
Multiply by $ 528 $:
$\quad 7920 x \equiv 2174304 \pmod{7919}$
$\quad 1 x \equiv 4498 \pmod{7919}$
Python Program
a = 3789
b = 1234
p = 7919
while 1:
q, r = divmod(p,a)
s_L = q * a
s_R = (q + 1) * a
M = q
left = True
if p - s_L > s_R - p:
M = q + 1
left = False
print()
print('Multiply by $', M,'$:',)
print()
print('$\quad', M*a, 'x \equiv', M*b, '\pmod{7919}$<br>')
if left:
a = M*a - p
b = M*b % p
print('$\quad',a, 'x \equiv', b, '\pmod{7919}$<br>')
a = -a
b = -b % p
print('$\quad',a, 'x \equiv', b, '\pmod{7919}$<br>')
else:
a = M*a - p
b = M*b % p
print('$\quad',a, 'x \equiv', b, '\pmod{7919}$<br>')
if a == 1:
break
raise SystemExit