Lange Primzahl

In der Zahlentheorie ist eine lange Primzahl zur Basis b eine Primzahl $p\in \mathbb{P}$, für welche gilt:

• $b\in \mathbb{N}$ ist eine natürliche Zahl, sodass $p$ kein Teiler von $b$ ist
• $x=\frac{b^{p-1}-1}{p}$ ist eine zyklische Zahl.

Der Ausdruck lange Primzahl (vom englischen long prime, aber auch full reptend prime, full repetend prime bzw. proper prime) wurde erstmals von John Horton Conway und Richard Kenneth Guy in ihrem Buch The Book of Numbers erwähnt.

Herleitung der Definition anhand von Beispielen

Wenn man die Basis $b=10$ betrachtet (also das Dezimalsystem), so erwähnt man dieses üblicherweise nicht. In diesem Abschnitt geht es um diese Basis $b=10$.

Eine Bruchzahl, zum Beispiel $n=\frac{1}{2}$ kann auch mit Komma geschrieben werden: $n=\frac{1}{2}=0,5$. Diese Dezimalzahlen hören, wie im Fall $n=\frac{1}{2}=0,5$ auf oder sind unendlich lang, wie zum Beispiel bei $n=\frac{1}{3}=0,333333\dots$. Diese unendliche Wiederholung derselben Ziffern nennt man Periode und schreibt $n=\frac{1}{3}=0,\bar{3}$. Die Periode kann auch länger sein, wie zum Beispiel bei $n=\frac{1}{13}=0,076923076923\dots =0,\overline{076923}$. Meistens verändern sich die Ziffern der Periode, wenn man die Zahl multipliziert (zum Beispiel ist $2\cdot \frac{1}{13}=0,153846153846\dots =0,\overline{153846}$). Es gibt aber periodische Bruchzahlen, deren Ziffern sich nach einer Multiplikation nicht ändern, wie zum Beispiel bei $n=\frac{1}{7}=0,14285714285\dots =0,\overline{142857}$. Um diese sechs Nachkommastellen zu einer ganzen Zahl zu machen, multipliziert man sie mit $10^{\text{Periodenlänge}}$, also mit $10^6$ und erhält die Zahl $142857,\overline{142857}$. Subtrahiert man nun noch $\frac{1}{7}=0,\overline{142857}$, so erhält man die ganze Zahl $x=142857$. Wenn man diese Zahl mit $k=1,2,3,\dots ,n-1$ multipliziert, so erhält man:

$1\cdot 142857=$	$\mathrm{𝟷}\mathrm{𝟺}\mathrm{𝟸}\mathrm{𝟾}\mathrm{𝟻}\mathrm{𝟽}$
$2\cdot 142857=$	$\mathrm{𝟸}\mathrm{𝟾}\mathrm{𝟻}\mathrm{𝟽}\mathrm{𝟷}\mathrm{𝟺}$
$3\cdot 142857=$	$\mathrm{𝟺}\mathrm{𝟸}\mathrm{𝟾}\mathrm{𝟻}\mathrm{𝟽}\mathrm{𝟷}$
$4\cdot 142857=$	$\mathrm{𝟻}\mathrm{𝟽}\mathrm{𝟷}\mathrm{𝟺}\mathrm{𝟸}\mathrm{𝟾}$
$5\cdot 142857=$	$\mathrm{𝟽}\mathrm{𝟷}\mathrm{𝟺}\mathrm{𝟸}\mathrm{𝟾}\mathrm{𝟻}$
$6\cdot 142857=$	$\mathrm{𝟾}\mathrm{𝟻}\mathrm{𝟽}\mathrm{𝟷}\mathrm{𝟺}\mathrm{𝟸}$

Jedes Mal erhält man die gleichen Ziffern in der gleichen Reihenfolge, nur zyklisch vertauscht. Eine solche Zahl wie $x$ gilt (im Dezimalsystem) als zyklische Zahl. Vor allem aber war bei der Bruchzahl $n=\frac{1}{7}=\frac{1}{p}$ die Periodenlänge $p-1=6$, also maximal lang, wenn man bedenkt, dass bei Division durch $p=7$ höchstens $p-1=6$ verschiedene Reste ungleich Null entstehen können (nämlich $1,2,\dots ,6$). Käme bei der Division Null Rest heraus, würde die Dezimalzahl und somit auch die Periode enden (und wäre somit auch keine Periode, weil sie eben endet). Insofern macht der Begriff „lange Primzahl“ $p$ also Sinn, weil beim Bruch $\frac{1}{p}$ die Periodenlänge $p-1$ beträgt und somit maximal lang ist. Bei zusammengesetzten Zahlen $p$ ist die Periodenlänge niemals $p-1$, deswegen kann man sich auf Primzahlen beschränken.

Kurzfassung im Dezimalsystem

