1.1 Euclid's Algorithm

Notation Given integers $a$ and $b$, not both zero, we write $\gcd (a,b)$ or $(a,b)$ for the greatest common divisor of $a$ and $b$.

Example 1.1.1

Very inefficiently—the positive divisors of 12 are 1, 2, 3, 4, 6 and 12, so $\gcd (12,20)$ = 4

Is there a more efficient way to do this?

Example 1.1.2

Suppose we want to find $\gcd (2024,70)$. We have

$$\begin{array}{rl}2024& =28\times 70+64\\ 70& =64+6\\ 64& =10\times 6+4\\ 6& =4+2\\ 4& =2\times 2\end{array}$$

So the gcd is 2.

Euclid’s Algorithm Process

We may assume that $0<a\le b$ since $(0,b)=b$

1. Put $a_0=a$ and $b_0=b$
2. Use the division algorithm to find $q_0,r_0\in \mathbb{Z}$ such that $b_0=q_0{a}_0+r_0$ and $0\le r_0<a_0$
3. If $r_0=0$ then $\gcd (a,b)=a_0$
4. If $0<r_0<a_0$, then set $a_1=r_0$ and $b_1=a_0$, and repeat the process

Proof

The $a_i\in {\mathbb{Z}}_{\ge 0}$ are decreasing, so the algorithm must terminate. If $b=aq+r$, then the common divisors of $r$ and $a$ are the same as the common divisors of $a$ and $b$, so $\gcd (r,a)=\gcd (a,b)$. If the algorithm terminates are $i+1$ steps, then
$a_i=\gcd (0,a_i)=\gcd (a_i,a_{i-1})=...=\gcd (a_1,a_{0)}=\gcd (a,b)$

---

Example 1.1.3

Euclid’s algorithm can be run backwards to express the gcd as a linear combination of the two numbers. This is called the extended Euclidean algorithm
We have

$$\begin{array}{rl}2& =6-4\\ & =6-(64-10\times 6)=11\times 6-64\\ & =11(70-644)-64=11\times 70-12\times 64\\ & =11\times 70-12(2024-28\times 70)=347\times 70-12\times 2024\end{array}$$

This gives a practical way to establish the fundamental result below

Multi

Lemma 1.1.4 (Bezout’s Lemma)

Let $a$ and $b$ be integers, not both zero. Then there exist $x,y\in \mathbb{Z}$ such that
$ax+by=\gcd (a,b)$

Corollary 1.15

Let $a$ and $b$ be integers, not both zero, and let $d\in \mathbb{Z}$. Then $d$ divides $a$ and $b$ if and only if $d\mid \gcd (a,b)$

Proof

If $d$ divides $\gcd (a,b)$, then it divides $a$ and $b$. Conversely, suppose $d$ divides $a$ and $b$. For some $x,y\in \mathbb{Z}$, we have
$\gcd (a,b)=ax+by$
which is divisible by $d$.