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.

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}$$

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} $$

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}$.

## 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$:

a) $a=13, b=32$

b) $a=40, b=148$

c) $a=55, b=300$

**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$.