Im Dezimalsystem hat man die Basis $b=10$. Man nehme eine Primzahl $p$, welche kein Teiler der Basis $b=10$ ist (also $p=2$ und $p=5$) und bilde den Bruch $\frac{1}{p}$. Dieser Bruch sollte die Periodenlänge $p-1$ haben. Nun multipliziert man diesen Bruch mit $b^{\text{Periodenlänge}}=10^{p-1}$ und subtrahiert die ursprüngliche Bruchzahl, damit die Periode hinter dem Komma wegfällt. Man erhält die der Zahl p entsprechende Zahl $x=10^{p-1}\cdot \frac{1}{p}-\frac{1}{p}=\frac{10^{p-1}-1}{p}$. Ist $x$ eine zyklische Zahl, so ist $p$ eine lange Primzahl.

Beispiele

• Für die Primzahl $p=7$ gilt im Dezimalsystem (mit Basis $b=10$): $p=7$ ist kein Teiler der Basis $b=10$ und es ist $\frac{b^{p-1}-1}{p}=\frac{10^{7-1}-1}{7}=\frac{999999}{7}=142857$ eine zyklische Zahl, wie schon vorher gezeigt wurde.
• Die ersten langen Primzahlen im Dezimalsystem sind die folgenden:
  • 7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983, … (Vorlage:OEIS)
• Die Perioden der Kehrwerte der obigen langen Primzahlen (bis $p=59$) sind die folgenden:
  • 142857, 5882352941176470, 526315789473684210, 4347826086956521739130, 3448275862068965517241379310, 2127659574468085106382978723404255319148936170, 1694915254237288135593220338983050847457627118644067796610, … (Vorlage:OEIS)
• Die Anzahl der langen Primzahlen im Dezimalsystem kleiner als $10^n$ für $n=1,2,\dots$ sind die folgenden:
  • 1, 9, 60, 467, 3617, 29500, 248881, 2155288, 19016617, 170169241, 1539964486, 14063663530, 129413160100, … (Vorlage:OEIS)
  • Beispiel:
    Obiger Liste kann man an der 7. Stelle die Zahl $248881$ entnehmen. Das heißt, dass unter $10^7=10.000.000$ genau $248881$ lange Primzahlen existieren.

Eigenschaften

• Die folgenden fünf Aussagen sind gleichbedeutend:
  • Die Zahl $p\in \mathbb{P}$ ist eine lange Primzahl im Dezimalsystem.
  • Die der Zahl $p$ entsprechende zyklische Zahl $x=\frac{10^{p-1}-1}{p}$ hat genau $p-1$ Stellen.
  • Für jede Restklasse $n=1,2,\dots ,p-1$ gibt es ein $i$, sodass $10^i\equiv n(\mathrm{mod}p)$ ist.
  • $10$ ist eine Primitivwurzel modulo $p$
  • $10^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p)$ für $p\ne 10^n+1$
• Sei $p\in \mathbb{P}$ eine lange Primzahl im Dezimalsystem, welche an der Einerstelle eine $1$ hat ($p$ hat also die Form $p=10k+1$ mit $k\in \mathbb{N}$). Dann gilt:
  • Jede Ziffer $0,1,2,\dots ,9$ taucht in der Periode von $\frac{1}{p}$ gleich oft auf.
  • Die Periodenlänge von $\frac{1}{p}$ ist durch $10$ ganzzahlig teilbar.
• Beispiel 1:
  • Für die lange Primzahl $p=2741$ gilt: Die Periodenlänge der Zahl $\frac{1}{p}=\frac{1}{2741}$ beträgt $p-1=2740$. In dieser Periode ist die Ziffer $0$ genau $274$ Mal enthalten, ebenso die Ziffern $1,2,3,\dots 9$.
• Beispiel 2:
  • Die kleinsten langen Primzahlen mit $1$ an der Einerstelle sind die folgenden:

    61, 131, 181, 461, 491, 541, 571, 701, 811, 821, 941, 971, 1021, 1051, 1091, 1171, 1181, 1291, 1301, 1349, 1381, 1531, 1571, 1621, 1741, 1811, 1829, 1861, 2141, 2221, 2251, 2341, 2371, 2411, 2621, 2731, 2741, 2851, 2861, 2971, 3011, 3221, 3251, 3301, … (Vorlage:OEIS)

• Im Dezimalsystem können folgende Primzahlen niemals lange Primzahlen sein:
  • $p=40k+n$ mit $n\in \{1,3,9,13,27,31,37,39\}$
• Studien haben ergeben, dass im Dezimalsystem etwa zwei Drittel der Primzahlen mit folgender Form lange Primzahlen sind:
  • $p=40k+n$ mit $n\in \{7,11,17,19,21,23,29,33\}$
