Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.1.Podzielność,liczbypierwsze
17
pokazano,żeliczba2228il1o687cyfrachjestpierwsza(Robinson[1]nakompute-
rzeSWAC).Następnelataprzyniosłyszybkipostępwtejdziedzinie.Listękolejnych
rekordówmożnaznaleźćwksiążceP.Ribenboima[2].Przeglądającemująrzucasię
woczy,żezwyjątkiemrekorduMilleranaliścietejznajdująsięwyłącznieliczby
postaciMpl2pl1,przyczymwykładnikpjestliczbąpierwszą.Sątotzw.liczby
Mersenne’a.M.Mersennenapisałw1644r.,żedlapl2,3,5,7,13,17,19,31,67,127
i257liczbyMpsąpierwsze,adlapozostałychp<257sązłożone.Toniejestwpełni
słuszne,gdyżokazałosiępóźniej,iżliczbyM67iM257sązłożone,aM6i,M89iMio7
sąpierwsze.PojawianiesięliczbMersenne’analiścierekordówwynikazistnieniasto-
sunkowoprostejmetodysprawdzaniapierwszościliczbtejpostaci,znalezionejprzez
E.Lucasa[1],auproszczonejprzezD.H.Lehmera[1](testLucasa–Lehmera):
JeśliSil4orazSklS2
klil2(dlak≥2),toliczbaMpjestpierwszawtedy
itylkowtedy,gdyMp|Spli.
Dowódtegotestuznaleźćmożnam.in.wnastępującychksiążkach:Sierpiński[4],
Narkiewicz[2].BardzoprostydowódznalazłniedawnoJ.W.Bruce[1].
Największąobecnie(grudzień2002)znanąliczbąpierwsząjestliczbaMi34669i7,
mająca4053946cyfr(M.Cameron,studentzKanady),apoprzednimirekordembyła
liczbaM6972593(N.Hajratwalaizespół,czerwiec1999).Zobaczymypóźniej,żezbiór
wszystkichliczbpierwszychjestnieskończony,awięcznajdowaniecoraztowiększych
takichliczbmożeświadczyćjedynieorozwojutechnikiobliczeniowej,adosamejteorii
wnosiniewiele.Niejesttowszakżezadaniecałkowiciebezużyteczne,gdyżdużeliczby
pierwszesąużywanedokonstrukcjitrudnychdozłamaniakodów(patrznp.Koblitz[1]).
4.Ilośćliczbpierwszychnieprzekraczającychxoznaczasiętradycyjnieprzezπ(x).
Mamyoczywiścieπ(2)l1,π(10)l4,anietrudnosprawdzić,żeπ(100)l25,
π(1000)l168,π(104)l1291.Niecodłużejtrwasprawdzenierównościπ(108)l
5761455.JużwElementachEuklidesamożnaznaleźćdowódtego,żeliczbpierwszych
jestnieskończeniewiele,tj.
x→∞
lim
π(x)l∞.
Podamyterazczterydowodytegorezultatu:
TWIERDZENIE1.4.ZbiórPliczbpierwszychjestnieskończony.
DowódI(Euklides).Przypuśćmy,żePl{pi,p2,...,pn}jestzbioremskończonym.
LiczbaNl1+pip2···pnjestwiększaodjedności,aprzytymdajeonaresztęrówną
1/l0przydzieleniuprzezkażdąliczbępierwszą.Zatemniedzielisięprzezżadną
liczbępierwszą,coprzeczywnioskowi1zpoprzedniegotwierdzenia.
DowódII(L.Euler).Wtymdowodziewykorzystamyrozbieżnośćszereguharmo-
nicznego
Σ
kli
∞
1
k
.
1Aktualnąlistęnajwiększychznanychliczbpierwszychmożnaznaleźćwinterneciepodadresem
www.utm.edu/research/primes//largest.html
