Primzahlen: VI. Kapitel: Verschiedene Primzahl-Arten

Primzahlen

Cullen-Zahl

Eine Cullen-Zahl ist eine Zahl der Form $C_{n}=n\cdot 2^{n}+1$, mit der sich Reverend James Cullen 1905 beschäftigt hat. Ihm fiel auf, dass außer $C_{1}=3$ alle Zahlen dieser Form bis $C_{99}$ zusammengesetzte Zahlen, also keine Primzahlen sind. Seine Unsicherheit bezüglich $C_{53}$ konnte von Allan J.C. Cunningham 1906 ausgeräumt werden, indem dieser den Teiler 5519 fand. Cunningham zeigte, dass alle $C_{n}$ bis $n=200$ zusammengesetzt sind, mit einer möglichen Ausnahme für $n=141$.

1958 bestätigte Raphael M. Robinson, dass $C_{141}$ eine Primzahl ist und wies nach, dass alle Cullen-Zahlen $C_{n}$ mit $n\leq 1000$, mit Ausnahme von $C_{1}$ und $C_{141}$ zusammengesetzte Zahlen sind.

Wilfrid Keller hat 1984 gezeigt, das $C_{4713}$, $C_{5795}$, $C_{6611}$ und $C_{18496}$ ebenfalls Primzahlen sind, aber alle anderen $C_{n}$ mit $n\leq 30.000$ zusammengesetzte Cullen-Zahlen sind.

Inzwischen (Juli 2004) ist bekannt, dass $C_{n}$ für folgende n Primzahlen sind: 32292, 32469, 59656, 90825, 262419, 361275, 481899 und 1354828. Außer diesen gibt es keine Cullen-Primzahlen bis n=1150000.

Es wird vermutet, dass es unendlich viele Cullen-Primzahlen gibt.

Woodall-Zahl

Eine Zahl der Form $C_{n}=n\cdot 2^{n}-1$ wird Cullen-Zahl der zweiten Art oder auch Woodall-Zahl genannt (nach H.J. Woodall, der sie 1917 beschrieb).

Im Bereich von $n\leq 20.000$ sind nur die Woodall-Zahlen C^'₂, C^'₃, C^'₆, C^'₃₀, C^'₇₅, C^'₈₁, C^'₁₁₅, C^'₁₂₃, C^'₂₄₉, C^'₃₆₂, C^'₃₈₄, C^'₄₆₂, C^'₅₁₂, C^'₇₅₁, C^'₈₂₂, C^'₅₃₁₂, C^'₇₇₅₅, C^'₉₅₃₁, C^'₁₂₃₇₉, C^'₁₅₈₂₂ und C^'₁₈₈₈₅ Primzahlen.

Weitere Woodall-Primzahlen sind C^'_n für folgende n: 22971, 23005, 98726, 143018, 151023, 667071, 1195203

Es wird vermutet, dass es unendlich viele Woodall-Primzahlen gibt.

Verallgemeinerte Cullen- und Woodall-Zahlen

Zahlen der Form $n\cdot b^{n}+1$ bezeichnet man als verallgemeinerte Cullen-Zahlen. Zahlen der Form $n\cdot b^{n}-1$ bezeichnet man als verallgemeinerte Woodall-Zahlen

Sophie-Germain-Primzahlen

Eine Primzahl $\ p\$ nennt man Sophie-Germain-Primzahl oder auch Germainsche Primzahl wenn auch $\ 2p+1\$ eine Primzahl ist.

Da alle Primzahlen außer 3 nicht durch 3 teilbar sind, ist bei Sophie-Germain-Primzahlen ab 5 der Divisionrest durch 3 immer 2, da sie außerdem ungerade sind, gilt also

$\ p=6\cdot k-1{\text{ mit }}k>0$.

Außer bei 2 ist der Divisionrest durch 5 nie 2, weil dann $\ 2\cdot p+1\$ durch 5 teilbar ist; im Dezimalsystem enden Sophie-Germain-Primzahlen daher nie mit der Ziffer 7.

Beispiele

$p=2\$ ist eine Sophie-Germain-Primzahl, denn $2p+1=5\$ ist eine Primzahl. Das gleiche gilt für 3, 5, 11 und 23.

$2\cdot 3+1=7$

$2\cdot 5+1=11$

$2\cdot 11+1=23$

$2\cdot 23+1=47$

$p=7\$ ist keine Sophie-Germain-Primzahl, denn $2p+1=15\$ ist keine Primzahl.

Cunningham-Ketten

Cunningham-Ketten der ersten Art

In dem obigen Beispiel der Sophie-Germain-Primzahlen sind die Zahlen wie an einer Kette aufgereiht. Diese Folge ist eine Cunningham-Kette der ersten Art (benannt nach Allan Joseph Champneys Cunningham); sie ist eine Folge von Primzahlen mit der Rekursionsvorschrift