• $285$ der $295$ Primzahlen der Form $p=120k+23$ mit $p<100000$ sind lange Primzahlen. Die erste Primzahl dieser Form, die keine lange Primzahl ist, ist $p=20903$.
• Eine notwendige, aber nicht hinreichende Bedingung, dass $p$ eine lange Primzahl im Dezimalsystem ist, gibt die folgende Eigenschaft an:
• Die Zahl $10^{p-1}-1=9\cdot R_{p-1}$ ist durch $p$ teilbar.
  • (dabei ist $R_p$ eine Repunit, also eine Zahl, die ausschließlich aus Einsen besteht und genau $p$ Stellen hat.)
• Beispiel:
  • Die folgenden $n$ sind Teiler von $10^{n-1}-1$:

    1, 3, 7, 9, 11, 13, 17, 19, 23, 29, 31, 33, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 259, 263, … (Vorlage:OEIS)

• (das heißt, dass alle langen Primzahlen in dieser Liste enthalten sein müssen, aber nicht alle in dieser Liste sind lange Primzahlen)
• Wenn für eine Primzahl $p$ die Repunit-Zahl $R_{\frac{p-1}{2}}$ eine Repunit-Primzahl ist, dann ist $p$ eine lange Primzahl. Ebenso gilt umgekehrt, dass, wenn für eine Repunit-Primzahl $R_p$ die Zahl $2p+1$ ebenfalls prim ist, dass $2p+1$ dann eine lange Primzahl ist.

Ungelöste Probleme

Artins Vermutung

Es wird vermutet, dass genau $37,39558136\dots \mathrm{\%}$ (Vorlage:OEIS) aller Primzahlen im Dezimalsystem lange Primzahlen sind.

Die Zahl $C_{\mathrm{A}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{n}}:=\prod _{p\in \mathbb{P}}(1-\frac{1}{p(p-1)})=0.3739558136\dots$ nennt sich Artins Konstante und bezieht sich eigentlich auf den Anteil der Primzahlen, für welche $10$ eine Primitivwurzel modulo $p$ ist. Die Vermutung nennt sich Artins Vermutung und wurde von Emil Artin 1927 erstmals erwähnt.

Beispiel

Die folgenden beiden Listen geben gemeinsam betrachtet an, wie viel Prozent aller Primzahlen unter $10^n$ lange Primzahlen sind. Zunächst der Zähler dieses Wertes:

1, 9, 5, 467, 3617, 14750, 248881, 2155288, 19016617, 170169241, … (Vorlage:OEIS)

Es folgt der Nenner dieses Wertes:

4, 25, 14, 1229, 9592, 39249, 664579, 5761455, 50847534, 455052511, … (Vorlage:OEIS)

Obigen beiden Listen kann man jeweils an der 4. Stelle die Zahlen $467$ und $1229$ entnehmen. Das bedeutet, dass $\frac{467}{1229}\approx 37,998\mathrm{\%}$ aller Primzahlen bis $10^4$ lange Primzahlen sind, was sehr nah an Artins Konstante herankommt. Unter $10^{10}$ sind es schon $\frac{170169241}{455052511}\approx 37,374\mathrm{\%}$ aller Primzahlen, womit man noch näher an Artins Konstante herangerückt ist.

Lange Primzahlen im Dualsystem

Beispiele

• Für $b=2$ und $p=11=1011_2$ ist die Zahl

  $x:=\frac{b^{p-1}-1}{p}=\frac{2^{10}-1}{11}=\frac{1023}{11}=93=0001011101_2$

eine zyklische Zahl. Denn es ist:

$\begin{array}{ccccc}1\cdot 93& =& 0001_2\cdot 0001011101_2& =& {\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}}_2.\\ 2\cdot 93& =& 0010_2\cdot 0001011101_2& =& {\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}}_2.\\ 3\cdot 93& =& 0011_2\cdot 0001011101_2& =& {\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟷}}_2.\\ 4\cdot 93& =& 0100_2\cdot 0001011101_2& =& {\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟶}}_2.\\ 5\cdot 93& =& 0101_2\cdot 0001011101_2& =& {\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟷}}_2.\\ 6\cdot 93& =& 0110_2\cdot 0001011101_2& =& {\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟶}}_2.\\ 7\cdot 93& =& 0111_2\cdot 0001011101_2& =& {\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟷}}_2.\\ 8\cdot 93& =& 1000_2\cdot 0001011101_2& =& {\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟶}}_2.\\ 9\cdot 93& =& 1001_2\cdot 0001011101_2& =& {\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}}_2.\\ 10\cdot 93& =& 1010_2\cdot 0001011101_2& =& {\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟶}\mathrm{𝟷}\mathrm{𝟶}}_2.\end{array}$

