Number Theory: An Introduction to Mathematics

2TheB ́ezout Identity 91

For example, ifa 1 ,...,anare given elements ofZ, then the set of all linear com-

binationsa 1 x 1 +···+anxnwithx 1 ,...,xn∈Zis an ideal, the idealgeneratedby

a 1 ,...,an. An ideal generated by a single element, i.e. the set of all multiples of that

element, is said to be aprincipal ideal.

Lemma 9Any ideal J in the ringZis a principal ideal.

Proof If 0 is the only element ofJ, then 0 generatesJ. Otherwise there is a nonzero

a∈Jwith minimum absolute value. For anyb∈ J, we can writeb=qa+r,for

someq,r ∈Zwith|r|<|a|. By the definition of an ideal,r∈ Jand so, by the

definition ofa,r=0. ThusageneratesJ. 

Proposition 10Any a,b∈Zhave a greatest common divisor d=(a,b). Moreover,

for any c∈Z,thereexistx,y∈Zsuch that

ax+by=c

if and only if d divides c.

Proof LetJbe the ideal generated byaandb. By Lemma 9,Jis generated by a
single elementd.Sincea,b∈J,dis a common divisor ofaandb. On the other hand,
sinced∈J,thereexistu,v∈Zsuch thatd=au+bv. Hence any common divisor of
aandbalso dividesd. Thusd=(a,b). The final statement of the proposition follows
immediately since, by definition,c∈Jif and only if there existx,y∈Zsuch that
ax+by=c.

It is readily shown that if the ‘linear Diophantine’ equationax+by=chas a

solutionx 0 ,y 0 ∈Z, then all solutionsx,y∈Zare given by the formula

x=x 0 +kb/d, y=y 0 −ka/d,

whered=(a,b)andkis an arbitrary integer.

Proposition 10 provides a new proof for the existence of greatest common divisors

and, in addition, it shows that the greatest common divisor of two integers can be rep-

resented as a linear combination of them. This representation is usually referred to as

theB ́ezout identity, although it was already known to Bachet (1624) and even earlier

to the Hindu mathematicians Aryabhata (499) and Brahmagupta (628).

In exactly the same way that we proved Proposition 10 – or, alternatively, by

induction from Proposition 10 – we can prove

Proposition 11Any finite set a 1 ,...,anof elements ofZhas a greatest common

divisor d=(a 1 ,...,an). Moreover, for any c∈Z,thereexistx 1 ,...,xn∈Zsuch that

a 1 x 1 +···+anxn=c

if and only if d divides c.

The proof which we gave for Proposition 10 is a pure existence proof – it does

not help us to find the greatest common divisor. The following constructive proof was

already given in Euclid’sElements(Book VII, Proposition 2). Leta,bbe arbitrary