Modular Multiplicative Inverse

Suppose for an integer $a$ there exists integer $b$ such that $a * b = 1$, then $b$ is called multiplicative inverse of $a$. Same idea can be extended to modular arithmetic as well.

Definition

For an integer $a$, under modulo $m$, multiplicative inverse of $a$ is defined as :-
$(a * b) \,\%\, m = 1$

Formally, if you have two integers $a$ and $m$, $b$ is said to be modular multiplicative inverse of $a$ under modulo $m$ if it satisfies the following equation: $a * b \equiv 1 \,mod\, m$

Modular Division

To perform modular division, we usually start by finding modular multiplicative inverse of divisor as explained below in equation

• $(a / b) \,\%\, m$ = $(a * b ^ {-1}) \,\%\, m$

Modular multiplicative inverse lies in range $[1, m - 1]$ if it exists

Existence of Modular Multiplicative Inverse

Modular multiplicative inverse of $a$ under modulo $m$ exists, iff
$gcd(a, m) = 1$ i.e $a$ and $m$ are co-prime

Proof using Bézout's Identity:

If $a$ and $m$ are coprime, by Bézout's identity: There exist integers $x$ and $y$ such that: $ax + my = 1$

Rearranging the equation:
$a * x = 1 - m * y$
$a * x = 1 + (-y) * m$
$a * x \equiv 1 \pmod{m}$

$\therefore$ $x$ is the modular multiplicative inverse of $a$ modulo $m$ Because when we divide both sides by $m$, we get a remainder of 1

The converse:
If a modular multiplicative inverse $x$ exists: $a * x \equiv 1 \pmod{m}$ This means $a * x = 1 + k * m$ for some integer $k$. Upon rearranging equation we get
$a * x - k * m = 1$
$\therefore gcd(a,m)$ must divide $1$
$\therefore gcd(a,m) = 1$

This proves both necessity and sufficiency - MMI exists iff $a$ and $m$ are coprime.
Example:
For $a = 3$ and $m = 7$ Using Extended Euclidean Algorithm: $3 \cdot 5 + 7 \cdot (-2) = 1$ Therefore, $5$ is the modular multiplicative inverse of $3$ modulo $7$
We can verify: $3 \cdot 5 = 15 \equiv 1 \pmod{7}$