Die 10-stellige binäre Ziffernfolge von $x$ wird bei der Multiplikation mit $k=2,3,\dots ,10$ jedes Mal zyklisch rotiert, also ist $x=93$ im Dualsystem eine zyklische Zahl. Somit ist $p=11$ im Dualsystem eine lange Primzahl (im Dezimalsystem übrigens nicht).

• Die ersten langen Primzahlen im Dualsystem sind die folgenden:

3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, … (Vorlage:OEIS)

Eigenschaften

• Sei $p$ eine lange Primzahl im Dualsystem (also mit Basis $n=2$). Dann gilt:
  • Für jede Restklasse $n=1,2,\dots ,p-1$ gibt es ein $i$, sodass $2^i\equiv n(\mathrm{mod}p)$ ist.
  • $2$ ist eine Primitivwurzel modulo $p$

(Dieser Satz ist ein Spezialfall eines schon weiter oben erwähnten Satzes.)

• Im Dualsystem können folgende Primzahlen niemals lange Primzahlen sein:

$p=8k+n$ mit $n\in \{1,7\}$

Beweis:

Für diese $p$ ist $2$ ein quadratischer Rest modulo $p$, daher muss $p$ ein Teiler von $2^{\frac{p-1}{2}}-1$ sein. Die Periodenlänge von $\frac{1}{p}$ im Dualsystem muss also $\frac{p-1}{2}$ teilen und kann somit nicht $p-1$ sein. Somit kann $p$ auch keine lange Primzahl im Dualsystem sein. $◻$

• Sei $p$ eine lange Primzahl im Dualsystem. Dann gilt:

$p$ hat die Form $p=8k+3$ oder $p=8k+5$ mit $k\in \mathbb{N}$

• Alle sicheren Primzahlen $p$ mit $p\equiv 3(\mathrm{mod}8)$ (inklusive $p=3$) sind lange Primzahlen im Dualsystem.

Die kleinsten sicheren Primzahlen $p<2000$ mit dieser Eigenschaft sind die folgenden:

3, 11, 59, 83, 107, 179, 227, 347, 467, 563, 587, 1019, 1187, 1283, 1307, 1523, 1619, 1907, …

• Studien haben ergeben, dass im Dualsystem etwa drei Viertel der Primzahlen mit folgender Form lange Primzahlen sind:

• $p=8k+n$ mit $n\in \{3,5\}$

Beispiel:

Es gibt $87$ Primzahlen $p<1000$, welche die Kongruenz $p\equiv 3(\mathrm{mod}8)$ oder $p\equiv 5(\mathrm{mod}8)$ erfüllen. $67$ von ihnen sind lange Primzahlen zur Basis $b=2$. Das sind etwa $77\mathrm{\%}$.

• $1078$ der $1206$ Primzahlen der Form $p=24k+5$ mit $p<100000$ sind lange Primzahlen im Dualsystem. Die erste Primzahl dieser Form, die keine lange Primzahl ist, ist $p=1013$.

Ungelöste Probleme

• Artin vermutet, dass es unendlich viele lange Primzahlen im Dualsystem gibt.
• Es wird vermutet, dass es unendlich viele Primzahlzwillinge gibt, die lange Primzahlen im Dualsystem sind.

Lange Primzahlen zur Basis b

Beispiele

• Die kleinsten langen Primzahlen zur Basis $b$ für $b=1,2,\dots$ sind die folgenden (dabei bedeutet 0, dass keine solche Primzahl existiert):

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, 2, 3, 2, 13, 2, 5, 2, 3, 2, 5, 2, 11, 2, 3, 2, 5, 2, 11, 2, 3, 2, 7, 2, 7, 2, 3, 2, … (Vorlage:OEIS)

Beispiel 1:

In obiger Liste steht an der 6. Stelle die Zahl $11$. Das heißt, dass $p=11$ die kleinste lange Primzahl zur Basis $b=6$ ist.

Beispiel 2:

In obiger Liste steht an der 4. Stelle die Zahl $0$. Das heißt, dass es keine Primzahl $p$ gibt, die eine lange Primzahl zur Basis $b=4$ ist.

• Es folgt eine Auflistung der kleinsten langen Primzahlen zu verschiedensten Basen $b$:

lange Primzahlen bis zur Basis b=30

