Voorbeeld: de grootste gemene deler van 100 en 15 vinden we door 100 = 6×15 + 10 en 15 = 1×10 + 5 en 10 = 2×5 op te schrijven. De grootste gemene deler is dus 5.
Notatie: ggd(a,b), in het Engels gcd(a,b), greatest common divisor. Als geen verwarring kan ontstaan laat men "ggd" weg, en schrijft (100,15) = (15,10) = (10,5) = 5.
Dit algoritme om de grootste gemene deler te bepalen heet het Euclidisch algoritme. Het is heel belangrijk omdat het efficiënt is, ook als de getallen zeer groot zijn, terwijl bijvoorbeeld ontbinden in factoren van grote getallen (zeg, van meer dan 200 cijfers) vaak ondoenlijk is.
Stelling (Euclides) Er zijn oneindig veel priemgetallen.
Als een getal n (groter dan 1) niet priem is, dan heeft het een deler die niet groter dan wortel(n) is. Dus om te controleren dat 103 priem is hoef ik alleen vast te stellen dat het niet door 2, 3, 5, 7 deelbaar is.
Algoritme: alle priemgetallen tot aan zekere (kleine) grens N vindt men met de zeef van Eratosthenes: Schrijf de getallen 2 t/m N op. Het kleinste niet doorgestreepte en niet omcirkelde getal is priem. Omcirkel het en streep alle veelvouden door. Herhaal dit totdat het kleinste niet doorgestreepte getal groter dan wortel(N) is. Omcirkel alle overige niet doorgestreepte getallen. De omcirkelde getallen zijn de priemgetallen niet groter dan N.
(Bewijs: (i) (am,bm) = (a,b)m, (ii) als (a,c)=1 dan (ab,c) = (b,c) (want (ab,bc)=b), (iii) als p priem is en een product deelt, dan deelt p een van de factoren.)
Later zal blijken dat bijvoorbeeld ook Z[i], de verzameling getallen van de vorm a+bi met a,b geheel en i de wortel uit -1, eenduidige ontbinding in priemfactoren kent. Sommige oude priemgetallen blijven priem (bijvoorbeeld 3), andere priemgetallen zijn niet priem in Z[i] (bijvoorbeeld 2 = (1+i)(1-i)). Andere getalverzamelingen hebben geen eenduidige ontbinding in priemfactoren. Bijvoorbeeld als w de wortel uit -5 is, dan is 6 = 2×3 = (1+w)(1-w), en de vier getallen 2,3,1+w,1-w zijn alle priem binnen de verzameling van getallen a+bw, a en b geheel.
Deze "priemgetalstelling" zegt dus dat de kans dat een getal in de buurt van x priem is gelijk aan 1/log(x) is. Het bewijs is niet triviaal. Makkelijker is om te laten zien dat de verhouding tussen pi(x) en x/log(x) begrensd blijft, bijvoorbeeld tussen 1/2 en 2 ligt. (Stelling [Rosser]: voor x >= 55 geldt x/(log(x)+2) < pi(x) < x/(log(x)-4).)
De verdeling van priemgetallen is grillig. Een priemtweeling is een paar priemgetallen met verschil 2, zoals 11 en 13, of 10016957 en 10016959. Het vermoeden van Goldbach zegt dat er oneindig veel priemtweelingen zijn. Er is een grote geldprijs uitgeloofd voor degene die dit ook bewijzen kan.
Bij een priemtweeling is het gat klein. Ook grote gaten komen voor. Er ligt geen priem tussen 1327 en 1361 of tussen 370261 en 370373. Het interval van n!+2 tot aan n!+n bevat geen priemgetallen, dus er zijn willekeurig lange stukken zonder priem.
Met eenvoudige middelen bewijzen we de stelling van Bertrand:
Stelling Voor elk natuurlijk getal n is er een priemgetal
p met n < p <= 2n.
Bewijs: (i) het product van alle priemen kleiner of gelijk aan x
is kleiner of gelijk aan 4^x. (Inductie. Gebruik dat (2m+1 kies m)
kleiner is dan 4^m.)
(ii) De exponent waarmee p voorkomt in n! is gelijk aan
[n/p] + [n/p^2] + [n/p^3] + ...
(iii) De exponent waarmee p voorkomt in
N = (2n kies n) is gelijk aan
som ([2n / p^i] - 2[n / p^i]).
(iv) Als er tussen n en 2n geen priemen zijn dan zijn alle
priemdelers van N kleiner of gelijk aan n, en vanwege (iii)
zelfs kleiner of gelijk aan 2n/3.
(v) Nu is log N klein vanwege (i): niet meer dan
(2n/3) log 4 plus termen voor priemen die tot een hogere macht
voorkomen, een bijdrage van niet meer dan wortel(2n).log(2n).
Aan de andere kant is log N groot omdat N de grootste term is
in de binomiale expansie van (1+1)^2n in 2n+1 termen, zodat
N > 4^n / (2n+1) en log N > n log 4 min
weinig.
Dus zo ongeveer: n log 4 < (2/3) n log 4, een tegenspraak.
Met de kleine termen meegenomen komt de tegenspraak by n=500
en moet voor kleine n gecontroleerd worden dat de stelling klopt.
In[1]:= PrimePi[1000000] Out[1]= 78498Hoeveel had je verwacht? Als je x/log(x) verwacht, met x=1000000 dan vind je
In[2]:= x=1000000 In[3]:= N[x/Log[x]] Out[3]= 72382.4Veel nauwkeuriger is de integraal van 2 tot x van 1/log(x). (Dat is x/log(x) + x/log(x)^2 + ...) Dit levert
In[4]:= Integrate[1/Log[y],{y,2,1000000}]
Out[4]= -LogIntegral[2] + LogIntegral[1000000]
In[5]:= N[%]
Out[5]= 78626.5
Over vierlingen gaat het verhaal Enumeration of prime quadruplets van Nicely. Hij rekent 5,7,11,13 mee, en 2,3,5,7 niet, maar telt verder dezelfde dingen. (Want: als n+1,n+3,n+7,n+9 allen priem zijn, en n > 4, dan volgt dat n deelbaar is door 10.) De tabel van Nicely heeft 166, dus ons antwoord is 165 als 2,3,5,7 niet telt (zoals ik op college vroeg) of ook 166 (bij de vraag als boven geformuleerd). Met Mathematica (oplossing van Petra Janssen):
In[6]:= Sum[If[PrimeQ[10*i + 1] && PrimeQ[10*i + 3] && PrimeQ[10*i + 7] &&
PrimeQ[10*i + 9], 1, 0], {i, 99999}]
Out[6]= 165
Oplossing van Stefan Cardon:
In[7]:= Prime[Range[78498]];
In[8]:= L = % - Mod[%, 10];
In[9]:= T = 0; Do[If[L[[i]] == L[[i + 3]], T++, 0], {i, 1, Length[L] - 3}];
In[10]:= T
Out[10]= 166
Wat moeten we verwachten? Dat is niet heel eenvoudig.
De kans dat een getal in de buurt van x priem is, is 1/log(x). Maar als dat dan priem is, zijn de kansen van x+2 verbeterd: de helft van de getallen is even, en de kans dat een even getal priem is, is 0. Dat betekent dat de kans dat een oneven getal priem is, 2/log(x) is. Kortom, als we naar de priem 2 kijken staat x+2 er gunstiger voor dan zo maar een getal. Aan de andere kant, als we naar 3 kijken, dan is de kans dat een willekeurig getal door 3 deelbaar is: 1/3. Maar als we al weten dat x niet door 3 deelbaar is, dan is de kans dat x+2 door 3 deelbaar 50% want x is 1 of 2 mod 3 en dan is x+2 gelijk aan 0 of 1 mod 3. OK, dus voor het priemgetal 2 staat x+2 er goed voor, en voor alle andere priemgetallen wat slechter dan een gemiddeld getal.
Zulke overwegingen leiden tot de conclusie dat de kans op een priemtweeling in de buurt van x gelijk aan 1.3203/log(x)^2 zou moeten zijn, waarbij die constante 1.3203 berekend is als 2 keer het product over alle oneven priemgetallen p van p(p-2)/(p-1)^2. Als "controle": het aantal priemtweelingen onder de 10^11 is 224376048. En
In[11]:= Integrate[1.3203/Log[y]^2,{y,2,100000000000}]
8
Out[11]= 2.24365 10 + 0. I
Dat klopt buitengewoon goed, al is het grappig dat Mathematica
denkt dat er misschien een klein imaginair deel is.
Bij priemvierlingen gelden dergelijke overwegingen. Het verwachte aantal is 4.15118/log(x)^4, waarbij die constante berekend is als 27/2 keer het product over alle priemgetallen p groter dan 3 van p^3(p-4)/(p-1)^4. Kortom, we verwachten
In[12]:= Integrate[4.15118/Log[y]^4,{y,2,1000000}]
Out[12]= 183.677 + 0. I
Iets te veel. Bij Nicely vinden we dat het aantal vierlingen onder de
10^15 gelijk aan 3314576487 is. Nu is de schatting
In[13]:= Integrate[4.15118/Log[y]^4,{y,2,1000000000000000}]
9
Out[13]= 3.31455 10 + 0. I
ook buitengewoon goed.
Natuurlijk is dit alles alleen maar heuristiek - zoals gezegd kan niemand bewijzen dat er oneindig veel priemtweelingen (laat staan priemviertallen) zijn. De grootst bekende kun je in Prime k-tuplets van Tony Forbes vinden.