Euclidean Algorithm

Theorem (Euclidean Algorithm)

Given $a,b\in\mathbb{Z},b\not=0$ , then we can divide $a$ by $b$ such that $\exists q,r$ , the quotient and remainder, such that $a=bq+r$ with $0\le r<|b|$ . If $r=0$ , $b$ , is said to be a divisor of $a$ .

Remark

This algorithm leads to the notion of the Greatest Common Divisor, where $d=gcd(a,b)$ is the largest number that divided both $a$ and $b$ .

Algorithm

The Euclidean (division) algorithm, allows us to find the gcd of any two numbers, $a,b\in\mathbb{Z}$ . Noting that $(a,b)=(b,r)$ then we can recursively repeat the process until we reach a dead end (i.e. $r_{i}=0$ for some iteration $i$ ). Suppose the process terminates after $k+1$ steps then $\begin{align*} a&=qb+r\\ b&=q_{1}r+r_{1}\\ \vdots\\ r_{k-2}&=q_{k}r_{k-1}+r_{k}&r_{k}=(a,b) \end{align*}$ This implies that $\exists x,y\in\mathbb{Z}$ such that $r_{k}=ax+by$ .

Theorem (1.1)

For any two integers $a,b$ with $b\not=0$ $\exists x_{0},y_{0}\in\mathbb{Z}$ such that for $d=(a,b)$ we have $ax_{0}+by_{0}=d$ It is clear that there are infinitely many such integers because given one pair $x_{0},y_{0}$ we also have $a(x_{0}+tb)+b(y_{0}-ta)=d$ $\forall t\in\mathbb{Z}$ .

Theorem (1.6)

For any two integers $a,b\in\mathbb{Z}$ with $b\not=0$ , $\exists x_{0},y_{0}\in\mathbb{Z}$ such that for $d=(a,b)$ , we have by Theorem 1.1 $ax_{0}+by_{0}=d$ Given this information we have that all integer solutions of $ax+by=d$ are given by the parameterization $\begin{align*} x&=x_{0}+\frac{tb}{d}\\\\ y&=y_{0}-\frac{ta}{d} \end{align*}$ for $t\in\mathbb{Z}$ .

Linked from

Polynomials