2TheB ́ezout Identity 95chosen vertices is equal to the greatest common divisor of the remaining three vertices.
Hillman and Hoggatt also gave generalizations along the lines of Proposition 12.
The hypotheses of Proposition 12 are also satisfied ifan =qn−1, for some
integerq > 1, since in this caseam+n = aman+am+an. The corresponding
q-binomial coefficientswere studied by Gauss and, as mentioned in Chapter XIII, they
play a role in the theory of partitions.
We m a y a l s o t a k e(an)to be the sequence defined recurrently by
a 1 = 1 , a 2 =c, an+ 2 =can+ 1 +ban(n≥ 1 ),wherebandcare coprime positive integers. Indeed it is easily shown by induction that
(an,an+ 1 )=(b,an+ 1 )=1foralln≥ 1.By induction onmone may also show that
am+n=am+ 1 an+baman− 1 for allm≥ 1 ,n> 1.It follows that the hypotheses of Proposition 12 are satisfied. In particular, for
b=c=1, they are satisfied by the sequence ofFibonacci numbers.
We consider finally extensions of our results to more general algebraic structures.
An integral domainRis said to be aBezout domain ́ if anya,b∈ Rhave a com-
mon divisor of the formau+bvfor someu,v∈R. Since such a common divisor
is necessarily a greatest common divisor, any B ́ezout domain is a GCD domain. It is
easily seen, by induction on the number of generators, that an integral domain is a
B ́ezout domain if and only if every finitely generated ideal is a principal ideal. Thus
Propositions 10 and 11 continue to hold ifZis replaced by any B ́ezout domain.
An integral domainRis said to be aprincipal ideal domainif every ideal is a
principal ideal.
Lemma 13An integral domain R is a principal ideal domain if and only if it is a
B ́ezout domain satisfying the chain condition
(#) there exists no infinite sequence (an) of elements of R such that an+ 1 is a proper
divisor of anfor every n.
Proof It is obvious that any principal ideal domain is a B ́ezout domain. SupposeRis
aB ́ezout domain, but not a principal ideal domain. ThenRcontains an idealJwhich
is not finitely generated. Hence there exists a sequence (bn)ofelementsofJsuch that
bn+ 1 is not in the idealJngenerated byb 1 ,...,bn.ButJnis a principal ideal. Ifan
generatesJn,thenan+ 1 is a proper divisor ofanfor everyn. Thus the chain condition
is violated.
Suppose now thatRis a B ́ezout domain containing a sequence (an) such thatan+ 1
is a proper divisor ofanfor everyn.LetJdenote the set of all elements ofRwhich
are divisible by at least one term of this sequence. ThenJis an ideal. For ifaj|band
ak|c,wherej≤k,thenalsoak|band henceak|bx+cyfor allx,y∈R.IfJwere
generated by a single elementa, we would havea|anfor everyn. On the other hand,
sincea∈J,aN|afor someN. HenceaN|aN+ 1 .SinceaN+ 1 is a proper divisor ofaN,
this is a contradiction. ThusRis not a principal ideal domain.