$a_{0}=p,\quad a_{n+1}=2\cdot a_{n}+1$ $\quad \Rightarrow \quad a_{n}=(p+1)\cdot 2^{n}-1{\text{ mit }}n\geq 0$.

(also p, 2p+1, 4p+3, 8p+7, ...)

Alle Primzahlen einer solchen Folge, mit Ausnahme der letzten Primzahl, sind Sophie-Germain-Primzahlen. Die erste Cunningham-Kette ist die Folge: 2, 5, 11, 23, 47.

Anfangswerte:

Auf eine Primzahl $p$, die mit 5 den Divisionsrest 1 hat, folgen in der Kette Zahlen mit den Divisionsresten 3, 2 und 0; wenn der Divisionsrest 4 ist, haben auch alle folgenden Kettenglieder den Divisionsrest 4. Alle Kettenglieder von Cunninghamketten mit größerer Länge als 3 und Anfangswert $p>5$ haben daher ebenfalls mit 5 den Divisionsrest 4, und mit der obengenannten Bedingung für Sophie-Germain-Primzahlen gilt dann $p=30k-1{\text{ mit }}k>0$, also $p\equiv 29{\pmod {30}}$. Entsprechend gilt dann für alle Kettenglieder $a_{n}\equiv 29{\pmod {30}}$.

Die jeweils ersten vorkommenden Cunninghamketten mit k Kettengliedern, die mit der Primzahl p beginnen, sind in der nachfolgenden Tabelle aufgeführt:

Erste Cunningham-Kette mit k Kettengliedern
k	p
5	2
6	89
7	1.122.659
8	19.099.919
9	85.864.769
10	26.089.808.579
11	665.043.081.119
12	554.688.278.429
13	4.090.932.431.513.069
14	95.405.042.230.542.329

Cunningham-Ketten der zweiten Art

Eine Cunningham-Kette der zweiten Art ist eine Folge von Primzahlen der Form

$a_{0}=p,\quad a_{n+1}=2\!\cdot \!a_{n}-1$ $\quad \Rightarrow \quad a_{n}=(p-1)\cdot 2^{n}+1{\text{ mit }}n\geq 0$.

Zwei Beispiele für Cunningham-Ketten der zweiten Art sind die Folge 2, 3, 5 und die Folge 1531, 3061, 6121, 12241, 24481 .

Verallgemeinerte Cunningham-Ketten

Eine Folge von Primzahlen der Form

$\ a_{0}=p,\ a_{n+1}=a\!\cdot \!a_{n}+b\ \quad \Rightarrow \quad a_{n}=\left(p+{\frac {b}{a-1}}\right)\cdot a^{n}-{\frac {b}{a-1}}{\text{ mit }}n\geq 0$

mit festem $a$ und festem $b$ nennt man eine verallgemeinerte Cunningham-Kette. Dabei muss $b$ zu $a$ und $p$ teilerfremd sein, andernfalls sind $a_{1}$ und alle nachfolgenden Folgeglieder Vielfache des gemeinsamen Teilers und damit keine Primzahlen.

Beweis der Funktionsgleichung:

${\begin{array}{lcl}\\{\text{1.}}\quad a_{0}&=&\left(p+{\frac {b}{a-1}}\right)\cdot a^{0}-{\frac {b}{a-1}}\\&=&p+{\frac {b}{a-1}}-{\frac {b}{a-1}}\\&=&p\\\ \\{\text{2.}}\quad a_{n+1}&=&\left(\left(p+{\frac {b}{a-1}}\right)\cdot a^{n}-{\frac {b}{a-1}}\right)\cdot a+b\\&=&\left(p+{\frac {b}{a-1}}\right)\cdot a^{n+1}-{\frac {b\cdot a}{a-1}}+b\\&=&\left(p+{\frac {b}{a-1}}\right)\cdot a^{n+1}-{\frac {b\cdot a-b\cdot (a-1)}{a-1}}\\&=&\left(p+{\frac {b}{a-1}}\right)\cdot a^{n+1}-{\frac {b}{a-1}}\end{array}}$

Durch Einsetzen von $a=2,b=\pm 1$ erhält man die oben angegebenen Funktionsgleichungen für Cunningham-Ketten erster und zweiter Art.

_{Quelle: Der Abschnitt mit Cullen-Zahl und Woodall-Zahl stamt aus dem Artikel Cullen-Zahl entnommen von der deutsprachigen de.wikipedia.org. Der Abschnitt Cuningham-Kette stamt aus dem Artikel Cunningham-Kette entnommen von der deutsprachigen de.wikipedia.org. Weitere Informationen zu den verschiedenen Primzahlarten findet man u.a. bei primes.utm.edu und www.prothsearch.net}