Euclides' bewijs dat er oneindig veel priemgetallen zijn
Ergens rond 300 v.Chr. schreef Euclides een argument op dat kort genoeg is om in één alinea te passen. Het is nooit verbeterd, omdat het niet kan. De bewering is dat de priemgetallen eeuwig doorgaan, en het bewijs is een constructie: geef me willekeurig welke eindige lijst van priemen, en ik geef je een priemgetal dat er niet op staat.
Tweeduizend jaar later heeft het argument nog altijd de kwaliteit van een goede goocheltruc. Je ziet elke stap helder. Je weet precies hoe het eindigt. En het landt nog steeds.
Wat een priemgetal is, en waarom de vraag ertoe doet
Een priemgetal is een geheel getal groter dan 1 waarvan de enige delers 1 en het getal zelf zijn. De eerste zijn 2, 3, 5, 7, 11, 13. Ze zitten in de gehele getallen als atomen: elk ander geheel getal wordt gebouwd door priemen te vermenigvuldigen. Het getal 30, bijvoorbeeld, valt uiteen als 2 keer 3 keer 5, en er is in wezen maar één manier om die ontbinding te doen.
Gegeven dat priemen de bouwstenen van alle gehele getallen zijn, is het natuurlijk om te vragen: raken ze op? Is er een grootste priemgetal, waarna de put droog is? Euclides' antwoord is nee, en de route die hij neemt is elegant genoeg om in één zitting te volgen.
De opzet: neem aan dat de lijst compleet is
Het argument is een bewijs uit het ongerijmde. Je begint met de tegenstander alles te gunnen wat die wil.
Neem aan dat er maar eindig veel priemgetallen zijn
Stel, ter wille van het argument, dat de complete verzameling van alle priemen een eindige lijst is: . Buiten deze lijst bestaan geen priemen. Dit is de aanname die we gaan vernietigen.
Nu je elk bestaand priemgetal in die lijst hebt verzameld, bouw je er een nieuw getal van.
Het getal construeren dat de lijst breekt
Vorm N door alle opgesomde priemen te vermenigvuldigen en 1 op te tellen
Laat . Dat is: neem het product van elk priemgetal op de zogenaamd complete lijst, tel dan 1 op.
Dit is de sleutelzet, en het loont om te vertragen en te zien wat hij doet. Alle opgesomde priemen vermenigvuldigen geeft je een getal dat elk priemgetal op de lijst evenredig deelt. 1 optellen verstoort ze allemaal tegelijk.
Als je N deelt door p1, krijg je rest 1, omdat het product (p1 keer p2 keer ... keer pk) deelbaar is door p1, en 1 optellen de rest naar 1 verschuift. Dezelfde logica geldt voor p2, voor p3, voor elk priemgetal op de lijst. Geen ervan deelt N evenredig.
De tegenspraak
N heeft een priemfactor, maar die factor kan niet op de lijst staan
Elk geheel getal groter dan 1 heeft minstens één priemfactor. Dat is een gevolg van de hoofdstelling van de rekenkunde: blijf ontbinden tot je niet meer kunt, en je blijft met priemen over. Dus N heeft een priemfactor. Noem die q.
We lieten net zien dat geen priemgetal op de lijst N deelt. Daarom staat q niet op de lijst. Maar we namen aan dat de lijst elk priemgetal bevatte. Dat is de tegenspraak: we hebben een priemgetal gevonden, q, dat niet op de zogenaamd complete lijst staat.
De aanname moet onjuist zijn
Omdat de aanname dat er maar eindig veel priemen zijn direct tot een tegenspraak leidt, is de aanname onjuist. Er is geen eindige lijst die alle priemen bevat. De priemen gaan eeuwig door.
Het tegenvoorbeeld dat het bewijs eerlijk maakt
Hier gaan veel populaire versies van Euclides' bewijs de mist in. Ze beweren dat N zelf altijd priem is. Dat is het niet, en het onderscheid doet ertoe.
Neem de lijst {2, 3, 5, 7, 11, 13}. Het product is 2 keer 3 keer 5 keer 7 keer 11 keer 13, wat 30030 is. Tel 1 op en je krijgt N = 30031.
Is 30031 priem? Nee.
Zowel 59 als 509 zijn priem, en geen van beide staat op de lijst {2, 3, 5, 7, 11, 13}. Precies wat het bewijs voorspelt: niet dat N priem is, maar dat de priemfactoren van N van de lijst afwezig zijn. In dit geval zijn de priemfactoren 59 en 509, twee priemen die van de eindige lijst zijn weggelaten. Het argument wordt bevestigd, maar de bevestiging komt van de factoren, niet van N zelf.
Wat het bewijs eigenlijk zegt
Het loont om stil te staan bij de vorm van het argument, omdat het uitzonderlijk schoon is.
Je construeert het ontbrekende priemgetal niet expliciet. Je zoekt er niet naar. Je bewijst dat het moet bestaan door te laten zien dat het tegendeel aannemen tot een logisch doodlopend spoor leidt. Het priemgetal q dat in de factoren van N schuilt kan makkelijk te vinden zijn (zoals 59 en 509, als je een paar kleine delers van 30031 probeert) of het kan enorm zijn. Het bewijs trekt zich er niets van aan. Zijn kracht komt van onvermijdelijkheid: welke lijst je ook overhandigt, de constructie vindt een gat.
Dit sluit vanzelf aan op andere bewijzen die vanuit dezelfde geest van "neem het tegendeel aan, kijk hoe het instort" werken. Cantors diagonaalargument gebruikt dezelfde structuur op grotere schaal: neem aan dat een complete lijst van reële getallen bestaat, en construeer dan een reëel getal dat bewijsbaar ontbreekt. De echo van Euclides is onmiskenbaar.
Waarom de priemen nooit helemaal uitdunnen
Eén ding dat het bewijs je niet vertelt is hoe ver priemen uit elkaar kunnen liggen, of hoe groot het volgende priemgetal na een gegeven priem kan zijn. Euclides' argument garandeert alleen bestaan: ergens voorbij elke eindige verzameling leeft een ander priemgetal. De verdeling van priemen over de getallenlijn is een veel lastigere vraag, en blijft een van de diepste open gebieden van de wiskunde.
Wat het bewijs wél vertelt is structureel. De priemgetallen kunnen door geen enkel eindig middel worden uitgeput. Je zou een leven kunnen wijden aan het opsommen van priemen, en je zou altijd opsommen in een oneindige rest. Elk priemgetal dat je vond was echt, maar die voor je lagen waren even echt, even talrijk, en even onbereikbaar voor een eindige lijst.
Voor een gevoel van hoe snel getallen kunnen groeien als je bouwt met vermenigvuldiging en exponenten is het artikel over exponenten intuïtief begrijpen een natuurlijke metgezel: het product p1 keer p2 keer ... keer pk groeit sneller dan je misschien verwacht, en die groei is deel van waarom N zo snel zo groot wordt.
De zen ervan
Euclides' bewijs is meer dan twee millennia oud, en wiskundigen hebben sindsdien honderden bewijzen van hetzelfde resultaat gevonden. Geen ervan heeft dit overbodig gemaakt. Het houdt zijn plek niet omdat het het slimste of het algemeenste is, maar omdat het het doorzichtigste is.
Je ziet het hele argument in één doorgang. De constructie is natuurlijk. De tegenspraak is scherp. Er is geen stap waar je iets op geloof moet aannemen of moet vertrouwen dat een ingewikkelde machine doet wat hij beweert.
Wat het bewijs je vraagt vast te houden is één idee: elke eindige lijst van priemen is al incompleet. Niet omdat de lijst slecht gekozen is, maar omdat priemen het soort ding zijn dat door geen eindige telling kan worden bevat. Ze horen bij het oneindige zoals de gehele getallen, of de breuken, of de punten op een lijn. Het bewijs vertelt je niet waar het volgende priemgetal is. Het vertelt je dat het volgende priemgetal er altijd is.
Dat is genoeg. Dat is altijd genoeg geweest.
Voor andere resultaten die deze geest van onvermijdelijkheid delen laat de stelling van Goodstein een rij zien die altijd naar nul terugkeert ondanks groei voorbij alles wat je kunt opschrijven, met dezelfde logica van "iets moet gebeuren omdat het alternatief onmogelijk is." De familie van argumenten is de moeite van het kennen waard. Elk is een andere hoek op hetzelfde onderliggende feit: de wiskunde bevat geen ontsnappingsluiken. De structuur houdt.
Veelgestelde vragen
- Zijn er oneindig veel priemgetallen?
- Ja. Euclides bewees dit rond 300 v.Chr. Hoeveel priemen je ook in een lijst verzamelt, het argument construeert een getal waarvan alle priemfactoren buiten die lijst liggen, dus minstens één nieuw priemgetal moet bestaan.
- Laat Euclides' bewijs zien dat N = (p1 × p2 × ... × pk) + 1 altijd priem is?
- Nee, en dit is de meest voorkomende verkeerde weergave van het bewijs. N hoeft alleen een priemfactor te hebben die niet op de lijst staat, wat N zelf kan zijn of een kleiner getal. Bijvoorbeeld: 2x3x5x7x11x13 + 1 = 30031, wat NIET priem is: 30031 = 59 x 509. Zowel 59 als 509 zijn priemen die ontbreken in de lijst {2,3,5,7,11,13}, dus het bewijs werkt nog steeds perfect.
- Wat voor bewijs is Euclides' argument?
- Het is een bewijs uit het ongerijmde (reductio ad absurdum). Je neemt het tegenovergestelde aan van wat je wilt bewijzen, namelijk dat er maar eindig veel priemen zijn, en laat dan zien dat die aanname tot een tegenspraak leidt.
- Hoe garandeert het bewijs een priemgetal buiten de lijst?
- Het geconstrueerde getal N laat rest 1 als je deelt door elk priemgetal op de lijst, dus geen van de opgesomde priemen deelt N. Maar elk geheel getal groter dan 1 heeft minstens één priemfactor. Daarom heeft N een priemfactor, en die factor kan niet op de lijst staan. Een priem buiten de lijst is gegarandeerd.
- Houdt dit verband met Cantors diagonaalargument of de stelling van Goodstein?
- Alle drie zitten in dezelfde familie van resultaten waarin een eenvoudige constructie elke poging tot een complete eindige (of aftelbare) beschrijving verslaat. Euclides verslaat elke eindige lijst van priemen, Cantor verslaat elke aftelbare lijst van reële getallen, en Goodstein produceert een rij die de bewijskracht van de Peano-rekenkunde verslaat.
Oefen het zelf
Vond je het leuk om dit door te denken?
Math Zen maakt van dit soort inzicht dagelijkse oefening, met adaptieve opgaven bij 24 wiskundeonderwerpen.
