Suppose $a$ and $b$ are integers, not both zero. The greatest common divisor (gcd, for short) of $a$ and $b$, written $(a,b)$ or $\gcd(a,b)$, is the largest positive integer that divides both $a$ and $b$. We will be concerned almost exclusively with the case where $a$ and $b$ are non-negative, but the theory goes through with essentially no change in case $a$ or $b$ is negative. The notation $(a,b)$ might be somewhat confusing, since it is also used to denote ordered pairs and open intervals. The meaning is usually clear from the context. We begin with some simple observations:

Lemma 3.3.1 Suppose $a$ and $b$ are not both zero.

    a) $(a,b)=(b,a)$,

    b) if $a>0$ and $a\vert b$ then $(a,b)=a$,

    c) if $a\equiv c\pmod b$, then $(a,b)=(c,b)$.

Proof. Part (a) is clear, since a common divisor of $a$ and $b$ is a common divisor of $b$ and $a$. For part (b), note that if $a\vert b$, then $a$ is a common divisor of $a$ and $b$. Clearly $a$ is the largest divisor of $a$, so we are done. Finally, if $a\equiv c\pmod b$, then $b\vert a-c$, so there is a $y$ such that $a-c=by$, i.e., $c=a-by$. If $d$ divides both $a$ and $b$, then it also divides $a-by$. Therefore any common divisor of $a$ and $b$ is also a common divisor of $c$ and $b$. Similarly, if $d$ divides both $c$ and $b$, then it also divides $c+by=a$, so any common divisor of $c$ and $b$ is a common divisor of $a$ and $b$. This shows that the common divisors of $a$ and $b$ are exactly the common divisors of $c$ and $b$, so, in particular, they have the same greatest common divisor.$\qed$

It perhaps is surprising to find out that this lemma is all that is necessary to compute a gcd, and moreover, to compute it very efficiently. This remarkable fact is known as the Euclidean Algorithm. As the name implies, the Euclidean Algorithm was known to Euclid, and appears in The Elements; see section 2.6. As we will see, the Euclidean Algorithm is an important theoretical tool as well as a practical algorithm. Here is how it works:

To compute $(a,b)$, divide the larger number (say $a$) by the smaller number, so $a=bq_1+r_1$ and $r_1< b$. By 3.3.1(c), $(a,b)=(b,r_1)$. Now $b=r_1q_2+r_2$, $r_2< r_1$, and $(b,r_1)=(r_1,r_2)$; then $r_1=r_2q_3+r_3$, $r_3< r_2$, and $(r_1,r_2)=(r_2,r_3)$, and so on. Since $r_1>r_2>r_3\ldots$, eventually some $r_k=0$ and $(a,b)=(r_{k-1},r_k)=(r_{k-1},0)=r_{k-1}$; in other words, $(a,b)$ is the last non-zero remainder we compute. Note that $(a,0)=a$, by 3.3.1(b).

Example 3.3.2 $$\normalbaselines \eqalign {(198,168)&= (168,30) \cr &= (30,18) \cr &= (18,12) \cr &= (12,6) \cr &= (6,0)=6. \cr}$$ $\square$

If you have done some computer programming, you should see just how easy it is to implement this algorithm in any reasonable programming language. Since it is a very fast algorithm it plays an important role in many applications.

With a little extra bookkeeping, we can use the Euclidean Algorithm to show that $\gcd(a,b)$ is actually a linear combination of $a$ and $b$.

Example 3.3.3 Again taking $a=198$ and $b=168$: $$\normalbaselines \eqalign { 30 &= 198-168=a-b, \cr 18 &= 168-5\cdot30=b-5(a-b)=-5a+6b, \cr 12 &= 30-18=(a-b)-(-5a+6b)= 6a-7b, \cr 6 &= 18-12=(-5a+6b)-(6a-7b) = -11a+13b \cr} $$ $\square$

Notice that the numbers in the left column are precisely the remainders computed by the Euclidean Algorithm. With a little care, we can turn this into a nice theorem, the Extended Euclidean Algorithm.

Theorem 3.3.4 Suppose $a$ and $b$ are integers, not both zero. Then there are integers $x$ and $y$ such that $(a,b)=ax+by$.

Proof. The Euclidean Algorithm proceeds by finding a sequence of remainders, $r_1$, $r_2$, $r_3$, and so on, until one of them is the gcd. We prove by induction that each $r_i$ is a linear combination of $a$ and $b$. It is most convenient to assume $a>b$ and let $r_0=a$ and $r_1=b$. Then $r_0$ and $r_1$ are linear combinations of $a$ and $b$, which is the base of the induction. The repeated step in the Euclidean Algorithm defines $r_{n+2}$ so that $r_n=qr_{n+1}+r_{n+2}$, or $r_{n+2}=r_n-qr_{n+1}$. If $r_n$ and $r_{n+1}$ are linear combinations of $a$ and $b$ (this is the induction hypothesis) then so is $r_{n+2}$.$\qed$

Exercises 3.3

Ex 3.3.1 For the pairs of integers $a$, $b$ given below, find the gcd $g$ and integers $x$ and $y$ satisfying $g=ax+by$:

Ex 3.3.2 If $p$ is a prime, and $a$ is a positive integer, describe $(a,p)$.

Ex 3.3.3 Suppose $g$ is the gcd of $a$ and $b$. If $i$ and $j$ are integers and $c=ai+bj$, prove $g\vert c$.

Ex 3.3.4 Suppose $g$ is the gcd of $a$ and $b$. If $g\vert c$, prove that there are integers $i$ and $j$ such that $c=ai+bj$.

Ex 3.3.5 If $g=(a,b)$ and $x=ab$, prove $g^2\vert x$.

Ex 3.3.6 Suppose that $d\vert a$ and $d\vert b$. Prove that $d\vert(a,b)$.

Ex 3.3.7 Suppose $g>0$ and $x$ is a multiple of $g^2$. Show that there are integers $a$ and $b$ such that $(a,b)=g$ and $ab=x$. (Hint: there is an $n$ such that $x=g^2n$; aim for a trivial case remembering that you get to define $a$ and $b$.)

Ex 3.3.8 Show that there are, in fact, an infinite number of ways of expressing $(a,b)$ as a combination of $a$ and $b$. (Hint: use one way to generate an infinite number of other possibilities.)

Ex 3.3.9 In the proof of theorem 3.3.4, suppose that $r_n=x_na+y_nb$ and $r_{n+1}=x_{n+1}a+y_{n+1}b$, by the induction hypothesis. Write $r_{n+2}$ as an explicit linear combination of $a$ and $b$, and identify $x_{n+2}$ and $y_{n+2}$.

Ex 3.3.10 The Euclidean algorithm works so well that it is difficult to find pairs of numbers that make it take a long time. Find two numbers whose gcd is 1, for which the Euclidean Algorithm takes 10 steps.

Ex 3.3.11 Prove that $(F_n,F_{n-1})=1$ where $F_n$ is the $n$th Fibonacci number. (See exercise 7 in section 2.4.)

Ex 3.3.12 Write a computer program to implement the Extended Euclidean Algorithm. That is, given $a$ and $b$, the program should compute and display $\gcd(a,b)$, $x$, and $y$.