Euclidean Algorithm

We discuss the Euclidean algorithm and use it to compute the multiplicative inverse.

Multiplicative Inverse. Given $x, y \in \mathbb{N}^+$, $z$ is called the multiplicative inverse of $x$ (module $y$) if

$$xz \equiv 1 \pmod y.$$

Theorem 1

$x$ has a multiplicative inverse module $y \iff \gcd(x, y) = 1$.

Proof.
Define the set $S = \{ ax + by \mid a, b \in Z\}$. Let $d = a^* x + b^* y$ be the smallest positive integer in $S$. Our proof relies on the following lemma.

Lemma: $\gcd(x,y) = d$.

First, as $d$ is a linear combination of $x$ and $y$, $\gcd(x, y) | d$ and $\gcd(x, y) \le d$.

Second, we claim that $d | x$ and $d | y$. By symmetry, we prove only the former. If not, suppose that $d \nmid x$. Then $\exists k \in \mathbb{Z}, \ell \in [1, d - 1]$, s.t.,

Since $\ell = x - k d$ is a linear combination of $x$ and $y$, it holds that $\ell \in S$, contradicting $d$ being the smallest positive element in $S$.

It concludes that $d$ equals to $\gcd(x, y)$.

$\square$

The proof of the above theorem immediately follows from the lemma.

1. $\gcd(x, y) = 1 \rightarrow x$ has a multiplicative inverse.
   In this case, $d = a^* x + b^* y = 1$. $a^*$ is th multiplicative inverse of $x$ module $y$.

2. $x$ has a multiplicative inverse $\rightarrow \gcd(x, y) = 1$.
   If $x$ has a multiplicative inverse, there exists some $z$ and $l$, such that $zx = ly + 1$.

$\blacksquare$

Theorem 2

If $x$ has a multiplicative inverse module $y$, it is unique.

Proof.
Let $a$ and $b$ both be the multiplicative inverse of $x$ module $y$, then

$\blacksquare$

Basic Euclidean Algorithm

Euclidean algorithm computes $\gcd(x, y)$ as follows:

 unsigned gcd(unsigned x, unsigned y) {
     if(y == 0) return x;
     return gcd(y, x % y);
 }

Correctness

If $y =0$, whether $x = 0$ or not, we have $\gcd(x, y) = x$.

If $x < y$, $x \mod y = x$. The algorithm exchanges $x$ and $y$ at the first recursion. It suffices to consider only $x \ge y > 0$.

If $x \ge y > 0$, then $\gcd(x, y) = \gcd(y, x \mod y)$. Let $d = \gcd(x, y)$. Clearly $d | x$ and $d | y$. We claim that

Suppose $x = k d$ and $y = \ell d$, then $x \mod y = d \cdot (k \mod \ell)$, which finishes proof.

Time

Let $n$ be the the total number of bits to represent $x$ and $y$. Then the algorithm stops after $O(n)$ recursions.

Proof.

We can assume $x \ge y$. Otherwise, they are swapped by a recursive call.

The key observation is that, after every two recursive calls, the first argument $x$ shrinks at least by a factor of two.

1. If $y \le x / 2$, the observation holds after the first call.
2. If $y > x / 2$, then after two recursive call, the first argument becomes $x \mod y$, which is smaller than $x / 2$.

$\square$

Extended Euclidean Algorithm

We extend the basic version to return a pair $a^*, b^* \in \mathbb{N}$ s.t. $\gcd(x, y) = d = a^* x + b^* y$.

 std::pair<unsigned, unsigned> gcd(unsigned x, unsigned y) {
     if(y == 0) return {1, 0};
     auto (a', b') = gcd(y, x mod y);
     return (b', a' - b' * (x / y));
 }

Correctness

Suppose $s = a' y + b' \cdot (x \mod y)$. Then

This is why the algorithm work.

$\square$

Example