The whole post was completed on Oct 12, 2026. I have to say it is easy to come up with a good idea or something interesting… But it is hard (at least for me) to finish the work on time and do it well. This post is now done because I pushed myself to finish it, with the help of AI to polish the writing and correct errors.
Bézout’s Identity through the Lens of Algebra
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 Euclidean algorithm is a well-known method for finding the greatest common divisor of 2 given integers. Its underlying idea is 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
By Bézout’s identity, there exist $x,y\in\mathbb{Z}$ such that $ax+by=\gcd(a,b)=d$, and the extended Euclidean algorithm finds such integers. We can approach this recursively. Recall that $\gcd(a,b)=\gcd(b,a\pmod{b})$. Now suppose that $x’,y’$ satisfy $bx’+(a\pmod{b})y’=d$. Substituting the expression for the remainder gives
\[bx'+(a-\lfloor a/b\rfloor\cdot b)y'=d\Leftrightarrow ay'+b(x'-\lfloor a/b\rfloor y')=d.\]Comparing coefficients, we obtain $x=y’$ and $y=x’-\lfloor a/b\rfloor y’$. The recursion terminates just as in the original Euclidean algorithm, when $b=0$. In this case, $a=d$ so we can easily take $x=1,y=0$. The pseudocode is as follows:
\[\begin{array}{l} \textbf{ExtendedGCD}(a,b):\\ \quad \textbf{if } b=0:\; \textbf{return } (a,1,0)\\ \quad (d,x,y) \leftarrow \operatorname{ExtendedGCD}(b,a\bmod b)\\ \quad \textbf{return } (d,y,x-\lfloor a/b\rfloor y) \end{array}\]You can find this explanation everywhere on the Internet, but I want to go a little further here. Consider the $i$th division we apply: $r_{i-2}=r_{i-1}\cdot q_{i}+r_{i}$, which says $r_{i}=-q_{i}r_{i-1}+r_{i-2}$. Then
\[\begin{pmatrix} r_{i}\\ r_{i-1} \end{pmatrix}= \begin{pmatrix} -q_{i}&1\\ 1&0 \end{pmatrix} \begin{pmatrix} r_{i-1}\\ r_{i-2} \end{pmatrix}.\]Let $M_{q}$ denote the matrix
\[\begin{pmatrix} -q&1\\ 1&0 \end{pmatrix}.\]Set $r_0:=b,r_{-1}:=a$. Then
\[\begin{pmatrix} 0\\ d \end{pmatrix}= \begin{pmatrix} 0\\ r_{n-1} \end{pmatrix}= M_{q_n}M_{q_{n-1}}\ldots M_{q_1} \begin{pmatrix} b\\ a \end{pmatrix}= M_{q_n}M_{q_{n-1}}\ldots M_{q_1} \begin{pmatrix} r_0\\ r_{-1} \end{pmatrix}.\]From Left to Right
To see what we have done in the above pseudocode, let’s look at an intermediate stage of the recursion:
\[\begin{pmatrix} 0\\ d \end{pmatrix}= M_{q_n}M_{q_{n-1}}\ldots M_{q_{i+1}} \begin{pmatrix} r_{i}\\ r_{i-1} \end{pmatrix}.\]Let $N^{(i+1)}:=M_{q_n}M_{q_{n-1}}\ldots M_{q_{i+1}}$, with the empty product $N^{(n+1)}:=I$. Then $N_{22}^{(i+1)}r_{i-1}+N_{21}^{(i+1)}r_i=d$. Extending the product backward by one division step gives
\[N^{(i)}=N^{(i+1)}M_{q_i}.\]At this step, the current call has arguments $(r_{i-2},r_{i-1})$, and the recursive call has arguments $(r_{i-1},r_i)$. Their respective coefficients satisfy
\[\underbrace{x r_{i-2}+y r_{i-1}=d}_{\text{current call}}, \qquad \underbrace{x'r_{i-1}+y'r_i=d}_{\text{recursive call}}.\]Because our remainder vectors list the arguments in reverse order, the bottom rows of $N^{(i)}$ and $N^{(i+1)}$ are $(y,x)$ and $(y’,x’)$, respectively. Thus
\[\underbrace{ \begin{pmatrix} * & *\\ y & x \end{pmatrix}}_{N^{(i)}} = \underbrace{ \begin{pmatrix} * & *\\ y' & x' \end{pmatrix}}_{N^{(i+1)}} \underbrace{ \begin{pmatrix} -q_i & 1\\ 1 & 0 \end{pmatrix}}_{M_{q_i}} = \begin{pmatrix} * & *\\ x'-q_i y' & y' \end{pmatrix}.\]Reading off the bottom row gives $x=y’$ and $y=x’-q_i y’$. Since $q_i=\lfloor r_{i-2}/r_{i-1}\rfloor$, this is exactly the update in the pseudocode, with $a=r_{i-2}$ and $b=r_{i-1}$ at the current call.
Another way to see this is through a change-of-coordinates analogy. Think of $(y,x)$ as a pair of coordinates representing $d=yr_{i-1}+xr_{i-2}$ relative to the ordered pair $(r_{i-1},r_{i-2})$. Since $M_{q_i}(r_{i-1},r_{i-2})^{\mathsf T}=(r_i,r_{i-1})^{\mathsf T}$, we can transfer coefficients $(y’,x’)$ for the new pair back to the old pair by setting $(y,x)=(y’,x’)M_{q_i}$. The coefficients change while the represented integer $d$ stays the same.
From Right to Left
In the previous discussion, we traced the coefficients backward as the recursion unwound. Now let’s compute them forward, alongside the remainders. Every remainder $r_i$, including $d$, can be written as an integer linear combination $r_i=as_i+bt_i$. Starting from $r_{-1}=a$ and $r_0=b$, set
\[(s_{-1},t_{-1})=(1,0),\qquad (s_0,t_0)=(0,1).\]Substituting these representations into our matrix recurrence gives
\[\begin{pmatrix} as_{i}+bt_{i}\\ as_{i-1}+bt_{i-1} \end{pmatrix}= M_{q_{i}} \begin{pmatrix} as_{i-1}+bt_{i-1}\\ as_{i-2}+bt_{i-2} \end{pmatrix}.\]We now define the subsequent coefficients recursively by
\[\begin{pmatrix} s_{i}\\ s_{i-1} \end{pmatrix}= M_{q_{i}} \begin{pmatrix} s_{i-1}\\ s_{i-2} \end{pmatrix},\qquad \begin{pmatrix} t_{i}\\ t_{i-1} \end{pmatrix}= M_{q_{i}} \begin{pmatrix} t_{i-1}\\ t_{i-2} \end{pmatrix}.\]Thus the remainders and both coefficient sequences follow the same matrix recurrence. We can combine the three updates into a single equation:
\[\begin{pmatrix} r_{i}&s_{i}&t_{i}\\ r_{i-1}&s_{i-1}&t_{i-1} \end{pmatrix}= M_{q_{i}} \begin{pmatrix} r_{i-1}&s_{i-1}&t_{i-1}\\ r_{i-2}&s_{i-2}&t_{i-2} \end{pmatrix}.\]This recurrence gives several useful identities, which I leave as exercises.
Hint: Try using determinants.
Hint: Try using Bézout’s Identity and its relationship with GCD.
Euclidean Algorithm for Polynomials over Fields
The Euclidean algorithm also applies to $F[X]$, where $F$ is a field. We use polynomial division with remainder: for $f,g\in F[X]$ with $g\ne0$, there are unique polynomials $Q,R\in F[X]$ such that
\[f=Qg+R,\qquad R=0\ \text{or}\ \deg R<\deg g.\]Repeated division terminates because the degrees of the nonzero remainders strictly decrease. The last nonzero remainder is a GCD of the input polynomials; dividing it by its leading coefficient gives the unique monic GCD. Let $N=\max\lbrace\deg f,\deg g\rbrace$ be the larger of the two input degrees. For $N\ge1$, the classical algorithm uses $O(N^2)$ field operations with ordinary polynomial long division.
-
WLOG, we can assume $a\geq b$. ↩