4.2 Modular Inverse

Modular Inverse

In modular arithmetic, a modular inverse $a\in \mathbb{Z}$ exists for every $x\in \mathbb{Z}$, such that $a\cdot x\equiv 1(\mathrm{mod}m)$, if and only if $\gcd (x,m)=1$ (i.e., $x$ and $m$ must be coprime). The easiest way to find the greatest common divisor of two integers is using Euclid’s Algorithm, which recursively divides the integers based on the identity
$\gcd (x,m)=\gcd (m,x)=\gcd (m,x\mathrm{mod}m),$
and terminates when the remainder becomes zero.

The Extended Euclidean Algorithm not only computes $\gcd (x,m)$, but also performs a backward pass to find (not necessarily distinct) integers $a,b\in \mathbb{Z}$, which satisfy Bezout’s identity,
$ax+bm=\gcd (x,m).$
It is executed as follows:

1. Set the starting pair ${\alpha }_1=x$ and ${\beta }_1=m$.
2. While ${\beta }_i\ne 0$ (forward pass / standard Euclid):
3. Let ${\alpha }_{i+1}={\beta }_i$ and ${\beta }_{i+1}={\alpha }_i(\mathrm{mod}{\beta }_i)$.
4. Now set $a_n=1$ and $b_n=0$.
5. Then, for $j=n-1,\dots ,2,1$ (backward pass):
6. Let $a_j=b_{j+1}$ and $b_j=a_{j+1}-\lfloor {\alpha }_j/{\beta }_j\rfloor \cdot b_{j+1}$.
7. When you are done, you will have the coefficients and factor that solve $ax+bm=d$.

Proof & Intuition

Inversion

Here is where modular arithmetic gets a little tricky. We will go ahead and prove necessity and sufficiency for inversion:

1. Sufficiency ($⟹$): Since $x$ and $m$ are coprime, neither can divide the other. Enter Bezout’s Identity, which states that $ax+bm=1$. We take both sides modulo $m$, and obtain $a\cdot x\equiv 1(\mathrm{mod}m).$As such, we find that $a$ is the inverse of $x$. You can think of $b$ as the “correction term” for the linear Diophantine, although it has no modular meaning unless we rearrange $m$ and $x$, such that $b$ is the inverse of $m(\mathrm{mod}x)$.
2. Necessity ($⟸$) We have that $a\cdot x\equiv 1(\mathrm{mod}m)$. Then by definition of modular congruence, there exists an integer (quotient) $q$ such that: $ax=qm+1$. Rearranging, $ax-qm=1=\gcd (x,m)$ per Bezout’s identity.

Intuitively, why is $\gcd (x,m)$ the condition for modular inversion? Think about it this way: if $x$ and $m$ shared a common factor $d>1$, then that $d$ must be able to divide any linear combination of $x$ and $m$.

Euclid’s Algorithm

The statement above will help us prove the fact that $\gcd (x,m)=\gcd (m\mathrm{mod}x)$. In order to see it, express $x=qm+r$. Then, if $d$ divides $x$ and $m$, then $d$ also divides $qm$, as well as $r=x-qm$ when rearranging. Now plug $x=16$ and $m=10$ and try it yourself.

Extended Euclid

Now, let’s switch gears to extended Euclid.

Properties

(Divisibility) Let $x,y,z\in \mathbb{N}$, such that $\gcd (x,y)=1$. If $x\mid yz$, then $x\mid z$.

(Prime Modulus) If $p$ is a prime number, all numbers $\{p-1,\dots ,1\}$ have a modular inverse.

(Fermat’s Little Theorem) For all primes $p$, $a^{p-1}(\mathrm{mod}p)\equiv 1$ if $a\ne 0$, and $a^p\equiv a(\mathrm{mod}p)$ for all $a$.

Examples

(Easy) Finding Inverses

We will investigate the existence and uniqueness of inverses:

Is 3 an inverse of 5 modulo 14? $5\cdot 3\equiv 1(\mathrm{mod}14)$, the answer is yes.

Since

