Euklides bevis att det finns oändligt många primtal

Någon gång omkring 300 f.Kr. skrev Euklides ner ett argument kort nog att rymmas i ett enda stycke. Det har aldrig förbättrats, för det kan inte förbättras. Påståendet är att primtalen fortsätter för evigt, och beviset är en konstruktion: ge mig vilken ändlig lista av primtal som helst, och jag räcker dig ett primtal som inte står på den.

Tvåtusen år senare har argumentet fortfarande kvaliteten hos ett bra trolleritrick. Du ser varje steg tydligt. Du vet exakt hur det slutar. Och det landar ändå.

Vad ett primtal är, och varför frågan spelar roll

Ett primtal är ett heltal större än 1 vars enda delare är 1 och talet självt. De första är 2, 3, 5, 7, 11, 13. De sitter i heltalen som atomer: varje annat heltal byggs genom att multiplicera primtal. Talet 30, till exempel, bryts ner som 2 gånger 3 gånger 5, och det finns i grund och botten bara ett sätt att göra den faktoriseringen.

Givet att primtal är byggstenarna i alla heltal är det naturligt att fråga: tar de slut? Finns det ett största primtal, bortom vilket brunnen är torr? Euklides svar är nej, och vägen han tar är elegant nog att följa i ett enda sittning.

Upplägget: anta att listan är komplett

Argumentet är ett motsägelsebevis. Du börjar med att ge oppositionen allt den vill.

Nu när du samlat varje primtal som finns i den listan, bygg ett nytt tal av dem.

Att konstruera talet som bryter listan

Det är nyckeldraget, och det lönar sig att sakta ner och se vad det gör. Att multiplicera alla listade primtal ger dig ett tal som varje primtal på listan delar jämnt. Att addera 1 stör dem alla på en gång.

När du delar N med p1 får du rest 1, för produkten (p1 gånger p2 gånger ... gånger pk) är delbar med p1, och att addera 1 flyttar resten till 1. Samma logik gäller p2, p3, varje primtal på listan. Inget av dem delar N jämnt.

Motsägelsen

Motexemplet som gör beviset ärligt

Här är det många populära återgivningar av Euklides bevis går fel. De påstår att N själv alltid är primtal. Det är det inte, och distinktionen spelar roll.

Ta listan {2, 3, 5, 7, 11, 13}. Produkten är 2 gånger 3 gånger 5 gånger 7 gånger 11 gånger 13, vilket blir 30030. Addera 1 och du får N = 30031.

Är 30031 primtal? Nej.

$$30031 = 59 \times 509$$

Både 59 och 509 är primtal, och inget av dem står på listan {2, 3, 5, 7, 11, 13}. Precis vad beviset förutsäger: inte att N är primtal, utan att N:s primfaktorer saknas på listan. I det här fallet är primfaktorerna 59 och 509, två primtal som lämnades utanför den ändliga listan. Argumentet bekräftas, men bekräftelsen kommer från faktorerna, inte från N självt.

Vad beviset egentligen säger

Det lönar sig att stanna vid argumentets form, för den är ovanligt ren.

Du konstruerar inte det saknade primtalet explicit. Du söker inte efter det. Du bevisar att det måste finnas genom att visa att anta motsatsen leder till en logisk återvändsgränd. Primtalet q som gömmer sig i faktorerna av N kan vara lätt att hitta (som 59 och 509, om du provar några små delare av 30031) eller det kan vara enormt. Beviset bryr sig inte. Dess kraft kommer från oundviklighet: vilken lista du än räcker över, hittar konstruktionen en lucka.

Det kopplar naturligt till andra bevis som går i samma anda av "anta motsatsen, se den kollapsa". Cantors diagonalargument använder samma struktur i större skala: anta att en komplett lista av reella tal finns, och konstruera sedan ett reellt tal som bevisligen saknas. Ekot av Euklides är omisskännligt.

Varför primtalen aldrig tunnas ut helt

En sak beviset inte talar om är hur långt isär primtal kan ligga, eller hur stort nästa primtal efter ett givet kan vara. Euklides argument garanterar bara existens: någonstans bortom varje ändlig samling lever ett annat primtal. Fördelningen av primtal längs tallinjen är en mycket svårare fråga, och förblir ett av de djupaste öppna områdena i matematiken idag.

Vad beviset däremot talar om är strukturellt. Primtalen kan inte uttömmas med några ändliga medel. Du skulle kunna ägna ett liv åt att lista primtal, och du skulle alltid lista in i en oändlig rest. Varje primtal du fann var verkligt, men de framför dig var lika verkliga, lika talrika och lika ouppnåeliga för en ändlig lista.

För en känsla av hur snabbt tal kan växa när du bygger med multiplikation och exponenter är artikeln om förstå exponenter intuitivt en naturlig följeslagare: produkten p1 gånger p2 gånger ... gånger pk växer fortare än du kanske väntar dig, och den tillväxten är en del av varför N blir så stor så snabbt.

Zenen i det

Euklides bevis är mer än två årtusenden gammalt, och matematiker har hittat hundratals bevis av samma resultat sedan dess. Inget av dem har gjort det här föråldrat. Det behåller sin plats inte för att det är det fiffigaste eller det mest allmänna, utan för att det är det mest genomskinliga.

Du ser hela argumentet i ett svep. Konstruktionen är naturlig. Motsägelsen är skarp. Det finns inget steg där du måste ta något på tro eller lita på att en komplicerad maskin gör vad den påstår.

Vad beviset ber dig hålla i huvudet är en enda idé: varje ändlig lista av primtal är redan ofullständig. Inte för att listan är dåligt vald, utan för att primtal är den sortens sak som inte kan rymmas av någon ändlig räkning. De hör till det oändliga på samma sätt som heltalen, eller bråken, eller punkterna på en linje. Beviset talar inte om var nästa primtal är. Det talar om att nästa primtal alltid finns där.

Det räcker. Det har alltid räckt.

För andra resultat som delar den här andan av oundviklighet visar Goodsteins sats en följd som alltid återvänder till noll trots att den växer förbi allt skrivbart, med samma logik av "något måste hända för att alternativet är omöjligt." Familjen av argument är värd att känna till. Varje är en annan vinkel på samma underliggande faktum: matematiken innehåller inga nödutgångar. Strukturen håller.