The Greatest Common Divisor

We will use the notion of greatest common divisor of two integers to prove that if $p$ is a prime and $p\mid ab$ , then $p\mid a$ or $p\mid b$ . Proving this is the key step in our proof of Theorem 1.1.6.

Definition 1.1 (Greatest Common Divisor)   Let

$$\gcd(a,b)=\max\left\{d\in \mathbb {Z}: d \mid a\text{ and } d\mid b\right\},$$

unless both $a$ and $b$ are 0 in which case $\gcd(0,0)=0$ .

For example, $\gcd(1,2)=1$ , $\gcd(6,27)=3$ , and for any $a$ , $\gcd(0,a)=\gcd(a,0)=a$ .

If $a\neq 0$ , the greatest common divisor exists because if $d\mid a$ then $d\leq a$ , and there are only $a$ positive integers $\leq a$ . Similarly, the $\gcd$ exists when $b\neq 0$ .

Lemma 1.1   For any integers $a$ and $b$ we have

$$\gcd(a,b)= \gcd(b,a) = \gcd(\pm a, \pm b) = \gcd(a,b-a) = \gcd(a,b+a).$$

Proof. We only prove that $\gcd(a,b) = \gcd(a,b-a)$ , since the other cases are proved in a similar way. Suppose $d\mid a$ and $d\mid b$ , so there exist integers $c_1$ and $c_2$ such that $dc_1 = a$ and $dc_2 = b$ . Then $b - a = dc_2 - dc_1 = d(c_2-c_1)$ , so $d\mid b-a$ . Thus $\gcd(a,b)\leq \gcd(a,b-a)$ , since the set over which we are taking the max for $\gcd(a,b)$ is a subset of the set for $\gcd(a,b-a)$ . The same argument with $a$ replaced by $-a$ and $b$ replaced by $b-a$ , shows that $\gcd(a,b-a)=\gcd(-a,b-a)\leq \gcd(-a,b)=\gcd(a,b)$ , which proves that $\gcd(a,b) = \gcd(a,b-a)$ . $\qedsymbol$

Lemma 1.1   Suppose $a,b,n\in\mathbb {Z}$ . Then $\gcd(a,b) = \gcd(a,b-an)$ .

Proof. By repeated application of Lemma 1.1.9, we have

$$\gcd(a,b) = \gcd(a,b-a) = \gcd(a,b-2a) = \cdots = \gcd(a,b-an).$$

$\qedsymbol$

Assume for the moment that we have already proved Theorem 1.1.6. A natural (and naive!) way to compute $\gcd(a,b)$ is to factor $a$ and $b$ as a product of primes using Theorem 1.1.6; then the prime factorization of $\gcd(a,b)$ can read off from that of $a$ and $b$ . For example, if $a=2261$ and $b=1275$ , then $a=7\cdot {\bf 17}\cdot 19$ and $b=3\cdot 5^2\cdot {\bf 17}$ , so $\gcd(a,b) = 17$ . It turns out that the greatest common divisor of two integers, even huge numbers (millions of digits), is surprisingly easy to compute using Algorithm 1.1.13 below, which computes $\gcd(a,b)$ without factoring $a$ or $b$ .

To motivate Algorithm 1.1.13, we compute $\gcd(2261,1275)$ in a different way. First, we recall a helpful fact.

Proposition 1.1   Suppose that $a$ and $b$ are integers with $b\neq 0$ . Then there exists unique integers $q$ and $r$ such that $0\leq r< \vert b\vert$ and $a = bq + r$ .

Proof. For simplicity, assume that both $a$ and $b$ are positive (we leave the general case to the reader). Let $Q$ be the set of all nonnegative integers $n$ such that $a-bn$ is nonnegative. Then $Q$ is nonempty because $0\in Q$ and $Q$ is bounded because $a-bn<0$ for all $n>a/b$ . Let $q$ be the largest element of $Q$ . Then $r=a-bq < b$ , otherwise $q+1$ would also be in $Q$ . Thus $q$ and $r$ satisfy the existence conclusion.

