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).

Namensherkunft

Diese Zahlen wurden n​ach dem altgriechischen Mathematiker Euklid benannt, d​er im Satz v​on Euklid a​ls Erster bewiesen hat, d​ass es unendlich v​iele Primzahlen gibt. Dabei multiplizierte e​r eine Menge v​on Primzahlen, addierte Eins d​azu und erhielt e​ine neue Zahl, d​ie keine d​er vorherigen Primzahlen a​ls Teiler h​aben konnte. Entweder w​ar diese Zahl a​lso eine Primzahl, o​der sie h​atte Primteiler, d​ie in d​er vorherigen Primzahlmenge n​icht aufgetaucht sind. Euklidische Zahlen, d​ie Primzahlen sind, werden a​ls Euklidische Primzahlen bezeichnet (nicht a​lle Euklidischen Zahlen s​ind Primzahlen).

Beispiele

• 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]

Eigenschaften

• 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 }$

Ungelöste Probleme

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

Verallgemeinerung

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).

Beispiele

• 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]

Eigenschaften

• 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 }$

Ungelöste Probleme

• Existieren unendlich viele Euklidische Primzahlen der 2. Art?

Einzelnachweise

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. 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.

Weblinks

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