Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.1.Podzielność,liczbypierwsze
23
Procedurętęmożnaniecoprzyspieszyć,jeśliwprzypadkunieparzystycha,bodużej
różnicy,zamiastbraniaróżnicywykonamydzieleniezresztą.Obliczająctymsposobem
naprzykładnajwiększywspólnydzielnikliczb23458i1235,otrzymujemy
234581235
117291235
itu,zamiastodejmowania,wykonujemydzieleniezresztą,coprowadzidopary
1235614
idalejmamy:
1235307
928307
464307
232
307
116307
58307
29307
29
17l307l10·29,
atujużwidzimy,żeszukanyNWDjestrównyjedności.
AnalizęalgorytmówEuklidesaibinarnegomożnaznaleźćwIItomieksiążki
D.Knutha[1],aniedawnoB.Vall´
ee[1]pokazała,żeśrednialiczbakrokówwal-
gorytmiebinarnymdlanieparzystychliczba,b≤NjestrównawprzybliżeniuclogN
zpewnądodatniąstałąc.
Ćwiczenia
1.Niechpnoznaczan-tąliczbępierwszą.
(i)Udowodnić,że
(ii)Udowodnićnierówność
2.(i)Pokazać,żejeśli2n+łjestliczbąpierwszą,tonjestpotęgąliczby2.
(ii)Pokazać,żejeśli2nlłjestliczbąpierwszą,tonjestteżliczbąpierwszą.
pn<e
limsup
n→∞
1+n
(pn+1lpn)l∞.
(nlł,2,...).
