www.wikidata.de-de.nina.az

Lange Primzahl In der Zahlentheorie ist eine lange Primzahl zur Basis b eine Primzahl p P displaystyle p in mathbb P für

Lange Primzahl

In der Zahlentheorie ist eine lange Primzahl zur Basis b eine Primzahl , für welche gilt:

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 Bearbeiten

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

Eine Bruchzahl, zum Beispiel kann auch mit Komma geschrieben werden: . Diese Dezimalzahlen hören, wie im Fall auf oder sind unendlich lang, wie zum Beispiel bei . Diese unendliche Wiederholung derselben Ziffern nennt man Periode und schreibt . Die Periode kann auch länger sein, wie zum Beispiel bei . Meistens verändern sich die Ziffern der Periode, wenn man die Zahl multipliziert (zum Beispiel ist ). Es gibt aber periodische Bruchzahlen, deren Ziffern sich nach einer Multiplikation nicht ändern, wie zum Beispiel bei . Um diese sechs Nachkommastellen zu einer ganzen Zahl zu machen, multipliziert man sie mit , also mit und erhält die Zahl . Subtrahiert man nun noch , so erhält man die ganze Zahl . Wenn man diese Zahl mit multipliziert, so erhält man:

 
      
    
          
            
        

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

Kurzfassung im Dezimalsystem Bearbeiten

Im Dezimalsystem hat man die Basis . Man nehme eine Primzahl , welche kein Teiler der Basis ist (also und ) und bilde den Bruch . Dieser Bruch sollte die Periodenlänge haben. Nun multipliziert man diesen Bruch mit und subtrahiert die ursprüngliche Bruchzahl, damit die Periode hinter dem Komma wegfällt. Man erhält die der Zahl p entsprechende Zahl . Ist eine zyklische Zahl, so ist eine lange Primzahl.

Beispiele Bearbeiten

  • Für die Primzahl gilt im Dezimalsystem (mit Basis ): ist kein Teiler der Basis und es ist 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 ) sind die folgenden:
    • 142857, 5882352941176470, 526315789473684210, 4347826086956521739130, 3448275862068965517241379310, 2127659574468085106382978723404255319148936170, 1694915254237288135593220338983050847457627118644067796610, … (Folge A004042 in OEIS)
  • Die Anzahl der langen Primzahlen im Dezimalsystem kleiner als für 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 entnehmen. Das heißt, dass unter genau lange Primzahlen existieren.

Eigenschaften Bearbeiten

  • Die folgenden vier Aussagen sind gleichbedeutend:
    • Die Zahl ist eine lange Primzahl im Dezimalsystem.
    • Die der Zahl entsprechende zyklische Zahl hat genau Stellen.
    • Für jede Restklasse gibt es ein , sodass ist.
    • ist eine Primitivwurzel modulo
  • Sei eine lange Primzahl im Dezimalsystem, welche an der Einerstelle eine hat ( hat also die Form mit ). Dann gilt:
    • Jede Ziffer taucht in der Periode von gleich oft auf.
    • Die Periodenlänge von ist durch ganzzahlig teilbar.
  • Beispiel 1:
    • Für die lange Primzahl gilt: Die Periodenlänge der Zahl beträgt . In dieser Periode ist die Ziffer genau Mal enthalten, ebenso die Ziffern .
  • Beispiel 2:
    • Die kleinsten langen Primzahlen mit an der Einerstelle sind die folgenden:
  • Im Dezimalsystem können folgende Primzahlen niemals lange Primzahlen sein:
    • mit
  • Studien haben ergeben, dass im Dezimalsystem etwa zwei Drittel der Primzahlen mit folgender Form lange Primzahlen sind:
    • mit
  • der Primzahlen der Form mit sind lange Primzahlen. Die erste Primzahl dieser Form, die keine lange Primzahl ist, ist .
  • Eine notwendige, aber nicht hinreichende Bedingung, dass eine lange Primzahl im Dezimalsystem ist, gibt die folgende Eigenschaft an:
  • Die Zahl ist durch teilbar.
    • (dabei ist eine Repunit, also eine Zahl, die ausschließlich aus Einsen besteht und genau Stellen hat.)
  • Beispiel:
    • Die folgenden sind Teiler von :
  • (das heißt, dass alle langen Primzahlen in dieser Liste enthalten sein müssen, aber nicht alle in dieser Liste sind lange Primzahlen)

Ungelöste Probleme Bearbeiten

Artins Vermutung Bearbeiten

Es wird vermutet, dass genau (Folge A005596 in OEIS) aller Primzahlen im Dezimalsystem lange Primzahlen sind.

Die Zahl nennt sich Artins Konstante und bezieht sich eigentlich auf den Anteil der Primzahlen, für welche eine Primitivwurzel modulo ist. Die Vermutung nennt sich Artins Vermutung und wurde von Emil Artin 1927 erstmals erwähnt.

Beispiel Bearbeiten

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

Es folgt der Nenner dieses Wertes:

Obigen beiden Listen kann man jeweils an der 4. Stelle die Zahlen und entnehmen. Das bedeutet, dass aller Primzahlen bis lange Primzahlen sind, was sehr nah an Artins Konstante herankommt. Unter sind es schon aller Primzahlen, womit man noch näher an Artins Konstante herangerückt ist.

Lange Primzahlen im Dualsystem Bearbeiten

Beispiele Bearbeiten

  • Für und ist die Zahl
Die 10-stellige binäre Ziffernfolge von wird bei der Multiplikation mit jedes Mal zyklisch rotiert, also ist im Dualsystem eine zyklische Zahl. Somit ist im Dualsystem eine lange Primzahl (im Dezimalsystem übrigens nicht).
  • Die ersten langen Primzahlen im Dualsystem sind die folgenden:

