Euclidean Algorithm: A Review

Bézout’s Identity through the Lens of Algebra

Let $a, b$ be 2 positive integers, and denote by $d$ their greatest common divisor, then there exist 2 integers $s,t\in\mathbb{Z}$ such that $as+bt=d$.
Every subgroup $H$ of $(\mathbb{Z}, +)$ is of the form $n\mathbb{Z}$ for some $n \geq 0$.
We can see $a\mathbb{Z}+b\mathbb{Z}=\left\lbrace as+bt:s,t\in \mathbb{Z}\right\rbrace$ is a subgroup generated by $a$ and $b$, thus there exists a positive integer $d$ such that $a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$. This implies that there exist $s,t\in\mathbb{Z}$ such that $as+bt=d$. Moreover, since $a\in a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$, $d\mid a$. Similarly, $d\mid b$, which means $d$ is a common divisor of $a$ and $b$.
We next show that $d=\gcd(a,b)$. Indeed, if an integer $e$ divides both $a$ and $b$, then it also divides every linear combination $as+bt$, and in particular $d$. Thus $e \mid d$, $e\leq d$, showing that $d$ is the greatest common divisor.

From the above proof, we can also see that for any positive integer $e$, if $e\mid a$ and $e\mid b$, then $e\mid \gcd(a,b)$.

Euclidean Algorithm

The basic idea behind the Euclidean algorithm is quite simple. Since $\gcd(a, b)=\gcd(a - b, b)$, we can repeatedly replace a number by its remainder after division by the other. By performing this process until the remainder becomes 0, the last nonzero remainder is the GCD of $a$ and $b$. More specifically, we apply the division algorithm repeatedly1:

\[\begin{align*} &a=q_1 b + r_1\\ &b=q_2 r_1 + r_2\\ &r_1=q_3 r_2 + r_3\\ &\vdots\\ &r_{n-2}=q_n r_{n-1} + r_n (=0). \end{align*}\]

When this process terminates, $r_{n-1}$ is $\gcd(a,b)$. Now let’s analyze the time complexity of this algorithm. In each iteration, we have 2 integers $r_{i-2}$ and $r_{i-1}$, and we compute

\[r_i=r_{i-2}-q_ir_{i-1}.\]

If $r_{i-1}> \tfrac{r_{i-2}}{2}$, $r_{i}< \tfrac{r_{i-2}}{2}$ obviously; otherwise, since $r_i<r_{i-1}$, we also have $r_i<\tfrac{r_{i-2}}{2}$. Therefore, the remainder roughly halves at each iteration, and the algorithm terminates after $O(\log a)$ iterations.

Extended Euclidean Algorithm

TBD

Euclidean Algorithm for Polynomials over $\mathbb{F}$

  1. WLOG, we can assume $a\geq b$. ↩