Lange Primzahl

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

• ${\displaystyle b\in \mathbb {N} }${\displaystyle b\in \mathbb {N} } ist eine natürliche Zahl, sodass ${\displaystyle p}${\displaystyle p} kein Teiler von ${\displaystyle b}${\displaystyle b} ist
• ${\displaystyle x={\frac {b^{p-1}-1}{p}}}${\displaystyle 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^[1] ) wurde erstmals von John Horton Conway und Richard Kenneth Guy in ihrem Buch The Book of Numbers erwähnt.^[2]

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

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

Jedes Mal erhält man die gleichen Ziffern in der gleichen Reihenfolge, nur zyklisch vertauscht. Eine solche Zahl wie ${\displaystyle x}${\displaystyle x} gilt (im Dezimalsystem) als zyklische Zahl. Vor allem aber war bei der Bruchzahl ${\displaystyle n={\tfrac {1}{7}}={\tfrac {1}{p}}}${\displaystyle n={\tfrac {1}{7}}={\tfrac {1}{p}}} die Periodenlänge ${\displaystyle p-1=6}${\displaystyle p-1=6}, also maximal lang, wenn man bedenkt, dass bei Division durch ${\displaystyle p=7}${\displaystyle p=7} höchstens ${\displaystyle p-1=6}${\displaystyle p-1=6} verschiedene Reste ungleich Null entstehen können (nämlich ${\displaystyle 1,2,\ldots ,6}${\displaystyle 1,2,\ldots ,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" ${\displaystyle p}${\displaystyle p} also Sinn, weil beim Bruch ${\displaystyle {\tfrac {1}{p}}}${\displaystyle {\tfrac {1}{p}}} die Periodenlänge ${\displaystyle p-1}${\displaystyle p-1} beträgt und somit maximal lang ist. Bei zusammengesetzten Zahlen ${\displaystyle p}${\displaystyle p} ist die Periodenlänge niemals ${\displaystyle p-1}${\displaystyle p-1}, deswegen kann man sich auf Primzahlen beschränken.

Im Dezimalsystem hat man die Basis ${\displaystyle b=10}${\displaystyle b=10}. Man nehme eine Primzahl ${\displaystyle p}${\displaystyle p}, welche kein Teiler der Basis ${\displaystyle b=10}${\displaystyle b=10} ist (also ${\displaystyle p\not =2}${\displaystyle p\not =2} und ${\displaystyle p\not =5}${\displaystyle p\not =5}) und bilde den Bruch ${\displaystyle {\frac {1}{p}}}${\displaystyle {\frac {1}{p}}}. Dieser Bruch sollte die Periodenlänge ${\displaystyle p-1}${\displaystyle p-1} haben. Nun multipliziert man diesen Bruch mit ${\displaystyle b^{\text{Periodenlänge}}=10^{p-1}}${\displaystyle 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 ${\displaystyle x=10^{p-1}\cdot {\frac {1}{p}}-{\frac {1}{p}}={\frac {10^{p-1}-1}{p}}}${\displaystyle x=10^{p-1}\cdot {\frac {1}{p}}-{\frac {1}{p}}={\frac {10^{p-1}-1}{p}}}. Ist ${\displaystyle x}${\displaystyle x} eine zyklische Zahl, so ist ${\displaystyle p}${\displaystyle p} eine lange Primzahl.

• Für die Primzahl ${\displaystyle p=7}${\displaystyle p=7} gilt im Dezimalsystem (mit Basis ${\displaystyle b=10}${\displaystyle b=10}): ${\displaystyle p=7}${\displaystyle p=7} ist kein Teiler der Basis ${\displaystyle b=10}${\displaystyle b=10} und es ist ${\displaystyle {\frac {b^{p-1}-1}{p}}={\frac {10^{7-1}-1}{7}}={\frac {999999}{7}}=142857}${\displaystyle {\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, ... (Folge A001913 in OEIS)
• Die Perioden der Kehrwerte der obigen langen Primzahlen (bis ${\displaystyle p=59}${\displaystyle p=59}) sind die folgenden:
  • 142857, 5882352941176470, 526315789473684210, 4347826086956521739130, 3448275862068965517241379310, 2127659574468085106382978723404255319148936170, 1694915254237288135593220338983050847457627118644067796610, ... (Folge A004042 in OEIS)
• Die Anzahl der langen Primzahlen im Dezimalsystem kleiner als ${\displaystyle 10^{n}}${\displaystyle 10^{n}} für ${\displaystyle n=1,2,\ldots }${\displaystyle n=1,2,\ldots } sind die folgenden:
  • 1, 9, 60, 467, 3617, 29500, 248881, 2155288, 19016617, 170169241, 1539964486, 14063663530, 129413160100, ... (Folge A086018 in OEIS)
  • Beispiel:
    Obiger Liste kann man an der 7. Stelle die Zahl ${\displaystyle 248881}${\displaystyle 248881} entnehmen. Das heißt, dass unter ${\displaystyle 10^{7}=10.000.000}${\displaystyle 10^{7}=10.000.000} genau ${\displaystyle 248881}${\displaystyle 248881} lange Primzahlen existieren.

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

• Im Dezimalsystem können folgende Primzahlen niemals lange Primzahlen sein:
  • ${\displaystyle p=40k+n}${\displaystyle p=40k+n} mit ${\displaystyle n\in \{1,3,9,13,27,31,37,39\}}${\displaystyle 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:
  • ${\displaystyle p=40k+n}${\displaystyle p=40k+n} mit ${\displaystyle n\in \{7,11,17,19,21,23,29,33\}}${\displaystyle n\in \{7,11,17,19,21,23,29,33\}}
• ${\displaystyle 285}${\displaystyle 285} der ${\displaystyle 295}${\displaystyle 295} Primzahlen der Form ${\displaystyle p=120k+23}${\displaystyle p=120k+23} mit ${\displaystyle p<100000}${\displaystyle p<100000} sind lange Primzahlen. Die erste Primzahl dieser Form, die keine lange Primzahl ist, ist ${\displaystyle p=20903}${\displaystyle p=20903}.
• Eine notwendige, aber nicht hinreichende Bedingung, dass ${\displaystyle p}${\displaystyle p} eine lange Primzahl im Dezimalsystem ist, gibt die folgende Eigenschaft an:^[3]
• Die Zahl ${\displaystyle 10^{p-1}-1=9\cdot R_{p-1}}${\displaystyle 10^{p-1}-1=9\cdot R_{p-1}} ist durch ${\displaystyle p}${\displaystyle p} teilbar.
  • (dabei ist ${\displaystyle R_{p}}${\displaystyle R_{p}} eine Repunit, also eine Zahl, die ausschließlich aus Einsen besteht und genau ${\displaystyle p}${\displaystyle p} Stellen hat.)
• Beispiel:
  • Die folgenden ${\displaystyle n}${\displaystyle n} sind Teiler von ${\displaystyle 10^{n-1}-1}${\displaystyle 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, ... (Folge A104381 in 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 ${\displaystyle p}${\displaystyle p} die Repunit-Zahl ${\displaystyle R_{\frac {p-1}{2}}}${\displaystyle R_{\frac {p-1}{2}}} eine Repunit-Primzahl ist, dann ist ${\displaystyle p}${\displaystyle p} eine lange Primzahl. Ebenso gilt umgekehrt, dass, wenn für eine Repunit-Primzahl ${\displaystyle R_{p}}${\displaystyle R_{p}} die Zahl ${\displaystyle 2p+1}${\displaystyle 2p+1} ebenfalls prim ist, dass ${\displaystyle 2p+1}${\displaystyle 2p+1} dann eine lange Primzahl ist.

Es wird vermutet, dass genau ${\displaystyle 37{,}39558136\ldots ,円\%}${\displaystyle 37{,}39558136\ldots ,円\%} (Folge A005596 in OEIS) aller Primzahlen im Dezimalsystem lange Primzahlen sind.^[3]

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

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

1, 9, 5, 467, 3617, 14750, 248881, 2155288, 19016617, 170169241, ... (Folge A103362 in OEIS)

Es folgt der Nenner dieses Wertes:

4, 25, 14, 1229, 9592, 39249, 664579, 5761455, 50847534, 455052511, ... (Folge A103363 in OEIS)

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

• Für ${\displaystyle b=2}${\displaystyle b=2} und ${\displaystyle p=11=1011_{2}}${\displaystyle p=11=1011_{2}} ist die Zahl

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

eine zyklische Zahl. Denn es ist:

${\displaystyle {\begin{array}{rrrrr}1\cdot 93&=&0001_{2}\cdot 0001011101_{2}&=&{\mathtt {0001011101}}_{2}.\2円\cdot 93&=&0010_{2}\cdot 0001011101_{2}&=&{\mathtt {0010111010}}_{2}.\3円\cdot 93&=&0011_{2}\cdot 0001011101_{2}&=&{\mathtt {0100010111}}_{2}.\4円\cdot 93&=&0100_{2}\cdot 0001011101_{2}&=&{\mathtt {0101110100}}_{2}.\5円\cdot 93&=&0101_{2}\cdot 0001011101_{2}&=&{\mathtt {0111010001}}_{2}.\6円\cdot 93&=&0110_{2}\cdot 0001011101_{2}&=&{\mathtt {1000101110}}_{2}.\7円\cdot 93&=&0111_{2}\cdot 0001011101_{2}&=&{\mathtt {1010001011}}_{2}.\8円\cdot 93&=&1000_{2}\cdot 0001011101_{2}&=&{\mathtt {1011101000}}_{2}.\9円\cdot 93&=&1001_{2}\cdot 0001011101_{2}&=&{\mathtt {1101000101}}_{2}.\10円\cdot 93&=&1010_{2}\cdot 0001011101_{2}&=&{\mathtt {1110100010}}_{2}.\\\end{array}}}${\displaystyle {\begin{array}{rrrrr}1\cdot 93&=&0001_{2}\cdot 0001011101_{2}&=&{\mathtt {0001011101}}_{2}.\2円\cdot 93&=&0010_{2}\cdot 0001011101_{2}&=&{\mathtt {0010111010}}_{2}.\3円\cdot 93&=&0011_{2}\cdot 0001011101_{2}&=&{\mathtt {0100010111}}_{2}.\4円\cdot 93&=&0100_{2}\cdot 0001011101_{2}&=&{\mathtt {0101110100}}_{2}.\5円\cdot 93&=&0101_{2}\cdot 0001011101_{2}&=&{\mathtt {0111010001}}_{2}.\6円\cdot 93&=&0110_{2}\cdot 0001011101_{2}&=&{\mathtt {1000101110}}_{2}.\7円\cdot 93&=&0111_{2}\cdot 0001011101_{2}&=&{\mathtt {1010001011}}_{2}.\8円\cdot 93&=&1000_{2}\cdot 0001011101_{2}&=&{\mathtt {1011101000}}_{2}.\9円\cdot 93&=&1001_{2}\cdot 0001011101_{2}&=&{\mathtt {1101000101}}_{2}.\10円\cdot 93&=&1010_{2}\cdot 0001011101_{2}&=&{\mathtt {1110100010}}_{2}.\\\end{array}}}

Die 10-stellige binäre Ziffernfolge von ${\displaystyle x}${\displaystyle x} wird bei der Multiplikation mit ${\displaystyle k=2,3,\ldots ,10}${\displaystyle k=2,3,\ldots ,10} jedes Mal zyklisch rotiert, also ist ${\displaystyle x=93}${\displaystyle x=93} im Dualsystem eine zyklische Zahl. Somit ist ${\displaystyle p=11}${\displaystyle 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, ... (Folge A001122 in OEIS)

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

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

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

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

Beweis:

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

• Sei ${\displaystyle p}${\displaystyle p} eine lange Primzahl im Dualsystem. Dann gilt:

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

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

Die kleinsten sicheren Primzahlen ${\displaystyle p<2000}${\displaystyle 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:

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

Beispiel:

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

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

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

• Die kleinsten langen Primzahlen zur Basis ${\displaystyle b}${\displaystyle b} für ${\displaystyle b=1,2,\ldots }${\displaystyle b=1,2,\ldots } 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, ... (Folge A056619 in OEIS)

Beispiel 1:

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

Beispiel 2:

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

• Es folgt eine Auflistung der kleinsten langen Primzahlen zu verschiedensten Basen ${\displaystyle b}${\displaystyle b}:

• Die folgenden vier Aussagen sind gleichbedeutend:

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 37{,}39558136\ldots ,円\%}${\displaystyle 37{,}39558136\ldots ,円\%} aller Primzahlen zur Basis ${\displaystyle b}${\displaystyle b} sind lange Primzahlen.

Beispiel:

Folgende Zahlen sind keine Potenz einer ganzen Zahl und haben keinen quadratfreien Teil, welcher ${\displaystyle \equiv 1{\pmod {4}}}${\displaystyle \equiv 1{\pmod {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, ... (Folge A085397 in OEIS)

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

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

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

• Sei ${\displaystyle p=13}${\displaystyle p=13} und die Basis ${\displaystyle b=10}${\displaystyle b=10}. Dann gilt:

${\displaystyle {\begin{array}{cccccccc}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}}}${\displaystyle {\begin{array}{cccccccc}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 ${\displaystyle {\frac {k}{13}}}${\displaystyle {\frac {k}{13}}} (mit ${\displaystyle k=1,2,\ldots ,12}${\displaystyle k=1,2,\ldots ,12}) sind zyklische Verschiebungen der ersten beiden Perioden. Somit hat die Zahl ${\displaystyle p=13}${\displaystyle p=13} genau ${\displaystyle 2}${\displaystyle 2} verschiedene Zykel und ${\displaystyle p=13}${\displaystyle p=13} ist somit eine lange Primzahl 2. Grades zur Basis ${\displaystyle b=10}${\displaystyle b=10}.

• Sei ${\displaystyle p=41}${\displaystyle p=41} und die Basis ${\displaystyle b=10}${\displaystyle b=10}. Dann gilt:

${\displaystyle {\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}}}${\displaystyle {\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 ${\displaystyle {\frac {k}{41}}}${\displaystyle {\frac {k}{41}}} (mit ${\displaystyle k=1,2,\ldots ,40}${\displaystyle k=1,2,\ldots ,40}) sind zyklische Verschiebungen von acht verschiedenen Perioden. Somit hat die Zahl ${\displaystyle p=41}${\displaystyle p=41} genau ${\displaystyle 8}${\displaystyle 8} verschiedene Zykel und ${\displaystyle p=41}${\displaystyle p=41} ist somit eine lange Primzahl 8. Grades zur Basis ${\displaystyle b=10}${\displaystyle b=10}.

• Im Dezimalsystem sind die jeweils ersten langen Primzahlen n-ten Grades die folgenden (für ${\displaystyle n=1,2,\ldots }${\displaystyle n=1,2,\ldots }):
• 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, ... (Folge A054471 in OEIS)
• Beispiel:
  • An der 8. Stelle obiger Liste steht die Zahl ${\displaystyle 41}${\displaystyle 41}. Das heißt, dass ${\displaystyle p=41}${\displaystyle 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 ${\displaystyle n=1,2,\ldots }${\displaystyle n=1,2,\ldots }):
• 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, ... (Folge A101208 in OEIS)
• Beispiel:
  • An der 2. Stelle obiger Liste steht die Zahl ${\displaystyle 7}${\displaystyle 7}. Das heißt, dass ${\displaystyle p=7}${\displaystyle p=7} die kleinste lange Primzahl 2. Grades (im Dualsystem) ist.
• Es folgt eine Liste von langen Primzahlen n-ten Grades im Dezimalsystem:

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

• Eric W. Weisstein: Full Reptend Prime. In: MathWorld (englisch).
• Eric W. Weisstein: Artins Constant. In: MathWorld (englisch).
• Full Reptend Prime. In: PlanetMath. (englisch)

1. ↑ ^{a b} Leonard Eugene Dickson: History of the Theory of numbers. Volume 1: Divisibility and primality. Carnegie Institution of Washington, 1919, S. 166; Textarchiv – Internet Archive
2. ↑ John H. Conway, Richard K. Guy: The Book of Numbers. Springer-Verlag, 1996, S. 157–163, 166–171, abgerufen am 11. Juli 2018 (englisch). 
3. ↑ ^{a b} Eric W. Weisstein: Full Reptend Prime. In: MathWorld (englisch).
4. ↑ ^{a b} Neil Sloane: Primes with primitive root 2 – Comments. OEIS, abgerufen am 12. Juli 2018. 

• Ganzzahlmenge
• Primzahl
• Zahlentheorie

• Wikipedia:Wikidata P2812 verschieden