## Greatest common divisors and Euclid's algorithm

Last update: 05 March 2012

## Number systems - $ℤ$, the integers

$ℤ={...,(-1)+(-1)+(-1),(-1)+(-1),-1,0,1,1+1,1+1+1,...}$ with Let $d\in ℤ.$ The multiples of $d$ is $dℤ = {...,(-d)+(-d)+(-d),(-d)+(-d),-d,0,d,d+d,d+d+d,...}.$ Let $a,d\in ℤ.$ The integer $d$ divides $a$, $d|a,$ if $a\in dℤ.$ Let $x,m\in ℤ.$ The greatest common divisor of $x$ and $m$, $\mathrm{gcd}\left(x,m\right),$ is $d\in {ℤ}_{>0}$ such that

1. $d|x$ and $d|m$
2. If $l\in {ℤ}_{>0}$ and $l|x$ and $l|m$ then $l|d.$
Let $a,b\in ℤ.$ Define

(Euclidean algorithm) Let $a,b\in ℤ.$ There exist unique $q,r\in ℤ$ such that

1. $a=bq+r$
2. $0\le r<|b|,$ where
If (a) and (b) hold write

Example. The 15th row of the multiplication table for $ℤ/36ℤ$ is $⋅ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 15 15 30 9 24 3 18 33 12 27 6 21 36 15 30 9 24 3 18 ⋯$ Notice that

1. The numbers in row $15$ of the multiplication table for $ℤ/36ℤ$ are $3,6,9,15,18,21,24,27,30,33,36$ (all multiples of $3$ in $ℤ/36ℤ$)
2. $3=15\cdot 17+12\left(-7\right)$

Let $x,m\in ℤ.$ There exists $l\in {ℤ}_{>0}$ such that $lℤ=xℤ+mℤ.$

Let $x,m\in ℤ.$ Let $l\in {ℤ}_{>0}$ such that $lℤ=xℤ+mℤ.$ Let $d=\mathrm{gcd}\left(x,m\right).$ Then $d=l.$

(Euclidean algorithm). Let $a,b\in ℤ.$ There exist unique $q,r\in ℤ$ such that

1. $a=bq+r$
2. $0\le r<|b|,$ where

 Proof. Assume $a,b\in ℤ.$ To show: There exist $q,r\in ℤ$ such that $a=bq+r$ $0\le r<|b|$ $q,r\in ℤ$ such that $a=bq+r$ and $0\le r<|b|$ are unique. Let $bq=$ the smallest integer in $bℤ$ less than or equal to $a$ and $r=a-qb.$ To show: $a=bq+r$ $0\le r<|b|.$ Since $r=a-qb$ then $a=bq+r.$ Since $bq\le a$ and $b\left(q+1\right)>a,$ $0≤a-bq and b>a-bq.$ So $0\le r$ and $b>r.$ Assume ${q}_{1},{r}_{1}\in ℤ$ and $a=b{q}_{1}+{r}_{1}$ and $0\le {r}_{1}<|b|$ and assume ${q}_{2},{r}_{2}\in ℤ$ and $a=b{q}_{2}+{r}_{2}$ and $0\le {r}_{2}<|b|.$ To show: $q1=q2 and r1=r2$ Since $a-{r}_{1}=b{q}_{1}$ and $0\le {r}_{1}<|b|,$ $b{q}_{1}$ is the largest integer in $bℤ$ which is $\le a.$ Since $a-{r}_{2}=b{q}_{2}$ and $0\le {r}_{2}<|b|,$ $b{q}_{2}$ is the largest integer in $bℤ$ which is $\le a.$ $\square$

Example. Using Euclids algorithm find $gcd(1288,1144)$ Hodgson says: $1288 = 1144+144 1144 = 7⋅144+136 9⋅144 = 1296 144 = 136+8 8⋅144 = 1152 136 = 17⋅8+0. 7⋅144 = 1008$ So $gcd(1288,144) = gcd(1144,144) = gcd(144,136) = gcd(136,8) = gcd(8,0) = 8.$ Note: $8 = 144-136 = 144-(1144-7⋅144) = 8⋅144-1144 = 8(1288-1144)-1144 = 8⋅1288-9⋅1144$

Let $x,m\in {ℤ}_{>0}$ with $1\le x\le m.$ There exists $l\in {ℤ}_{>0}$ such that $lℤ=xℤ+mℤ.$

 Proof. Let $l\in {ℤ}_{>0}$ be minimal such that $l\in xℤ+mℤ.$ To show: $lℤ\subseteq xℤ+mℤ$ $xℤ+mℤ\subseteq lℤ.$ Since $l\in xℤ+mℤ,$ $lℤ⊆xℤ+mℤ$ Assume $y\in xℤ+mℤ.$ Since $l$ is minimal $y\ge l.$ $\square$

Let $x,m\in ℤ.$ Let $l\in {ℤ}_{>0}$ such that $lℤ=xℤ+mℤ.$ Let $d=\mathrm{gcd}\left(x,m\right).$ Then $d=l.$

 Proof. Let $d=\mathrm{gcd}\left(x,m\right).$ Let $l\in {ℤ}_{>0}$ such that $lℤ=xℤ+mℤ.$ To show: $d|l$ $l|d$ Since $d|x$ and $d|m,$ then $x\in dℤ$ and $m\in dℤ.$ $So xℤ+mℤ⊆dℤ. So lℤ⊆dℤ. So l∈dℤ. So d|l.$ $\square$

## Notes and References

Where are these from?

References?