Greatest common divisors and Euclid's algorithm

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 05 March 2012

Number systems - $\mathbb{Z}$, the integers

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

1. $d|x$ and $d|m$
2. If $l\in {\mathbb{Z}}_{>0}$ and $l|x$ and $l|m$ then $l|d.$

Let $a,b\in \mathbb{Z}.$ Define $$\begin{array}{ll}a<b& if\; there\; exists\; x\in {\mathbb{Z}}_{>0} \; such\; that\; a+x=b;\\ a\le b& if\; a<bor\; a=b.\end{array}$$

(Euclidean algorithm) Let $a,b\in \mathbb{Z}.$ There exist unique $q,r\in \mathbb{Z}$ such that

1. $a=bq+r$
2. $0\le r<\left|b\right|,$ where $$\left|b\right|=\{\begin{array}{ll}b,& if\; b\in {\mathbb{Z}}_{>0},\\ 0,& if\; b=0,\\ -b,& if\; -b\in {\mathbb{Z}}_{>0}.\end{array}\phantom{\}}$$

If (a) and (b) hold write $a=r \mathrm{mod}b.$

Example. The 15^th row of the multiplication table for $\mathbb{Z}/36\mathbb{Z}$ is $$\begin{array}{cccccccccccccccccccc}\cdot & 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& \cdots \end{array}$$ Notice that

1. $\begin{array}{rcl}15\cdot 10& =& 150 \; in\; \mathbb{Z},\\ 150& =& 4\cdot 36+6, \; and\\ 15\cdot 10& =& 6 \; in\; \mathbb{Z}/36\mathbb{Z}.\end{array}$
2. The numbers in row $15$ of the multiplication table for $\mathbb{Z}/36\mathbb{Z}$ are $$3,6,9,15,18,21,24,27,30,33,36$$ (all multiples of $3$ in $\mathbb{Z}/36\mathbb{Z}$)
3. $3=15\cdot 17+12(-7)$

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

Let $x,m\in \mathbb{Z}.$ Let $l\in {\mathbb{Z}}_{>0}$ such that $l\mathbb{Z}=x\mathbb{Z}+m\mathbb{Z}.$ Let $d=\gcd (x,m).$ Then $d=l.$

(Euclidean algorithm). Let $a,b\in \mathbb{Z}.$ There exist unique $q,r\in \mathbb{Z}$ such that

1. $a=bq+r$
2. $0\le r<\left|b\right|,$ where $$\left|b\right|=\{\begin{array}{ll}b,& if\; b\in {\mathbb{Z}}_{>0},\\ 0,& if\; b=0,\\ -b,& if\; -b\in {\mathbb{Z}}_{>0}.\end{array}\phantom{\}}$$

		Proof.
	Assume $a,b\in \mathbb{Z}.$ To show: There exist $q,r\in \mathbb{Z}$ such that $a=bq+r$ $0\le r<\left|b\right|$ $q,r\in \mathbb{Z}$ such that $a=bq+r$ and $0\le r<\left|b\right|$ are unique. Let $bq=$ the smallest integer in $b\mathbb{Z}$ less than or equal to $a$ and $r=a-qb.$ To show: $a=bq+r$ $0\le r<\left|b\right|.$ Since $r=a-qb$ then $a=bq+r.$ Since $bq\le a$ and $b(q+1)>a,$ $$0\le a-bqandb>a-bq.$$ So $0\le r$ and $b>r.$ Assume $q_1,r_1\in \mathbb{Z}$ and $a=b{q}_1+r_1$ and $0\le r_1<\left|b\right|$ and assume $q_2,r_2\in \mathbb{Z}$ and $a=b{q}_2+r_2$ and $0\le r_2<\left|b\right|.$ To show: $$q_1=q_{2}and{r}_1=r_2$$ Since $a-r_1=b{q}_1$ and $0\le r_1<\left|b\right|,$ $b{q}_1$ is the largest integer in $b\mathbb{Z}$ which is $\le a.$ Since $a-r_2=b{q}_2$ and $0\le r_2<\left|b\right|,$ $b{q}_2$ is the largest integer in $b\mathbb{Z}$ which is $\le a.$ $$\begin{array}{l}So\; b{q}_1=b{q}_2 \; and\; q_1=q_2.\\ So\; r_1=a-b{q}_1=a-b{q}_2=r_2.\end{array}$$ $\square$

