Theorem

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

Note

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