Is 3 an inverse of 5 modulo 10? $\gcd (5,10)=5\ne 1$ (also because $5\cdot 3\equiv 5(\mathrm{mod}10)$).

No, since

For all $n\in N$, is $3+14n$ an inverse of 5 modulo 14? We have that $5(3+14n)\equiv 1+5\cdot 0n\equiv 1(\mathrm{mod}14)$, so yes.

Does 4 have an inverse modulo 8? $\gcd (4,8)=2\ne 1$.

No, because

(Easy) Inverse Proofs

Prove or disprove the following statements:

There exists some $x\in \mathbb{Z}$ such that $x\equiv 3(\mathrm{mod}16)$ and $x\equiv 4(\mathrm{mod}6)$. Let $x=16k+3$ and $x=6n+4$. Then, $x\equiv 1(\mathrm{mod}2)$ and $x\equiv 0(\mathrm{mod}2)$, which is a contradiction. Therefore,y this statement is false.

The congruence $2x\equiv 4(\mathrm{mod}12)$ is equivalent to $x\equiv 2(\mathrm{mod}12)$. We can divide both sides by $2$ (using the modular inverse) if $2$ and $12$ are coprime. However, $\gcd (2,12)=2\ne 1$, which means that naive division does not work here. As a counterexample, consider $x\equiv 8(\mathrm{mod}12)$.

The congruence $2x\equiv 4(\mathrm{mod}12)$ is equivalent to $x\equiv 2(\mathrm{mod}6)$. Let $2x=12k+4$. Then, $x=6k+2$, which is true.

The congruence $3x+12\equiv 4(\mathrm{mod}21)$ has a solution. The easy way out is to say that $\gcd (3,21)=3\ne 1$, and so there is no solution.

For a more intuitive understanding, consider the congruence $3x\equiv 13(\mathrm{mod}21)$. Since $\gcd (3,21)=3$, we must check whether $3$ divides the right-hand side. But $13\not\equiv 0(\mathrm{mod}3)$, so there is no solution–the congruence is inconsistent modulo $3$. In other words, for any solution to exist, both sides must be divisible by $3$. Since $3$ does not divide $13$, no value of $x$ will satisfy the equation modulo $21$.

Let $x,x^{\prime }\in Z$ be inverses of $a$ modulo $m$. Is it possible that $x\ne x^{\prime }(\mathrm{mod}m)$?

(Medium) Proving the Fundamental Theorem of Arithmetic

Prove that every integer greater than 1 can be written uniquely as a product of (not necessarily unique) prime numbers, up to the order of the factors.

Solution. $n=p_1^{k_1}\cdot p_2^{k_2}\cdot \dots \cdot p_i^{k_i}$. We leverage Bezout's Identity,

In other words, FTA states that any number can be expressed as

(Medium) Iterative EGCD!?

In this example, we explore an alternative way of finding the triple $(d,a,b)$ in an iterative, rather than a recursive way.

How Many Solutions?

Consider the equation $ax\equiv b(\mathrm{mod}p)$ for prime $p$. In the below three parts, all values $a$, $b$, $x$ are defined as values in the range $\{0,1,\dots ,p-1\}$. In addition, include justification for your answers to all the subparts of this problem.

For how many pairs $(a,b)$ does the equation have (1) a unique solution, (2) no solution, (3) $p$ solutions? (1) Since $\gcd (i,p)=1$ for all $i\in \{1,\dots ,p-1\}$, there are exactly $p-1$ values of $a$ such that $x\equiv a^{-1}b$. Then, $b$ supports all $p$ values in the set $\{0,1,\dots ,p-1\}$. As such, there are $(p-1)p$ value pairs of $(a,b)$ that have a unique solution.

(2) In order for $ax\equiv b(\mathrm{mod}p)$ to have no solution, $a$ must not have an inverse. In the set $\{0,1,\dots ,p-1\}$, the only value of $a$ that has no solution is $0$. Set $a$ to $0$, and $b$ can be any of the $p-1$ nonzero elements. Therefore, there are exactly $1\cdot (p-1)=p-1$ pairs with no solution.

(3)