Example. Using Euclids algorithm find $$\gcd (1288,1144)$$ Hodgson says: $$If\; a=bq+r \; with\; 0\le r<\left|b\right| \; then\; \gcd (a,b)=\gcd (b,r).$$ $$\begin{array}{rclllll}1288& =& 1144+144& & & & \\ 1144& =& 7\cdot 144+136& & 9\cdot 144& =& 1296\\ 144& =& 136+8& & 8\cdot 144& =& 1152\\ 136& =& 17\cdot 8+0.& & 7\cdot 144& =& 1008\end{array}$$ So $$\begin{array}{rcl}\gcd (1288,144)& =& \gcd (1144,144)\\ & =& \gcd (144,136)\\ & =& \gcd (136,8)\\ & =& \gcd (8,0)\\ & =& 8.\end{array}$$ Note: $$\begin{array}{rcl}8& =& 144-136\\ & =& 144-(1144-7\cdot 144)\\ & =& 8\cdot 144-1144\\ & =& 8(1288-1144)-1144\\ & =& 8\cdot 1288-9\cdot 1144\end{array}$$

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

		Proof.
	Let $l\in {\mathbb{Z}}_{>0}$ be minimal such that $l\in x\mathbb{Z}+m\mathbb{Z}.$ $$To\; show:\; l\mathbb{Z}=x\mathbb{Z}+m\mathbb{Z}$$ To show: $l\mathbb{Z}\subseteq x\mathbb{Z}+m\mathbb{Z}$ $x\mathbb{Z}+m\mathbb{Z}\subseteq l\mathbb{Z}.$ Since $l\in x\mathbb{Z}+m\mathbb{Z},$ $$l\mathbb{Z}\subseteq x\mathbb{Z}+m\mathbb{Z}$$ Assume $y\in x\mathbb{Z}+m\mathbb{Z}.$ $$To\; show:\; y\in l\mathbb{Z}.$$ Since $l$ is minimal $y\ge l.$ $$\begin{array}{ll}So& y=ql+r \; with\; 0\le r<l.\\ So& r=y-ql\in x\mathbb{Z}+m\mathbb{Z}.\\ So& r=0, \; since\; l \; is\; minimal\; positive\; integer\; in\; x\mathbb{Z}+m\mathbb{Z}.\\ So& y=ql.\\ So& y\in l\mathbb{Z}.\\ So& l\mathbb{Z}=x\mathbb{Z}+m\mathbb{Z}.\end{array}$$ $\square$

Let $x,m\in \mathbb{Z}.$ Let $l\in {\mathbb{Z}}_{>0}$ such that $l\mathbb{Z}=x\mathbb{Z}+m\mathbb{Z}.$ Let $d=\gcd (x,m).$ Then $d=l.$

		Proof.
	Let $d=\gcd (x,m).$ Let $l\in {\mathbb{Z}}_{>0}$ such that $l\mathbb{Z}=x\mathbb{Z}+m\mathbb{Z}.$ $$To\; show:\; l=d.$$ To show: $d|l$ $l|d$ $\begin{array}{lll}Since& x\in l\mathbb{Z},& then\; l|x.\\ Since& m\in l\mathbb{Z},& then\; l|m.\\ Since& d=\gcd (x,m),& then\; l|d.\end{array}$ Since $d|x$ and $d|m,$ then $x\in d\mathbb{Z}$ and $m\in d\mathbb{Z}.$ $$\begin{array}{ll}So& x\mathbb{Z}+m\mathbb{Z}\subseteq d\mathbb{Z}.\\ So& l\mathbb{Z}\subseteq d\mathbb{Z}.\\ So& l\in d\mathbb{Z}.\\ So& d|l.\end{array}$$ $\square$

Notes and References

Where are these from?

References

References?

page history