Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
20
Rozdział1.Arytmetykaliczbcałkowitych
Zauważmy,żeskorodlakażdego
n
,dlaktórego
rn>0
zachodzi
0⩽rn+1<rn
,
ciąg
(rn)
jestskończony.Istniejewięctakie
k>1
,że
rk>0
oraz
rk+1=0
.Stądmamy
ciągkrówności:
(
I
I
I
I
I
I
4
r0=!1r1+r2,
r1=!2r2+r3,
...
r2<r1,
r3<r2,
(1.5)
I
I
I
I
rk−2=!k−1rk−1+rk,rk<rk−1,
I
I
l
rk−1=!krk.
NWD(rk−2,rk−1)=NWD(rk−1,rk)=rk
twierdzenie.
Zfaktu1.7wynika,że
(gdzieciąg
Niech
mamywówczasrk=NWD(a,b).
Twierdzenie1080
a,b∈Z,a,b̸=0
(rn)
jestwyznaczonyzapomocąalgorytmuEuklidesa).Cowięcej,
NWD(a,b)=NWD(r0,r1)=NWD(r1,r2)=...=
.Istniejetakie
.Tooznacza,żeprawdziwejestnastępujące
k
całkowite,że
rk̸=0
oraz
rk+1=0
AlgorytmEuklidesakończysięwliczbiekrokówograniczonejprzez
|b|
iwtym
sensiejesttoalgorytmszybki12.
Niech
czas
Twierdzenie1090
a
i
b
będąliczbamicałkowitymi,nierównymirównocześniezero.Wów-
NWD(a,b)=min{d>0:d=ax+by,x,y∈Z}.
Dowód0Niech
A={d∈N−{0}:d=Ia+βb,I,β∈Z}
.Zauważmy,że
A̸=∅
oraz,żeminAistnieje.
Oznaczmyd=minA.
Oczywiścied∈A,awięcistniejątakieIiβ,żed=Ia+βb.
Wykażemywpierw,żed|a.
Rzeczywiście,przypuśćmy,że
a=!d+r,
gdzied>r>0.Wówczas
0<r=a−!d=a−!(Ia+βb)=a(1−!I)+b(−!β)<d,
atojestsprzecznezdefnicjądjakonajmniejszegoelementuzbioruA.
12
Zaalgorytmszybkiuważasiętaki,którykończydziałaniepoczasieograniczonymprzezfunkcję
wielomianowąwielkościproblemu.Wnaszymprzypadkurozsądnejestprzyjąć,żewielkośćproblemu,to
|b|
.
