Euklidische Zahl

In der Zahlentheorie ist eine Euklidische Zahl eine natürliche Zahl der Form ${\displaystyle E_{n}=p_{n}\#+1}$, wobei ${\displaystyle p_{n}\#=2\cdot 3\cdot 5\cdot 7\cdot \dotsm \cdot p_{n}}$ das Produkt der ersten ${\displaystyle n}$ Primzahlen bis ${\displaystyle p_{n}}$ ist (Primfakultät).

Diese Zahlen wurden nach dem altgriechischen Mathematiker Euklid benannt, der im Satz von Euklid als Erster bewiesen hat, dass es unendlich viele Primzahlen gibt. Dabei multiplizierte er eine Menge von Primzahlen, addierte Eins dazu und erhielt eine neue Zahl, die keine der vorherigen Primzahlen als Teiler haben konnte. Entweder war diese Zahl also eine Primzahl, oder sie hatte Primteiler, die in der vorherigen Primzahlmenge nicht aufgetaucht sind. Euklidische Zahlen, die Primzahlen sind, werden als Euklidische Primzahlen bezeichnet (nicht alle Euklidischen Zahlen sind Primzahlen).

• Die erste Euklidische Zahl lautet in der Literatur entweder ${\displaystyle E_{0}=p_{0}\#+1=1+1=2}$ oder ${\displaystyle E_{1}=p_{1}\#+1=2+1=3}$, je nachdem, ob man ${\displaystyle p_{0}\#:=1}$ definiert^[1] oder nicht.^[2]
• Die ersten vier Primzahlen sind ${\displaystyle 2,3,5}$ und ${\displaystyle 7}$. Das Produkt dieser vier Primzahlen ergibt die Primfakultät ${\displaystyle p_{4}\#=7\#=2\cdot 3\cdot 5\cdot 7=210}$. Somit ist die Euklidische Zahl ${\displaystyle E_{4}=p_{4}\#+1=7\#+1=210+1=211}$.
• Die ersten Euklidischen Zahlen lauten (beginnend mit ${\displaystyle n=(0),1,2,\ldots }$):

(2), 3, 7, 31, 211, 2311, 30031, 510511, 9699691, 223092871, 6469693231, 200560490131, 7420738134811, 304250263527211, 13082761331670031, 614889782588491411, 32589158477190044731, 1922760350154212639071, 117288381359406970983271, 7858321551080267055879091, … (Folge A006862 in OEIS)

• Diese Euklidischen Zahlen haben einen oder mehrere Primfaktoren. Die folgende Liste gibt die kleinsten dieser Primfaktoren für ${\displaystyle E_{n}}$ an (mit ${\displaystyle n=(0),1,2,\ldots }$):

(2), 3, 7, 31, 211, 2311, 59, 19, 347, 317, 331, 200560490131, 181, 61, 167, 953, 73, 277, 223, 54730729297, 1063, 2521, 22093, 265739, 131, 2336993, 960703, 2297, 149, 334507, 5122427, 1543, 1951, 881, 678279959005528882498681487, 87549524399, 23269086799180847, … (Folge A051342 in OEIS)

Beispiel:

Der obigen Liste kann man entnehmen, dass an der 7. Stelle (ohne ${\displaystyle (2)}$) die Zahl ${\displaystyle 19}$ steht. Somit ist der kleinste Teiler von ${\displaystyle E_{7}=510511}$ die Zahl ${\displaystyle 19}$.

• Die folgende Liste gibt die größten dieser Primfaktoren für ${\displaystyle E_{n}}$ an (mit ${\displaystyle n=(0),1,2,\ldots }$):

(2), 3, 7, 31, 211, 2311, 509, 277, 27953, 703763, 34231, 200560490131, 676421, 11072701, 78339888213593, 13808181181, 18564761860301, 19026377261, 525956867082542470777, 143581524529603, 2892214489673, 16156160491570418147806951, 96888414202798247, 1004988035964897329167431269, … (Folge A002585 in OEIS)

Beispiel:

Der obigen Liste kann man entnehmen, dass an der 7. Stelle (ohne ${\displaystyle (2)}$) die Zahl ${\displaystyle 277}$ steht. Somit ist der größte Teiler von ${\displaystyle E_{7}=510\,511}$ die Zahl ${\displaystyle 277}$.

• Die folgende Liste gibt die ersten ${\displaystyle n}$ an, für die die Euklidische Zahl ${\displaystyle E_{n}}$ prim ist:

(0), 1, 2, 3, 4, 5, 11, 75, 171, 172, 384, 457, 616, 643, 1391, 1613, 2122, 2647, 2673, 4413, 13494, 31260, 33237, … (Folge A014545 in OEIS)

Beispiel:

An der 6. Stelle obiger Liste (ohne ${\displaystyle (0)}$) steht die Zahl ${\displaystyle 11}$. Somit ist ${\displaystyle E_{11}=p_{11}\#+1=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23\cdot 29\cdot 31+1=200\,560\,490\,131}$ die 6. Euklidische Primzahl.

• Die bisher größte bekannte Euklidische Primzahl (Stand: 8. Juli 2018) ist ${\displaystyle E_{33\,237}=p_{33\,237}\#+1=392\,113\#+1}$. Sie hat ${\displaystyle 169\,966}$ Stellen und wurde am 20. September 2001 von Daniel Heuer entdeckt.^[3]

• Nicht alle Euklidischen Zahlen sind Primzahlen.

Beweis:

Schon die sechste Euklidische Zahl ist eine zusammengesetzte Zahl: ${\displaystyle E_{6}=p_{6}\#+1=13\#+1=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30\,031=59\cdot 509}$. ${\displaystyle \Box }$

• Zwei verschiedene Euklidische Zahlen sind nicht immer teilerfremd zueinander.^[4]

Beweis:

Es genügt ein Gegenbeispiel:

${\displaystyle E_{8}=510\,511}$ und ${\displaystyle E_{18}=1\,922\,760\,350\,154\,212\,639\,071}$ haben den größten gemeinsamen Teiler ${\displaystyle {\operatorname {ggT} (E_{8},E_{18})}=277}$. ${\displaystyle \Box }$

• Sei ${\displaystyle E_{n}}$ eine beliebige Euklidische Zahl. Dann gilt:

${\displaystyle E_{n}=4k+3}$ mit ${\displaystyle k\in \mathbb {N} }$

Mit anderen Worten:

${\displaystyle E_{n}\equiv 3{\pmod {4}}}$

Beweis:

Das Produkt von ungeraden (Prim-)Zahlen ist wieder ungerade und, mit Kongruenzen geschrieben, somit entweder ${\displaystyle \equiv 1{\pmod {4}}}$ oder ${\displaystyle \equiv 3{\pmod {4}}}$. Die Primfakultät ${\displaystyle p_{n}\#}$ ist das Produkt von ${\displaystyle 2}$ und mehreren ungeraden Primzahlen und somit entweder ${\displaystyle \equiv 2\cdot 1\equiv 2{\pmod {4}}}$ oder ${\displaystyle \equiv 2\cdot 3=6\equiv 2{\pmod {4}}}$. Sie ist also in beiden Fällen ${\displaystyle \equiv 2{\pmod {4}}}$. Für eine Euklidische Zahl muss man noch ${\displaystyle 1}$ zur Primfakultät dazuzählen und erhält ${\displaystyle E_{n}=p_{n}\#+1\equiv 2+1=3{\pmod {4}}}$, was zu zeigen war. ${\displaystyle \Box }$

• Sei ${\displaystyle E_{n}}$ eine Euklidische Zahl mit ${\displaystyle n\geq 3}$. Dann gilt:

Die letzte Stelle (also die Einerstelle) von ${\displaystyle E_{n}}$ ist immer ${\displaystyle 1}$.

Mit anderen Worten:

• ${\displaystyle E_{n}=10k+1}$ mit ${\displaystyle k\in \mathbb {N} }$ für ${\displaystyle n\geq 3}$
• ${\displaystyle E_{n}\equiv 1{\pmod {10}}}$ für ${\displaystyle n\geq 3}$

Beweis:

Für ${\displaystyle n\geq 3}$ muss ${\displaystyle E_{n}-1=p_{n}\#+1-1=2\cdot 3\cdot 5\cdot \dotsm \cdot p_{n}}$ sein. Somit ist ${\displaystyle E_{n}-1}$ auf jeden Fall durch ${\displaystyle 2}$ und ${\displaystyle 5}$ und somit auch durch ${\displaystyle 10}$ teilbar. ${\displaystyle E_{n}-1}$ hat an der Einerstelle also eine ${\displaystyle 0}$. Addiert man noch ${\displaystyle 1}$ dazu, erhält man an der Einerstelle eine ${\displaystyle 1}$. ${\displaystyle \Box }$

• Sei ${\displaystyle E_{n}=2\cdot 3\cdot 5\cdot 7\cdot \dotsm \cdot p_{n}+1}$ eine Euklidische Zahl. Dann gilt:

${\displaystyle E_{n}\equiv 1{\pmod {p}}}$ für alle ${\displaystyle p\leq p_{n}}$

Beweis:

Der Beweis ergibt sich aus der Definition der Euklidischen Zahlen. ${\displaystyle E_{n}=p_{n}\#+1=2\cdot 3\cdot 5\cdot 7\cdot \dotsm \cdot p_{n}+1=k\cdot p+1}$ mit ${\displaystyle k\in \mathbb {N} }$ und ${\displaystyle p\leq p_{n}}$. Somit ist ${\displaystyle E_{n}=k\cdot p+1\equiv 1{\pmod {p}}}$ ${\displaystyle \Box }$

• Existieren unendlich viele Euklidische Primzahlen?
• Sind alle Euklidischen Zahlen quadratfrei?^[4]

Eine Euklidische Zahl der 2. Art (oder auch Kummer-Zahl, benannt nach Ernst Eduard Kummer^[5][6]) ist eine ganze Zahl der Form ${\displaystyle {\overline {E}}_{n}=p_{n}\#-1}$, wobei ${\displaystyle p_{n}\#=2\cdot 3\cdot 5\cdot 7\cdot \dotsm \cdot p_{n}}$ das Produkt der ersten ${\displaystyle n}$ Primzahlen bis ${\displaystyle p_{n}}$ ist (Primfakultät).

• Die ersten vier Primzahlen sind ${\displaystyle 2,3,5}$ und ${\displaystyle 7}$. Das Produkt dieser vier Primzahlen ergibt die Primfakultät ${\displaystyle p_{4}\#=7\#=2\cdot 3\cdot 5\cdot 7=210}$. Somit ist die vierte Euklidische Zahl der 2. Art die Zahl ${\displaystyle {\overline {E}}_{4}=p_{4}\#-1=7\#-1=210-1=209}$.
• Die ersten Euklidischen Zahlen der 2. Art lauten:

1, 5, 29, 209, 2309, 30029, 510509, 9699689, 223092869, 6469693229, 200560490129, 7420738134809, 304250263527209, 13082761331670029, 614889782588491409, 32589158477190044729, 1922760350154212639069, … (Folge A057588 in OEIS)

• Diese Euklidischen Zahlen der 2. Art haben einen oder mehrere Primfaktoren. Die folgende Liste gibt die kleinsten dieser Primfaktoren für ${\displaystyle {\overline {E}}_{n}}$ an (mit ${\displaystyle n=1,2,\dotsc }$):

1, 5, 29, 11, 2309, 30029, 61, 53, 37, 79, 228737, 229, 304250263527209, 141269, 191, 87337, 27600124633, 1193, 163, 260681003321, 313, 163, 139, 23768741896345550770650537601358309, 66683, 2990092035859, 15649, 17515703, 719, 295201, 15098753, 10172884549, 20962699238647, 4871, 673, 311, 1409, 1291, 331, 1450184819, 23497, 711427, 521, 673, 519577, 1372062943, 56543, 811, 182309, 53077, 641, 349, 389, … (Folge A057713 in OEIS)

Beispiel:

Der obigen Liste kann man entnehmen, dass an der 7. Stelle die Zahl ${\displaystyle 61}$ steht. Somit ist der kleinste Teiler von ${\displaystyle {\overline {E}}_{7}=510\,509}$ die Zahl ${\displaystyle 61}$.

• Die folgende Liste gibt die größten dieser Primfaktoren für ${\displaystyle {\overline {E}}_{n}}$ an (mit ${\displaystyle n=1,2,\dotsc }$):

1, 5, 29, 19, 2309, 30029, 8369, 929, 46027, 81894851, 876817, 38669, 304250263527209, 92608862041, 59799107, 1143707681, 69664915493, 1146665184811, 17975352936245519, 2140320249725509, … (Folge A002584 in OEIS)

Beispiel:

Der obigen Liste kann man entnehmen, dass an der 7. Stelle die Zahl ${\displaystyle 8\,369}$ steht. Somit ist der größte Teiler von ${\displaystyle {\overline {E}}_{7}=510\,509}$ die Zahl ${\displaystyle 8\,369}$.

• Die folgende Liste gibt die ersten ${\displaystyle n}$ an, für die die Euklidische Zahl der 2. Art ${\displaystyle {\overline {E}}_{n}}$ prim ist:

2, 3, 5, 6, 13, 24, 66, 68, 167, 287, 310, 352, 564, 590, 620, 849, 1552, 1849, 67132, 85586, … (Folge A057704 in OEIS)

Beispiel:

An der 6. Stelle obiger Liste steht die Zahl ${\displaystyle 24}$. Somit ist ${\displaystyle {\overline {E}}_{24}=23\,768\,741\,896\,345\,550\,770\,650\,537\,601\,358\,309}$ die 6. Euklidische Primzahl der 2. Art.

• Die bisher größte bekannte Euklidische Primzahl 2. Art ist (Stand: 8. Juli 2018) ${\displaystyle {\overline {E}}_{85\,586}=p_{85\,586}\#-1=1\,098\,133\#-1}$. Sie hat ${\displaystyle 476\,311}$ Stellen und wurde am 28. Februar 2012 von James P. Burt entdeckt.^[7][8]

• Nicht alle Euklidischen Zahlen der 2. Art sind Primzahlen.

Beweis:

Schon die vierte Euklidische Zahl der 2. Art ist eine zusammengesetzte Zahl: ${\displaystyle {\overline {E}}_{4}=p_{4}\#-1=7\#-1=2\cdot 3\cdot 5\cdot 7-1=209=11\cdot 19}$. ${\displaystyle \Box }$

• Euklidische Zahlen der 2. Art sind nicht immer teilerfremd zueinander.

Beweis:

Es genügt ein Gegenbeispiel:

${\displaystyle {\overline {E}}_{19}=7\,858\,321\,551\,080\,267\,055\,879\,089}$ und ${\displaystyle {\overline {E}}_{22}=3\,217\,644\,767\,340\,672\,907\,899\,084\,554\,129}$ haben den größten gemeinsamen Teiler ${\displaystyle {\operatorname {ggT} ({\overline {E}}_{19},{\overline {E}}_{22})}=163}$. ${\displaystyle \Box }$

• Sei ${\displaystyle {\overline {E}}_{n}}$ eine Euklidische Zahl der 2. Art mit ${\displaystyle n\geq 3}$. Dann gilt:

Die letzte Stelle (also die Einerstelle) von ${\displaystyle {\overline {E}}_{n}}$ ist immer ${\displaystyle 9}$.

Mit anderen Worten:

• ${\displaystyle {\overline {E}}_{n}=10k+9}$ mit ${\displaystyle k\in \mathbb {N} }$ für ${\displaystyle n\geq 3}$
• ${\displaystyle {\overline {E}}_{n}\equiv 9{\pmod {10}}}$ für ${\displaystyle n\geq 3}$

Beweis: Analog zum obigen Beweis für „normale“ Euklidische Zahlen.

Für ${\displaystyle n\geq 3}$ muss ${\displaystyle {\overline {E}}_{n}+1=p_{n}\#-1+1=2\cdot 3\cdot 5\cdot \dotsm \cdot p_{n}}$ sein. Somit ist ${\displaystyle {\overline {E}}_{n}+1}$ auf jeden Fall durch ${\displaystyle 2}$ und ${\displaystyle 5}$ und somit auch durch ${\displaystyle 10}$ teilbar. ${\displaystyle {\overline {E}}_{n}+1}$ hat an der Einerstelle also eine ${\displaystyle 0}$. Subtrahiert man noch ${\displaystyle 1}$, erhält man an der Einerstelle eine ${\displaystyle 9}$. ${\displaystyle \Box }$

• Sei ${\displaystyle {\overline {E}}_{n}=2\cdot 3\cdot 5\cdot 7\cdot \dotsm \cdot p_{n}-1}$ eine Euklidische Zahl der 2. Art. Dann gilt:^[9]

${\displaystyle {\overline {E}}_{n}\equiv -1{\pmod {p}}}$ für alle ${\displaystyle p\leq p_{n}}$

Beweis:

Der Beweis ergibt sich aus der Definition der Euklidischen Zahlen der 2. Art. ${\displaystyle {\overline {E}}_{n}=p_{n}\#-1=2\cdot 3\cdot 5\cdot 7\cdot \dotsm \cdot p_{n}-1=k\cdot p-1}$ mit ${\displaystyle k\in \mathbb {N} }$ und ${\displaystyle p\leq p_{n}}$. Somit ist ${\displaystyle {\overline {E}}_{n}=k\cdot p-1\equiv -1{\pmod {p}}}$. ${\displaystyle \Box }$

• Existieren unendlich viele Euklidische Primzahlen der 2. Art?

1. ↑ Neil Sloane: Euclid numbers: 1 + product of the first n primes. In: OEIS.org. Abgerufen am 8. Januar 2021. 
2. ↑ Eric W. Weisstein: Euclid Number. In: archive.lib.msu.edu. Abgerufen am 8. Januar 2021. 
3. ↑ 392113# + 1. In: Primes.utm.edu. Abgerufen am 8. Januar 2021.
4. ↑ ^{a b} Neil Sloane: Euclid numbers: 1 + product of the first n primes – Comments. In: OEIS.org. Abgerufen am 8. Januar 2021. 
5. ↑ Ernst Eduard Kummer: Neuer elementarer Beweis des Satzes, dass die Anzahl aller Primzahlen eine unendliche ist. In: Monatsbericht der Preuß. Akad. d. Wiss. Berlin. 1878, S. 777–778. 
6. ↑ Neil Sloane: Kummer numbers: −1 + product of first n consecutive primes – References. In: OEIS.org. Abgerufen am 8. Januar 2021. 
7. ↑ 1098133# − 1. In: Primes.utm.edu. Abgerufen am 8. Januar 2021.
8. ↑ 1098133# − 1. In: primegrid.com. (PDF; 97,9 kB). Abgerufen am 8. Januar 2021.
9. ↑ Neil Sloane: Kummer numbers: −1 + product of first n consecutive primes – Comments. In: OEIS.org. Abgerufen am 8. Januar 2021. 

• Eric W. Weisstein: Euclid Number. In: MathWorld (englisch).
• Eric W. Weisstein: Euclid Number. In: archive.lib.msu.edu. Abgerufen am 8. Juli 2018.