Basis b	lange Primzahlen zur Basis $b$	OEIS-Folge
2	3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, …	Vorlage:OEIS
3	2, 5, 7, 17, 19, 29, 31, 43, 53, 79, 89, 101, 113, 127, 137, 139, 149, 163, 173, 197, 199, 211, 223, 233, 257, …	Vorlage:OEIS
4	(es gibt keine langen Primzahlen zur Basis b=4)
5	2, 3, 7, 17, 23, 37, 43, 47, 53, 73, 83, 97, 103, 107, 113, 137, 157, 167, 173, 193, 197, 223, 227, 233, 257, …	Vorlage:OEIS
6	11, 13, 17, 41, 59, 61, 79, 83, 89, 103, 107, 109, 113, 127, 131, 137, 151, 157, 179, 199, 223, 227, 229, 233, …	Vorlage:OEIS
7	2, 5, 11, 13, 17, 23, 41, 61, 67, 71, 79, 89, 97, 101, 107, 127, 151, 163, 173, 179, 211, 229, 239, 241, 257, …	Vorlage:OEIS
8	3, 5, 11, 29, 53, 59, 83, 101, 107, 131, 149, 173, 179, 197, 227, 269, 293, 317, 347, 389, 419, 443, 461, 467, …	Vorlage:OEIS
9	2 (es gibt keine weiteren langen Primzahlen zur Basis b=9)
10	7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, …	Vorlage:OEIS
11	2, 3, 13, 17, 23, 29, 31, 41, 47, 59, 67, 71, 73, 101, 103, 109, 149, 163, 173, 179, 197, 223, 233, 251, 277, …	Vorlage:OEIS
12	5, 7, 17, 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, 223, 257, 269, 281, 283, …	Vorlage:OEIS
13	2, 5, 11, 19, 31, 37, 41, 47, 59, 67, 71, 73, 83, 89, 97, 109, 137, 149, 151, 167, 197, 227, 239, 241, 281, 293, …	Vorlage:OEIS
14	3, 17, 19, 23, 29, 53, 59, 73, 83, 89, 97, 109, 127, 131, 149, 151, 227, 239, 241, 251, 257, 263, 277, 283, 307, …	Vorlage:OEIS
15	2, 13, 19, 23, 29, 37, 41, 47, 73, 83, 89, 97, 101, 107, 139, 149, 151, 157, 167, 193, 199, 227, 263, 269, 271, …	Vorlage:OEIS
16	(es gibt keine langen Primzahlen zur Basis b=16)
17	2, 3, 5, 7, 11, 23, 31, 37, 41, 61, 97, 107, 113, 131, 139, 167, 173, 193, 197, 211, 227, 233, 269, 277, 283, …	Vorlage:OEIS
18	5, 11, 29, 37, 43, 53, 59, 61, 67, 83, 101, 107, 109, 139, 149, 157, 163, 173, 179, 181, 197, 227, 251, 269, …	Vorlage:OEIS
19	2, 7, 11, 13, 23, 29, 37, 41, 43, 47, 53, 83, 89, 113, 139, 163, 173, 191, 193, 239, 251, 257, 263, 269, 281, …	Vorlage:OEIS
20	3, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 103, 107, 113, 137, 157, 163, 167, 173, 223, 227, 233, 257, 263, 277, …	Vorlage:OEIS
21	2, 19, 23, 29, 31, 53, 71, 97, 103, 107, 113, 137, 139, 149, 157, 179, 181, 191, 197, 223, 233, 239, 263, 271, …	Vorlage:OEIS
22	5, 17, 19, 31, 37, 41, 47, 53, 71, 83, 107, 131, 139, 191, 193, 199, 211, 223, 227, 233, 269, 281, 283, 307, …	Vorlage:OEIS
23	2, 3, 5, 17, 47, 59, 89, 97, 113, 127, 131, 137, 149, 167, 179, 181, 223, 229, 281, 293, 307, 311, 337, 347, …	Vorlage:OEIS
24	7, 11, 13, 17, 31, 37, 41, 59, 83, 89, 107, 109, 113, 137, 157, 179, 181, 223, 227, 229, 233, 251, 257, 277, …	Vorlage:OEIS
25	2 (es gibt keine weiteren langen Primzahlen zur Basis b=25)
26	3, 7, 29, 41, 43, 47, 53, 61, 73, 89, 97, 101, 107, 131, 137, 139, 157, 167, 173, 179, 193, 239, 251, 269, 271, …	Vorlage:OEIS
27	2, 5, 17, 29, 53, 89, 101, 113, 137, 149, 173, 197, 233, 257, 269, 281, 293, 317, 353, 389, 401, 449, 461, 509, …	Vorlage:OEIS
28	5, 11, 13, 17, 23, 41, 43, 67, 71, 73, 79, 89, 101, 107, 173, 179, 181, 191, 229, 257, 263, 269, 293, 313, 331, …	Vorlage:OEIS
29	2, 3, 11, 17, 19, 41, 43, 47, 73, 79, 89, 97, 101, 113, 127, 131, 137, 163, 191, 211, 229, 251, 263, 269, 293, …	Vorlage:OEIS
30	11, 23, 41, 43, 47, 59, 61, 79, 89, 109, 131, 151, 167, 173, 179, 193, 197, 199, 251, 263, 281, 293, 307, 317, …	Vorlage:OEIS

Eigenschaften

• Die folgenden vier Aussagen sind gleichbedeutend:

