Number Theory Home

## GCD

The greatest common divisor of two integers $$a$$ and $$b$$ that are not all zero is the largest integer integer that divides both $$a$$ and $$b$$. It is denoted by $$\gcd(a,b)$$.
Example. Common divisors of $$a=-12$$ and $$b=18$$ are $$\pm 1,\; \pm 2,\; \pm 3,\; \pm 6$$. So $$\gcd(-12,18)=6$$.

Two integers $$a$$ and $$b$$ are called relatively prime or coprime if $$\gcd(a,b)=1$$.
Example. Since $$\gcd(4,9)=1$$, $$4$$ and $$9$$ are relatively prime.

Theorem. (Bézout's Lemma) Let $$a$$ and $$b$$ be integers, not both zero. Then there exist integers $$x$$ and $$y$$ such that $\gcd(a,b)=ax+by.$

Proof. If $$a=0$$, then $$\gcd(a,b)=|b|=ax+by$$ for $$x=0$$ and $$y=\pm 1$$. Suppose $$a\neq 0$$. Let $S=\{au+bv\;|\;u,v\in \mathbb Z \text{ such that } au+bv> 0 \}.$ For $$u=a$$ and $$v=0$$, $$au+bv=a^2>0$$. So $$a^2\in S$$ and $$S\neq \varnothing$$. By the well-ordering principle (every non-empty set of positive integers contains a least element) $$S$$ has a smallest element, say $$d$$. Then $$d=ax+by>0$$ for some $$x,y\in \mathbb Z$$.

Now we show $$d=\gcd(a,b)$$. By the Division Theorem, there exist unique integers $$q$$ and $$r$$ such that $$a=dq+r,\;0\leq r< d$$. Then $r=a-dq=a-(ax+by)q=a(1-xq)+b(-yq).$ If $$r>0$$, then $$r\in S$$ contradicting the fact that $$d$$ is the smallest element in $$S$$. So $$r=0$$ which implies $$a=dq$$. Thus $$d\vert a$$. Similarly using $$b=dq'+r',\;0\leq r'< d$$, we can show that $$d\vert b$$. Then $$d$$ is a common divisor of $$a$$ and $$b$$. Suppose $$c\vert a$$ and $$c\vert b$$. Then $$c\vert ax+by=d$$ which implies $$c\leq |d|=d$$. Thus $$d=\gcd(a,b)$$. ◼

Corollary. Let $$a$$ and $$b$$ be integers and $$d=\gcd(a,b)$$. Then

1. $$\gcd(a,b)=1$$ if and only if $$ax+by=1$$ for some integers $$x$$ and $$y$$.

2. $$\gcd\left(\displaystyle\frac{a}{d},\frac{b}{d}\right)=1$$, i.e., $$\frac{a}{d}$$ and $$\frac{b}{d}$$ are relatively prime.

Example. $$\gcd(12,30)=6=12(-2)+30(1)=12(3)+30(-1)$$. So $$\gcd(2,5)=\gcd(\frac{12}{6},\frac{30}{6})=1=\frac{12}{6}(-2)+\frac{30}{6}(1)=\frac{12}{6}(3)+\frac{30}{6}(-1)$$.

The following useful results also follow from Bézout's Lemma.

Corollary. Let $$a$$, $$b$$, and $$c$$ be integers.

1. If $$a\vert c$$, $$b\vert c$$, and $$\gcd(a,b)=1$$, then $$ab\vert c$$.

2. If $$a\vert bc$$ and $$\gcd(a,b)=1$$, then $$a\vert c$$. (Euclid's Lemma)

Proof.
1. Suppose $$a\vert c$$, $$b\vert c$$, and $$\gcd(a,b)=1$$. By Bézout's Lemma, $$ax+by=1$$ for some integers $$x,y$$. Then $$c=c\cdot 1=c\cdot (ax+by)=acx+bcy$$. Since $$a\vert c$$ and $$b\vert c$$, $$c=ar=bs$$ for some integers $$r,s$$. Then $$c=acx+bcy=absx+bary$$ is divisible by $$ab$$.

2. Exercise. ◼

Question.How to find the GCD of two integers?
The Euclidean Algorithm finds the GCD by repeatedly using the following result:

Proposition Let $$a$$ and $$b$$ be two integers. If $$a=bq+r$$ for $$q,r\in \mathbb Z$$, then $\gcd(a,b)=\gcd(b,r).$

Proof. Let $$d=\gcd(a,b)$$. Since $$d\vert a$$ and $$d\vert b$$, $$d\vert a-bq=r$$. So $$d$$ is a common divisor of $$b$$ and $$r$$. To show $$d=\gcd(b,r)$$, let $$c\vert b$$ and $$c\vert r$$. Then $$c\vert bq+r=a$$. Since $$c\vert a$$ and $$c\vert b$$, $$c\leq \gcd(a,b)=d$$. Thus $$d=\gcd(b,r)$$. ◼

Theorem.(The Euclidean Algorithm) Let $$a$$ and $$b$$ be two positive integers. Construct a sequence of integers $$\{r_1,r_2,r_3,\ldots\}$$ with $$r_1=a,\; r_2=b$$ where successively applied Division Theorem gives $r_{i}=q_{i+1}r_{i+1}+r_{i+2},\; 0\leq r_{i+2}< r_{i+1},\; i=1,2,3,\ldots.$ If $$r_n>0$$ and $$r_{n+1}=0$$ for some integer $$n$$, then $$r_n=\gcd(a,b)$$.

Proof. Applying the Division Theorem repeatedly, we have \begin{align*} &&&&r_1 &=q_2r_2+r_3,\; &&0\leq r_3< r_2, &&&&\\ &&&&r_2 &=q_3r_3+r_4,\; &&0\leq r_4< r_3, &&&&\\ &&&& &\hspace{6pt}\vdots && &&&&\\ &&&&r_{n-2} &=q_{n-1}r_{n-1}+r_n,\; &&0\leq r_{n}< r_{n-1}, &&&&\\ &&&&r_{n-1} &=q_nr_{n}+0,\; &&0=r_{n+1}. &&&& \end{align*} By the preceding result we get, $\gcd(a,b)=\gcd(r_1,r_2)=\gcd(r_2,r_3)=\gcd(r_3,r_4)=\cdots=\gcd(r_{n-2},r_{n-1})=\gcd(r_{n-1},r_n)=r_n. ◼$

Example. Let us find $$\gcd(1479,272)$$ by the Euclidean Algorithm. \begin{align*} 1479 &=5\cdot 272+119,\\ 272 &=2\cdot 119+34,\\ 119 &=3\cdot 34+17,\\ 34 &=2\cdot 17. \end{align*} Thus $$\gcd(1479,272)=17$$.

Note that the Euclidean Algorithm gives a way to write $$\gcd(1479,272)$$ as a linear combination of $$1479$$ and $$272$$. \begin{align*} 17 &=119-3\cdot 34\\ &=119-3\cdot (272-2\cdot 119)\\ &=7\cdot 119-3\cdot 272\\ &=7\cdot (1479-5\cdot 272)-3\cdot 272\\ &=7\cdot 1479+(-38)\cdot 272 \end{align*}

Last edited