Hoofdstuk 20 Priemgetallen

Hoofdstuk 20
Priemgetallen
20.1
Het aantal priemgetallen < X
In Hoofdstuk 3 hebben we kennis gemaakt met de echt elementaire zaken rond
priemgetallen zoals unieke priemontbinding en de oneindigheid van de verzameling priemgetallen. Hier gaan we iets dieper in op de vraag hoeveel priemgetallen
er nu eigenlijk zijn.
Een eerste indicatie wordt gegeven door een opmerkelijk bewijs van Euler over
de oneindigheid van de verzameling priemgetallen.
∑1
, genomen over alle priemgetallen p, diStelling 20.1.1 (Euler) De som
p
vergeert.
In iets uitgebreidere taal betekent dit dat de som
∑ 1
p
p≤N
p priem
naar oneindig gaat als N → ∞. In het bijzonder betekent dit dat er oneindig
veel priemgetallen zijn. Het bewijs van Euler beschouwt het product
)−1
∏(
1
1−
p
p≤N
over alle priemgetallen p ≤ N . Gebruiken we de meetkundige reeksontwikkeling
(1 − 1/p)−1 = 1 + 1/p + 1/p2 + · · · dan vinden we
)
)−1 ∏ (
∏(
1
1
1
=
1 + + 2 + ···
1−
p
p p
p≤N
p≤N
Om dit laatste product te berekenen moeten we haakjes wegwerken en we krijgen
een som van termen van de vorm 1/n waarin n bestaat uit priemfactoren ≤ N .
191
192
HOOFDSTUK 20. PRIEMGETALLEN
Bovendien komt, vanwege ´e´enduidige priemontbinding, voor elke n die bestaat
uit priemgetallen ≤ N de term 1/n in de sommatie voor. In het bijzonder komt
elke term 1/n met n ≤ N voor in onze sommatie. Dus
∏(
p≤N
1
1
1 + + 2 + ···
p p
)
N
∑
1
≥
n
n=1
∑
∏
1
Omdat de reeks ∞
n=1 n divergeert concluderen we dat het product
p≤N (1 −
−1
1/p) naar oneindig gaat als N → ∞.
1
Nu komt de ﬁnishing touch. Uit elementaire analyse weten we dat x > 12 log 1−x
als 0 < x ≤ 1/2. Hieruit volgt, met x = 1/p,
(
)−1 )
∑1
∏(
1∑
1
1
1
= log
>
log
1−
−1
p
2
1
−
p
2
p
p≤N
p≤N
p≤N
Omdat het laatste
∑ 1 product naar ∞ gaat als N → ∞ volgt uit deze ongelijkheid
dat de reeks
divergeert.
2
p
Het is niet moeilijk, maar wel technisch,
om bovenstaande analyse wat precieser
∑
1
uit te voeren. Het blijkt dat
p<X p in ongeveer hetzelfde tempo groeit als
log log X. Preciezer,
Stelling 20.1.2 (Mertens) Het verschil
∑1
− log log X
p
p<X
gaat naar een limiet A als X → ∞. Bovendien geldt
)
∑ (
1
1
A=γ+
log(1 − ) +
p
p
p priem
waarin γ Euler’s constante is.
∑
Hoewel de functie p<X p1 naar oneindig gaat als X → ∞, gaat dit in een ongelofelijk langzaam tempo. Bijvoorbeeld bij X = 104 is de som 2.483 bij X = 105
is het 2.705. Bij X = 106 , 107 vinden we respectievelijk 2.887 en 3.041.
We beschouwen nu de functie π(x) die het aantal priemgetallen ≤ x telt. Dus
π(x) = #{p ≤ x|p priem}.
Het gedrag van deze funktie is altijd een bron van inspiratie geweest voor wiskundigen. De rij priemgetallen heeft een onvoorspelbaar gedrag in die zin, als we een
priemgetal hebben dan is het onmogelijk te voorspellen wanneer het volgende
20.1. HET AANTAL PRIEMGETALLEN < X
193
priemgetal zal voorkomen. Bekijken we de funktie π(x) daarentegen dan zien we,
mits op grote schaal bekeken, een vloeiend verloop. Ter illustratie volgt hier de
graﬁek van π(x) voor x ≤ 100,
25
20
15
10
5
20
40
60
80
100
Nemen we nu een grotere schaal, dan zien we de sprongen niet meer en nemen
we een vloeiend verloop van de graﬁek waar. Hier is bijvoorbeeld de graﬁek voor
x ≤ 105 ,
8000
6000
4000
2000
20000
40000
60000
80000
100000
De grote vraag is of we deze graﬁek kunnen identiﬁceren met een ons bekende
funktie uit de analyse. Het dichtst bij de werkelijkheid kwam C.F.Gauss. Hij
telde het aantal priemgetallen in korte intervallen, maar met grote waarden, en
kwam tot de conclusie dat de lokale dichtheid van priemgetallen van de grootte
X er uit ziet als 1/ log(X). Wat we hiermee bedoelen illustreren we met de tabel
aan het eind van deze paragraaf. Daarin is het aantal priemgetallen s(x) in het
interval [x, x + 100000] geteld voor diverse grote waarden van x. Ter vergelijking
staat in de laatste kolom 105 / log(x), de lengte van ons interval gedeeld door
log(x). Uit dit soort gegevens kwam Gauss tot het vermoeden dat
∫
x
π(x) ∼ li(x) :=
2
dt
.
log t
194
HOOFDSTUK 20. PRIEMGETALLEN
Het teken ∼ geeft een zogenaamde asymptotische gelijkheid aan. In het algemeen,
als we schrijven f (x) ∼ g(x) dan bedoelen we daarmee dat f (x)/g(x) → 1 als
x → ∞. Het is trouwens niet moeilijk om aan te tonen dat li(x) ∼ x/ log(x)
zodat uit het vermoeden van Gauss zou volgen,
π(x) ∼
x
log x
Het eerste resultaat in deze richting werd bereikt door Chebyshev in 1852. Hij
liet zien dat
x
x
0.92
< π(x) < 1.11
log x
log x
als x voldoende groot is. De methoden van Chebyshev zijn elementair maar zeer
ingenieus en we zullen er in een latere paragraaf iets van laten zien. Hier is
trouwens de beloofde tabel.
x
108
109
1010
1011
1012
1013
1014
1015
s(x) 105 / log(x)
5411
5428
4832
4825
4306
4342
4019
3948
3614
3619
3382
3340
3045
3102
2804
2895
De belangrijkste stap in de studie van π(x) werd in 1860 gezet door de beroemde
wiskundige Riemann. We besteden hier de volgende paragraaf aan.
20.2
De Riemann zeta-functie
In zijn studie van π(x) gebruikte Riemann de functie
ζ(s) =
∞
∑
1
ns
n=1
waarin s een complex getal is met re¨eel deel groter dan 1, opdat de reeks convergeert. Tussen haakjes, in deze paragraaf zal het gedrag van ζ(s) voor complexe
s van cruciaal belang zijn. Enige vertrouwdheid met complexe getallen is hier
dus wel gewenst. Hoewel Euler de functie ζ(s) al eerder bekeken had in verband
met priemgetallen, is hij toch naar Riemann vernoemd. De relatie met priemgetallen, zoals Euler reeds opmerkte, wordt gegeven door de zogenaamde Euler
factorisatie.
20.2. DE RIEMANN ZETA-FUNCTIE
195
Stelling 20.2.1 (Euler) Zij s een complex getal met re¨eel deel groter dan 1.
Dan geldt,
)−1
∏(
1
ζ(s) =
1− s
p
p
waarin het product genomen wordt over alle priemgetallen.
We zullen ons bewijs beperken tot re¨ele getallen s groter dan > 1 om het iets
eenvoudiger te maken. Beschouw eerst het product
∑ 1
∑ 1
1
−
.
ζ(s)(1 − s ) =
2
ns n=1 (2n)s
n=1
∞
∞
Rechts staat de som van alle 1/ns minus de som van 1/ms over alle even m(= 2n).
Het verschil is dus de som van 1/ns over alle oneven getallen n. Evenzo is
ζ(s)(1 − 1/2s )(1 − 1/3s ) gelijk aan de som van 1/ns over alle n die noch deelbaar
door 2, noch deelbaar door 3 zijn. Kies nu N willekeurig en zij p1 = 2, p2 =
3, . . . , pr de verzameling priemgetallen ≤ N . Dan is ζ(s)(1 − 1/ps1 ) · · · (1 − 1/psr )
gelijk aan de som van 1/ns over alle n die niet deelbaar zijn door een priemgetal
≤ N . In het bijzonder impliceert dit dat ofwel n = 1 ofwel n > N . Dus
∑ 1
1
1
(20.1)
1 < ζ(s)(1 − s ) · · · (1 − s ) < 1 +
p1
pr
ns
n>N
∑
We weten door middel van de afschattingen uit
de Appendix dat n>N 1/ns <
∑
N 1−s /(s − 1). Omdat s > 1 volgt hieruit dat∏ n>N 1/ns → 0 als N → ∞. Laat
nu N → ∞ in (19.1) en we vinden dat ζ(s) p (1 − 1/ps ) = 1. Hieruit volgt ons
Euler product.
2
E´en van Riemann’s ontdekkingen was dat ζ(s) analytisch kan worden voortgezet
tot het complexe vlak met uitzondering van s = 1, waar de functie een pool van
eerste orde heeft. Het zou te ver voeren om dit hier allemaal uit te leggen. Wat
we wel kunnen laten zien is dat, hoewel we ζ(s) alleen deﬁnieerden voor s met
Res > 1, deze functie op natuurlijke wijze uit te breiden is tot een functie op het
gebied Res > 0, s ̸= 1. Dit gaat als volgt. Voor Res > 1 geldt,
∫ ∞
∞
∑
1
1
dx
ζ(s) −
=
−
s
s−1
n
xs
1
n=1
∫ ∞
∫ ∞
dx
dx
−
=
s
[x]
xs
1
)
∫1 ∞ (
1
1
=
− s dx
s
[x]
x
1
Nu komt de belangrijke opmerking. Het verschil 1/[x]s −1/xs kunnen we schrijven
als
∫ x
1
dt
1
− s =s
s
s+1
[x]
x
[x] t
196
HOOFDSTUK 20. PRIEMGETALLEN
Neem nu aan beide zijden de absolute waarde en schat de integraal af,
∫ x
1
1
dt
[x]s − xs ≤ |s|
s+1
|
[x] |t
∫ x
dt
= |s|
Res+1
[x] t
1
≤ |s| Res+1
[x]
∫∞
Res+1
Omdat 1 dx/[x]
convergeert voor alle Res > 0, volgt hieruit dat ook
∫∞
de integraal 1 (1/[x]s − 1/xs )dx convergeert voor alle Res > 0. Deze integraal deﬁnieert dus een functie op, die kan worden gezien als een natuurlijke
voortzetting van ζ(s) tot het gebied Res > 0.
Het gebied 0 < Res < 1 wordt wel de kritieke strook genoemd. Het gedrag van
ζ(s) in de kritieke strook is van cruciaal belang voor de theorie van de priemgetallen en dit was de schitterende ontdekking van Riemann. E´en van de vragen
die Riemann over ζ(s) stelde is zo hardnekkig onbeantwoord gebleven, dat het
nu te boek staat als het volgende vermoeden,
Vermoeden 20.2.2 (Riemann hypothese) Alle nulpunten van ζ(s) in de kritieke strook liggen op de lijn Res = 1/2.
Talloze wiskundigen na Riemann hebben hun tanden stukgebeten op dit probleem
en tot nu is het nog steeds onopgelost. Naast het, inmiddels opgeloste, vermoeden
van Fermat is dit ´e´en van de bekendste problemen in de wiskunde. Uit Riemann’s
nalatenschap blijkt dat hij zelf, met de hand, expliciet nulpunten berekend had
tot vele decimalen nauwkeurig. Dit alleen al mag een prestatie van formaat
worden genoemd. Omdat de nulpunten symmetrisch rond de x-as liggen, kunnen
we ons beperken tot nulpunten met positief imaginair deel. Tevens ordenen we
deze punten naar stijgend imaginair deel. Recente computerberekeningen door
Brent, v.d.Lune, te Riele en Winter hebben aangetoond dat de eerste 1.5 × 109
nulpunten inderdaad op de lijn Res = 1/2 liggen. Verder toonde Levinson in
1974 aan dat minstens een derde van de nulpunten op deze lijn ligt.
Uit het nagelaten werk van Riemann leidde C.L.Siegel af dat Riemann zijn numerieke berekeningen baseerde op een verwante, re¨ele, functie Z(t) die de eigenschap heeft dat |Z(t)| = |ζ( 12 + it)| voor alle t ∈ R. Voor de aardigheid volgt hier
een graﬁek van Z(t) gemaakt met het wiskundige pakket Mathematica,
20.2. DE RIEMANN ZETA-FUNCTIE
197
4
2
20
40
60
80
100
-2
-4
Wat is het belang van de nulpunten van ζ(s)? Het blijkt dat als de Riemann
hypothese waar is, dan geldt dat
π(x) − li(x)
√
x log x
naar nul gaat als x →
√ ∞. Grof gezegd, het verschil tussen π(x) en li(x) is van
de orde van grootte x log x, een stuk kleiner dus dan de grootte van li(x) zelf.
Hieronder volgt een graﬁek van de functie li(x) − π(x) voor x < 10000,
20
15
10
5
2000
4000
6000
8000
10000
-5
Men zou misschien kunnen denken dat het verschil li(x) − π(x) altijd positief
is. Het blijkt in ieder geval voor alle x < 1016 zo te zijn. Dat experimentele
resultaten soms bedriegelijk kunnen zijn werd duidelijk toen Littlewood (1914)
aantoonde dat li(x) − π(x) oneindig vaak van teken verandert. Echter het punt
waar li(x)−π(x) voor het eerst negatief wordt, heeft men nog nooit gezien. Onder
aanname van de Riemann hypothese bewees Skewes in 1933 dat dit punt kleiner
1034
dan 1010
is. Getallen van dit formaat werden al snel Skewes getallen genoemd.
Tegenwoordig is deze grens verbeterd en weet men, zonder de Riemann hypothese
aan te nemen, dat li(x) − π(x) negatief is voor een x kleiner dan 6.7 × 10370 .
Gelukkig hebben we niet de volle Riemann-hypothese nodig om iets over priemgetallen te kunnen concluderen. Met wat minder informatie ook wat te doen. Het
198
HOOFDSTUK 20. PRIEMGETALLEN
is namelijk niet heel moeilijk om aan te tonen dat ζ(s) geen nulpunten op de lijn
Res = 1 heeft. Met deze informatie slaagden Hadamard en De la Vall´ee-Poussin
er, onafhankelijk van elkaar, in de volgende stelling te bewijzen.
Stelling 20.2.3 (Priemgetalstelling, 1899) Er geldt,
π(x) ∼
x
.
log(x)
In 1949 gaven Selberg en Erd¨os, min of meer onafhankelijk van elkaar, een elementair bewijs van deze stelling. Elementair wil zeggen dat er geen gebruik
wordt gemaakt van eigenschappen van de complexe ζ-functie. Het wil echter niet
zeggen dat het een eenvoudig bewijs is!
20.3
Lokale verdeling
In de vorige paragraaf hebben we het gehad over de groei van de functie π(x).
Deze functie geeft de globale groei van het aantal priemgetallen weer. Het is ook
interessant om eens naar het lokale gedrag te kijken. Een vraag is bijvoorbeeld,
gegeven een priemgetal p, hoe groot is het volgende priemgetal? Anders gezegd,
hoe groot of klein kan de afstand tussen twee opeenvolgend priemgetallen zijn. We
kunnen gemakkelijk laten zien dat deze afstand willekeurig groot kan zijn. Kies
namelijk N ∈ N willekeurig en beschouw de rij getallen N !+2, N !+3, . . . , N !+N .
Omdat N !+k deelbaar is door k is geen van de getallen in onze rij priem. Door N
willekeurig groot te kiezen kunnen we op deze wijze het bestaan van willekeurig
lange ‘gaten’ in de rij priemgetallen aantonen.
Chebyshev bewees met elementaire methoden dat elk interval van de vorm [n, 2n]
een priemgetal bevat. Hiermee werd het zogenaamde postulaat van Bertrand
bewezen. Met behulp van de priemgetalstelling is het niet moeilijk om aan te
tonen dat voor elke θ > 1 en voldoend grote n elk interval [n, θn] een priemgetal
bevat.
Met geavanceerde methoden uit de analytische getaltheorie weet men nu dat er
een C > 0 bestaat zodat elk interval [n, n + Cnθ ] een priemgetal bevat, waarin
θ = 11/12 − 1/384 (Iwaniec, Pintz, Mozzochi). Indien de Riemann-hypothese
waar is kan men θ = 1/2 aantonen. Grofweg zou dit betekenen dat er tussen elk
tweetal gehele kwadraten en priemgetal ligt. Echter, men vermoedt dat er nog
iets veel sterkers waar is. Een vermoeden van Cram´er zegt dat er een C > 0 is
zo dat elk interval [n, n + C(log n)2 ] een priemgetal bevat. Niemand heeft echter
enig idee hoe een dergelijk probleem aangepakt moet worden.
Aan de andere kant gebeurt het opvallend vaak dat twee opeenvolgende oneven
getallen priem zijn. We noemen dergelijke paren priemtweelingen. Voorbeelden:
(71, 73), (1997, 1999), (20771, 20773), enzovoort. Het blijkt dat ze relatief vaak
voorkomen. Het grootst bekende paar in 1993 was 4650828×1001×103429 ±1 maar
20.4. ELEMENTAIRE BESCHOUWINGEN
199
intussen zal dit record wel weer gebroken zijn. Net als bij de priemgetallen kunnen
we een telfunctie π2 (x) invoeren die het aantal priemtweelingen kleiner dan x
aangeeft. Om een idee van de groei van π2 (x) te krijgen treden we in de voetsporen
van Gauss en tellen het aantal priemtweelingen s2 (x) in het interval [x, x+100000]
voor diverse x. Ter vergelijking geven we ook het aantal priemgetallen s(x). Hier
zijn de resultaten,
x
108
109
1010
1011
1012
1013
1014
1015
s(x) s2 (x)
5411 377
4832 341
4306 262
4019 182
3614 171
3382 142
3045 123
2804 117
(1.32) × 105 /(log x)2
389
307
249
205
172
147
127
110
De getallen in de laatste kolom vormen de verwachting van het aantal priemgetaltweelingen op grond van heuristische beschouwingen die we hier niet zullen
uitvoeren (zie [HW] hoofdstuk XXII).Het ∏
getal 1.32 bovenin de laatste kolom is
een afronding van het oneindige product p (1 − 1/(p − 1)2 ) genomen over alle
oneven priemgetallen p.
Als de verwachtingen kloppen, dan zou het aantal priemgetaltweelingen
kleiner
∏
dan x asymptotisch gelijk zijn aan π2 (x) ∼ Cx/(log x)2 met C = p (1 − 1/(p −
1)2 ). Helaas is er nog niets van dit alles bewezen. Het is zelfs niet bekend of er
oneindig veel priemgetaltweelingen zijn en de vraag naar de (on)eindigheid van
deze verzameling behoort tot de bekendste problemen in de getaltheorie. E´en van
de weinige bewezen∑
resultaten op dit gebied vormt de stelling van Brun (1919), die
zegt dat de reeks p p1 , genomen over alle p behorend tot een priemgetaltweeling, convergent is. Dit in tegenstelling tot de som over alle priemgetallen die
divergeert, zoals we gezien hebben. Om zijn stelling te bewijzen introduceerde
Brun een nieuwe techniek in de getaltheorie, namelijk die van de zeefmethoden.
Tegenwoordig is dit ´e´en van de standaardtechnieken in wat men noemt de analytische getaltheorie.
20.4
Elementaire beschouwingen
Na alle vermoedens en speculaties uit de vorige paragrafen willen we nu ook echt
iets gaan bewijzen. Doel van deze paragraaf is het bewijs van de volgende stelling.
Stelling 20.4.1 Voor elke n ≥ 3 geldt,
n
1 n
< π(n) < 2
.
2 log n
log n
200
HOOFDSTUK 20. PRIEMGETALLEN
Allereerst gebruiken we voor de aﬂeiding van de bovengrens voor π(x) de binomiaalco¨eﬃcient (zie eventueel de Appendix)
( )
2m
2m(2m − 1) · · · (m + 1)
=
m
m(m − 1) · · · 2 · 1
en het feit dat dit een geheel getal is. De cruciale opmerking is dat in de teller
alle priemgetallen p met m < p ≤ 2m optreden
en dat ze (niet) door de factoren
∏
uit de noemer worden weggedeeld. Dus m<p≤2m p deelt 2m
en is dus kleiner
m
(2m)
(2m)
of gelijk m . We gaan nu de grootte van m afschatten.
Lemma 20.4.2 Voor alle m ∈ N geldt,
( )
2m
< 4m .
m
()
Voor m = 1 controleren we dat 21 = 2 en 41 = 4 en het Lemma is dus juist. Stel
nu m > 1 en merk op dat
(
)
(
)
( )
2(m − 1)
2m
2m(2m − 1) 2(m − 1)
<4
=
m·m
m−1
m−1
m
Ons Lemma volgt nu door inductie naar m.
2
Een iets eleganter manier om dit Lemma aan te tonen is ∑
de opmerking
dat uit
(n)
n
n
de binomiaalformule van Newton,
k=0 k door x = 1
(n) 21.1,n volgt dat 2 =
in
te
vullen.
Hieruit
volgt
dat
<
2
voor
elke
k,
n
∈
N.
In het bijzonder,
k
(2m)
2m
m
<2 =4 .
m
Hoe dan ook, we concluderen dat voor alle m ∈ N geldt,
∏
p < 4m .
p priem
m<p≤2m
Het aantal factoren in het product is gelijk aan π(2m) − π(m). Al deze factoren
zijn groter dan m. Dus volgt,
mπ(2m)−π(m) < 4m .
Na het nemen van logaritmen aan beide zijden en deling door log m concluderen
we dat π(2m) − π(m) < m log 4/ log m.
We kunnen nu onze bovengrens door inductie naar n aﬂeiden. Omdat, behalve
2, alle priemgetallen oneven zijn, geldt π(n) ≤ (n + 1)/2. Elementaire analyse
laat zien dat (n + 1)/2 kleiner is dan 2n/ log n voor alle n ≤ 400 en dus is onze
bovengrens waar voor alle n ≤ 50. Stel nu n > 400 en dat de bovengrens in de
Stelling geldt voor alle π(k) met k < n. Stel n = 2m als n even is en n = 2m + 1
20.4. ELEMENTAIRE BESCHOUWINGEN
201
als n oneven is. In de volgende berekening maken we gebruik van onze bovengrens
voor π(2m) − π(m) en de inductiehypothese,
π(n) ≤
<
=
≤
π(2m) + 1 = π(2m) − π(m) + π(m) + 1
m log 4/ log m + 2m/ log m + 1
(2 + log 4)m/ log m + 1
(1 + log 2)n/ log(n/2) + 1
Elementaire analyse laat zien dat deze laatste bovengrens kleiner is dan 2n/ log n
voor alle n ≥ 150 en daarmee is onze inductiestap afgerond.
2
Voor de aﬂeiding van de ondergrens gebruiken we een iets ander idee. Beschouw
de integraal
∫ 1
tm (1 − t)m dt.
Im =
0
Omdat de integrand positief is in het open interval geldt Im > 0. Verder geldt
|tm (1 − t)m | ≤ (1/4)m voor alle t ∈ [0, 1]. Dus, Im < (1/4)m . Anderzijds is Im
een rationaal getal. Dit kunnen we zien door de haakjes in tm (1 − t)m weg te
werken en term voor term te integreren. Haakjes wegwerken levert een lineaire
combinatie met gehele co¨eﬃcienten van tk met k = m, m + 1, . . . , 2m. Integratie
van tk levert 1/(k + 1). Met andere woorden Im is een gehele lineaire combinatie
van de getallen 1/(k + 1) met k = m, . . . , 2m. Gevolg, Im is een rationaal getal
waarvan de noemer een deler is van kgv(m+1, m+2, . . . , 2m+1). Omdat Im niet
nul is, is het groter of gelijk 1/kgv(m + 1, . . . , 2m + 1). Combineren we dit met
de bovengrens voor Im dan vinden we kgv(m + 1, . . . , 2m + 1) > 4m en, omdat
kgv(1, 2, . . . , 2m + 1) ≥ kgv(m + 1, . . . , 2m + 1)
kgv(1, 2, . . . , 2m + 1) > 4m
Nu volgt een belangrijk Lemma.
Lemma 20.4.3 Voor elke N ∈ N geldt,
kgv(1, 2, . . . , N ) < N π(N ) .
We kunnen dit zien door op te merken dat het kgv van de getallen 1, 2, . . . , N
als volgt tot stand komt. Van elk priemgetal p bepalen we de grootste k z´o
dat pk ≤ N en vervolgens vermenigvuldigen we de machten pk met elkaar. Dit
product gaan we nu afschatten,
∏
kgv(1, 2, . . . , N ) =
p[log N/ log p]
p
<
∏
p(log N/ log p)
p
=
∏
p
N = N π(N )
202
HOOFDSTUK 20. PRIEMGETALLEN
2
In ons geval volgt door toepassing van dit Lemma dat 4m < (2m + 1)π(2m+1) . Na
het nemen van logaritmen en deling door log(2m + 1), geeft dit
π(2m + 1) > m log 4/ log(2m + 1)
Kies nu n ∈ N willekeurig. Stel n = 2m + 1 als n oneven is en n = 2m + 2 als n
even is. Merk nu op dat
π(n) = π(2m + 1) > m log 4/ log(2m + 1))
≥ (log 4)(n/2 − 1)/ log(n − 1)
Elementaire analyse laat zien dat de laatste ondergrens groter is dan 0.5n/ log(n)
als n ≥ 10. En zo vinden we de gewenste ondergrens als n ≥ 10. Voor n =
3, 4, . . . , 9 controleren we de ondergrens numeriek.
2
Tenslotte volgt hier nog een heel amusante opgave van H.W.Lenstra. Bewijs dat
er oneindig veel waarden van n zijn z´o dat π(n) een deler is van n. Het aardige is
dat het bewijs helemaal niet diepzinnig is, maar wel veel te leuk om hier te verklappen. Als hint kan ik de lezer meegeven dat we alleen maar limn→∞ π(n)/n = 0
hoeven te gebruiken.

Download Report