• Die Zahl $p\in \mathbb{P}$ ist eine lange Primzahl zur Basis $b\in \mathbb{N}$
• Die der Zahl $p$ entsprechende zyklische Zahl $x=\frac{b^{p-1}-1}{p}$ hat genau $p-1$ Stellen
• Für jede Restklasse $n=1,2,\dots ,p-1$ gibt es ein $i$, sodass $b^i\equiv n(\mathrm{mod}p)$ ist.
• $b$ ist eine Primitivwurzel modulo $p$

(Dieser Satz ist eine Verallgemeinerung eines weiter oben stehenden Satzes im Dezimalsystem.)

• Sei $p\in \mathbb{P}$ eine lange Primzahl zur Basis $b$, welche an der Einerstelle eine $1$ hat ($p$ hat also die Form $p=b\cdot k+1$ mit $k\in \mathbb{N}$). Dann gilt:

• Jede Ziffer $0,1,2,\dots ,b-1$ taucht in der Periode von $\frac{1}{p}$ gleich oft auf.
• Die Periodenlänge von $\frac{1}{p}$ ist durch $b$ ganzzahlig teilbar.

(Auch dieser Satz ist eine Verallgemeinerung eines weiter oben stehenden Satzes im Dezimalsystem.)

• Jede lange Primzahl $p\in \mathbb{P}$ zur Basis $b=12$ endet mit $5$ oder $7$.

(Es gibt also keine langen Primzahlen zur Basis $b=12$, welche an der Einerstelle eine $1$ haben.)

• Sei $p\in \mathbb{P}$ eine lange Primzahl zur Basis $b$ mit $b\equiv 0(\mathrm{mod}4)$ oder $b\equiv 1(\mathrm{mod}4)$. Dann gilt:

Es gibt keine langen Primzahlen zur Basis $b$, welche an der Einerstelle eine $1$ haben.

(Dieser Satz ist eine Verallgemeinerung des direkt darüber stehenden Satzes.)

Ungelöste Probleme

• Es wird (ebenfalls von Artin) vermutet, dass es unendlich viele lange Primzahlen gibt, wenn die Basis $b$ keine Quadratzahl ist.
• Sei die Basis $b$ keine Potenz einer ganzen Zahl (also $b=x^y$ mit $x,y\in \mathbb{N}$) und sei $b$ keine Basis, dessen quadratfreier Teil $\equiv 1(\mathrm{mod}4)$ ist. Dann wird (ebenfalls von Artin) vermutet:

$37,39558136\dots \mathrm{\%}$ aller Primzahlen zur Basis $b$ sind lange Primzahlen.

Beispiel:

Folgende Zahlen sind keine Potenz einer ganzen Zahl und haben keinen quadratfreien Teil, welcher $\equiv 1(\mathrm{mod}4)$ ist:

2, 3, 6, 7, 10, 11, 12, 14, 15, 18, 19, 22, 23, 24, 26, 28, 30, 31, 34, 35, 38, 39, 40, 42, 43, 44, 46, 47, 48, 50, 51, 54, 55, 56, 58, 59, 60, 62, 63, 66, 67, 70, 71, 72, 74, 75, 76, 78, 79, 82, 83, 86, 87, 88, 90, 91, 92, 94, 95, 96, 98, 99, 102, 103, 104, 106, 107, 108, … (Vorlage:OEIS)

Verallgemeinerung

Eine lange Primzahl n-ten Grades zur Basis b ist eine Primzahl $p\in \mathbb{P}$ mit folgender Eigenschaft:

Sei $k\in \mathbb{N}$ mit $1\le k\le p-1$. Dann gilt:

$\frac{k}{p}$ hat $n$ verschiedene Zykel in der dazugehörigen Dezimalbruchentwicklung

Beispiele im Dezimalsystem

• Sei $p=13$ und die Basis $b=10$. Dann gilt:

$\begin{array}{cc}1/13=0,\overline{076923}& 2/13=0,\overline{153846}\\ 3/13=0,\overline{230769}& 5/13=0,\overline{384615}\\ 4/13=0,\overline{307692}& 6/13=0,\overline{461538}\\ 9/13=0,\overline{692307}& 7/13=0,\overline{538461}\\ 10/13=0,\overline{769230}& 8/13=0,\overline{615384}\\ 12/13=0,\overline{923076}& 11/13=0,\overline{846153}\end{array}$

Alle 12 Perioden von $\frac{k}{13}$ (mit $k=1,2,\dots ,12$) sind zyklische Verschiebungen der ersten beiden Perioden. Somit hat die Zahl $p=13$ genau $2$ verschiedene Zykel und $p=13$ ist somit eine lange Primzahl 2. Grades zur Basis $b=10$.

• Sei $p=41$ und die Basis $b=10$. Dann gilt:

