Elementary Number Theory – Proof of Extended Euclidean Algorithm

Question

There exist $x$ and $y$ such that: $\gcd (a,b) = xa + yb$.

Why is this true? What's the reasoning behind it?

Answer 1

Bezout's Identity says that

For any pair of positive integers $a$ and $b$, there exist $x,y\in\mathbb{Z}$ so that $ax + by = \gcd(a,b)$.

Proof:

Consider the set $$ K = \{ ax + by\ |\ x,y\in\mathbb{Z}\}\tag{1} $$ Let $k$ be the smallest positive element of $K$. Since $k\in K$, there are $x,y\in\mathbb{Z}$ so that $$ k = ax + by\tag{2} $$ Because $\mathbb{Z}$ is a Euclidean Domain, we can write $$ a = qk + r\text{ with }0\le r < k\tag{3} $$ Therefore, we can write $$ \begin{align} r &= a - qk\\ &= a - q(ax+by)\\ &= a(1-qx)+b(-qy)\\ &\in K\tag{4} \end{align} $$ Since $k$ is the smallest positive element in $K$, $(3)$ and $(4)$ imply that $r$ must be $0$. Thus, $a = qk$, and therefore, $k$ divides $a$. Similarly, $k$ divides $b$. Thus, $k$ is a common divisor of $a$ and $b$, and therefore, $k\le\gcd(a,b)$.

Since $\gcd(a,b)$ divides both $a$ and $b$, and $k = ax + by$, $\gcd(a,b)$ divides $k$.

Since $\gcd(a,b)$ divides $k$ and $k\le\gcd(a,b)$, we get that $k=\gcd(a,b)$. Thus, $(2)$ becomes $$ \gcd(a,b)=ax+by\tag{5} $$

---

Futhermore, in this answer, the following are shown for $\gcd(a,b)=1$:

1. If $c\ge(a-1)(b-1)$, then $ax+by=c$ has a non-negative solution, that is, one in which both $x$ and $y$ are non-negative integers.

2. Suppose that $0 < c < ab$ and neither $a|c$ nor $b|c$. Then one and only one of $$ ax+by=c\tag{6} $$ and $$ ax+by=ab-c\tag{7} $$ has a non-negative solution.