📂Number Theory

Proof of the Extended Euclidean Theorem

Theorem ¹

For two integers $a,b$, there always exists an integer solution for $ax + by = \gcd (a,b)$.

Description

This theorem is also known as the Linear Congruence Theorem as it implies that $\gcd (a,b)$ can be expressed as a linear equation involving $a$ and $b$.

Although its appearance seems somewhat complex and it only discusses existence, it is surprisingly widely used. It might not provide a specific solution $(x,y)$, but the fact that we can start from the relationship between $a$ and $b$ is a significant gain. It is incredibly useful especially when we don’t know what $x$ and $y$ are.

Proof

Elementary Proof

Strategy: As the name suggests, the Extended Euclidean Theorem repeats the Euclidean algorithm. Hence, it is also referred to as the Extended Euclidean Algorithm.

---

Euclidean algorithm: For $ r_i<r_{i+1}$, let’s define $a: = r_{-1}$ and $b:=r_{0}$ that satisfy the recurrence relation $r_{i-1} = q_{i+1} \cdot r_{i} + r_{i+1}$. For $n$ that satisfies $r_{n+1} = 0$, $r_{n} = \gcd (a,b)$

According to the Euclidean algorithm, $r_{1}$ is $$ r_{1} = a - q_{1} b $$ In other words, it can be represented as a linear combination of $a$ and $b$. Meanwhile, $$ r_{2} = b - q_{2} r_{1} $$ and substituting the above $r_{1} = a - q_{1} b$ yields $$ \begin{align*} r_{2} =& b - q_{2} r_{1} \\ =& b - q_{2} ( a - q_{1} b ) \\ =& -q_{2} a + ( 1 + q_{1} q_{2} ) b \end{align*} $$ meaning $r_{2}$ can also be represented as a linear combination of $a$ and $b$. Repeating this $n$ times, $r_{n}$ can be expressed for some $x,y \in \mathbb{Z}$ as $$ r_{n} = x a + y b $$ Since the Euclidean algorithm ensures $r_{n} = \gcd (a,b)$, $(x,y)$ exists as a solution for $ax + by = \gcd (a,b)$.

■

Algebraic Proof

The ring of integers $\mathbb{Z}$ is a PID, hence a Bezout domain.

■

See Also

Generalization: Bezout Domain

As pointed out in the algebraic proof, if a domain is a Bezout domain, then the Extended Euclidean Theorem applies no matter where that domain is.