$\begin{array}{cccccccc}1/41=0,\overline{02439}& 2/41=0,\overline{04878}& 3/41=0,\overline{07317}& 4/41=0,\overline{09756}& 5/41=0,\overline{12195}& 6/41=0,\overline{14634}& 11/41=0,\overline{26829}& 15/41=0,\overline{36585}\\ 10/41=0,\overline{24390}& 20/41=0,\overline{48780}& 7/41=0,\overline{17073}& 23/41=0,\overline{56097}& 8/41=0,\overline{19512}& 14/41=0,\overline{34146}& 12/41=0,\overline{29268}& 22/41=0,\overline{53658}\\ 16/41=0,\overline{39024}& 32/41=0,\overline{78048}& 13/41=0,\overline{31707}& 25/41=0,\overline{60975}& 9/41=0,\overline{21951}& 17/41=0,\overline{41463}& 28/41=0,\overline{68292}& 24/41=0,\overline{58536}\\ 18/41=0,\overline{43902}& 33/41=0,\overline{80487}& 29/41=0,\overline{70731}& 31/41=0,\overline{75609}& 21/41=0,\overline{51219}& 19/41=0,\overline{46341}& 34/41=0,\overline{82926}& 27/41=0,\overline{65853}\\ 37/41=0,\overline{90243}& 36/41=0,\overline{87804}& 30/41=0,\overline{73170}& 40/41=0,\overline{97560}& 39/41=0,\overline{95121}& 26/41=0,\overline{63414}& 38/41=0,\overline{92682}& 35/41=0,\overline{85365}\end{array}$

Alle 40 Perioden von $\frac{k}{41}$ (mit $k=1,2,\dots ,40$) sind zyklische Verschiebungen von acht verschiedenen Perioden. Somit hat die Zahl $p=41$ genau $8$ verschiedene Zykel und $p=41$ ist somit eine lange Primzahl 8. Grades zur Basis $b=10$.

• Im Dezimalsystem sind die jeweils ersten langen Primzahlen n-ten Grades die folgenden (für $n=1,2,\dots$):
• 7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289, 859, 239, 27581, 9613, 18131, 13757, 33931, 9161, 118901, 6763, 18233, … (Vorlage:OEIS)
• Beispiel:
  • An der 8. Stelle obiger Liste steht die Zahl $41$. Das heißt, dass $p=41$ die kleinste lange Primzahl 8. Grades (im Dezimalsystem) ist. Direkt darüber wurde diese Primzahl als Beispiel verwendet.
• Im Dualsystem sind die jeweils ersten langen Primzahlen n-ten Grades die folgenden (für $n=1,2,\dots$):
• 3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593, 17029, 2687, 42701, 11161, 13099, 1103, 71293, 13121, 17467, 2143, 83077, 25609, 5581, … (Vorlage:OEIS)
• Beispiel:
  • An der 2. Stelle obiger Liste steht die Zahl $7$. Das heißt, dass $p=7$ die kleinste lange Primzahl 2. Grades (im Dualsystem) ist.
• Es folgt eine Liste von langen Primzahlen n-ten Grades im Dezimalsystem:

n	lange Primzahlen n-ten Grades im Dezimalsystem	OEIS-Folge
1	7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, …	Vorlage:OEIS
2	3, 13, 31, 43, 67, 71, 83, 89, 107, 151, 157, 163, 191, 197, 199, 227, 283, 293, 307, 311, 347, 359, 373, 401, 409, 431, 439, 443, 467, 479, 523, 557, 563, 569, 587, 599, …	Vorlage:OEIS
3	103, 127, 139, 331, 349, 421, 457, 463, 607, 661, 673, 691, 739, 829, 967, 1657, 1669, 1699, 1753, 1993, 2011, 2131, 2287, 2647, 2659, 2749, 2953, 3217, 3229, 3583, 3691, 3697, 3739, 3793, 3823, 3931, …	Vorlage:OEIS
4	53, 173, 277, 317, 397, 769, 773, 797, 809, 853, 1009, 1013, 1093, 1493, 1613, 1637, 1693, 1721, 2129, 2213, 2333, 2477, 2521, 2557, 2729, 2797, 2837, 3329, 3373, 3517, 3637, 3733, 3797, 3853, 3877, …	Vorlage:OEIS
5	11, 251, 1061, 1451, 1901, 1931, 2381, 3181, 3491, 3851, 4621, 4861, 5261, 6101, 6491, 6581, 6781, 7331, 8101, 9941, 10331, 10771, 11251, 11261, 11411, 12301, 14051, 14221, 14411, …	Vorlage:OEIS
6	79, 547, 643, 751, 907, 997, 1201, 1213, 1237, 1249, 1483, 1489, 1627, 1723, 1747, 1831, 1879, 1987, 2053, 2551, 2683, 3049, 3253, 3319, 3613, 3919, 4159, 4507, 4519, 4801, 4813, 4831, 4969, …	Vorlage:OEIS
7	211, 617, 1499, 2087, 2857, 6007, 6469, 7127, 7211, 7589, 9661, 10193, 13259, 13553, 14771, 18047, 18257, 19937, 20903, 21379, 23549, 26153, 27259, 27539, 32299, 33181, 33461, 34847, 35491, 35897, …	Vorlage:OEIS
8	41, 241, 1601, 1609, 2441, 2969, 3041, 3449, 3929, 4001, 4409, 5009, 6089, 6521, 6841, 8161, 8329, 8609, 9001, 9041, 9929, 13001, 13241, 14081, 14929, 16001, 16481, 17489, 17881, 18121, 19001, …	Vorlage:OEIS
9	73, 1423, 1459, 2377, 2503, 3457, 7741, 9433, 10891, 10909, 16057, 17299, 17623, 20269, 21313, 22699, 24103, 26263, 28621, 28927, 29629, 30817, 32257, 34273, 34327, …	Vorlage:OEIS
10	281, 521, 1031, 1951, 2281, 2311, 2591, 3671, 5471, 5711, 6791, 7481, 8111, 8681, 8761, 9281, 9551, 10601, 11321, 12401, 13151, 13591, 14831, 14951, 15671, 16111, 16361, 18671, …	Vorlage:OEIS

