Proof of Extended Euclidean Algorithm?

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

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

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} $$

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.

To understand why "there exists numbers $x$ and $y$ such that $\gcd(a,b)=xa+yb$" you should understand the Euclidean Algorithm:

http://en.wikipedia.org/wiki/Euclidean_algorithm

Euclidean Algorithm:

Let's see what it's all about.

Given two numbers $a,b$ either $b$ divides $a$, denoted $b|a$, in which case $a=bq$ for $q\in \mathbb{Z}$; or $b$ does not divide $a$. If $b$ does not divide $a$, then there exists unique numbers $r$ and $q$ such that $a=bq+r$ with $0\le r\lt b$ (this includes the case when $b|a$, i.e. $r=0$). This is one of the first theorems addressed in most number theory texts and is key to the Euclidean Algorithm. We do this repeatedly and result with the following:

$a=bq_1+r_1$ where $0\lt r_1\lt b$
$b=r_1q_2+r_2$ where $0\lt r_2\lt r_1$
$\vdots$
$r_{n-2}=r_{n-1}q_{n}+r_{n}$ where $0\lt r_{n-1}\lt r_n$
$r_{n-1}=r_nq_{n+1}$

This terminates when $r_{n+1}=0$, which must occur since each number $r_i$ decreases by atleast $1$ (termination at $r_n=0$ is formally proven by induction).

The claim is that $r_n=\gcd(a,b)$. Following the algorithm from the top down, we can see that the greatest common divisor of $a$ and $b$ is identical with the greatest common divisor of $b$ and $r_1$:

$\gcd(a,b)=\gcd(b,r_1)=\gcd(r_1,r_2)=\dots =\gcd(r_{n-1},r_n)=r_n$ (The last equality follows from the last line in Euclid's Algorithm)

Result:

Now that we have established $r_n=gcd(a,b)$ and Euclid's Algorithm, all we need to do is rewrite $r_n$ in terms of the previous $r_i's$. Solving the second to last line of the algorithm for $r_n$, we have $r_n=r_{n-2}-r_{n-1}q_{n}$ and substituting for $r_{n-1}$ from the previous line, we obtain $r_n=r_{n-2}-(r_{n-3}-r_{n-2}q_{n-1})q_n$. Rearranging the terms, we get $r_n=r_{n-2}m+r_{n-3}n$ where $m=1+q_{n-1}q_n$ and $n=q_n$. This process is repeated until we have $r_n=ax+by$ where $x$ and $y$ are integers. This reasoning leads us to conclude that $\gcd(a,b)=ax+by$.

Example:

Using the Euclideaan Algorithm let's compute the $\gcd(68,20)=4$:

$68=20*3+8$
$20=8*2+4$
$8=4*2$

Using the procedures discussed above, we have $4=20-8*2$ and $8=68-20*3$. A little rearranging and sustitution gives us $4=20-(68-20*3)2$ which yields $4=20*7-68*2$.

Hope this helps!

The actual theorem is that

if $a$ and $b$ are integers, and at least one of them is non-zero, then there exist integers $x$ and $y$ such that $ax+by=\gcd(a,b)$; moreover, $\gcd(a,b)$ is the smallest positive integer that can be written in this form.

This result is sometimes called Bézout’s lemma. It should not be confused with the extended Euclidean algorithm, which is an algorithm that simultaneously computes $\gcd(a,b)$ and a pair of integers $x$ and $y$ such that $ax+by=\gcd(a,b)$. It is entirely possible to prove Bézout’s lemma without any reference to the Euclidean algorithm; such a proof can be found here. (Note that they write $a\backslash b$ instead of $a\mid b$ for a divides b.) However, this argument merely proves the existence of such $x$ and $y$; the extended Euclidean algorithm gives an efficient mechanism for finding such a pair. The Wikipedia article on it (to which I already linked) gives a concise but complete description of the algorithm and proof of its correctness.

Hint $\ $ The set $\rm\:S\:$ of integers of the form $\rm\:x\:a + y\:b,\ x,y\in \mathbb Z\:$ is closed under subtraction so, by the Lemma below, every $\rm\:n\in S\:$ is divisible by the least positive $\rm\:d\in S.\:$ Thus $\rm\:a,b\in S\:$ $\Rightarrow$ $\rm\:d\:|\:a,b,\:$ i.e. $\rm\:d\:$ is a common divisor of $\rm\:a,b,\:$ necessarily greatest, by $\rm\:c\:|\:a,b\:$ $\Rightarrow$ $\rm\:c\:|\: \hat x\:a+\hat y\:b = d\:$ $\Rightarrow$ $\rm\:c\le d.$

This linear representation of the the gcd is known as the Bezout identity for the gcd. It need not hold true in all domains where gcds exist, e.g. in the domain $\rm\:D = \mathbb Q[x,y]\:$ of polynomials in $\rm\:x,y\:$ with rational coefficients we have $\rm\:gcd(x,y) = 1\:$ but there are no $\rm\:f(x,y),\: g(x,y)\in D\:$ such that $\rm\:x\:f(x,y) + y\:g(x,y) = 1;\:$ indeed, if so, then evaluating at $\rm\:x = 0 = y\:$ yields $\:0 = 1.$

The fundamental lemma below, interpreted procedurally, yields Euclid's classical algorithm to compute the gcd using repeated subtraction. For a simple approach to the extended gcd algorithm see my post here.

Lemma $\ \ $ If a nonempty set of positive integers $\rm\: S\:$ satisfies $\rm\ n > m\ \in\ S \ \Rightarrow\ \: n-m\ \in\ S$
then every element of $\rm\:S\:$ is a multiple of the least element $\rm\:m_{\:1} \in S\:.$

Proof $\ \: $ If not there is a least nonmultiple $\rm\:n\in S\:,$ contra $\rm\:n-m_{\:1} \in S\:$ is a nonmultiple of $\rm\:m_{\:1}.$