To prove uniqueness, suppose for the sake of contradiction that $q'$ and $r'=a-bq'$ also satisfy the conclusion but that $q'\neq q$ . Then $q'\in Q$ since $r'=a-bq'\geq 0$ , so $q'<q$ and we can write $q'=q-m$ for some $m>0$ . But then $r' = a-bq' = a-b(q-m) = a-bq + bm = r + bm > b$ since $r\geq 0$ , a contradiction. $\qedsymbol$

For us an algorithm is a finite sequence of instructions that can be followed to perform a specific task, such as a sequence of instructions in a computer program, which must terminate on any valid input. The word ``algorithm'' is sometimes used more loosely (and sometimes more precisely) than defined here, but this definition will suffice for us.

Algorithm 1.1 (Division Algorithm)   Suppose $a$ and $b$ are integers with $b\neq 0$ . This algorithm computes integers $q$ and $r$ such that $0\leq r< \vert b\vert$ and $a = bq + r$ . We will not describe the actual steps of this algorithm, since it is just the familiar long division algorithm.

We use the division algorithm repeatedly to compute $\gcd(2261,1275)$ . Dividing $2261$ by $1275$ we find that

$$2261 = 1\cdot 1275 + 986,$$

so $q=1$ and $r=986$ . Notice that if a natural number $d$ divides both $2261$ and $1275$ , then $d$ divides their difference $986$ and $d$ still divides $1275$ . On the other hand, if $d$ divides both $1275$ and $986$ , then it has to divide their sum $2261$ as well! We have made progress:

$$\gcd(2261,1275) = \gcd(1275,986).$$

This equality also follows by repeated application of Lemma 1.1.9. Repeating, we have

$$1275 = 1\cdot 986 + 289,$$

so $\gcd(1275,986)=\gcd(986,289)$ . Keep going:

$$986 =3\cdot 289 + 119$$

$$289 =2\cdot 119 + 51$$

$$119 =2\cdot 51 + 17.$$

Thus $\gcd(2261,1275)=\cdots=\gcd(51,17)$ , which is $17$ because $17\mid 51$ . Thus

$$\gcd(2261,1275)=17.$$

Aside from some tedious arithmetic, that computation was systematic, and it was not necessary to factor any integers (which is something we do not know how to do quickly if the numbers involved have hundreds of digits).

Algorithm 1.1 (Greatest Common Division)   Given integers $a, b$ , this algorithm computes $\gcd(a,b)$ .

1. [Assume $a>b\geq 0$ ] We have $\gcd(a,b) = \gcd(\vert a\vert,\vert b\vert) = \gcd(\vert b\vert,\vert a\vert)$ , so we may replace $a$ and $b$ by their absolute value and hence assume $a, b \geq 0$ . If $a=b$ output $a$ and terminate. Swapping if necessary we assume $a>b$ .
2. [Quotient and Remainder] Using Algorithm 1.1.12, write $a = bq + r$ , with $0\leq r<b$ and $q\in\mathbb {Z}$ .
3. [Finished?] If $r=0$ then $b\mid a$ , so we output $b$ and terminate.
4. [Shift and Repeat] Set $a\leftarrow b$ and $b \leftarrow r$ , then go to step 2.

Proof. Lemmas 1.1.9-1.1.10 imply that $\gcd(a,b) = \gcd(b,r)$ so the gcd does not change in step 4. Since the remainders form a decreasing sequence of nonnegative integers, the algorithm terminates. $\qedsymbol$

Example 1.1   Set $a=15$ and $b=6$ .

$$15 = 6\cdot 2 + 3 \qquad\gcd(15,6)=\gcd(6,3)$$

$$6 = 3\cdot 2 + 0 \qquad\gcd(6,3) =\gcd(3,0)=3$$

