Number Theory Home
Home Courses News Videos Contact
☰

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