Eigenschaften Bearbeiten

  • Sei eine lange Primzahl im Dualsystem (also mit Basis ). Dann gilt:
    • Für jede Restklasse gibt es ein , sodass ist.
    • ist eine Primitivwurzel modulo
  • Im Dualsystem können folgende Primzahlen niemals lange Primzahlen sein:
  • Sei eine lange Primzahl im Dualsystem. Dann gilt:
  • Studien haben ergeben, dass im Dualsystem etwa drei Viertel der Primzahlen mit folgender Form lange Primzahlen sind:
  • der Primzahlen der Form mit sind lange Primzahlen im Dualsystem. Die erste Primzahl dieser Form, die keine lange Primzahl ist, ist .

Ungelöste Probleme Bearbeiten

  • 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 Bearbeiten

Beispiele Bearbeiten

  • Die kleinsten langen Primzahlen zur Basis für sind die folgenden (dabei bedeutet 0, dass keine solche Primzahl existiert):
Beispiel 2:
  • Es folgt eine Auflistung der kleinsten langen Primzahlen zu verschiedensten Basen :
lange Primzahlen bis zur Basis b=30
Basis b lange Primzahlen zur Basis 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, … Folge A001122 in 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, … Folge A019334 in 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, … Folge A019335 in 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, … Folge A019336 in 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, … Folge A019337 in 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, … Folge A019338 in 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, … Folge A001913 in 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, … Folge A019339 in 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, … Folge A019340 in 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, … Folge A019341 in 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, … Folge A019342 in 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, … Folge A019343 in 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, … Folge A019344 in 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, … Folge A019345 in 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, … Folge A019346 in 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, … Folge A019347 in 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, … Folge A019348 in 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, … Folge A019349 in 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, … Folge A019350 in 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, … Folge A019351 in 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, … Folge A019352 in 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, … Folge A019353 in 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, … Folge A019354 in 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, … Folge A019355 in 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, … Folge A019356 in OEIS

Eigenschaften Bearbeiten

  • Die folgenden vier Aussagen sind gleichbedeutend:
(Dieser Satz ist eine Verallgemeinerung eines weiter oben stehenden Satzes im Dezimalsystem.)
  • Sei eine lange Primzahl zur Basis , welche an der Einerstelle eine hat ( hat also die Form mit ). Dann gilt:
(Auch dieser Satz ist eine Verallgemeinerung eines weiter oben stehenden Satzes im Dezimalsystem.)
  • Jede lange Primzahl zur Basis endet mit oder .
  • Sei eine lange Primzahl zur Basis mit oder . Dann gilt:
(Dieser Satz ist eine Verallgemeinerung des direkt darüber stehenden Satzes.)

Ungelöste Probleme Bearbeiten

  • Es wird (ebenfalls von Artin) vermutet, dass es unendlich viele lange Primzahlen gibt, wenn die Basis keine Quadratzahl ist.
  • Sei die Basis keine Potenz einer ganzen Zahl (also mit ) und sei keine Basis, dessen quadratfreier Teil ist. Dann wird (ebenfalls von Artin) vermutet:

Verallgemeinerung Bearbeiten

Eine lange Primzahl n-ten Grades zur Basis b ist eine Primzahl mit folgender Eigenschaft:

Beispiele im Dezimalsystem Bearbeiten

  • Sei und die Basis . Dann gilt:
Alle 12 Perioden von (mit ) sind zyklische Verschiebungen der ersten beiden Perioden. Somit hat die Zahl genau verschiedene Zykel und ist somit eine lange Primzahl 2. Grades zur Basis .
  • Sei und die Basis . Dann gilt:
Alle 40 Perioden von (mit ) sind zyklische Verschiebungen von acht verschiedenen Perioden. Somit hat die Zahl genau verschiedene Zykel und ist somit eine lange Primzahl 8. Grades zur Basis .
  • Im Dezimalsystem sind die jeweils ersten langen Primzahlen n-ten Grades die folgenden (für ):
  • 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 . Das heißt, dass 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 ):
  • 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 . Das heißt, dass 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, … Folge A006883 in 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, … Folge A275081 in 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, … Folge A055628 in 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, … Folge A056157 in 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, … Folge A056210 in 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, … Folge A056211 in 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, … Folge A056212 in 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, … Folge A056213 in 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, … Folge A056214 in 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, … Folge A056215 in 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, … Folge A001122 in 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, … Folge A115591 in 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, … Folge A001133 in 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, … Folge A001134 in 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, … Folge A001135 in 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, … Folge A001136 in 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, … Folge A152307 in 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, … Folge A152308 in 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, … Folge A152309 in 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, … Folge A152310 in OEIS

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. ↑ 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. ↑ Eric W. Weisstein: Full Reptend Prime. In: MathWorld (englisch).
  4. ↑ Neil Sloane: Primes with primitive root 2 – Comments. OEIS, abgerufen am 12. Juli 2018.
Primzahl­mengen


formelbasiert

Carol ((2n − 1)2 − 2) | Doppelte Mersenne (22p − 1 − 1) | Fakultät (n! ± 1) | Fermat (22n + 1) | Kubisch (x3 − y3)/(x − y) | Kynea ((2n + 1)2 − 2) | Leyland (xy + yx) | Mersenne (2p − 1) | Mills (A3n) | Pierpont (2u⋅3v + 1) | Primorial (pn# ± 1) | Proth (k⋅2n + 1) | Pythagoreisch (4n + 1) | Quartisch (x4 + y4) | Thabit (3⋅2n − 1) | Wagstaff ((2p + 1)/3) | Williams ((b-1)⋅bn − 1) | Woodall (n⋅2n − 1)

Primzahlfolgen

Bell | Fibonacci | Lucas | Motzkin | Pell | Perrin

eigenschaftsbasiert

Elitär | Fortunate | Gut | Glücklich | Higgs | Hochkototient | Isoliert | Pillai | Ramanujan | Regulär | Stark | Stern | Wall–Sun–Sun | Wieferich | Wilson

basis­abhängig

Belphegor | Champernowne | Dihedral | Einzigartig | Fröhlich | Keith | Lange | Minimal | Mirp | Permutierbar | Primeval | Palindrom | Repunit-Primzahl ((10n − 1)/9) | Schwach | Smarandache–Wellin | Strobogrammatisch | Tetradisch | Trunkierbar | Zirkular

basierend auf Tupel

Ausbalanciert (p − n, p, p + n) | Chen | Cousin (p, p + 4) | Cunningham (p, 2p ± 1, …) | Drilling (p, p + 2 oder p + 4, p + 6) | Konstellation | Sexy (p, p + 6) | Sichere (p, (p − 1)/2) | Sophie Germain (p, 2p + 1) | Vierling (p, p + 2, p + 6, p + 8) | Zwilling (p, p + 2) | Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)

