Euklidische Zahl

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

Namensherkunft

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

Beispiele

• Die erste Euklidische Zahl lautet in der Literatur entweder $E_{0}=p_{0}\#+1=1+1=2$ oder $E_{1}=p_{1}\#+1=2+1=3$, je nachdem, ob man $p_{0}\#:=1$ definiert oder nicht.
• Die ersten vier Primzahlen sind $2,3,5$ und $7$. Das Produkt dieser vier Primzahlen ergibt die Primfakultät $p_{4}\#=7\#=2\cdot 3\cdot 5\cdot 7=210$. Somit ist die Euklidische Zahl $E_{4}=p_{4}\#+1=7\#+1=210+1=211$.
• Die ersten Euklidischen Zahlen lauten (beginnend mit $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 $E_{n}$ an (mit $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 $(2)$) die Zahl $19$ steht. Somit ist der kleinste Teiler von $E_{7}=510511$ die Zahl $19$.

• Die folgende Liste gibt die größten dieser Primfaktoren für $E_{n}$ an (mit $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 $(2)$) die Zahl $277$ steht. Somit ist der größte Teiler von $E_{7}=510\,511$ die Zahl $277$.

• Die folgende Liste gibt die ersten $n$ an, für die die Euklidische Zahl $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 $(0)$) steht die Zahl $11$. Somit ist $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 $E_{33\,237}=p_{33\,237}\#+1=392\,113\#+1$. Sie hat $169\,966$ Stellen und wurde am 20. September 2001 von Daniel Heuer entdeckt.

Eigenschaften

• Nicht alle Euklidischen Zahlen sind Primzahlen.

Beweis:

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

• Zwei verschiedene Euklidische Zahlen sind nicht immer teilerfremd zueinander.

Beweis:

Es genügt ein Gegenbeispiel:

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

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

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

Mit anderen Worten:

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

Beweis:

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

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

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

Mit anderen Worten:

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

Beweis:

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

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

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

Beweis:

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

Ungelöste Probleme

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

Verallgemeinerung

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

Beispiele

• Die ersten vier Primzahlen sind $2,3,5$ und $7$. Das Produkt dieser vier Primzahlen ergibt die Primfakultät $p_{4}\#=7\#=2\cdot 3\cdot 5\cdot 7=210$. Somit ist die vierte Euklidische Zahl der 2. Art die Zahl ${\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 ${\overline {E}}_{n}$ an (mit $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 $61$ steht. Somit ist der kleinste Teiler von ${\overline {E}}_{7}=510\,509$ die Zahl $61$.

• Die folgende Liste gibt die größten dieser Primfaktoren für ${\overline {E}}_{n}$ an (mit $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 $8\,369$ steht. Somit ist der größte Teiler von ${\overline {E}}_{7}=510\,509$ die Zahl $8\,369$.

• Die folgende Liste gibt die ersten $n$ an, für die die Euklidische Zahl der 2. Art ${\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 $24$. Somit ist ${\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) ${\overline {E}}_{85\,586}=p_{85\,586}\#-1=1\,098\,133\#-1$. Sie hat $476\,311$ Stellen und wurde am 28. Februar 2012 von James P. Burt entdeckt.

Eigenschaften

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

Beweis:

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

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

Beweis:

Es genügt ein Gegenbeispiel:

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

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

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

Mit anderen Worten:

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

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

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

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

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

Beweis:

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

Ungelöste Probleme

• Existieren unendlich viele Euklidische Primzahlen der 2. Art?

Weblinks

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