92 II Divisibility
integers. Since( 0 ,b)=b, we may assumea=0. Then there exist integersq,rsuch
that
b=qa+r, |r|<|a|.Puta 0 =b,a 1 =aand repeatedly apply this procedure:a 0 =q 1 a 1 +a 2 , |a 2 |<|a 1 |,
a 1 =q 2 a 2 +a 3 , |a 3 |<|a 2 |,
···
aN− 2 =qN− 1 aN− 1 +aN, |aN|<|aN− 1 |,
aN− 1 =qNaN.The process must eventually terminate as shown, because otherwise we would obtain
an infinite sequence of positive integers with no least element. We claim thataNis a
greatest common divisor ofaandb. In fact, working forwards from the first equation
we see that any common divisorcofaandbdivides eachakand so, in particular,aN.
On the other hand, working backwards from the last equation we see thataNdivides
eachakand so, in particular,aandb.
The B ́ezout identity can also be obtained in this way, although Euclid himself
lacked the necessary algebraicnotation. Define sequences (xk), (yk) by the recurrence
relations
xk+ 1 =xk− 1 −qkxk, yk+ 1 =yk− 1 −qkyk ( 1 ≤k<N),with the starting values
x 0 = 0 , x 1 = 1 , resp.y 0 = 1 ,y 1 = 0.It is easily shown by induction thatak = axk+byk and so, in particular,aN =
axN+byN.
The Euclidean algorithm is quite practical. For example, the reader may use it to
verify that 13 is the greatest common divisor of 2171 and 5317, and that
49 × 5317 − 120 × 2171 = 13.However, the first proof given for Proposition 10 also has its uses: there is some
advantage in separating the conceptual from the computational and the proof actually
rests on more general principles, since there are quadratic number fields whose ring of
integers is a ‘principal ideal domain’ that does not possess any Euclidean algorithm.
It is not visibly obvious that the binomial coefficients
m+nC
n=(m+^1 )···(m+n)/^1 ·^2 ·····n
are integers for all positive integersm,n, although it is apparent from their combina-
torial interpretation. However, the property is readily proved by induction, using the
relation
m+nC
n=m+n− (^1) C
n+
m+n− (^1) C
n− 1.