nach Größe

Titanisch (1.000+ Stellen) | Gigantisch (10.000+ Stellen) | Mega (1.000.000+ Stellen) | Beva (1.000.000.000+ Stellen)

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Zahlentheorie ist eine lange Primzahl zur Basis b eine Primzahl p P displaystyle p in mathbb P fur welche gilt b N displaystyle b in mathbb N ist eine naturliche Zahl sodass p displaystyle p kein Teiler von b displaystyle b ist x 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 erwahnt 2 Inhaltsverzeichnis 1 Herleitung der Definition anhand von Beispielen 1 1 Kurzfassung im Dezimalsystem 2 Beispiele 3 Eigenschaften 4 Ungeloste Probleme 4 1 Artins Vermutung 4 2 Beispiel 5 Lange Primzahlen im Dualsystem 5 1 Beispiele 5 2 Eigenschaften 5 3 Ungeloste Probleme 6 Lange Primzahlen zur Basis b 6 1 Beispiele 6 2 Eigenschaften 7 Ungeloste Probleme 8 Verallgemeinerung 8 1 Beispiele im Dezimalsystem 9 Weblinks 10 EinzelnachweiseHerleitung der Definition anhand von Beispielen BearbeitenWenn man die Basis b 10 displaystyle b 10 nbsp betrachtet also das Dezimalsystem so erwahnt man dieses ublicherweise nicht In diesem Abschnitt geht es um diese Basis b 10 displaystyle b 10 nbsp Eine Bruchzahl zum Beispiel n 1 2 displaystyle n frac 1 2 nbsp kann auch mit Komma geschrieben werden n 1 2 0 5 displaystyle n frac 1 2 0 5 nbsp Diese Dezimalzahlen horen wie im Fall n 1 2 0 5 displaystyle n frac 1 2 0 5 nbsp auf oder sind unendlich lang wie zum Beispiel bei n 1 3 0 333 333 displaystyle n frac 1 3 0 333333 ldots nbsp Diese unendliche Wiederholung derselben Ziffern nennt man Periode und schreibt n 1 3 0 3 displaystyle n frac 1 3 0 overline 3 nbsp Die Periode kann auch langer sein wie zum Beispiel bei n 1 13 0 076 923076923 0 076923 displaystyle n frac 1 13 0 076923076923 ldots 0 overline 076923 nbsp Meistens verandern sich die Ziffern der Periode wenn man die Zahl multipliziert zum Beispiel ist 2 1 13 0 153 846153846 0 153846 displaystyle 2 cdot frac 1 13 0 153846153846 ldots 0 overline 153846 nbsp Es gibt aber periodische Bruchzahlen deren Ziffern sich nach einer Multiplikation nicht andern wie zum Beispiel bei n 1 7 0 142 85714285 0 142857 displaystyle n frac 1 7 0 14285714285 ldots 0 overline 142857 nbsp Um diese sechs Nachkommastellen zu einer ganzen Zahl zu machen multipliziert man sie mit 10 Periodenlange displaystyle 10 text Periodenlange nbsp also mit 10 6 displaystyle 10 6 nbsp und erhalt die Zahl 142857 142857 displaystyle 142857 overline 142857 nbsp Subtrahiert man nun noch 1 7 0 142857 displaystyle frac 1 7 0 overline 142857 nbsp so erhalt man die ganze Zahl x 142857 displaystyle x 142857 nbsp Wenn man diese Zahl mit k 1 2 3 n 1 displaystyle k 1 2 3 ldots n 1 nbsp multipliziert so erhalt man 1 142857 displaystyle 1 cdot 142857 nbsp 142857 displaystyle mathtt 142857 nbsp 2 142857 displaystyle 2 cdot 142857 nbsp 285714 displaystyle mathtt 285714 nbsp 3 142857 displaystyle 3 cdot 142857 nbsp 428571 displaystyle mathtt 428571 nbsp 4 142857 displaystyle 4 cdot 142857 nbsp 571428 displaystyle mathtt 571428 nbsp 5 142857 displaystyle 5 cdot 142857 nbsp 714285 displaystyle mathtt 714285 nbsp 6 142857 displaystyle 6 cdot 142857 nbsp 857142 displaystyle mathtt 857142 nbsp Jedes Mal erhalt man die gleichen Ziffern in der gleichen Reihenfolge nur zyklisch vertauscht Eine solche Zahl wie x displaystyle x nbsp gilt im Dezimalsystem als zyklische Zahl Vor allem aber war bei der Bruchzahl n 1 7 1 p displaystyle n tfrac 1 7 tfrac 1 p nbsp die Periodenlange p 1 6 displaystyle p 1 6 nbsp also maximal lang wenn man bedenkt dass bei Division durch p 7 displaystyle p 7 nbsp hochstens p 1 6 displaystyle p 1 6 nbsp verschiedene Reste ungleich Null entstehen konnen namlich 1 2 6 displaystyle 1 2 ldots 6 nbsp Kame bei der Division Null Rest heraus wurde die Dezimalzahl und somit auch die Periode enden und ware somit auch keine Periode weil sie eben endet Insofern macht der Begriff lange Primzahl p displaystyle p nbsp also Sinn weil beim Bruch 1 p displaystyle tfrac 1 p nbsp die Periodenlange p 1 displaystyle p 1 nbsp betragt und somit maximal lang ist Bei zusammengesetzten Zahlen p displaystyle p nbsp ist die Periodenlange niemals p 1 displaystyle p 1 nbsp deswegen kann man sich auf Primzahlen beschranken Kurzfassung im Dezimalsystem Bearbeiten Im Dezimalsystem hat man die Basis b 10 displaystyle b 10 nbsp Man nehme eine Primzahl p displaystyle p nbsp welche kein Teiler der Basis b 10 displaystyle b 10 nbsp ist also p 2 displaystyle p not 2 nbsp und p 5 displaystyle p not 5 nbsp und bilde den Bruch 1 p displaystyle frac 1 p nbsp Dieser Bruch sollte die Periodenlange p 1 displaystyle p 1 nbsp haben Nun multipliziert man diesen Bruch mit b Periodenlange 10 p 1 displaystyle b text Periodenlange 10 p 1 nbsp und subtrahiert die ursprungliche Bruchzahl damit die Periode hinter dem Komma wegfallt Man erhalt die der Zahl p entsprechende Zahl x 10 p 1 1 p 1 p 10 p 1 1 p displaystyle x 10 p 1 cdot frac 1 p frac 1 p frac 10 p 1 1 p nbsp Ist x displaystyle x nbsp eine zyklische Zahl so ist p displaystyle p nbsp eine lange Primzahl Beispiele BearbeitenFur die Primzahl p 7 displaystyle p 7 nbsp gilt im Dezimalsystem mit Basis b 10 displaystyle b 10 nbsp p 7 displaystyle p 7 nbsp ist kein Teiler der Basis b 10 displaystyle b 10 nbsp und es ist b p 1 1 p 10 7 1 1 7 999999 7 142857 displaystyle frac b p 1 1 p frac 10 7 1 1 7 frac 999999 7 142857 nbsp 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 p 59 displaystyle p 59 nbsp sind die folgenden 142857 5882352941176470 526315789473684210 4347826086956521739130 3448275862068965517241379310 2127659574468085106382978723404255319148936170 1694915254237288135593220338983050847457627118644067796610 Folge A004042 in OEIS Die Anzahl der langen Primzahlen im Dezimalsystem kleiner als 10 n displaystyle 10 n nbsp fur n 1 2 displaystyle n 1 2 ldots nbsp 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 248881 displaystyle 248881 nbsp entnehmen Das heisst dass unter 10 7 10 000 000 displaystyle 10 7 10 000 000 nbsp genau 248881 displaystyle 248881 nbsp lange Primzahlen existieren Eigenschaften BearbeitenDie folgenden vier Aussagen sind gleichbedeutend Die Zahl p P displaystyle p in mathbb P nbsp ist eine lange Primzahl im Dezimalsystem Die der Zahl p displaystyle p nbsp entsprechende zyklische Zahl x 10 p 1 1 p displaystyle x frac 10 p 1 1 p nbsp hat genau p 1 displaystyle p 1 nbsp Stellen Fur jede Restklasse n 1 2 p 1 displaystyle n 1 2 ldots p 1 nbsp gibt es ein i displaystyle i nbsp sodass 10 i n mod p displaystyle 10 i equiv n pmod p nbsp ist 10 displaystyle 10 nbsp ist eine Primitivwurzel modulo p displaystyle p nbsp Sei p P displaystyle p in mathbb P nbsp eine lange Primzahl im Dezimalsystem welche an der Einerstelle eine 1 displaystyle 1 nbsp hat p displaystyle p nbsp hat also die Form p 10 k 1 displaystyle p 10k 1 nbsp mit k N displaystyle k in mathbb N nbsp Dann gilt 1 Jede Ziffer 0 1 2 9 displaystyle 0 1 2 ldots 9 nbsp taucht in der Periode von 1 p displaystyle frac 1 p nbsp gleich oft auf Die Periodenlange von 1 p displaystyle frac 1 p nbsp ist durch 10 displaystyle 10 nbsp ganzzahlig teilbar Beispiel 1 Fur die lange Primzahl p 2741 displaystyle p 2741 nbsp gilt Die Periodenlange der Zahl 1 p 1 2741 displaystyle frac 1 p frac 1 2741 nbsp betragt p 1 2740 displaystyle p 1 2740 nbsp In dieser Periode ist die Ziffer 0 displaystyle 0 nbsp genau 274 displaystyle 274 nbsp Mal enthalten ebenso die Ziffern 1 2 3 9 displaystyle 1 2 3 ldots 9 nbsp Beispiel 2 Die kleinsten langen Primzahlen mit 1 displaystyle 1 nbsp 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 konnen folgende Primzahlen niemals lange Primzahlen sein p 40 k n displaystyle p 40k n nbsp mit n 1 3 9 13 27 31 37 39 displaystyle n in 1 3 9 13 27 31 37 39 nbsp Studien haben ergeben dass im Dezimalsystem etwa zwei Drittel der Primzahlen mit folgender Form lange Primzahlen sind p 40 k n displaystyle p 40k n nbsp mit n 7 11 17 19 21 23 29 33 displaystyle n in 7 11 17 19 21 23 29 33 nbsp 285 displaystyle 285 nbsp der 295 displaystyle 295 nbsp Primzahlen der Form p 120 k 23 displaystyle p 120k 23 nbsp mit p lt 100000 displaystyle p lt 100000 nbsp sind lange Primzahlen Die erste Primzahl dieser Form die keine lange Primzahl ist ist p 20903 displaystyle p 20903 nbsp Eine notwendige aber nicht hinreichende Bedingung dass p displaystyle p nbsp eine lange Primzahl im Dezimalsystem ist gibt die folgende Eigenschaft an 3 Die Zahl 10 p 1 1 9 R p 1 displaystyle 10 p 1 1 9 cdot R p 1 nbsp ist durch p displaystyle p nbsp teilbar dabei ist R p displaystyle R p nbsp eine Repunit also eine Zahl die ausschliesslich aus Einsen besteht und genau p displaystyle p nbsp Stellen hat Beispiel Die folgenden n displaystyle n nbsp sind Teiler von 10 n 1 1 displaystyle 10 n 1 1 nbsp 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 heisst dass alle langen Primzahlen in dieser Liste enthalten sein mussen aber nicht alle in dieser Liste sind lange Primzahlen Ungeloste Probleme BearbeitenArtins Vermutung Bearbeiten Es wird vermutet dass genau 37 395 58136 displaystyle 37 39558136 ldots nbsp Folge A005596 in OEIS aller Primzahlen im Dezimalsystem lange Primzahlen sind 3 Die Zahl C A r t i n p P 1 1 p p 1 0 3739558136 displaystyle C mathrm Artin prod p in mathbb P left 1 frac 1 p p 1 right 0 3739558136 ldots nbsp nennt sich Artins Konstante und bezieht sich eigentlich auf den Anteil der Primzahlen fur welche 10 displaystyle 10 nbsp eine Primitivwurzel modulo p displaystyle p nbsp ist Die Vermutung nennt sich Artins Vermutung und wurde von Emil Artin 1927 erstmals erwahnt Beispiel Bearbeiten Die folgenden beiden Listen geben gemeinsam betrachtet an wie viel Prozent aller Primzahlen unter 10 n displaystyle 10 n nbsp lange Primzahlen sind Zunachst der Zahler 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 467 displaystyle 467 nbsp und 1229 displaystyle 1229 nbsp entnehmen Das bedeutet dass 467 1229 37 998 displaystyle frac 467 1229 approx 37 998 nbsp aller Primzahlen bis 10 4 displaystyle 10 4 nbsp lange Primzahlen sind was sehr nah an Artins Konstante herankommt Unter 10 10 displaystyle 10 10 nbsp sind es schon 170169241 455052511 37 374 displaystyle frac 170169241 455052511 approx 37 374 nbsp aller Primzahlen womit man noch naher an Artins Konstante herangeruckt ist Lange Primzahlen im Dualsystem BearbeitenBeispiele Bearbeiten Fur b 2 displaystyle b 2 nbsp und p 11 1011 2 displaystyle p 11 1011 2 nbsp ist die Zahl x b p 1 1 p 2 10 1 11 1023 11 93 0001011101 2 displaystyle x frac b p 1 1 p frac 2 10 1 11 frac 1023 11 93 0001011101 2 nbsp eine zyklische Zahl Denn es ist 1 93 0001 2 0001011101 2 0001011101 2 2 93 0010 2 0001011101 2 0010111010 2 3 93 0011 2 0001011101 2 0100010111 2 4 93 0100 2 0001011101 2 0101110100 2 5 93 0101 2 0001011101 2 0111010001 2 6 93 0110 2 0001011101 2 1000101110 2 7 93 0111 2 0001011101 2 1010001011 2 8 93 1000 2 0001011101 2 1011101000 2 9 93 1001 2 0001011101 2 1101000101 2 10 93 1010 2 0001011101 2 1110100010 2 displaystyle begin array rrrrr 1 cdot 93 amp amp 0001 2 cdot 0001011101 2 amp amp mathtt 0001011101 2 2 cdot 93 amp amp 0010 2 cdot 0001011101 2 amp amp mathtt 0010111010 2 3 cdot 93 amp amp 0011 2 cdot 0001011101 2 amp amp mathtt 0100010111 2 4 cdot 93 amp amp 0100 2 cdot 0001011101 2 amp amp mathtt 0101110100 2 5 cdot 93 amp amp 0101 2 cdot 0001011101 2 amp amp mathtt 0111010001 2 6 cdot 93 amp amp 0110 2 cdot 0001011101 2 amp amp mathtt 1000101110 2 7 cdot 93 amp amp 0111 2 cdot 0001011101 2 amp amp mathtt 1010001011 2 8 cdot 93 amp amp 1000 2 cdot 0001011101 2 amp amp mathtt 1011101000 2 9 cdot 93 amp amp 1001 2 cdot 0001011101 2 amp amp mathtt 1101000101 2 10 cdot 93 amp amp 1010 2 cdot 0001011101 2 amp amp mathtt 1110100010 2 end array nbsp dd Die 10 stellige binare Ziffernfolge von x displaystyle x nbsp wird bei der Multiplikation mit k 2 3 10 displaystyle k 2 3 ldots 10 nbsp jedes Mal zyklisch rotiert also ist x 93 displaystyle x 93 nbsp im Dualsystem eine zyklische Zahl Somit ist p 11 displaystyle p 11 nbsp im Dualsystem eine lange Primzahl im Dezimalsystem ubrigens 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 dd Eigenschaften Bearbeiten Sei p displaystyle p nbsp eine lange Primzahl im Dualsystem also mit Basis n 2 displaystyle n 2 nbsp Dann gilt Fur jede Restklasse n 1 2 p 1 displaystyle n 1 2 ldots p 1 nbsp gibt es ein i displaystyle i nbsp sodass 2 i n mod p displaystyle 2 i equiv n pmod p nbsp ist 2 displaystyle 2 nbsp ist eine Primitivwurzel modulo p displaystyle p nbsp Dieser Satz ist ein Spezialfall eines schon weiter oben erwahnten Satzes Im Dualsystem konnen folgende Primzahlen niemals lange Primzahlen sein p 8 k n displaystyle p 8k n nbsp mit n 1 7 displaystyle n in 1 7 nbsp Beweis Fur diese p displaystyle p nbsp ist 2 displaystyle 2 nbsp ein quadratischer Rest modulo p displaystyle p nbsp daher muss p displaystyle p nbsp ein Teiler von 2 p 1 2 1 displaystyle 2 frac p 1 2 1 nbsp sein Die Periodenlange von 1 p displaystyle frac 1 p nbsp im Dualsystem muss also p 1 2 displaystyle frac p 1 2 nbsp teilen und kann somit nicht p 1 displaystyle p 1 nbsp sein Somit kann p displaystyle p nbsp auch keine lange Primzahl im Dualsystem sein displaystyle Box nbsp dd dd Sei p displaystyle p nbsp eine lange Primzahl im Dualsystem Dann gilt p displaystyle p nbsp hat die Form p 8 k 3 displaystyle p 8k 3 nbsp oder p 8 k 5 displaystyle p 8k 5 nbsp mit k N displaystyle k in mathbb N nbsp dd Alle sicheren Primzahlen p displaystyle p nbsp mit p 3 mod 8 displaystyle p equiv 3 pmod 8 nbsp inklusive p 3 displaystyle p 3 nbsp sind lange Primzahlen im Dualsystem Die kleinsten sicheren Primzahlen p lt 2000 displaystyle p lt 2000 nbsp mit dieser Eigenschaft sind die folgenden 3 11 59 83 107 179 227 347 467 563 587 1019 1187 1283 1307 1523 1619 1907 dd dd Studien haben ergeben dass im Dualsystem etwa drei Viertel der Primzahlen mit folgender Form lange Primzahlen sind p 8 k n displaystyle p 8k n nbsp mit n 3 5 displaystyle n in 3 5 nbsp Beispiel Es gibt 87 displaystyle 87 nbsp Primzahlen p lt 1000 displaystyle p lt 1000 nbsp welche die Kongruenz p 3 mod 8 displaystyle p equiv 3 pmod 8 nbsp oder p 5 mod 8 displaystyle p equiv 5 pmod 8 nbsp erfullen 67 displaystyle 67 nbsp von ihnen sind lange Primzahlen zur Basis b 2 displaystyle b 2 nbsp Das sind etwa 77 displaystyle 77 nbsp dd dd 1078 displaystyle 1078 nbsp der 1206 displaystyle 1206 nbsp Primzahlen der Form p 24 k 5 displaystyle p 24k 5 nbsp mit p lt 100000 displaystyle p lt 100000 nbsp sind lange Primzahlen im Dualsystem Die erste Primzahl dieser Form die keine lange Primzahl ist ist p 1013 displaystyle p 1013 nbsp Ungeloste Probleme Bearbeiten 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 Lange Primzahlen zur Basis b BearbeitenBeispiele Bearbeiten Die kleinsten langen Primzahlen zur Basis b displaystyle b nbsp fur b 1 2 displaystyle b 1 2 ldots nbsp 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 11 displaystyle 11 nbsp Das heisst dass p 11 displaystyle p 11 nbsp die kleinste lange Primzahl zur Basis b 6 displaystyle b 6 nbsp ist dd Beispiel 2 In obiger Liste steht an der 4 Stelle die Zahl 0 displaystyle 0 nbsp Das heisst dass es keine Primzahl p displaystyle p nbsp gibt die eine lange Primzahl zur Basis b 4 displaystyle b 4 nbsp ist dd dd Es folgt eine Auflistung der kleinsten langen Primzahlen zu verschiedensten Basen b displaystyle b nbsp lange Primzahlen bis zur Basis b 30 Basis b lange Primzahlen zur Basis b displaystyle b nbsp OEIS Folge2 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 Folge A001122 in OEIS3 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 Folge A019334 in OEIS4 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 Folge A019335 in OEIS6 11 13 17 41 59 61 79 83 89 103 107 109 113 127 131 137 151 157 179 199 223 227 229 233 Folge A019336 in OEIS7 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 Folge A019337 in OEIS8 3 5 11 29 53 59 83 101 107 131 149 173 179 197 227 269 293 317 347 389 419 443 461 467 Folge A019338 in OEIS9 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 Folge A001913 in OEIS11 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 Folge A019339 in OEIS12 5 7 17 31 41 43 53 67 101 103 113 127 137 139 149 151 163 173 197 223 257 269 281 283 Folge A019340 in OEIS13 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 Folge A019341 in OEIS14 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 Folge A019342 in OEIS15 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 Folge A019343 in OEIS16 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 Folge A019344 in OEIS18 5 11 29 37 43 53 59 61 67 83 101 107 109 139 149 157 163 173 179 181 197 227 251 269 Folge A019345 in OEIS19 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 Folge A019346 in OEIS20 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 Folge A019347 in OEIS21 2 19 23 29 31 53 71 97 103 107 113 137 139 149 157 179 181 191 197 223 233 239 263 271 Folge A019348 in OEIS22 5 17 19 31 37 41 47 53 71 83 107 131 139 191 193 199 211 223 227 233 269 281 283 307 Folge A019349 in OEIS23 2 3 5 17 47 59 89 97 113 127 131 137 149 167 179 181 223 229 281 293 307 311 337 347 Folge A019350 in OEIS24 7 11 13 17 31 37 41 59 83 89 107 109 113 137 157 179 181 223 227 229 233 251 257 277 Folge A019351 in OEIS25 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 Folge A019352 in OEIS27 2 5 17 29 53 89 101 113 137 149 173 197 233 257 269 281 293 317 353 389 401 449 461 509 Folge A019353 in OEIS28 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 Folge A019354 in OEIS29 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 Folge A019355 in OEIS30 11 23 41 43 47 59 61 79 89 109 131 151 167 173 179 193 197 199 251 263 281 293 307 317 Folge A019356 in OEIS Eigenschaften Bearbeiten Die folgenden vier Aussagen sind gleichbedeutend Die Zahl p P displaystyle p in mathbb P nbsp ist eine lange Primzahl zur Basis b N displaystyle b in mathbb N nbsp Die der Zahl p displaystyle p nbsp entsprechende zyklische Zahl x b p 1 1 p displaystyle x frac b p 1 1 p nbsp hat genau p 1 displaystyle p 1 nbsp Stellen Fur jede Restklasse n 1 2 p 1 displaystyle n 1 2 ldots p 1 nbsp gibt es ein i displaystyle i nbsp sodass b i n mod p displaystyle b i equiv n pmod p nbsp ist b displaystyle b nbsp ist eine Primitivwurzel modulo p displaystyle p nbsp dd Dieser Satz ist eine Verallgemeinerung eines weiter oben stehenden Satzes im Dezimalsystem Sei p P displaystyle p in mathbb P nbsp eine lange Primzahl zur Basis b displaystyle b nbsp welche an der Einerstelle eine 1 displaystyle 1 nbsp hat p displaystyle p nbsp hat also die Form p b k 1 displaystyle p b cdot k 1 nbsp mit k N displaystyle k in mathbb N nbsp Dann gilt Jede Ziffer 0 1 2 b 1 displaystyle 0 1 2 ldots b 1 nbsp taucht in der Periode von 1 p displaystyle frac 1 p nbsp gleich oft auf Die Periodenlange von 1 p displaystyle frac 1 p nbsp ist durch b displaystyle b nbsp ganzzahlig teilbar dd Auch dieser Satz ist eine Verallgemeinerung eines weiter oben stehenden Satzes im Dezimalsystem Jede lange Primzahl p P displaystyle p in mathbb P nbsp zur Basis b 12 displaystyle b 12 nbsp endet mit 5 displaystyle 5 nbsp oder 7 displaystyle 7 nbsp Es gibt also keine langen Primzahlen zur Basis b 12 displaystyle b 12 nbsp welche an der Einerstelle eine 1 displaystyle 1 nbsp haben dd Sei p P displaystyle p in mathbb P nbsp eine lange Primzahl zur Basis b displaystyle b nbsp mit b 0 mod 4 displaystyle b equiv 0 pmod 4 nbsp oder b 1 mod 4 displaystyle b equiv 1 pmod 4 nbsp Dann gilt Es gibt keine langen Primzahlen zur Basis b displaystyle b nbsp welche an der Einerstelle eine 1 displaystyle 1 nbsp haben dd Dieser Satz ist eine Verallgemeinerung des direkt daruber stehenden Satzes Ungeloste Probleme BearbeitenEs wird ebenfalls von Artin vermutet dass es unendlich viele lange Primzahlen gibt wenn die Basis b displaystyle b nbsp keine Quadratzahl ist Sei die Basis b displaystyle b nbsp keine Potenz einer ganzen Zahl also b x y displaystyle b not x y nbsp mit x y N displaystyle x y in mathbb N nbsp und sei b displaystyle b nbsp keine Basis dessen quadratfreier Teil 1 mod 4 displaystyle equiv 1 pmod 4 nbsp ist Dann wird ebenfalls von Artin vermutet 37 395 58136 displaystyle 37 39558136 ldots nbsp aller Primzahlen zur Basis b displaystyle b nbsp sind lange Primzahlen Beispiel Folgende Zahlen sind keine Potenz einer ganzen Zahl und haben keinen quadratfreien Teil welcher 1 mod 4 displaystyle equiv 1 pmod 4 nbsp 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 dd dd dd Verallgemeinerung BearbeitenEine lange Primzahl n ten Grades zur Basis b ist eine Primzahl p P displaystyle p in mathbb P nbsp mit folgender Eigenschaft Sei k N displaystyle k in mathbb N nbsp mit 1 k p 1 displaystyle 1 leq k leq p 1 nbsp Dann gilt k p displaystyle frac k p nbsp hat n displaystyle n nbsp verschiedene Zykel in der dazugehorigen Dezimalbruchentwicklung dd Beispiele im Dezimalsystem Bearbeiten Sei p 13 displaystyle p 13 nbsp und die Basis b 10 displaystyle b 10 nbsp Dann gilt 1 13 0 076923 2 13 0 153846 3 13 0 230769 5 13 0 384615 4 13 0 307692 6 13 0 461538 9 13 0 692307 7 13 0 538461 10 13 0 769230 8 13 0 615384 12 13 0 923076 11 13 0 846153 displaystyle begin array cccccccc 1 13 0 overline 076923 amp 2 13 0 overline 153846 3 13 0 overline 230769 amp 5 13 0 overline 384615 4 13 0 overline 307692 amp 6 13 0 overline 461538 9 13 0 overline 692307 amp 7 13 0 overline 538461 10 13 0 overline 769230 amp 8 13 0 overline 615384 12 13 0 overline 923076 amp 11 13 0 overline 846153 end array nbsp dd dd Alle 12 Perioden von k 13 displaystyle frac k 13 nbsp mit k 1 2 12 displaystyle k 1 2 ldots 12 nbsp sind zyklische Verschiebungen der ersten beiden Perioden Somit hat die Zahl p 13 displaystyle p 13 nbsp genau 2 displaystyle 2 nbsp verschiedene Zykel und p 13 displaystyle p 13 nbsp ist somit eine lange Primzahl 2 Grades zur Basis b 10 displaystyle b 10 nbsp Sei p 41 displaystyle p 41 nbsp und die Basis b 10 displaystyle b 10 nbsp Dann gilt 1 41 0 02439 2 41 0 04878 3 41 0 07317 4 41 0 09756 5 41 0 12195 6 41 0 14634 11 41 0 26829 15 41 0 36585 10 41 0 24390 20 41 0 48780 7 41 0 17073 23 41 0 56097 8 41 0 19512 14 41 0 34146 12 41 0 29268 22 41 0 53658 16 41 0 39024 32 41 0 78048 13 41 0 31707 25 41 0 60975 9 41 0 21951 17 41 0 41463 28 41 0 68292 24 41 0 58536 18 41 0 43902 33 41 0 80487 29 41 0 70731 31 41 0 75609 21 41 0 51219 19 41 0 46341 34 41 0 82926 27 41 0 65853 37 41 0 90243 36 41 0 87804 30 41 0 73170 40 41 0 97560 39 41 0 95121 26 41 0 63414 38 41 0 92682 35 41 0 85365 displaystyle begin array cccccccc 1 41 0 overline 02439 amp 2 41 0 overline 04878 amp 3 41 0 overline 07317 amp 4 41 0 overline 09756 amp 5 41 0 overline 12195 amp 6 41 0 overline 14634 amp 11 41 0 overline 26829 amp 15 41 0 overline 36585 10 41 0 overline 24390 amp 20 41 0 overline 48780 amp 7 41 0 overline 17073 amp 23 41 0 overline 56097 amp 8 41 0 overline 19512 amp 14 41 0 overline 34146 amp 12 41 0 overline 29268 amp 22 41 0 overline 53658 16 41 0 overline 39024 amp 32 41 0 overline 78048 amp 13 41 0 overline 31707 amp 25 41 0 overline 60975 amp 9 41 0 overline 21951 amp 17 41 0 overline 41463 amp 28 41 0 overline 68292 amp 24 41 0 overline 58536 18 41 0 overline 43902 amp 33 41 0 overline 80487 amp 29 41 0 overline 70731 amp 31 41 0 overline 75609 amp 21 41 0 overline 51219 amp 19 41 0 overline 46341 amp 34 41 0 overline 82926 amp 27 41 0 overline 65853 37 41 0 overline 90243 amp 36 41 0 overline 87804 amp 30 41 0 overline 73170 amp 40 41 0 overline 97560 amp 39 41 0 overline 95121 amp 26 41 0 overline 63414 amp 38 41 0 overline 92682 amp 35 41 0 overline 85365 end array nbsp dd dd Alle 40 Perioden von k 41 displaystyle frac k 41 nbsp mit k 1 2 40 displaystyle k 1 2 ldots 40 nbsp sind zyklische Verschiebungen von acht verschiedenen Perioden Somit hat die Zahl p 41 displaystyle p 41 nbsp genau 8 displaystyle 8 nbsp verschiedene Zykel und p 41 displaystyle p 41 nbsp ist somit eine lange Primzahl 8 Grades zur Basis b 10 displaystyle b 10 nbsp Im Dezimalsystem sind die jeweils ersten langen Primzahlen n ten Grades die folgenden fur n 1 2 displaystyle n 1 2 ldots nbsp 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 41 displaystyle 41 nbsp Das heisst dass p 41 displaystyle p 41 nbsp die kleinste lange Primzahl 8 Grades im Dezimalsystem ist Direkt daruber wurde diese Primzahl als Beispiel verwendet Im Dualsystem sind die jeweils ersten langen Primzahlen n ten Grades die folgenden fur n 1 2 displaystyle n 1 2 ldots nbsp 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 7 displaystyle 7 nbsp Das heisst dass p 7 displaystyle p 7 nbsp 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 Folge1 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 Folge A006883 in OEIS2 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 Folge A275081 in OEIS3 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 Folge A055628 in OEIS4 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 Folge A056157 in OEIS5 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 Folge A056210 in OEIS6 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 Folge A056211 in OEIS7 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 Folge A056212 in OEIS8 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 Folge A056213 in OEIS9 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 Folge A056214 in OEIS10 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 Folge A056215 in OEISEs folgt eine Liste von langen Primzahlen n ten Grades im Dualsystem n lange Primzahlen n ten Grades im Dualsystem OEIS Folge1 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 Folge A001122 in OEIS2 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 Folge A115591 in OEIS3 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 Folge A001133 in OEIS4 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 Folge A001134 in OEIS5 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 Folge A001135 in OEIS6 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 Folge A001136 in OEIS7 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 Folge A152307 in OEIS8 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 Folge A152308 in OEIS9 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 Folge A152309 in OEIS10 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 Folge A152310 in OEISWeblinks BearbeitenEric W Weisstein Full Reptend Prime In MathWorld englisch Eric W Weisstein Artins Constant In MathWorld englisch Full Reptend Prime In PlanetMath englisch Einzelnachweise Bearbeiten 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 John H Conway Richard K Guy The Book of Numbers Springer Verlag 1996 S 157 163 166 171 abgerufen am 11 Juli 2018 englisch a b Eric W Weisstein Full Reptend Prime In MathWorld englisch a b Neil Sloane Primes with primitive root 2 Comments OEIS abgerufen am 12 Juli 2018 V DPrimzahl mengenformelbasiert Carol 2n 1 2 2 Doppelte Mersenne 22p 1 1 Fakultat n 1 Fermat 22n 1 Kubisch x3 y3 x y Kynea 2n 1 2 2 Leyland xy yx Mersenne 2p 1 Mills A3n Pierpont 2u 3v 1 Primorial pn 1 Proth k 2n 1 Pythagoreisch 4n 1 Quartisch x4 y4 Thabit 3 2n 1 Wagstaff 2p 1 3 Williams b 1 bn 1 Woodall n 2n 1 Primzahlfolgen Bell Fibonacci Lucas Motzkin Pell Perrineigenschaftsbasiert Elitar Fortunate Gut Glucklich Higgs Hochkototient Isoliert Pillai Ramanujan Regular Stark Stern Wall Sun Sun Wieferich Wilsonbasis abhangig Belphegor Champernowne Dihedral Einzigartig Frohlich Keith Lange Minimal Mirp Permutierbar Primeval Palindrom Repunit Primzahl 10n 1 9 Schwach Smarandache Wellin Strobogrammatisch Tetradisch Trunkierbar Zirkularbasierend auf Tupel Ausbalanciert p n p p n Chen Cousin p p 4 Cunningham p 2p 1 Drilling p p 2 oder p 4 p 6 Konstellation Sexy p p 6 Sichere p p 1 2 Sophie Germain p 2p 1 Vierling p p 2 p 6 p 8 Zwilling p p 2 Zwillings Bi Kette n 1 2n 1 nach Grosse Titanisch 1 000 Stellen Gigantisch 10 000 Stellen Mega 1 000 000 Stellen Beva 1 000 000 000 Stellen Abgerufen von https de wikipedia org w index php title Lange Primzahl amp oldid 222689476