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 \dots \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^[1] oder nicht.^[2]
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, \dots$ ):

(2), 3, 7, 31, 211, 2311, 30031, 510511, 9699691, 223092871, 6469693231, 200560490131, 7420738134811, 304250263527211, 13082761331670031, 614889782588491411, 32589158477190044731, 1922760350154212639071, 117288381359406970983271, 7858321551080267055879091, … (Vorlage: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, \dots$ ):

(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, … (Vorlage: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, \dots$ ):

(2), 3, 7, 31, 211, 2311, 509, 277, 27953, 703763, 34231, 200560490131, 676421, 11072701, 78339888213593, 13808181181, 18564761860301, 19026377261, 525956867082542470777, 143581524529603, 2892214489673, 16156160491570418147806951, 96888414202798247, 1004988035964897329167431269, … (Vorlage: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, … (Vorlage: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.^[3]

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

.

◻

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

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

ggT (E_{8}, E_{18}) = 277

.

◻

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

E_{n} = 4 k + 3

mit

k \in ℕ

Mit anderen Worten:

E_{n} \equiv 3 (\mod 4)

Beweis:

Das Produkt von ungeraden (Prim-)Zahlen ist wieder ungerade und, mit Kongruenzen geschrieben, somit entweder

\equiv 1 (\mod 4)

oder

\equiv 3 (\mod 4)

. Die Primfakultät

p_{n} #

ist das Produkt von

2

und mehreren ungeraden Primzahlen und somit entweder

\equiv 2 \cdot 1 \equiv 2 (\mod 4)

oder

\equiv 2 \cdot 3 = 6 \equiv 2 (\mod 4)

. Sie ist also in beiden Fällen

\equiv 2 (\mod 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 (\mod 4)

, was zu zeigen war.

◻

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} = 10 k + 1$ mit $k \in ℕ$ für $n \geq 3$
$E_{n} \equiv 1 (\mod 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 \dots \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

.

◻

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

E_{n} \equiv 1 (\mod 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 \dots \cdot p_{n} + 1 = k \cdot p + 1

mit

k \in ℕ

und

p \leq p_{n}

. Somit ist

E_{n} = k \cdot p + 1 \equiv 1 (\mod p)

◻

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 ${\overline{E}}_{n} = p_{n} # - 1$ , wobei $p_{n} # = 2 \cdot 3 \cdot 5 \cdot 7 \cdot \dots \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, … (Vorlage: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, \dots$ ):

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, … (Vorlage: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, \dots$ ):

1, 5, 29, 19, 2309, 30029, 8369, 929, 46027, 81894851, 876817, 38669, 304250263527209, 92608862041, 59799107, 1143707681, 69664915493, 1146665184811, 17975352936245519, 2140320249725509, … (Vorlage: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, … (Vorlage: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.^[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:

{\overline{E}}_{4} = p_{4} # - 1 = 7 # - 1 = 2 \cdot 3 \cdot 5 \cdot 7 - 1 = 209 = 11 \cdot 19

.

◻

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

ggT ({\overline{E}}_{19}, {\overline{E}}_{22}) = 163

.

◻

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} = 10 k + 9$ mit $k \in ℕ$ für $n \geq 3$
${\overline{E}}_{n} \equiv 9 (\mod 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 \dots \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

.

◻

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

{\overline{E}}_{n} \equiv - 1 (\mod 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 \dots \cdot p_{n} - 1 = k \cdot p - 1

mit

k \in ℕ

und

p \leq p_{n}

. Somit ist

{\overline{E}}_{n} = k \cdot p - 1 \equiv - 1 (\mod p)

.

◻

Ungelöste Probleme

Existieren unendlich viele Euklidische Primzahlen der 2. Art?

Einzelnachweise

↑ Vorlage:Internetquelle
↑ Vorlage:Internetquelle
↑ 392113# + 1. In: Primes.utm.edu. Abgerufen am 8. Januar 2021.
↑ ^4,0 ^4,1 Vorlage:Internetquelle
↑ Vorlage:Literatur
↑ Vorlage:Internetquelle
↑ 1098133# − 1. In: Primes.utm.edu. Abgerufen am 8. Januar 2021.
↑ 1098133# − 1. In: primegrid.com. (PDF; 97,9 kB). Abgerufen am 8. Januar 2021.
↑ Vorlage:Internetquelle

Weblinks

[1] Vorlage:Internetquelle

[2] Vorlage:Internetquelle

[3] 392113# + 1. In: Primes.utm.edu. Abgerufen am 8. Januar 2021.

[OEIS-4] 4,0 ^4,1 Vorlage:Internetquelle

[5] Vorlage:Literatur

[6] Vorlage:Internetquelle

[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] Vorlage:Internetquelle

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Euklidische Zahl

Inhaltsverzeichnis

Namensherkunft

Beispiele

Eigenschaften

Ungelöste Probleme

Verallgemeinerung

Beispiele

Eigenschaften

Ungelöste Probleme

Einzelnachweise

Weblinks

Navigationsmenü

Euklidische Zahl

Namensherkunft

Beispiele

Eigenschaften

Ungelöste Probleme

Verallgemeinerung

Beispiele

Eigenschaften

Ungelöste Probleme

Einzelnachweise

Weblinks

Navigationsmenü

Suche