Note that we can just as easily do an example that is ten times as big, an observation that will be important in the proof of Theorem 1.1.19 below.

Example 1.1   Set $a=150$ and $b=60$ .

$$150 = 60\cdot 2 + 30 \qquad\gcd(150,60)=\gcd(60,30)$$

$$60 = 30\cdot 2 + 0 \qquad \gcd(60,30) =\gcd(30,0)=30$$

SAGE Example 1.1   SAGE uses the command gcd to compute the greatest common divisor of two integers. For example,

sage: gcd(97,100)
1
sage: gcd(97 * 10^15, 19^20 * 97^2)
97

Lemma 1.1   For any integers $a,b,n$ , we have

$$\gcd(an,bn) = \gcd(a,b)\cdot n.$$

Proof. The idea is to follow Example 1.1.15; we step through Euclid's algorithm for $\gcd(an,bn)$ and note that at every step the equation is the equation from Euclid's algorithm for $\gcd(a,b)$ but multiplied through by $n$ . For simplicity, assume that both $a$ and $b$ are positive. We will prove the lemma by induction on $a+b$ . The statement is true in the base case when $a+b=2$ , since then $a=b=1$ . Now assume $a, b$ are arbitrary with $a\geq b$ . Let $q$ and $r$ be such that $a = bq + r$ and $0\leq r<b$ . Then by Lemmas 1.1.9-1.1.10, we have $\gcd(a,b) = \gcd(b,r)$ . Multiplying $a = bq + r$ by $n$ we see that $an = bnq + rn$ , so $\gcd(an,bn) = \gcd(bn,rn)$ . Then

$$b+r = b + (a-bq)= a-b(q-1) \leq a < a+b,$$

so by induction $\gcd(bn,rn) = \gcd(b,r)\cdot n$ . Since $\gcd(a,b) = \gcd(b,r)$ , this proves the lemma. $\qedsymbol$

Lemma 1.1   Suppose $a,b,n\in\mathbb {Z}$ are such that $n\mid a$ and $n\mid b$ . Then $n\mid \gcd(a,b)$ .

Proof. Since $n\mid a$ and $n\mid b$ , there are integers $c_1$ and $c_2$ , such that $a=n c_1$ and $b=n c_2$ . By Lemma 1.1.17, $\gcd(a,b) = \gcd(n c_1, nc_2) = n\gcd(c_1, c_2)$ , so $n$ divides $\gcd(a,b)$ . $\qedsymbol$

At this point it would be natural to formally analyze the complexity of Algorithm 1.1.13. We will not do this, because the main reason we introduced Algorithm 1.1.13 is that it will allow us to prove Theorem 1.1.6, and we have not chosen to formally analyze the complexity of the other algorithms in this book. For an extensive analysis of the complexity of Algorithm 1.1.13, see [#!knuth2!#, §4.5.3].

With Algorithm 1.1.13, we can prove that if a prime divides the product of two numbers, then it has got to divide one of them. This result is the key to proving that prime factorization is unique.

Theorem 1.1 (Euclid)   Let $p$ be a prime and $a, b\in \mathbb {N}$ . If $p\mid ab$ then $p\mid a$ or $p\mid b$ .

You might think this theorem is ``intuitively obvious'', but that might be because the fundamental theorem of arithmetic (Theorem 1.1.6) is deeply ingrained in your intuition. Yet Theorem 1.1.19 will be needed in our proof of the fundamental theorem of arithmetic.

Proof. [Proof of Theorem 1.1.19] If $p\mid a$ we are done. If $p\nmid a$ then $\gcd(p,a)=1$ , since only $1$ and $p$ divide $p$ . By Lemma 1.1.17, $\gcd(pb,ab) = b$ . Since $p\mid pb$ and, by hypothesis, $p\mid ab$ , it follows from Lemma 1.1.17 that

$$p\mid \gcd(pb,ab) = b\gcd(p,a) = b\cdot 1 = b.$$

$\qedsymbol$