Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
321.Podstawowepojęcia
R.Weinstock[1]podałprostąmetodępraktycznegoznajdowaniaprzynajmniejjed-
negorozwiązaniarównania(1.7),opartąnadowodzietwierdzenia1.6.Wystarczyprzy
tymograniczyćsiędoprzypadku,gdybl(ai,a2,...,an).Wybierzmyliczbycałkowite
zi,z2,...,zntak,byliczbabilΣ
jliajzjbyładodatnia.(Ododpowiedniegodoboru
n
tychliczbzależyszybkośćalgorytmu).Jeślibilb,torozwiązaniejużmamy.Wprze-
ciwnymrazieztwierdzenia1.6wynikabi>b,azatemniewszystkieliczbyaidzielą
sięprzezbi.Niechnaprzykładbiłai.Wtedymożemynapisaćailqbi+b2,przyczym
0<b2<bi.Jeśliterazprzyjmiemywil1lqziiwillqzi(il2,3,...,n),to
otrzymamy
0<b2l
Σ
jli
n
ajwj<bi.
Powtarzająctęprocedurę,otrzymamymalejącyciągbi>b2>...≥bliczb
naturalnych,dającychsięprzedstawićwpostaciΣ
jliajXjprzycałkowitychXj,azatem
n
poodpowiedniejliczbiekrokówdojdziemydoprzedstawieniabwżądanejpostaci.(Inne
algorytmypodaliW.A.Blankinship[1]iG.H.Bradley[1]).
Wprzypadkunl2możemyzastosowaćalgorytmEuklidesadoparyai,a2,gdyż
wzór(1.5)pokazuje,żewszystkieresztyrjpojawiającesięprzywykonywaniutego
algorytmudadząsięprzedstawićwpostaciaiXi+a2X2przyodpowiednichXi,X2∈Z.
Wtensposóbotrzymamytakieprzedstawienieidlaostatniejniezerowejreszty,równej
(ai,a2).
Wprzypadkugdyliczbaa2jestniewielka,łatwiejdojdziemydotegocelu,obliczając
resztyzdzielenialiczbjai(jl1,2,...)przeza2ażdomomentu,gdyprzypewnym
joliczbajoaidaresztę1.Wówczas,kładącxiljo,x2ll(aijol1)/a2,otrzymujemy
rozwiązanie.(InnysposóbpodałD.A.Marcus[1]).
2.Zajmiemysięterazwyznaczeniemwszystkichrozwiązańrównania(1.7),zakła-
dającoczywiście,żeb|(ai,a2,...,an).Wtymceluwygodniebędzieużywaćjęzyka
przestrzeniliniowych.OznaczmyprzezQnprzestrzeńliniową,którejelementamisą
wszystkieciągi(xi,x2,...,xn)liczbwymiernychonwyrazach,aprzezZnjejpod-
zbiórutworzonyzwektorówocałkowitychskładowych.OznaczmyprzezL(x)funkcję
owartościachwymiernych,określonądlaxl(xi,x2,...,xn)∈Qnwzorem
L(x)l
Σ
jli
n
ajxj,
przyczymzakładamy,żeprzynajmniejjednazliczbajnieznika.WtedyoczywiścieL
jestprzekształceniemliniowym,tj.zachodziwzór
L(Ix+;y)lIL(x)+;L(y)
(I,;∈Q,x,y∈Qn),
arównanie(1.7)przybierapostaćL(x)lb.
Poniższylematsprowadzanaszezagadnieniedoznalezieniawszystkichrozwiązań
równaniajednorodnegoL(x)l0,przyx∈Zn:
