Number Theory: An Introduction to Mathematics

2TheB ́ezout Identity 93

Binomial coefficients have other arithmetic properties. Hermite observed thatm+nCn
is divisible by the integers(m+n)/(m,n)and(m+ 1 )/(m+ 1 ,n). In particular, the
Catalan numbers(n+ 1 )−^12 nCnare integers. The following proposition is a substan-
tial generalization of these results and illustrates the application of Proposition 10.

Proposition 12Let(an)be a sequence of nonzero integers such that, for all m,n≥ 1 ,
every common divisor of amand andivides am+n, and every common divisor of am
and am+ndivides an. Then, for all m,n≥ 1 ,

(i)(am,an)=a(m,n);
(ii) Am,n:=am+ 1 ···am+n/a 1 ···an∈Z;
(iii)Am,nis divisible by am+n/(am,an),byam+ 1 /(am+ 1 ,an)and by an+ 1 /(am,an+ 1 );
(iv)(Am,n− 1 ,Am+ 1 ,n,Am− 1 ,n+ 1 )=(Am− 1 ,n,Am+ 1 ,n− 1 ,Am,n+ 1 ).

Proof The hypotheses imply that

(am,an)=(am,am+n) for allm,n≥ 1.

Sinceam=(am,am), it follows by induction thatam|akmfor allk≥1. Moreover,

(akm,a(k+ 1 )m)=am,

since every common divisor ofakmanda(k+ 1 )mdividesam.
Putd=(m,n).Thenm=dm′,n=dn′,where(m′,n′)=1. Thus there exist
integersu,vsuch thatm′u−n′v=1. By replacingu,vbyu+tn′,v+tm′with any
t>max{|u|,|v|}, we may assume thatuandvare both positive. Then

(amu,anv)=(a(n′v+ 1 )d,an′vd)=ad.

Sinceaddivides (am,an)and(am,an)divides(amu,anv), this implies (am,an)=ad.
This proves (i).
Sincea 1 |am+ 1 , it is evident thatAm, 1 ∈Zfor allm≥1. We assume thatn>1and
Am,n∈Zfor all smaller values ofnand allm≥1. Since it is trivial thatA 0 ,n∈Z,we
assume also thatm≥1andAm,n∈Zfor all smaller values ofm. By Proposition 10,
there existx,y∈Zsuch that

amx+any=am+n,

since (am,an)dividesam+n.Since

Am,n=

am+ 1 ···am+n

a 1 ···an

=

amam+ 1 ···am+n− 1

a 1 ···an

x+

am+ 1 ···am+n− 1

a 1 ···an− 1

y,

our induction hypotheses imply thatAm,n∈Z. This proves (ii).
Since

am+nAm,n− 1 =anAm,n,

am+ndivides (an,am+n)Am,nand, since(an,am+n)=(am,an), this in turn implies
thatam+n/(am,an)dividesAm,n.