• Es folgt eine Liste von langen Primzahlen n-ten Grades im Dualsystem:

n	lange Primzahlen n-ten Grades im Dualsystem	OEIS-Folge
1	3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, …	Vorlage:OEIS
2	7, 17, 23, 41, 47, 71, 79, 97, 103, 137, 167, 191, 193, 199, 239, 263, 271, 311, 313, 359, 367, 383, 401, 409, 449, 463, 479, 487, 503, 521, 569, 599, 607, 647, 719, 743, 751, 761, 769, …	Vorlage:OEIS
3	43, 109, 157, 229, 277, 283, 307, 499, 643, 691, 733, 739, 811, 997, 1021, 1051, 1069, 1093, 1459, 1579, 1597, 1627, 1699, 1723, 1789, 1933, 2179, 2203, 2251, 2341, 2347, 2749, 2917, …	Vorlage:OEIS
4	113, 281, 353, 577, 593, 617, 1033, 1049, 1097, 1153, 1193, 1201, 1481, 1601, 1889, 2129, 2273, 2393, 2473, 3049, 3089, 3137, 3217, 3313, 3529, 3673, 3833, 4001, 4217, 4289, 4457, 4801, 4817, 4937, …	Vorlage:OEIS
5	251, 571, 971, 1181, 1811, 2011, 2381, 2411, 3221, 3251, 3301, 3821, 4211, 4861, 4931, 5021, 5381, 5861, 6221, 6571, 6581, 8461, 8501, 9091, 9461, 10061, 10211, 10781, 11251, 11701, 11941, 12541, …	Vorlage:OEIS
6	31, 223, 433, 439, 457, 727, 919, 1327, 1399, 1423, 1471, 1831, 1999, 2017, 2287, 2383, 2671, 2767, 2791, 2953, 3271, 3343, 3457, 3463, 3607, 3631, 3823, 3889, 4129, 4423, 4519, 4567, 4663, 4729, 4759, …	Vorlage:OEIS
7	1163, 1709, 2003, 3109, 3389, 3739, 5237, 5531, 5867, 7309, 9157, 9829, 10627, 10739, 11117, 11243, 11299, 11411, 11467, 13259, 18803, 20147, 20483, 21323, 21757, 27749, 27763, 29947, …	Vorlage:OEIS
8	73, 89, 233, 937, 1217, 1249, 1289, 1433, 1553, 1609, 1721, 1913, 2441, 2969, 3257, 3449, 4049, 4201, 4273, 4297, 4409, 4481, 4993, 5081, 5297, 5689, 6089, 6449, 6481, 6689, 6857, 7121, 7529, 7993, …	Vorlage:OEIS
9	397, 7867, 10243, 10333, 12853, 13789, 14149, 14293, 14563, 15643, 17659, 18379, 18541, 21277, 21997, 23059, 23203, 26731, 27739, 29179, 29683, 31771, 34147, 35461, 35803, 36541, 37747, 39979, …	Vorlage:OEIS
10	151, 241, 431, 641, 911, 3881, 4751, 4871, 5441, 5471, 5641, 5711, 6791, 6871, 8831, 9041, 9431, 10711, 12721, 13751, 14071, 14431, 14591, 15551, 16631, 16871, 17231, 17681, 17791, 18401, 19031, 19471, …	Vorlage:OEIS

Weblinks

• Vorlage:MathWorld
• Vorlage:MathWorld
• Vorlage:PlanetMath