Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
241.Podstawowepojęcia
3.Udowodnić,żejeślizmodyfikujemyalgorytmEuklidesa,biorączamiast
najmniejszejnieujemnejresztyresztęonajmniejszejbezwzględnejwartości,to
tezatwierdzeniał.7pozostanieniezmieniona.
4.Niechunoznaczan-tywyrazciąguFibonacciegozdefiniowanegowzorami
u1lu2lł,
un+1lun+unl1(nl2,3,...).
(i)Udowodnić,że(um,un)lu(m,n)iwykorzystaćtododowoduistnienia
nieskończeniewieluliczbpierwszych.
(ii)Udowodnić,żedlanlł,2,...zachodziwzór
unl
(ł+d5)nl(łld5)n
2nd5
.
5.(i)Pokazać,żedlaciąguFibonacciego{un}zachodzinierówność
un+5l>ł0
lu
n
(nl2,3,...;llł,2,...).
(ii)Wykorzystać(i)dopokazania,żejeślim<n,toliczbakrokówwalgoryt-
mieEuklidesazastosowanegodoparya,b(gdziealum,blun)nieprzekracza
5r,gdzierjestilościącyfrliczbyawzapisiedziesiętnym.
(iii)(Lam´
e[ł])Pokazać,żewynik(ii)jestsłusznydladowolnychliczbnatu-
ralnycha<b.
6.Wykorzystaćmetodępierwszegodowodutwierdzeniał.4dopokazania,że
istniejenieskończeniewieleliczbpierwszychzarównowpostępiearytmetycznym
4nlł,jakiwpostępie6nlł.
1.2.Jednoznacznośćrozkładunaczynnikipierwsze
1.Jednymzpodstawowychrezultatówelementarnejteoriiliczbjesttwierdzenie
ojednoznacznościrozkładuliczbnaturalnychnaczynnikipierwsze,któreterazprzed-
stawimy:
TWIERDZENIE1.8.Każdąliczbęnaturalnąn>1możnaprzedstawićjednoznaczniewpo-
staci
nlpi···pk,
(1.6)
przyczympi≤p2≤...≤pksąliczbamipierwszymi.Wśródliczbpiwystąpikażdy
dzielnikpierwszyliczbyn.
Dowód:Istnienietakiegoprzedstawieniajestzawartewtwierdzeniu1.3.Pozostaje
zatemwykazaniejedyności.Zastosujemytuindukcję.Dlaliczbynl2tezatwierdzenia
jestoczywista.Przypuśćmy,żetwierdzeniejestfałszyweiniechNbędzienajmniejszą
liczbęnaturalną,mającądwaróżnerozkłady(1.6),powiedzmy
Nlpip2···prlqiq2···q5,
