202 Greatest common divisor
5.1 gcd(a, b)as an integer combination ofaandb
It is well known that the gcd of two (positive) integersaandbcan be
calculated efficiently by repeated divisions. Assumea>b. We form
two sequencesrkandqkas follows. Beginning withr− 1 =aandr 0 =b,
fork≥ 0 , let
qk=⌊
rk− 1
rk⌋
,rk+1=mod(rk− 1 ,rk):=rk− 1 −qkrk.These divisions eventually terminate when somerndividesrn− 1. In that
case,gcd(a, b)=rn.
If, along with these divisions, we introduce two more sequences(xk)
and(yk)with the same rule but specific initial values, namely,
xk+1=xk− 1 −qkxk,x− 1 =1,x 0 =0;
yk+1=yk− 1 −qkyk,y− 1 =0,y 0 =1.then we obtaingcd(a, b)as an integer combination ofaandb:^1
gcd(a, b)=rn=axn+byn.k rk qk xk yk
− 1 a ∗∗∗ 1 0
0 b ab 0 1
1 a−abb rb 1 x 1 y 1
..
.
n− 1 rn− 1 qn− 1 xn− 1 yn− 1
n rn qn xn yn
n+1 0
It can be proved that|xn|<band|yn|<a.Theorem 5.1.Given relatively prime integersa>b, there are unique
integersh,k<asuch thatak−bh=1.
Proof.Clearly,xnandynare opposite in sign. Take(k, h)=(xn,−yn)
or(b+xn,a−yn)according asxn> 0 or< 0.
Corollary 5.2.Letpbe a prime number. For every integeranot divisible
byp, there exists a positive integerb<psuch thatab− 1 is divisible by
p.
(^1) In each of these steps,rk=axk+byk.