Zum Inhalt springen

Pseudoprimzahlen: Meta: Überblick

Aus Wikibooks


Vorwort

Was soll das Buch bezwecken?

[Bearbeiten]

Das Buch soll das zeigen, was jenseits der Primzahlen kommt. Die faszinierende Welt der Pseudoprimzahlen.

Warum dieses Buch?

[Bearbeiten]

In der deutschen Wikipedia sind einige interessante Artikel über den Bereich Pseudoprimzahlen, Primzahlen und Randbereiche entstanden. So die Artikel Carmichael-Zahl, Eulersche Pseudoprimzahl, Starke Pseudoprimzahl, Lucas-Folge u.s.w. . Nun ist die Wikipedia ja eine Enzyklopädie und kein Lehrbuch, was bedeutet, dass man weder in die Tiefe gehen kann, noch Zusammenhänge so vernetzen kann, wie man das gerne möchte.

Für wen ist dieses Buch gedacht?

[Bearbeiten]

Dieses Buch ist für jene gedacht, die gerne tüfteln. Der Stoff ist vielleicht nicht einfach zugänglich, aber wer eine gewisse Hürde übersprungen hat, für den eröffnen sich Welten (auch in Bezug auf die Primzahlen). Was dieses Buch nicht ist, ist ein Lehrbuch, das den Leser von Punkt zu Punkt führt. Der Leser muß sich seine Ziele selber suchen. Wer sich nicht schon für die natürlichen Zahlen, und insbesondere für Primzahlen interessiert, der wird mit diesem Lehrbuch wenig Freude haben.

Ein rechenintensives Thema

[Bearbeiten]

Da bei den Pseudoprimzahlen, insbesondere denen, die unter das Schema fermatsche Pseudoprimzahlen fallen, oft große Potenzen auftauchen, kommt man, wenn man das in diesem Buch geschriebene nachvollziehen möchte, nicht darum herum, selbst Programme zu schreiben. Manches läßt sich auch "zu Fuß" oder mit dem Taschenrechner nachrechnen, aber ohne Computer kommt man letztlich nicht aus. In dem Buch ist auch ein Kapitel mit fertigen Quellcodes, aber man läßt sich möglicherweise etwas entgehen, wenn man sich nicht selbst Gedanken macht, und die Programme selbst schreibt. Aber das muss der Leser letztendlich selber wissen.

Unterscheidung

[Bearbeiten]

Wenn in dem Text über eine Zahl gesagt wird, sie sei eine Pseudoprimzahl, dann bedeutet das, dass diese Zahl zusammengesetzt ist, und sich nach irgendeinem Kriterium wie eine Primzahl verhält. Genauso bedeutet ein eine Zahl ist eine starke Pseudoprimzahl, dass eine Basis existiert, zu der sich diese zusammengesetzte Zahl, aufgrund des Kriteriums für starke Pseudoprimzahlen, wie eine Primzahl verhält.

Ist dagegen von einer fpsp(a) die Rede, also einer fermatschen Pseudoprimzahl zu einer bestimmten Basis , dann ist klar, dass man sich genau auf diese Basis bezieht (abgesehen davon, dass diese fermatsche Pseudoprimzahl noch zu anderen Basen pseudoprim ist).


Definition

[Bearbeiten]

Eine Pseudoprimzahl ist eine zusammengesetzte natürliche Zahl, die bestimmte Eigenschaften mit Primzahlen gemeinsam hat. Sie wird Pseudoprimzahl bezüglich dieser Eigenschaft genannt. Da es viele solche Eigenschaften gibt, ist der Begriff Pseudoprimzahl ohne Angabe der Eigenschaft nicht sinnvoll.

Hintergrund

[Bearbeiten]

Die Beschäftigung mit Pseudoprimzahlen ist aus dem Bedürfnis entstanden, schnelle Primzahltests für große Zahlen zu finden.

Primzahlen sind natürliche Zahlen größer 1, die nur durch 1 und durch sich selbst teilbar sind. So sind sie definiert.

Allerdings lassen sich damit größere Zahlen schlecht darauf prüfen, ob sie Primzahlen sind. Wie unpraktisch diese Eigenschaft für den Primzahlentest ist, lässt sich daran ermessen, dass um eine Zahl der Größenordnung auf ihre Primalität zu testen, ihre Teilbarkeit durch Zahlen getestet werden müsste.

Aber Primzahlen haben noch viele andere Eigenschaften, Eigenschaften der Form: "Wenn eine Primzahl ist, dann hat die Eigenschaft ".

Um aus dem Buch Prime Numbers - A Computational Perspective 1 zu zitieren: "Wenn eine Primzahl ist, dann ist gleich 2, oder ist eine ungerade Zahl". In dieser Richtung funktioniert die Aussage. Allerdings lässt sie sich nicht umkehren: "Wenn gleich 2 oder eine ungerade Zahl ist, dann ist eine Primzahl" ist ausgemachter Blödsinn. Es gibt weitere solcher "Wenn eine Primzahl ist, dann hat die Eigenschaft ", die sinnvoller sind, deren Umkehrung aber ebenfalls falsche Schlüsse wären:

Wenneine Primzahl und größer als 3 ist,
  • dann hatdie Form oder (das gilt für alle ungeraden Zahlen)
  • dann hatdie Form oder (ungerade und nicht durch 3 teilbar)
  • dann teiltjede Zahl der Form mit
  • dann teiltden Ausdruck , wobei das p.te Glied der Lucas-Folge ist.
  • dann teiltdas p.te Glied der Perrin-Folge

Vermeintliche Primzahlen, die man aus der Umkehrung solcher "Wenn eine Primzahl ist, dann hat die Eigenschaft "-Regeln bekommt, nennt man Pseudoprimzahlen. Das allerdings mit einer gewissen Einschränkung:

Zusammengesetze Zahlen werden nicht als Pseudoprimzahlen bezeichnet, nur weil sie den Formen , , bzw. entsprechen. Dazu sind schon striktere Eigenschaften wie beispielsweise teilt oder teilt oder teilt nötig.

Zusammengesetze Zahlen, die dem Satz (kleiner fermatscher Satz) genügen, nennt man fermatsche Pseudoprimzahlen zur Basis . Dies ist die bekannteste und wichtigste Klasse der Pseudoprimzahlen.

Allgemein sind Pseudoprimzahlen zusammengesetze Zahlen, die einen probabilistischen Primzahltest bestehen.

Der Umkehrschluss

[Bearbeiten]

Wenn eine natürliche Zahl eine Eigenschaft, die alle Primzahlen haben, nicht hat, kann sie keine Primzahl sein; dieser Schluss ist immer zulässig. Wenn die Zahl eine solche Eigenschaft hat, und die Eigenschaft selten bei zusammengesetzten Zahlen auftritt, kann daraus nur geschlossen werden, dass sie wahrscheinlich eine Primzahl ist.

Unterscheidung

[Bearbeiten]

Wenn im Text über eine Zahl gesagt wird, sie sei eine Pseudoprimzahl, dann bedeutet das, dass diese Zahl zusammengesetzt ist, und sich nach irgendeinem Kriterium wie eine Primzahl verhält. Genauso bedeutet ein eine Zahl ist eine starke Pseudoprimzahl, dass eine Basis existiert, zu der sich diese zusammengesetzte Zahl, aufgrund des Kriteriums für starke Pseudoprimzahlen, wie eine Primzahl verhält.

Ist dagegen von einer fpsp(a) die Rede, also einer fermatschen Pseudoprimzahl zu einer bestimmten Basis , dann ist klar, dass man sich genau auf diese Basis bezieht (abgesehen davon, dass diese fermatsche Pseudoprimzahl noch zu anderen Basen pseudoprim ist).

Absolute Pseudoprimzahlen

[Bearbeiten]

Absolute Pseudoprimzahlen bezüglich einer Eigenschaft sind zusammengesetze Zahlen, die mit allen Parametern, die bestimmte Bedingungen erfüllen, pseudoprim bezüglich dieser Eigenschaft sind; Bedingungen für Parameter sind zum Beispiel, dass bei Fermatschen Pseudoprimzahlen die Basis teilerfremd zu ist, oder bei Lucas-Pseudoprimzahlen die Diskriminante den gleichen Wert hat.

Starke Pseudoprimzahlen

[Bearbeiten]

Starke Pseudoprimzahlen bezüglich einer Kongruenzbedingung sind zusammengesetzte Zahlen, die eine verschärfte Form derselben Kongruenzbedingung mit denselben Parametern erfüllen, z. B. statt :

  • oder
  • für ein , jeweils mit .

Aus der Erfüllung der starken Kongruenzbedingung folgt die Erfüllung der ursprünglichen. Der Parameter bleibt dabei gleich.


Ein paar Daten zu den fermatschen Pseudoprimzahlen

[Bearbeiten]

Zu jeder Basis gibt es eine kleinste fermatsche Pseudoprimzahl. In der folgenden Tabelle sind die kleinsten Pseudoprimzahlen bis zur Basis 121 aufgeführt:

Die kleinste fermatsche Pseudoprimzahl zur Basis a
a fpsp a fpsp a fpsp a fpsp a fpsp a fpsp
2: 341 22: 69 42: 205 62: 91 82: 91 102: 133
3: 91 23: 33 43: 77 63: 341 83: 105 103: 133
4: 15 24: 115 44: 65 64: 85 84: 415 104: 145
5: 124 25: 28 45: 76 65: 112 85: 129 105: 451
6: 35 26: 45 46: 133 66: 91 86: 145 106: 133
7: 25 27: 65 47: 65 67: 85 87: 91 107: 133
8: 21 28: 45 48: 91 68: 91 88: 91 108: 341
9: 28 29: 35 49: 66 69: 85 89: 99 109: 117
10: 33 30: 49 50: 119 70: 169 90: 623 110: 259
11: 15 31: 49 51: 65 71: 105 91: 115 111: 190
12: 65 32: 93 52: 85 72: 65 92: 105 112: 121
13: 21 33: 85 53: 65 73: 111 93: 301 113: 133
14: 39 34: 55 54: 265 74: 91 94: 121 114: 205
15: 341 35: 51 55: 63 75: 91 95: 141 115: 133
16: 51 36: 91 56: 95 76: 105 96: 133 116: 195
17: 45 37: 45 57: 65 77: 247 97: 105 117: 145
18: 25 38: 65 58: 133 78: 341 98: 153 118: 121
19: 45 39: 95 59: 87 79: 91 99: 145 119: 177
20: 57 40: 91 60: 341 80: 169 100: 153 120: 187
21: 55 41: 105 61: 91 81: 85 101: 175 121: 133

Wenn man nun alle Pseudoprimzahlen aus der Tabelle, unter der Weglassung der doppelten Pseudoprimzahlen auflistet, bekommt man folgende Folge:

 15,  21,  25,  28,  33,  35,  39,  45,  49,  51,  55,  57,  63,  65,  66,  69,  76,  77,  85,  87,  91,  93,  95,  99,
105, 111, 112, 115, 117, 119, 121, 124, 129, 133, 141, 145, 153, 169, 175, 177, 187, 190, 195, 205, 247, 259, 265, 301,
341, 415, 451, 623 

Das sind 52 Zahlen. Zum Vergleich: Bis 10 existieren 4 Primzahlen, hier sind es 0 Pseudoprimzahlen; bis 100 sind es 25 Primzahlen, hier sind es 24 Pseudoprimzahlen; bis 1000 sind es 168 Primzahlen, hier sind es 52. Allerdings muß man zugestehen, das noch gar nicht alle Pseudoprimzahlen berücksichtigt werden konnten. Wie aber verhält sich die Verteilung der Pseudoprimzahlen nun wirklich? Gibt es innerhab bestimmter Grenzen mehr Pseudoprimzahlen als Primzahlen, oder verhält es sich umgekehrt?

Dabei muß man Unterscheiden. Meint man die fermatschen Pseudoprimzahlen zu einer bestimmten Basis , so sind es, in definierten Grenzen, weniger Pseudoprimzahlen als Primzahlen:

Basis Fermatsche Pseudoprimzahlen
2 341, 561, 645, 949, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, ...
3 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, ...
4 15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, ...
5 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5611, 5662, 5731, 7449, 7813, 8029, ...
6 35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, ...
7 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, ...
8 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, ...
9 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, ...
10 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, ...

Meint man dagegen die Menge aller fermatschen Pseudoprimzahlen, die zu irgendeiner Basis pseudoprim ist, dann gibt es, in definierten Grenzen mehr Pseudoprimzahlen als Primzahlen:

  15    21    25    28    33    35    39    49    51    52    55    57    63    65    66    69    70    75
  76    77    85    87    91    93    95    99   105   111   112   115   117   119   121   123   124   125
 129   130   133   135   141   143   145   147   148   153   154   155   159   161   165   169   171   172
 175   176   177   183   185   186   187   189   190   195   196   201   203   205   207   208   209   213
 215   217   219   221   225   231   232   235   237   238   244   245   246   247   249   253   255   259
 261   265   267   268   273   275   276   279   280   285   286   287   289   291   292   295   297   299
 301   303   304   305   309   310   315   316   319   321   322   323   325   327   329   333   335   339
 341   

Der kleine fermatsche Satz besagt, dass für jede Primzahlund jede natürliche Zahl durchteilbar ist.

Für jede Primzahl gilt also

mit  

und

, wenn kein Vielfaches von ist. (1)


Definition

[Bearbeiten]

Eine zusammengesetzte Zahl ist fermatsche Pseudoprimzahl zur Basis , wenn mit und für und gilt:

.  


  • Beispiel:
ist eine zusammengesetze Zahl

Anzahl der Basen

[Bearbeiten]

Wenn die Primteilereiner Pseudoprimzahl bekannt sind, kann die Anzahl der Basen, zu denen sie pseudoprim ist, berechnet werden:

Mit der Faktorisierung

 

ist die Anzahl der Basen einschließlich 1 und bei ungeraden Zahlen n-1

.[1]  

Eigenschaften

[Bearbeiten]

Abgesehen von den Dreierpotenzen, also 9, 27, 81, 243, 729, ..., sind alle ungeraden zusammengesetzten Zahlen fermatsche Pseudoprimzahlen zu irgendeiner Basis. Bei den geraden zusammengesetzen Zahlen sieht das noch ein wenig anders als. Dort gibt es mehr zusammengesetzte Zahlen, die keine Fermatschen Pseudoprimzahlen sind.

Zusammenhänge zwischen den Basen

[Bearbeiten]

Natürlich gibt es zu einer fermatschen Pseudoprimzahl niemals nur eine Basis , zu der sie pseudoprim ist.

Das lässt sich an einer Pseudoprimzahl, sagen wir beispielsweise mal 21, zeigen:

Die 21 ist pseudoprim zur Basis 8.

  • Wenn eine ungerade Zahl zu einer Basis mit pseudoprim ist, so ist sie auch zur Basis pseudoprim.
Da 21 pseudoprim zur 8 ist, ist 21 auch pseudoprim zu (21 - 8) = 13.
  • Wenn eine Zahl zu einer Basis mit pseudoprim ist, so ist sie auch zu jeder Basis mit ganzzahligem Exponenten pseudoprim.
Da 21 pseudoprim zu 8 und 13 ist, ist 21 auch zu pseudoprim.
  • Wenn eine Zahl zu einer Basis der Form mit pseudoprim ist, so ist sie auch pseudoprim zu mit
  • Wenn eine Zahl zu den Basen und pseudoprim ist, so ist sie auch pseudoprim zu : .
Umgekehrt gilt das nicht: zum Beispiel ist 341 pseudoprim zur Basis 15, aber nicht zu 3 oder 5.

Teiler

[Bearbeiten]

Für alle Primteiler einer Fermatschen Pseudoprimzahl gilt

  • und damit
  • ,

wobei die multiplikative Ordnung von zur Basis ist.[2]



Ein paar Daten zu den fermatschen Pseudoprimzahlen

[Bearbeiten]

Zu jeder Basis gibt es eine kleinste fermatsche Pseudoprimzahl. In der folgenden Tabelle sind die kleinsten Pseudoprimzahlen bis zur Basis 121 aufgeführt:

Die kleinste fermatsche Pseudoprimzahl zur Basis a
a fpsp a fpsp a fpsp a fpsp a fpsp a fpsp
2: 341 22: 69 42: 205 62: 91 82: 91 102: 133
3: 91 23: 33 43: 77 63: 341 83: 105 103: 133
4: 15 24: 115 44: 65 64: 85 84: 415 104: 145
5: 124 25: 28 45: 76 65: 112 85: 129 105: 451
6: 35 26: 45 46: 133 66: 91 86: 145 106: 133
7: 25 27: 65 47: 65 67: 85 87: 91 107: 133
8: 21 28: 45 48: 91 68: 91 88: 91 108: 341
9: 28 29: 35 49: 66 69: 85 89: 99 109: 117
10: 33 30: 49 50: 119 70: 169 90: 623 110: 259
11: 15 31: 49 51: 65 71: 105 91: 115 111: 190
12: 65 32: 93 52: 85 72: 65 92: 105 112: 121
13: 21 33: 85 53: 65 73: 111 93: 301 113: 133
14: 39 34: 55 54: 265 74: 91 94: 121 114: 205
15: 341 35: 51 55: 63 75: 91 95: 141 115: 133
16: 51 36: 91 56: 95 76: 105 96: 133 116: 195
17: 45 37: 45 57: 65 77: 247 97: 105 117: 145
18: 25 38: 65 58: 133 78: 341 98: 153 118: 121
19: 45 39: 95 59: 87 79: 91 99: 145 119: 177
20: 57 40: 91 60: 341 80: 169 100: 153 120: 187
21: 55 41: 105 61: 91 81: 85 101: 175 121: 133

Wenn man nun alle Pseudoprimzahlen aus der Tabelle, unter der Weglassung der doppelten Pseudoprimzahlen auflistet, bekommt man folgende Folge:

 15,  21,  25,  28,  33,  35,  39,  45,  49,  51,  55,  57,  63,  65,  66,  69,  76,  77,  85,  87,  91,  93,  95,  99,
105, 111, 112, 115, 117, 119, 121, 124, 129, 133, 141, 145, 153, 169, 175, 177, 187, 190, 195, 205, 247, 259, 265, 301,
341, 415, 451, 623 

Das sind 52 Zahlen. Zum Vergleich: Bis 10 existieren 4 Primzahlen, hier sind es 0 Pseudoprimzahlen; bis 100 sind es 25 Primzahlen, hier sind es 24 Pseudoprimzahlen; bis 1000 sind es 168 Primzahlen, hier sind es 52. Allerdings muß man zugestehen, das noch gar nicht alle Pseudoprimzahlen berücksichtigt werden konnten. Wie aber verhält sich die Verteilung der Pseudoprimzahlen nun wirklich? Gibt es innerhab bestimmter Grenzen mehr Pseudoprimzahlen als Primzahlen, oder verhält es sich umgekehrt?

Dabei muß man Unterscheiden. Meint man die fermatschen Pseudoprimzahlen zu einer bestimmten Basis , so sind es, in definierten Grenzen, weniger Pseudoprimzahlen als Primzahlen:

Basis Fermatsche Pseudoprimzahlen
2 341, 561, 645, 949, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, ...
3 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, ...
4 15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, ...
5 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5611, 5662, 5731, 7449, 7813, 8029, ...
6 35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, ...
7 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, ...
8 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, ...
9 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, ...
10 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, ...

Meint man dagegen die Menge aller fermatschen Pseudoprimzahlen, die zu irgendeiner Basis pseudoprim ist, dann gibt es, in definierten Grenzen mehr Pseudoprimzahlen als Primzahlen:

  15    21    25    28    33    35    39    49    51    52    55    57    63    65    66    69    70    75
  76    77    85    87    91    93    95    99   105   111   112   115   117   119   121   123   124   125
 129   130   133   135   141   143   145   147   148   153   154   155   159   161   165   169   171   172
 175   176   177   183   185   186   187   189   190   195   196   201   203   205   207   208   209   213
 215   217   219   221   225   231   232   235   237   238   244   245   246   247   249   253   255   259
 261   265   267   268   273   275   276   279   280   285   286   287   289   291   292   295   297   299
 301   303   304   305   309   310   315   316   319   321   322   323   325   327   329   333   335   339
 341   

Quellen

[Bearbeiten]
  1. Lucas Pseudoprimes
  2. The pseudoprimes to 25 * 10^9

Für jede ungerade Primzahl gilt mit jeder teilerfremden Basis die Kongruenz

.  

Dabei bezeichnet das Jacobi-Symbol.

Eulersche Pseudoprimzahl

[Bearbeiten]

Eine zusammengesetzte Zahl n ist eine eulersche Pseudoprimzahl, wenn es mindestens eine natürliche Zahl im Bereich als Basis gibt, mit der entweder

(1a)

oder

(1b)

ist.

Eine solche Zahl nennt man eulersche Pseudoprimzahl zur Basis a, kurz: EPsP(a).

Eulersche Pseudoprimzahlen sind auch Fermatsche Pseudoprimzahlen

[Bearbeiten]

Es lässt sich ziemlich einfach, nämlich durch Quadrieren, zeigen, dass jede eulersche Pseudoprimzahl auch eine fermatsche Pseudoprimzahl ist. Es sei n eine eulersche Pseudoprimzahl zur Basis a. Es gilt also:

Folglich ist:

und deshalb ist n auch eine fermatsche Pseudoprimzahl zur Basis a.

Daraus dass eine eulersche Pseudoprimzahl eine fermatsche Pseudoprimzahl ist, lässt sich nicht der Umkehrschluss ziehen, dass jede fermatsche Pseudoprimzahl auch eine eulersche Pseudoprimzahl ist. Das lässt sich anhand der fermatschen Pseudoprimzahl 15 zeigen:

.

Die Zahl 15 ist also keine eulersche Pseudoprimzahl zur Basis 11. Aber

demzufolge ist 15 eine fermatsche Pseudoprimzahl zur Basis 11.

Euler-Jacobi-Pseudoprimzahl

[Bearbeiten]

Eine ungerade zusammengesetzte natürliche Zahl heißt Euler-Jacobi-Pseudoprimzahl zur Basis a, wenn und teilerfremd sind und

(2)

ist.

Euler-Jacobi-Pseudoprimzahlen werden oft auch "Eulersche Pseudoprimzahlen" genannt.

Da der Wert des Jacobi-Symbols mit teilerfremden Parametern nur 1 oder -1 sein kann, ist jede Euler-Jacobi-Pseudoprimzahl auch eine eulersche Pseudoprimzahl;

  • für 1 gilt Kongruenz 1a,
  • für -1 gilt 1b.

Anzahl der Basen

[Bearbeiten]

Wenn die Primteilereiner zusammengesetzten Zahl bekannt sind, kann die Anzahl der Basen, zu denen sie Euler-Jacobi-Pseudoprimzahl ist, berechnet werden:

Mit der Faktorisierung

 

ist die Anzahl der Basen einschließlich 1 und n-1

[1]  

Dabei ist

  • der größte Exponent, mit dem gilt,, so dass ist,
  • der größte ungerade Teiler von ,
  • der größte Exponent, mit dem gilt, so dass ist und
  • das Minimum aller .

Quellen

[Bearbeiten]
  1. On the number of false witnesses for a composite number, S. 270 (5.4)



Jede ungerade Primzahl erfüllt mit jeder teilerfremden ganzzahligen Basis eine der Kongruenzen

mit und ungerade (1)
für ein mit (2)

. Anmerkung: Kongruenz (2) ist gleichbedeutend mit .


Definition

[Bearbeiten]

Eine ungerade Zahl ist starke Pseudoprimzahl zur Basis , wenn sie zusammengesetzt ist, und mit einer ganzzahligen Basis , für die gilt, eine der obengenannten Kongruenzen erfüllt ist. In dieser Hinsicht verhält sie sich wie eine Primzahl.

Die obengenannten Kongruenzen werden im Miller-Rabin-Test[1] genutzt, um zu prüfen ob eine ungerade Zahl (wahrscheinlich) eine Primzahl oder sicher keine ist; dabei kann durch Tests mit mehreren Basen die Wahrscheinlichkeit, dass eine Pseudoprimzahl den Test besteht, reduziert werden.

Eigenschaften

[Bearbeiten]

Im Gegensatz zu den Fermatschen Pseudoprimzahlen gibt es keine starken Pseudoprimzahlen, die zu jeder teilerfremden Basis pseudoprim sind; eine Entsprechung zu den Carmichael-Zahlen gibt es also nicht.

Alle zusammengesetzten Mersennezahlen ( mit = prim) sind starke Pseudoprimzahlen zur Basis 2.

Alle zusammengesetzten Fermatzahlen () sind starke Pseudoprimzahlen zur Basis 2.[2]

ist starke Pseudoprimzahl zur Basis 2, wenn und eine Primzahl ist.[3]

Die Quadrate der Wieferich-Primzahlen sind starke Pseudoprimzahlen zur Basis 2.

Bezug zu Eulerschen Pseudoprimzahlen

[Bearbeiten]

Jede starke Pseudoprimzahl zur Basis ist auch eine Eulersche Pseudoprimzahl zur Basis .
Warum? Für eine eulersche Pseudoprimzahl zur Basis gilt .

lässt sich auch als schreiben. Wenn nun gilt, gilt auch und damit auch .


Jede eulersche Pseudoprimzahl der Form ist starke Pseudoprimzahl:
in diesem Fall ist und und damit ; mit ist also eine der obengenannten Kongruenzen erfüllt.


Teiler

[Bearbeiten]

Für alle Primteiler einer starken Pseudoprimzahl gilt

  • und damit
  • ,

wobei die multiplikative Ordnung von zur Basis ist.[4] [5][6]

Die höchste Zweierpotenz, durch die die multiplikative Ordnung eines Primteilers teilbar ist, ist für alle Teiler einer starken Pseudoprimzahl gleich, d. h. alle multiplikativen Ordnungen der Primteiler derselben starken Pseudoprimzahl sind Produkt einer ungeraden Zahl und derselben Zweierpotenz (einschließlich ).[7]

Starke Pseudoprimzahlen sind weitgehend quadratfrei; nur die Quadrate der Wieferich-Primzahlen zur Basis sind starke Pseudoprimzahlen zur Basis und können Teiler einer solchen sein. Mit der Basis 2 sind das die Wieferich-Primzahlen 1093 und 3511 (weitere sind bisher nicht bekannt).

Starke Pseudoprimzahlen lassen sich häufig als Produkte der Form

mit
,
und

ausdrücken. Umgekehrt ist der Anteil starker Pseudoprimzahlen bei solchen Produkten deutlich höher als bei ungeraden Zahlen allgemein.

Anzahl der Basen

[Bearbeiten]

Wenn die Primteilereiner zusammengesetzten Zahl bekannt sind, kann die Anzahl der Basen, zu denen sie starke Pseudoprimzahl ist, berechnet werden:

Mit der Faktorisierung

 

ist die Anzahl der Basen einschließlich 1 und n-1

[8]  

Dabei ist

  • der größte ungerade Teiler von (wie oben)
  • der größte ungerade Teiler von ,
  • der größte Exponent, mit dem gilt, so dass ist und
  • das Minimum aller .

Basen, zu denen eine zusammengesetze Zahl keine Pseudoprimzahl ist, werden Zeugen für die Zusammengesetztheit der Zahl genannt; solche zu denen sie pseudoprim ist, werden „falsche Zeugen“ genannt. Maximal ein Viertel der teilerfremden Basen zwischen 0 und n sind falsche Zeugen.

Häufigkeit

[Bearbeiten]

Starke Pseudoprimzahlen zu einer festen Basis sind viel seltener als Primzahlen. Folgende Tabelle zeigt die Anzahl starker Pseudoprimzahlen zur Basis 2 im Vergleich zur Anzahl fermatscher Pseudoprimzahlen zur Basis 2 und der Primzahlen bis zur angegebenen Obergrenze.

Anzahl Starker Pseudoprimzahlen zur Basis 2 im Vergleich zu Primzahlen
Obergrenze Primzahlen[9] Fermatsche Pseudoprimzahlen Starke Pseudoprimzahlen[10]
50.847.534 5.597 1.282
37.607.912.018 101.629 22.407
29.844.570.422.669 1.801.533 419.489
24.739.954.287.740.860 33.763.684 8.646.507

Restklassen

[Bearbeiten]

Starke Pseudoprimzahlen liegen wesentlich häufiger in der Restklasse 1 modulo kleiner Zahlen als in anderen Restklassen. Folgende Tabelle zeigt die Verteilung der starken Pseudoprimzahlen zur Basis 2 bis 1015 auf Restklassen modulo m an ein paar Beispielen.

Anzahl starker Pseudoprimzahlen zur Basis 2 in Restklasse
m 0 1 2 3 4 5 6 7
3 26 327193 92270
5 1373 199879 84716 74590 58931
7 370 142844 49224 62834 47482 57853 58882
8 0 207103 0 44885 0 122473 0 45028

Beispiele

[Bearbeiten]

Um zu zeigen, wie unterschiedlich starke Pseudoprimzahlen ausfallen können, werden als Beispiele die drei Zahlen 781, 1541 und 25 gezeigt. An der Zahl 781 wird erstmal die Zerlegung gezeigt:

Zerlegung

Gesucht wird das zu einer Zahl so dass mit ungeradem gilt. Die Formel können wir umstellen:

Am Beispiel der Zahl 781 sieht das so aus: Die Primfaktorzerlegung von . Wenn man die 2er-Potenzen entfernt, bleibt für das übrig.

781 zur Basis 5

also ist 781 eine starke Pseudoprimzahl zur Basis 5.

1541 zur Basis 5

also ist 1541 eine starke Pseudoprimzahl zur Basis 5.

25 zur Basis 7

also ist 25 eine starke Pseudoprimzahl zur Basis 7.

305 zur Basis 11

Dies ist ein Gegenbeispiel.

Somit ist 305 keine starke Pseudoprimzahl zur Basis 11.

Quellen

[Bearbeiten]
  1.  Miller-Rabin-Test
  2.  Pseudoprimes and Fermat numbers
  3. Prime Numbers - A Computational Perspective, Richard Crandall & Carl Pomerance, Springer Verlag, ISBN 0-387-25282-7 http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf
  4. The pseudoprimes to 25 * 10^9
  5. Glossar
  6.  Multiplicative order
  7. New Implementations for Tabulating Pseudoprimes and Liars.pdf
  8. On the number of false witnesses for a composite number, S. 270 (5.4)
  9.  Primzahlsatz
  10. Pseudoprime Statistics, Tables



Carmichael-Zahlen

[Bearbeiten]

Die Carmichael-Zahl ist eine besondere Form der fermatschen Pseudoprimzahl. In ihren Eigenschaften kommt sie der Primzahl am nächsten. Sowohl für Primzahlen als auch für Carmichael-Zahlen gilt der kleine Fermatsche Satz: Für jede ganze Zahl gilt . Erst wenn man diesen Satz modifiziert, ergibt sich ein Unterschied zwischen Primzahl und Carmichael-Zahl.

Carmichael-Zahlen haben folgende Eigenschaften:

  1. Eine Carmichael-Zahl ist quadratfrei.
  2. Eine Carmichael-Zahl hat mindestens drei Primfaktoren.
  3. Für jeden Primfaktor einer Carmichael-Zahl gilt teilt .
  4. Für alle Basen , die zu einer Carmichael-Zahl teilerfremd sind, ist .

Quadratfreiheit

[Bearbeiten]

Warum muss eine Carmichael-Zahl quadratfrei sein? Angenommen es gibt eine Carmichael-Zahl, die nicht quadratfrei ist. Sie hat der Einfachheit halber die Form mit . Außerdem sind und Primzahlen. Es gilt also teilt . Mit der Kenntnis der Faktorisierung von kann man die Carmichael-Funktion berechnen:

Da durch teilbar ist, ist auch durch teilbar, und damit gilt dadurch auch dass durch teilbar ist. Und das führt zu einem Widerspruch.

Es gilt nämlich teilt und teilt . Der Widerspruch liegt darin, dass und zueinander teilerfremd sind, also keinen gemeinsamen Teiler besitzen. Also ist es nicht möglich, dass eine Carmichael-Zahl nicht quadratfrei ist.

mindestens drei Primfaktoren

[Bearbeiten]

Jede Carmichael-Zahl besitzt mindestens 3 voneinander verschiedene Primfaktoren.

Beweis: Durch Widerspruch.

Sei eine Carmichael-Zahl. Angenommen, , wobei und Primfaktoren seien. Zunächst muss wegen der oben gezeigten Quadratfreiheit gelten, dass . Wir können also annehmen, dass (man kann die Schlüsse analog mit ziehen). Nun gilt wegen Eigenschaft (3) also .

Damit ist . Das bedeutet aber, im Widerspruch zu . Also war die Annahme falsch. Carmichael-Zahlen mit nur einem Primfaktor kann es nach Definition nicht geben (denn sie sind keine Primzahlen), und dass es Carmichael-Zahlen mit 3 Primfaktoren gibt, zeigt bereits die allererste: . Zusammen genommen ist also gezeigt worden, dass eine Carmichael-Zahl mindestens 3 Primfaktoren hat.

Satz von Korselt

[Bearbeiten]

Der deutsche Mathematiker Alwin Reinhold Korselt hat 1899 ein Theorem über eine bestimmte Art von Pseudoprimzahlen, die später Carmichael-Zahlen genannt wurden, aufgestellt:

  1. Es existieren ungerade, quadratfreie natürliche Zahlen , so dass für alle natürlichen Zahlen ein Vielfaches von ist
  2. Für alle Primteiler von gilt, dass die Zahl teilt.
  • Beispiel
ist das Produkt von , und . Da eine Carmichael-Zahl ist, gilt nach dem Satz von Korselt:
teilt
teilt und
teilt .

Pseudoprim zu allen zu c teilfremden Basen a

[Bearbeiten]

Unter den fermatschen Pseudoprimzahlen ist sie die Königin, denn für sie gilt, mit jeder natürlichen Zahl , zu der die Carmichael-Zahl teilerfremd ist,

.
  • Beispiel
Die Zahl ist eine Carmichael-Zahl.
Die Zahlen , und sind teilerfremd zur , also gelten:
Die Zahlen , und sind nicht teilerfremd zur , also gelten:

Carmichael-Zahlen generieren

[Bearbeiten]

Es gibt zwei Wege, an Carmichael-Zahlen zu kommen. Der eine ist, sich zufällig natürliche Zahlen zu erzeugen, um dann auf und für alle zu testen. Die Wahrscheinlichkeit, auf diese Weise Carmichael-Zahlen zu finden ist sehr gering. Will man allerdings Carmichael-Zahlen vermeiden, so ist dieser Weg vorzuziehen. Der andere Weg ist, konsequent das Produkt aus mindestens drei, zueinander teilerfremden Primzahlen zu bilden, um die so erzeugten Zahlen auf das Korselt-Kriterium zu prüfen.

Nicht jedes quadratfreie Produkt aus Primzahlen kann eine Carmichael-Zahl sein. Ansonsten gäbe es jede Menge Carmichael-Zahlen. Aber kann man bestimmte Primzahlkombinationen schon vorher ausschließen? Man kann! Es gilt nämlich, dass zwei natürliche Zahlen und zueinander teilerfremd sind. Das bedeutet, dass und keine gemeinsamen Teiler besitzen.

Es ist also wichtig, dass bei der generierten Zahl alle zu allen teilerfremd sind. Das ist nicht selbstverständlich, wie das folgende Beispiel zeigt:

Wichtig an dem Beispiel ist, dass (11-1) durch 5 teilbar ist, (23-1) durch 11 und (47-1) durch 23. Ein solches Produkt kann keine Carmichael-Zahl sein.

Wenn also die Primzahl Teiler einer Carmichael-Zahl sein soll, so sind alle Primzahlen der Form als Teiler der Carmichael-Zahl ausgeschlossen.

3 7 13 19 31 37 43 61 67 73 79 ...
5 11 31 41 61 71 101 ...
7 29 43 71 ...

Carmichael-Zahlen nach Chernick

[Bearbeiten]

Wenn man sich auf eine spezielle Form der Carmichael-Zahlen beschränken will, dann gibt es noch die Carmichael-Zahlen nach Chernick. Diese haben die allgemeine Form:

wobei alle Faktoren Primzahlen sind, und für k > 4 die Zahl durch teilbar sein muss.

Für lautet die Formel , die äquivalent zu der Formel für ist.

Für lautet die Formel .

Beweis der Äquivalenz

[Bearbeiten]

Warum sind die beiden Konstruktionsvorschriften:

Eine Zahl ist dann eine Carmichael-Zahl,
wenn alle 3 Faktoren , und Primzahlen sind.

und

Sei p > 3 eine Primzahl derart, dass auch 2p-1 und 3p-2 Primzahlen sind,
dann ist n = p(2p-1)(3p-2) eine Carmichael-Zahl

zueinander äquivalent? Es wäre doch möglich, das eine Primzahl , die nicht der Form entspricht, existiert, so daß und auch Primzahlen sind. Nun, so eine Primzahl existiert nicht.

Es gibt nur zwei Arten von Primzahlen mit , nämlich Primzahlen der Form und Primzahlen der Form . Wenn man durch ersetzt, bekommt man statt den Ausdruck . Ausmultipliziert und zusammengefaßt macht das . Dieser Ausdruck ist also stets durch drei teilbar. Nur mit einer Primzahl der Form kann man mit der Formel für eine Carmichael-Zahl bekommen.

Absolute eulersche Pseudoprimzahlen

[Bearbeiten]

Eine absolute eulersche Pseudoprimzahl ist eine Carmichael-Zahl, die zu jeder, zu ihr teilerfremden, Basis euler-pseudoprim ist.

Für jeden Primteiler einer absoluten Eulerschen Pseudoprimzahl gilt:

teilt .

Die ersten absoluten Eulerschen Pseudoprimzahlen sind 1729, 2465, 15841, 41041, 46657, 75361.

Es gibt keine absoluten Euler-Jacobi-Pseudoprimzahlen.

Häufigkeit und Überschneidung mit Lucas-Pseudoprimzahlen

[Bearbeiten]
Anzahl der Carmichael-Zahlen und Überschneidung
mit starken und Lucas-Pseudoprimzahlen
gleichzeitig Carmichael- &
Obergrenze x Carmichael[1] f(x)(I) abs epsp sPsp(2) lpsp Lucas3(7,*)
10 3 1 0.014 0 0 0 0
10 4 7 0.072 2 0 0 0
10 5 16 0.054 6 3 0 0
10 6 43 0.047 16 5 0 0
10 7 105 0.050 45 11 0 0
10 8 255 0.042 124 19 0 0
10 9 646 0.036 306 43 0 0
1010 1547 0.031 740 87 0 0
1011 3605 0.024 1736 171 0 0
1012 8241 0.019 4011 316 0 0
1013 19279 0.015 9362 621 0 0
1014 44706 0.012 21974 1153 0 0
1015 105212 0.009 52221 2234 0 0
1016 246683 0.007 122608 4185 0 0

(I) Mittlerer Anteil falscher Zeugen beim Miller-Rabin-Test.

Quellen

[Bearbeiten]
  1. http://www.s369624816.websitehome.co.uk/rgep/cartable.html Tables of Carmichael numbers


Eine Pseudoprimzahl , die zu irgendeiner natürlichen Zahl pseudoprim im Sinne des kleinen fermatschen Satz ist, zu konstruieren, ist recht einfach. Man nehme zwei beliebige Primzahlen mit , und multipliziere sie miteinander. Das Produkt wird dann schon zu mindestens einer natürlichen Zahl pseudoprim sein. Aber zu welcher Zahl ?

und müssen zueinander teilerfremd sein

Damit eine zusammengesetzte Zahl zu einer natürlichen Zahl pseudoprim sein kann, muss immerhin sichergestellt sein, dass und zueinander teilerfremd sind. Zu jeder solchen Fermatschen Pseudoprimzahl der Form lassen sich zwei Basen finden, und zwar durch folgende Vorgehensweise:

Man ermittelt die Vielfachen von und :
und

Dann sucht man jeweils ein Vielfaches und heraus, für die gilt. Die zwischen und liegende Zahl ist eine Basis, zu der die Zahl pseudoprim ist (im Sinne des kleinen fermatschen Satzes), und sie ist teilerfremd zu und . Es gibt zu jeder Zahl genau zwei Basen , die sich auf diese Weise finden lassen und kleiner als sind. Die Summe dieser beiden Basen und ist . Alle Basen , die größer als sind und sich nach dem beschriebenen Algorithmus konstruieren lassen, haben entweder die Form oder .

Das Produkt ist immer pseudoprim zur Basis , wenn ist, auch wenn oder zusammengesetzt ist.

Beweis:


Beispiel

[Bearbeiten]

Die Vielfachen von sind:

Die Vielfachen von sind:

Von diesen Vielfachen haben und beziehungsweise und eine Differenz von . Die zwischen und liegende Zahl und die zwischen und liegende Zahl sind Basen zu denen die Zahl pseudoprim ist.

Die Summe von und ist .

Mit folgendem Verfahren hat der Mathematiker Lehmer gezeigt, dass unendlich viele fermatsche Pseudoprimzahlen existieren müssen:

Man nimmt eine natürliche Zahl , die größer oder gleich 5 ist. Mit dieser Zahl bildet man die beiden Zahlen und . Von diesen beiden Zahlen nimmt man jeweils einen Primfaktor. Also je eine Primzahl und , so dass gilt: teilt und teilt . Das Produkt ist dann eine fermatsche Pseudoprimzahl zur Basis .

Beispiel

[Bearbeiten]

Man nimmt : ist dann und . Wenn man jetzt und wählt, bekommt man mit die Zahl 35, eine fermatsche Pseudoprimzahl zur Basis 64.

k 2k-1 2k+1 Pseudoprimzahlen nach Lehmer
5 31 3·11 93, 341
6 32·7 5·13 15, 35, 39, 91
7 127 3·43 381, 5461
8 3·5·17 257 771, 1285, 4369
9 7·73 33·19 21, 133, 219, 1387
10 3·11·31 52·41 15, 55, 123, 155, 451, 1221
11 23·89 3·683 69, 267, 15709, 60787
12 32·5·7·13 17·241 51, 85, 119, 221, 723, 1205, 1687, 3133
... ... ... ...

Dieses Kapitel oder dieser Abschnitt ist unverständlich formuliert. Ein Hinweis, was nicht verstanden wird, ist möglicherweise auf der Diskussionsseite des Artikels zu finden. Wenn Sie Hilfe benötigen, schauen Sie, welche Qualitätskriterien an ein gutes Buch gestellt werden. Das allgemeine Vorgehen bei diesem Baustein kannst Du hier nachlesen.

Fermatsche Pseudoprimzahlen zur Basis a nach Michele Cipolla

[Bearbeiten]

Michele Cipolla hat 1904 ein Verfahren zum Erzeugen beliebiger fermatscher Pseudoprimzahlen zu einer beliebigen, natürlichen Basis gefunden. Dazu benötigt man eine Primzahl, die nicht teilt. Warum, das wird weiter unten erklärt.

Mit der Basis und der Primzahl werden zwei Zahlen und erzeugt:

Das Produkt ist eine fermatsche Pseudoprimzahl zur Basis

Erklärung

[Bearbeiten]

Die Bedingung, dass teilerfremd zu sein soll, kann auch so formuliert werden: soll eine Primzahl sein, die nicht teilt, da nach der dritten binomischen Formel ist. Damit ist sichergestellt, dass zu , und teilerfremd ist.

und sind beides Partialsummen geometrischer Reihen, nämlich:

und


Aus und

folgt, dass auch ist.

Aus

folgt, dass ist,

so dass n eine Pseudoprimzahl zur Basis a sein muss. Da es unendlich viele Primzahlen gibt, muss es demnach auch unendlich viele Pseudoprimzahlen zu jeder Basis a geben.

Liste fermatscher Pseudoprimzahlen zur Basis a nach Michele Cipolla

[Bearbeiten]
a p n1 n2 n=n1•n2 Faktoren
2 5 31 11 341 11•31
2 7 127 43 5461 43•127
3 5 121 61 7381 11•11•61
3 7 1093 547 597871 547•1093
2 11 2047 683 1398101 23•89•683
7 5 2801 2101 5884901 11•191•2801
2 13 8191 2731 22369621 2731•8191
5 7 19531 13021 254313151 29•449•19531
13 5 30941 26521 809977861 11•2411•30941
3 11 88573 44287 3922632451 23•67•661•3851
2 17 131071 43691 5726623061 43691•131071
17 5 88741 78881 6999978821 11•71•101•88741
2 19 524287 174763 91625968981 174763•524287
3 13 797161 398581 317733228541 398581•797161
11 7 1948717 1623931 3164581946527 43•45319•1623931
2 23 8388608 2796203 23456248059221 47•178481•2796203


Die Zeisel-Zahl ist eine nach dem Mathematiker Helmut Zeisel benannte Zahl, die das Produkt wenigstens dreier Primzahlen ist, die einer bestimmten linearen Rekursion genügen. Eine besondere Bedeutung in der Mathematik haben sie nicht. Auf Grund gewisser Ähnlichkeiten mit den Carmichael-Zahlen sind sie hier aufgeführt.

Definition

[Bearbeiten]
p0 = 1
pn = a·pn-1 + b

Dabei muss jedes pn mit eine Primzahl ergeben, und sowohl a als auch b sind für alle pn konstant. Die Zeisel-Zahl z ist dann das Produkt .

Beispiel an der Zeisel-Zahl 1885

[Bearbeiten]

In diesem Beispiel ist a = 2 und b = 3.

p0 = 1
p1 = a·p0 + b = 2·1  + 3 = 5
p2 = a·p1 + b = 2·5  + 3 = 13
p3 = a·p2 + b = 2·13 + 3 = 29

z = p1 · p2 · p3 = 5 · 13 · 29 = 1885

Zusammenhang zwischen den Zeisel-Zahlen und den Carmichael-Zahlen nach J.Chernick

[Bearbeiten]

Die Bildungsregel der Carmichael-Zahlen nach J. Chernick lautet (6n+1)*(12n+1)*(18n+1). Diese Bildungsregel ist identisch mit der Bildungsregel für Zeisel-Zahlen mit einem a=1 und b=6n. Demzufolge sind alle Carmichael-Zahlen nach Chernick, die ein Produkt aus drei Primzahlen bilden, auch Zeisel-Zahlen.

Eine Liste von Zeisel-Zahlen

[Bearbeiten]

Die Carmichael-Zahlen sind fett geschrieben.

a b zn
1 2 105 3*5*7
4 -1 1419 3*11*43
1 6 1729 7*13*19
2 3 1885 5*13*29
3 2 4505 5*17*53
2 5 5719 7*19*43
10 -7 15387 3*23*223
2 9 24211 11*31*71
6 -1 25085 5*29*173
4 3 27559 7*31*127
13 -10 31929 3*29*367
8 -3 54205 5*37*293
3 8 59081 11*41*131
2 3 114985 5*13*29*61
25 -22 207177 3*53*1303
5 6 208681 11*61*311
9 -2 233569 7*61*547
28 -25 287979 3*59*1627
1 36 294409 37*73*109
6 5 336611 11*71*431
5 8 353977 13*73*373
17 -12 448585 5*73*1229
a b zn
34 -31 507579 3*71*2383
15 -8 982513 7*97*1447
9 2 1012121 11*101*911
23 -18 1073305 5*97*2213
8 5 1242709 13*109*877
49 -46 1485609 3*101*4903
55 -52 2089257 3*113*6163
12 -1 2263811 11*131*1571
4 27 2953711 31*151*631
33 -28 3077705 5*137*4493
14 -3 3506371 11*151*2111
2 9 3655861 11*31*71*151
36 -31 3973085 5*149*5333
2 59 4648261 61*181*421
4 33 5069629 37*181*757
2 65 6173179 67*199*463
42 -37 6253085 5*173*7229
11 6 6985249 17*193*2129
8 15 7355239 23*199*1607
2 69 7355671 71*211*491
10 9 7558219 19*199*1999
4 39 8011459 43*211*883
a b zn
88 -85 8413179 3*179*15667
6 25 8444431 31*211*1291
47 -42 8712985 5*193*9029
48 -43 9271805 5*197*9413
20 -9 9773731 11*211*4211
57 -52 15411785 5*233*13229
3 68 18175361 71*281*911
5 42 18578113 47*277*1427
6 35 19827641 41*281*1721
9 20 20771801 29*281*2549
3 8 23691481 11*41*131*401
68 -63 26000605 5*277*18773
5 48 26758057 53*313*1613
10 21 34179391 31*331*3331
14 9 35347159 23*331*4643
77 -72 37605385 5*313*24029
20 -3 38596273 17*337*6737
2 125 42501439 127*379*883
15 8 43055057 23*353*5303
83 -78 46999705 5*337*27893
8 35 49982899 43*379*3067
3 98 52691801 101*401*1301
a b zn
2 135 53399449 137*409*953
30 -17 54177877 13*373*11173
3 100 55902529 103*409*1327
1 210 56052361 211*421*631
9 34 69207769 43*421*3823
65 -58 71550913 7*397*25747
18 5 72730439 23*419*7547
11 26 76724569 37*433*4789
10 33 92835667 43*463*4663
2 165 96916279 167*499*1163
6 65 104966471 71*491*3011
1 270 118901521 271*541*811
8 -1 126893905 5*37*293*2341
4 105 133800661 109*541*2269
29 -10 161164441 19*541*15679
1 306 172947529 307*613*919
3 148 177055201 151*601*1951
15 22 185245273 37*577*8677
5 98 199708657 103*613*3163
4 123 212122639 127*631*2647
1 330 216821881 331*661*991
16 21 222931549 37*613*9829

Geschichte

[Bearbeiten]

Der Name "Zeisel-Zahl" wurde vermutlich von Kevin Brown eingeführt, der Zahlen suchte, für die der Ausdruck eine Primzahl ergibt. In einem Posting in die Usenet-Newsgroup sci.math vom 24. Februar 1994 lieferte Helmut Zeisel die Zahl 1885 als eine weitere Lösung. Später wurde (durch Kevin Brown?) entdeckt, dass die Primfaktoren von 1885 die oben beschriebenene Eigenschaft haben. Ein Name der Art Brown-Zeisel-Zahlen wäre daher passender.

Verallgemeinerung

[Bearbeiten]

Man muss sich bei der Bildung der Zeisel-Zahl nicht auf beschränken. Auch davon abweichende Werte sind möglich.

Beispiele

[Bearbeiten]
p0 = 4
p1 = a·p0 + b = 2·4  + 5 = 13
p2 = a·p1 + b = 2·13 + 5 = 31
p3 = a·p2 + b = 2·31 + 5 = 67

z = p1 · p2 · p3 = 13 · 31 · 67 = 27001


p0 = -1
p1 = a·p0 + b = 8·-1   + 27 =   19
p2 = a·p1 + b = 8·19   + 27 =  179
p3 = a·p2 + b = 28·179 + 27 = 1459

z = p1 · p2 · p3 = 19 · 179 · 1459 = 4962059
p0 = 13
p1 = 139
p2 = 1399
p3 = 13999
p4 = 139999
p5 = 1399999

z = 139 · 1399  · 13999 · 139999 · 1399999 = 533558677367032199539
[Bearbeiten]

Quelle: Die Zeisel-Zahlen sind aus dem Artikel Zeisel-Zahl der deutsprachigen de.wikipedia.org entnommen.

Carmichael-Zahlen

[Bearbeiten]

Ein Programm, das eine Liste von Carmichael-Zahlen ausgibt, ist geradezu trivial. Dass dem so ist, verdanken wir dem Kriterium von Korselt. Dieses Theorem besagt, dass eine Carmichel-Zahl eine quadratfreie, aus mindestens drei Primfaktoren bestehende, natürliche Zahl der Form ist, so dass für jedes gilt, dass die Zahl teilt. Daraus folgt, dass man sich um den kleinen Fermatschen Satz nicht im geringsten zu kümmern braucht. Neben Korselts Kriterium gibt es auch noch Formeln zum Erzeugen spezieller Carmichael-Zahlen. Auch bei diesen Beispielen braucht man sich um den kleinen Fermatschen Satz nicht zu kümmern.

zweiter Ansatz

[Bearbeiten]

Das folgende Programm benutzt drei ineinander verschachtelte Schleifen, durch die sichergestellt wird, dass drei zueinander teilerfremde Primzahlen ausgewählt werden. Aus diesen drei Primzahlen wird ein Produkt gebildet, das die zu testende Zahl darstellt. An dieser Zahl wird nun Korselts Kriterium getestet, was einfach ist, da dem Programm die Primteiler der zu testenden Zahl bekannt sind. Ist Korselt Kriterium erfüllt, dann handelt es sich bei der Zahl um eine Carmichael-Zahl, und die Zahl wird, samt Primzahlfaktoren als Carmichael-Zahl ausgegeben.

Details: Die Variable p.0 enthält die Anzahl der unterschiedlichen Primzahlen. In p.1 bis p.(p.0) sind die einzelnen Primzahlen abgelegt.

p.1  = 3
p.2  = 5
p.3  = 7
p.4  = 11
p.4  = 13
p.5  = 17
p.6  = 19
p.7  = 23
p.8  = 29
p.9  = 31
p.10 = 37
.
.
.
p.549 = 4001
p.550 = 4003
p.551 = 4007
p.552 = 4013
p.553 = 4019
p.554 = 4021
p.555 = 4027
p.556 = 4049
p.557 = 4051
p.558 = 4057
i=558
do a=1 to (i-2)
  do b=a+1 to (i-1)
    do c=b+1 to i
      t = 0
      z=p.a*p.b*p.c
      ax=p.a-1
      bx=p.b-1
      cx=p.c-1
      zax=(z/p.a)-1
      zbx=(z/p.b)-1
      zcx=(z/p.c)-1
      pz=(zax // ax) + (zbx // bx) + (zcx // cx)
      if (pz = 0) then t = 1
      if (t = 1) then do
        say z||"="||p.a||"*"||p.b||"*"||p.c
        lineout("rcrmn___.txt",z||" = "||p.a||"*"||p.b||"*"||p.c)
      end
      t=0
    end
  end
end

Das Programm kann man modifizieren, indem man die Anzahl der Primzahlen erhöht. Für Carmichael-Zahlen mit mehr als drei Primfaktoren muss man die Anzahl der Schleifen erhöhen, und die Prüfroutinen erweitern.

Carmichael-Zahlen nach Chernick

[Bearbeiten]

Die Carmichel-Zahlen nach Chernick sind nur ein kleiner Ausschnitt aus den Carmichael-Zahlen. Sie lassen sich durch folgende Formel generieren: . Es gibt dabei allerdings eine Einschränkung:

  • Jeder der drei Faktoren , und muss eine Primzahl sein. Halt, hier gibt es eine Ausnahme: Wenn ein einziger der drei Faktoren selbst eine Carmichael-Zahl ist, so ist trotzdem eine Carmichael-Zahl.

Da alle Carmichael-Zahlen quadratfrei sind, ist dann auch jeder der drei Faktoren , und quadratfrei - auch wenn einer davon eine Carmichael-Zahl ist. Da die drei Faktoren paarweise teilerfremd sind, ist auch der Ausdruck quadratfrei.

Alle gültigen für Carmichael-Zahlen nach Chernick enden im Dezimalsystem mit einer 0, einer 1 einer 5 oder einer 6.

l.1  = 0
l.2  = 1
l.3  = 5
l.4  = 6
do i = 0 to 1000
  do j = 1 to 4
    n=i+l.j
    m=(6*n+1)*(12*n+1)*(18*n+1)
    if((primzahl(6*n+1)=true) && (primzahl(12*n+1)=true) && (primzahl(18*n+1)=true)) then do
      say m||"="||(6*n+1)||"*"||(12*n+1)||"*"||(18*n+1)
      lineout("rcrmn___.txt",m||" = "||(6*n+1)||"*"||(12*n+1)||"*"||(18*n+1))
    end
  end
end

Das Programm lässt sich entsprechend der Formeln für Carmichael-Zahlen nach Chernick, mit mehr als drei Primzahlfaktoren, nach der entsprechenden Formel erweitern.

Absolute Eulersche Pseudoprimzahlen

[Bearbeiten]

Das Programm, mit dem oben Carmichael-Zahlen erzeugt werden, kann man mit einer kleinen Modifikation dazu bringen, absolute eulersche Pseudoprimzahlen zu erzeugen:

      zax=(z-1)/2
      pz=(zax // ax) + (zax // bx) + (zax // cx)
statt
      zax=(z/p.a)-1
      zbx=(z/p.b)-1
      zcx=(z/p.c)-1
      pz=(zax // ax) + (zbx // bx) + (zcx // cx)

Das hierbei alle absoluten eulerschen Pseudoprimzahlen ausgegeben werden, ist eine andere Frage. Aber die Zahlen, die ausgegeben werden, sind absolute Eulersche Pseudoprimzahlen.

Modulare Arithmetik

[Bearbeiten]

Da man es bei der Berechnung von fermatschen Pseudoprimzahlen häufig mit großen Potenzen großer Zahlen zu tun bekommt, hat man ein kleines Problem. Zum Beispiel für den Nachweis, dass 341 eine fermatsche Pseudoprimzahl zur Basis 2 ist, muss man die Zahl berechnen. Diese Zahl heißt ausgeschrieben:

2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115776

Das ist für ein Programm wie MuPad wahrscheinlich kein Problem, für die meisten herkömmlichen Programmiersprachen aber sehr wohl. Durch eine Kombination von Multiplikation und Modulo kann man aber auch wesentlich größere Potenzen kleinhalten.
Da bei Rechenoperationen Modulo nur Zahlen bis auftreten, ist das Ergebnis einer Multiplikation vor der Modulooperation immer kleiner als .

Beispiel: . Letztendlich interessiert uns ja aber nicht , sondern vielmehr mit sagen wir mal . Das ist . Nun lässt sich auch so berechnen:

Dabei wird der Wert 7 niemals überschritten.

/* REXX-Programm */
say 'Only a Library!'
exit 1
/* */
/* */
m_u: procedure
  arg a,l,m
/* initialisierung */
  as = a
  ai = a
  li = (l-1)
  DO li
    a = a * ai
    a = a // m
  END
return a

Binäres Potenzieren

[Bearbeiten]

Für Primzahltests nach dem kleinen fermatsche Satz müssen große Potenzen berechnet werden; dabei wäre es extrem zeitaufwendig, xk durch k - 1 Multiplikationen zu berechnen. Ein effiziente Berechnung ist durch binäre Exponentiation möglich:

Gegeben seien die Basis x und der Exponent k.

Berechnungsschritte:
setze P = 1 (Produkt) und b = x
wiederhole folgende Schritte solange k > 0 ist:
wenn k ungerade ist,

multipliziere P mit b → P und vermindere k um 1 → k

P = P * b

k = k - 1

quadriere b → b b = b * b
halbiere k → k k = k / 2
Ergebnis: P = xk, wenn k = 0 ist

Bei Berechnung Modulo wird das Ergebnis jeder Multiplikation mod reduziert, wie im vorherigen Absatz beschrieben.

Insgesamt sind mit dieser Methode nur maximal 2 Multiplikationen pro Bit des Exponenten notwendig, also .

Liste zusammengesetzter Zahlen

[Bearbeiten]

Um Primzahltests zu prüfen bzw. Pseudoprimzahlen zu finden, wäre eine Funktion, die eine Liste (ungerader) zusammengesetzter Zahlen erstellt, nützlich. Sie spart zum einen die Überprüfung aller Zahlen, die den Test bestehen, mit einem im untersuchten Zahlenbereich sicheren Primzahltest, um Pseudoprimzahlen von Primzahlen zu unterscheiden, und zum anderen werden Primzahlen von vornherein nicht getestet.

Mit einem Algorithmus, der wie das Sieb des Eratosthenes funktioniert, lässt sich ein solches Hilfmittel realisieren:

  • Erstelle eine leere Menge für das Ergebnis
  • Für alle ungeraden n von 3 bis Obergrenze:
    • wenn n nicht in der Menge enthalten ist:
      • nimm alle ungeraden Vielfachen von n (n² + 2k*n) von n² bis zur Obergrenze in die Menge auf
  • Sortiere die Elemente der Menge aufsteigend

Implementierung in Python

[Bearbeiten]
def odd_composites(lim):
    result = set()
    for n in range(3, lim, 2):
        if n not in result:
            for m in range(n*n, lim, 2*n):
                result.add(m)
    return sorted(result)

Die Funktion lässt sich leicht so erweitern, dass auch gerade Zahlen zurückgegeben werden; diese sind aber für Primzahltests weniger interessant.

Fermatsche Pseudoprimzahlen

[Bearbeiten]

Bei Primzahlen ist im Gegensatz zu fermatschen Pseudoprimzahlen und Carmichael-Zahlen die Kongruenz für alle Basen mit erfüllt. Carmichael-Zahlen unterscheiden sich von anderen fermatschen Pseudoprimzahlen dadurch, dass der Anteil der Primbasen mit , für die ist, größer als 97% ist. Der Einfachheit halber benutzt man als Basen nur die Primzahlen, die kleiner als die zu testende Zahl sind. Das Programm testet also zu jeder Primbasis , ob eine Zahl die Bedingung erfüllt. Erfüllt sie sie, wird die Variable tm1 = 1 gesetzt und gleichzeitig die Zählvariable tm3 um eins erhöht. Erfüllt die Zahl die Bedingung nicht, wird die Variable tm2 = 2 gesetzt. Nach Ablauf der Tests wird die Variable gtm = tm1 + tm2 gesetzt. Aus gtm und dtm lässt sich ablesen, ob es sich bei der Zahl um eine Primzahl, eine fermatsche Pseudoprimzahl oder eine Carmichael-Zahl handelt.


gtm dtm Art der Zahl
1 - Primzahl
3 tm3 < dtm fermatsche Pseudoprimzahl
3 tm3 >= dtm Carmichael-Zahl


/* Ein Programm zur Ermittlung von Primzahlen, Pseudoprimzahlen */
/* und Carmichaelzahlen   */
/* Ein langsames Programm */

#include <stdio.h>

int primfeld[400000];
int tst[400000];

unsigned long modup(unsigned long base, unsigned long y)
{
  unsigned long exponent, product = 1;
  exponent = y-1;
  while (exponent)
  {
    /* wenn Exponent gerade ist, Basis quadrieren und Exponent halbieren bis der Exponent ungerade ist: */
    while (exponent & 1 == 0)
    {
      exponent >>= 1;
      base = (base * base) % y;
    }
    /* Exponent ungerade (immer nach obiger Schleife): Produkt *= Basis ... %= y, Exponent dekrementieren: */
    product = (product * base) % y;
    exponent--;
  }
  return(product);
} 

int main()
{
  unsigned long index, index2, anzp=1, m, dtm;
  int tm1, tm2, tm3, gtm;
  FILE *prim;
  FILE *pspr;
  FILE *cnbr;
  prim = fopen("prim.dat","w");
  pspr = fopen("pspr.dat","w");
  cnbr = fopen("cnbr.dat","w");
  primfeld[1] = 2;
  for(index=3;index<=4000000;index++)
  {
    tm1 = 0;
    tm2 = 0;
    tm3 = 0;
    /* faktor$ = "" */
    for(index2=1;index2<=anzp;index2++)
    {
      m = modup(primfeld[index2], index);
      tst[index2] = m;
      if (m == 1)
      {
        tm1 = 1;
        tm3++;
      }
      if ( m != 1) { tm2 = 2; }
    }
    gtm = tm1 + tm2;
    if (gtm == 1)
    {
      anzp++;
      primfeld[anzp] = index;
      fprintf(prim,"%d \n",index);
    }
    if (gtm == 3)
    {
      dtm=anzp/2;
      if (tm3 < dtm)
      {
        fprintf(pspr,"%d: ",index);
        for(index2=1;index2<=anzp;index2++)
        {
          m = modup(primfeld[index2], index);
          if (m == 1)
          {
            fprintf(pspr,"%d, ",primfeld[index2]);
          }
        }
        fprintf(pspr,"\n",0);
      }
      if (tm3 >= dtm)
      {
        fprintf(pspr,"%d: ",index);
        for(index2=1;index2<=anzp;index2++)
        {
          m = modup(primfeld[index2], index);
          if (m != 1)
          {
            fprintf(cnbr,"N%d, ",primfeld[index2]);
          }
        }
        fprintf(cnbr,"\n",0);
      }
    }
  }
  fclose(prim);
  fclose(pspr);
  fclose(cnbr);
  return 0;
}

Nachteil des Programms: Es wird schnell sehr langsam. Außerdem ist es für einige Pseudoprimzahlen blind. So gibt es keine Primzahlen , zu denen die 39 pseudoprim ist.

Der kleine Fermatsche Satz besagt, dass für jede Primzahlund jede natürliche Zahl durchteilbar ist.

Beispiel anhand der Primzahl 5:

Ableitungen

[Bearbeiten]

Statt der Aussage: " ist (ohne Rest) durch teilbar", kann man auch schreiben. Wenn man aus ausklammert, kommt man auf einen Ausdruck . Da durch teilbar ist, aber nicht zwangsläufig durch teilbar ist, muss es der Ausdruck sein, der immer durch teilbar ist. Aus der Aussage: " ist durch teilbar", kann man ableiten. Die Aussage: " ist durch teilbar" und die Formel gelten allerdings nur, wenn die Basis teilerfremd zur Primzahl ist.

Was unterscheidet an ≡ a (mod n) von an-1 ≡ 1 (mod n)

[Bearbeiten]

Für jede Primzahl gilt, dass für jede natürliche Zahl der Ausdruck durch teilbar ist. Ebenso gilt für jede Carmichael-Zahl , dass für jede natürliche Zahl der Ausdruck durch teilbar ist.

Ja aber bitte wie unterscheidet man dann eine Primzahl von einer Carmichael-Zahl?

Es gibt natürlich noch andere Wege, um das Problem anzugehen, aber dafür hilft auch eine Modifikation des kleinen Fermatschen Satzes:

Für jede Primzahl gilt: für jede natürliche Zahl , die teilerfremd zu ist.

Das bedeutet, dass der kleine fermatsche Satz für nicht gilt: . Ähnliches gilt für jede Carmichael-Zahl : . Aber es gilt genauso für alle Primteiler der entsprechenden Carmichael-Zahl : .

Folgerung durch Euler

[Bearbeiten]

Auf den kleinen Fermatschen Satz lässt sich die dritte binomische Formel anwenden:

.

Das bedeutet, dass genau einer der beiden Faktoren durch teilbar sein muss, dass also oder durch teilbar ist. Das führt zu dem Satz, der Leonhard Euler zugesprochen wird:

Wenn eine ungerade Primzahl ist, muss entweder

  • oder
  • gelten.


Potenzen

[Bearbeiten]

Wenn man eine Zahl immer wieder mit sich selbst multipliziert, erhält man eine Potenz. Eine bekannte Folge von steigenden Potenzen ist die folgende Folge aus Zweierpotenzen:

Verallgemeinert sieht eine solche Folge für eine beliebige Basis so aus:

Ein Feld solcher Zahlen sieht so aus:

n 1 2 3 4 5 6 7 8 9 ...
a
1 1 1 1 1 1 1 1 1 1 ...
2 2 4 8 16 32 64 128 256 512 ...
3 3 9 27 81 243 729 2187 6561 19683 ...
4 4 16 64 256 1024 4096 16384 65536 262144 ...
5 5 25 125 625 3125 15625 78125 390625 1953125 ...
6 6 36 216 1296 7776 46656 279936 1679616 10077696 ...
7 7 49 343 2401 16807 117649 823543 5764801 40353607 ...
8 8 64 512 4096 32768 262144 2097152 16777216 134217728 ...
9 9 81 729 6561 59049 531441 4782969 43046721 387420489 ...
10 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 ...
11 11 121 1331 14641 161051 1771561 19487171 214358881 2357947691 ...
12 12 144 1728 20736 248832 2985984 35831808 429981696 5159780352 ...
.. .. ... ... ... ... ... ... ... ... ...

Die Struktur, die dahinter steckt, wird sichtbar, wenn man das ganze Feld eine mithilfe von Modulo und einem festen Faktor unterzieht:

  • Beispiel: Modulo 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ...
1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
2: 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 ...
3: 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 ...
4: 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 ...
5: 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 ...
6: 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 ...
7: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
8: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
9: 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 ...
10: 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 ...
11: 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 ...
12: 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 ...
13: 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 ...
14: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
15: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
16: 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 ...
17: 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 ...
18: 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 ...
19: 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 ...
20: 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 ...
21: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

Die kleinste Einheit wird durch zwei Größen festgelegt, nämlich einmal den Wert , zu dem man das Ganze Modulo nimmt und der die Einheit nach unten begrenzt, und andererseits die Carmichael-Funktion , die der kleinste gemeinsame Faktor darstellt, zu der für jeden zu teilerfremden Wert gilt: .

Muster

[Bearbeiten]

Zu jeder natürlichen Zahl gibt es ein individuelles Erscheinungsbild. Andererseits haben bestimmte Arten von Zahlen Gemeinsamkeiten. Um das, was Zahlen gemeinsam haben, geht es hier:

natürliche Zahlen

[Bearbeiten]

Alle natürlichen Zahlen haben eine Gemeinsamkeit in ihrer Struktur:

1 2 3 4 5 6
1: 1 1 1 1 1 1
X: X X X X X X
X: X X X X X X
X: X X X X X X
X: X X X X X X
A: A 1 A 1 A 1

In der obersten Zeile befinden sich immer Einsen und in der untersten Zeile befinden sich immer im Wechsel A und 1, wobei A für steht. Dies ist also keine Charakteristik, die für Primzahlen typisch ist.

Primzahlen

[Bearbeiten]

Die für eine Primzahl typische Struktur sieht so aus:

1 2 3 4 5 6
1: 1 1 1 1 1 1
X: X X 1 X X 1
X: X X A X X 1
X: X X 1 X X 1
X: X X A X X 1
A: A 1 A 1 A 1

Zu der für jede natürliche Zahl typischen Zeilen kommen zwei Charaktaristika bei Primzahlen hinzu:

Erstens die geschlossene Einserspalte
1 1 1 ...

in blau gefärbt. Die Einser sind die Werte, welche die Carmichael-Funktion zurückliefert.

Zweitens die, ebenfalls geschlossene, Zeile aus Einsern und Zahlen A die die Zahl (n-1) repräsentieren.

1 A ...

Hier sind es die Werte, die die nach der nach Euler modifizierten Funktion zurückgeliefert werden.

Unterscheidung der Primzahlen in 4k-1 und 4k+1-Form

[Bearbeiten]

Die Struktur von Primzahlen der Form 4k-1 und 4k+1 unterscheidet sich in einer Spalte:

1 2 3 4 5 6 7 8 9 10
1: 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 5 10 9 7 3 6 1
3: 3 9 5 4 1 3 9 5 4 1
4: 4 5 9 3 1 4 5 9 3 1
5: 5 3 4 9 1 5 3 4 9 1
6: 6 3 7 9 10 5 8 4 2 1
7: 7 5 2 3 10 4 6 9 8 1
8: 8 9 6 4 10 3 2 5 7 1
9: 9 4 3 5 1 9 4 3 5 1
10: 10 1 10 1 10 1 10 1 10 1
1 2 3 4 5 6 7 8 9 10 11 12
1: 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 3 6 12 11 9 5 10 7 1
3: 3 9 1 3 9 1 3 9 1 3 9 1
4: 4 3 12 9 10 1 4 3 12 9 10 1
5: 5 12 8 1 5 12 8 1 5 12 8 1
6: 6 10 8 9 2 12 7 3 5 4 11 1
7: 7 10 5 9 11 12 6 3 8 4 2 1
8: 8 12 5 1 8 12 5 1 8 12 5 1
9: 9 3 1 9 3 1 9 3 1 9 3 1
10: 10 9 12 3 4 1 10 9 12 3 4 1
11: 11 4 5 3 7 12 2 9 8 10 6 1
12: 12 1 12 1 12 1 12 1 12 1 12 1
Primzahl der Form 4k+3 Primzahl der Form 4k+1

Wie man sehen kann, ist die violette Spalte bei Primzahlen der Form 4k+1 symmetrisch und bei Primzahlen der Form 4k+3 komplementär.

Abgrenzung der Primzahlen von anderen natürlichen Zahlen

[Bearbeiten]

Bei allen anderen Arten natürlicher Zahlen fehlt die Geschlossenheit der beiden senkrechten Spalten.

1 2 3 4 5 6
1: 1 1 1 1 1 1
2: 2 4 8 7 5 1
3: 3 0 0 0 0 0
4: 4 7 1 4 7 1
5: 5 7 8 4 2 1
6: 6 0 0 0 0 0
7: 7 4 1 7 4 1
8: 8 1 8 1 8 1
1 2 3 4
1: 1 1 1 1
2: 2 4 8 1
3: 3 9 2 6
4: 4 1 4 1
5: 5 10 5 10
6: 6 6 6 6
7: 7 4 13 1
8: 8 4 2 1
9: 9 6 9 6
10: 10 10 10 10
11: 11 1 11 1
12: 12 9 3 6
13: 13 4 7 1
14: 14 1 14 1
Neun Fünfzehn

Wie man bei der Neun sehen kann, ist der Mittelbalken noch, wenn auch unterbrochen, vorhanden. Bei der 15 fehlt er vollständig.

Carmichael-Zahlen

[Bearbeiten]

Nachdem was bisher geschrieben worden ist, müßte die Neun, und damit alle Quadrate einer Primzahl, eine perfekte Fast-Primzahl sein. Dem ist aber nicht so. Damit eine Nichtprimzahl eine gute Fast-Primzahl sein kann, muß eines zutreffen: muß durch teilbar sein. Nichtprimzahlen mit dieser Eigenschaft nennt man Carmichael-Zahlen.

Was stimmt nun also an der Neun nicht? Die Einser liegen auf der blauen und, mit den Achten, auf der violetten Spalte.

Sie müßten allerdings auf der grünen Spalte liegen, und zusammen mit Achten auf der cyanen Spalte. Da ist aber weder eine Eins, noch eine Acht vorhanden. Einsen auf der grünen Spalte sind typisch für fermatsche Pseudoprimzahlen, und Einsen, bzw. (n-1) auf der cyanen Spalte sind typisch für eulersche Pseudoprimzahlen.

1 2 3 4 5 6
1: 1 1 1 1 1 1
2: 2 4 8 7 5 1
3: 3 0 0 0 0 0
4: 4 7 1 4 7 1
5: 5 7 8 4 2 1
6: 6 0 0 0 0 0
7: 7 4 1 7 4 1
8: 8 1 8 1 8 1

Die weiter oben abgebildete 15 ist eine fermatsche Pseudoprimzahl zu den Basen 4 und 11.

Folgerichtig muß man die Struktur für eine typische Primzahl ergänzen:

1 2 3 4 5 6
1: 1 1 1 1 1 1
X: X X 1 X X 1
X: X X A X X 1
X: X X 1 X X 1
X: X X A X X 1
A: A 1 A 1 A 1

Pseudoprimzahlen

[Bearbeiten]

Selbstreferenzierende Spalte

[Bearbeiten]

Wie ja schon bekannt ist, gilt für eine Primzahl , das für jede zu teilerfremde Basis gilt (Siehe blaue Spalte in der unteren Tabelle).

1 2 3 4 5 6 7 8 9 10 11 12
1: 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 3 6 12 11 9 5 10 7 1
3: 3 9 1 3 9 1 3 9 1 3 9 1
4: 4 3 12 9 10 1 4 3 12 9 10 1
5: 5 12 8 1 5 12 8 1 5 12 8 1
6: 6 10 8 9 2 12 7 3 5 4 11 1
7: 7 10 5 9 11 12 6 3 8 4 2 1
8: 8 12 5 1 8 12 5 1 8 12 5 1
9: 9 3 1 9 3 1 9 3 1 9 3 1
10: 10 9 12 3 4 1 10 9 12 3 4 1
11: 11 4 5 3 7 12 2 9 8 10 6 1
12: 12 1 12 1 12 1 12 1 12 1 12 1

Nun ist aber keine Primzahl, sondern läßt sich in Faktoren zerlegen. So gilt für die unten stehende Tabelle für die Primzahl das ist, sich also z.B. in und zerlegen läßt. Das bedeutet, wenn sich ein Exponent in zwei Faktoren uns zerlegen läßt, das gilt.

Beispiele:

1 2 3 4 5 6 7 8 9 10 11 12
1: 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 3 6 12 11 9 5 10 7 1
3: 3 9 1 3 9 1 3 9 1 3 9 1
4: 4 3 12 9 10 1 4 3 12 9 10 1
5: 5 12 8 1 5 12 8 1 5 12 8 1
6: 6 10 8 9 2 12 7 3 5 4 11 1
7: 7 10 5 9 11 12 6 3 8 4 2 1
8: 8 12 5 1 8 12 5 1 8 12 5 1
9: 9 3 1 9 3 1 9 3 1 9 3 1
10: 10 9 12 3 4 1 10 9 12 3 4 1
11: 11 4 5 3 7 12 2 9 8 10 6 1
12: 12 1 12 1 12 1 12 1 12 1 12 1

pure eulersche Pseudoprimzahl

[Bearbeiten]

Mit der puren eulerschen Pseudoprimzahl ist eine fermatsche Pseudoprimzahl gemeint, bei der jede Basis, zu der die Zahl eine fermatsche Pseuodoprimzahl ist, auch gilt, das die Zahl zu der gleichen Basis auch eine eulersche Pseudoprimzahl ist.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 16 7 14 3 6 12 24 23 21 17 9 18 11 22 19 13 1
3: 3 9 2 6 18 4 12 11 8 24 22 16 23 19 7 21 13 14 17 1
4: 4 16 14 6 24 21 9 11 19 1 4 16 14 6 24 21 9 11 19 1
5: 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6: 6 11 16 21 1 6 11 16 21 1 6 11 16 21 1 6 11 16 21 1
7: 7 24 18 1 7 24 18 1 7 24 18 1 7 24 18 1 7 24 18 1
8: 8 14 12 21 18 19 2 16 3 24 17 11 13 4 7 6 23 9 22 1
9: 9 6 4 11 24 16 19 21 14 1 9 6 4 11 24 16 19 21 14 1
10: 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11: 11 21 6 16 1 11 21 6 16 1 11 21 6 16 1 11 21 6 16 1
12: 12 19 3 11 7 9 8 21 2 24 13 6 22 14 18 16 17 4 23 1
13: 13 19 22 11 18 9 17 21 23 24 12 6 3 14 7 16 8 4 2 1
14: 14 21 19 16 24 11 4 6 9 1 14 21 19 16 24 11 4 6 9 1
15: 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16: 16 6 21 11 1 16 6 21 11 1 16 6 21 11 1 16 6 21 11 1
17: 17 14 13 21 7 19 23 16 22 24 8 11 12 4 18 6 2 9 3 1
18: 18 24 7 1 18 24 7 1 18 24 7 1 18 24 7 1 18 24 7 1
19: 19 11 9 21 24 6 14 16 4 1 19 11 9 21 24 6 14 16 4 1
20: 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
21: 21 16 11 6 1 21 16 11 6 1 21 16 11 6 1 21 16 11 6 1
22: 22 9 23 6 7 4 13 11 17 24 3 16 2 19 18 21 12 14 8 1
23: 23 4 17 16 18 14 22 6 13 24 2 21 8 9 7 11 3 19 12 1
24: 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1
1 2 3 4 5 6 7 8 9 10
1: 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 16 32 31 29 25 17 1
3: 3 9 27 15 12 3 9 27 15 12
4: 4 16 31 25 1 4 16 31 25 1
5: 5 25 26 31 23 16 14 4 20 1
6: 6 3 18 9 21 27 30 15 24 12
7: 7 16 13 25 10 4 28 31 19 1
8: 8 31 17 4 32 25 2 16 29 1
9: 9 15 3 27 12 9 15 3 27 12
10: 10 1 10 1 10 1 10 1 10 1
11: 11 22 11 22 11 22 11 22 11 22
12: 12 12 12 12 12 12 12 12 12 12
13: 13 4 19 16 10 31 7 25 28 1
14: 14 31 5 4 23 25 20 16 26 1
15: 15 27 9 3 12 15 27 9 3 12
16: 16 25 4 31 1 16 25 4 31 1
17: 17 25 29 31 32 16 8 4 2 1
18: 18 27 24 3 21 15 6 9 30 12
19: 19 31 28 4 10 25 13 16 7 1
20: 20 4 14 16 23 31 26 25 5 1
21: 21 12 21 12 21 12 21 12 21 12
22: 22 22 22 22 22 22 22 22 22 22
23: 23 1 23 1 23 1 23 1 23 1
24: 24 15 30 27 21 9 18 3 6 12
25: 25 31 16 4 1 25 31 16 4 1
26: 26 16 20 25 23 4 5 31 14 1
27: 27 3 15 9 12 27 3 15 9 12
28: 28 25 7 31 10 16 19 4 13 1
29: 29 16 2 25 32 4 17 31 8 1
30: 30 9 6 15 21 3 24 27 18 12
31: 31 4 25 16 1 31 4 25 16 1
32: 32 1 32 1 32 1 32 1 32 1

Es gibt auch fermatsche Pseudoprimzahlen, bei denen die Pseudoprimzahl keine eulersche Pseudoprimzahl ist. Zu diesen fermatschen Pseudoprimzahlen zählen u.a. die 45, 91 und 153.


Eine Primzahl hat viele Eigenschaften, an denen man sie als Primzahl erkennen kann. Dementsprechend gibt es viele Verfahren, um eine Zahl auf ihre Primalität zu prüfen. Ein Teil dieser Verfahren ist 100-prozentig sicher, dafür aber auch unheimlich zeitaufwendig. Für Zahlen mit hundert und mehr Stellen würde ein Menschenleben nicht ausreichen, sie nach diesen Verfahren auf Primalität zu testen. Der andere Teil der Verfahren kann relativ schnell ein Ergebnis ausgeben, ob eine Zahl wahrscheinlich eine Primzahl ist, oder sicher keine. Dafür sind solche Verfahren aber für Pseudoprimzahlen anfällig. Dabei sind die Pseudoprimzahlen aber nicht von gleicher Qualität. Einige Pseudoprimzahlen lassen sich leicht ausschließen, dafür sind andere richtig hartnäckig:

Pseudoprimzahlen ,

  • die zu allen Basen , zu denen sie teilerfremd sind, fermatsche Pseudoprimzahlen sind (Carmichael-Zahlen).


  • Ich kenne von einer Pseudoprimzahl nur die Primzahlbasen zu denen die Pseudoprimzahl pseudoprim ist, möchte aber alle Basen bekommen, zu denen die Pseudoprimzahl pseudoprim ist, ohne jede natürliche Zahl zu testen.

Beispiel 65:

die Primzahlbasen (a<65) zur Pseudoprimzahl 65 sind 31, 47 und 53.

Demzufolge ist 65 auch zu allen Potenzen dieser Primzahlen pseudoprim:

n 31 mod 65 47 mod 65 53 mod 65
2 961 51 2209 64 2809 14
3 29791 21 103823 18 148877 27
4 923521 1 4789681 1 7890481 1

Damit haben wir als Basen (a<65), zu denen die Pseudoprimzahl 65 pseudoprim ist, die Zahlen 14, 18, 21, 27, 31, 47, 51, 53 und 64. Jetzt fehlen noch die Basen der Form (65 - a):

65 - 53 = 12; 65 - 51 = 14; 65 - 47 = 18; 65 - 31 = 34; 65 - 27 = 38; 65 - 21 = 44; 65 - 18 = 47; 65 - 14 = 51.

Nun haben wir alle Basen a mit a<65, zu denen die 65 Pseudoprim ist: 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53 und 64.

Halt: es fehlen noch 8 und 57.

Dieses Buch oder Kapitel bedarf einer Überarbeitung oder Erweiterung.

Dieser Baustein wurde gesetzt ohne eine Begründung anzugeben, schau in der Versionsgeschichte, wer ihn gesetzt hat und frage im Zweifel nach. Sollte der Baustein ohne Begründung gesetzt worden sein, kann er bei der nächsten Änderung der Seite entfernt werden.

Wenn du Lust hast, beteilige dich an der Verbesserung! Dort steht, wie es geht: Hilfe:Seiten bearbeiten. Beachte aber, ob jemand aktuell an der Seite arbeitet.

Offene Fragen bezüglich der Pseudoprimzahlen

1. Existiert eine Pseudoprimzahl, die keine fermatsche Pseudoprimzahl ist?

Diese Frage muß man aufspalten in mehrere Aspekte:

1.1. Existiert eine Pseudoprimzahl, die nicht gleichzeitig eine fermatsche Pseudoprimzahl ist?

1.2.a. Läßt sich jedes beliebige Kriterium aufgrund dessen Pseudoprimzahlen existieren, auf den kleinen fermatschen Satz zurückführen?

1.2.b. Gibt es ein noch stärkeres Kriterium, auf das sich der kleine fermatsche Satz zurückführen läßt und auf das sich noch andere Kriterien zurückführen lassen, die ansonsten aber keine Gemeinsamkeiten mit dem kleinen fermatschen Satz besitzen?


Anhänge
Geschichte
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen


Geschichte der Pseudoprimzahl

Der französische Amateurmathematiker Pierre de Fermat schreibt Mersenne, dass wenn eine Primzahl ist, die Zahl teilt. Fermat schrieb Mersenne auch, dass ein Beweis dieses Satzes zu lang wäre, als dass er ihm ihn zusenden könnte. Dieser Satz ist als kleiner fermatscher Satz bekannt geworden.

Sarrus findet mit der Zahl ein Beispiel, dass es auch zusammengesetzte Zahlen gibt, die den kleinen fermatschen Satz erfüllen. Diese Zahl wird auch Sarrus-Zahl genannt, und ist die kleinste zusammengesetzte Zahl, die den kleinen fermatschen Satz zur Basis 2 erfüllt.

Mitte 19. Jahrhundert

[Bearbeiten]

Der chinesische Mathematiker Li Shanlan (1811–1882) glaubte, für natürliche Zahlen , dass wenn durch teilbar ist, dieses eine Primzahl sein muss.[1] Ausmultipliziert erhält man die Formel .

Der böhmische Mathematiker Václav Šimerka veröffentlicht in Zbytky z arithmetické posloupnosti die ersten 7 Carmichael-Zahlen (diese Bezeichnung wurde erst einige Jahre später vergeben); die Veröffentlichung blieb weitgehend unbekannt, nachfolgende Entdeckungen dieser Zahlen können also als unabhängig angesehen werden.

Der deutsche Mathematiker Alwin Reinhold Korselt stellt das nach ihm benannte korseltsche Kriterium auf:

  1. Es existieren ungerade, quadratfreie natürliche Zahlen , so dass für alle natürlichen Zahlen ein Vielfaches von ist
  2. Für alle Primteiler von gilt, dass die Zahl teilt.

Der Mathematiker Malo, und ein Jahr später der Mathematiker Cipolla finden jeweils einen Beweis für die Existenz von unendlich vielen Pseudoprimzahlen.

Robert Daniel Carmichael findet mit 561 als erster eine Zahl, die dem korseltschen Kriterium genügt. Nach ihm werden Zahlen dieser Art Carmichael-Zahlen genannt. 561 ist die kleinste Carmichael-Zahl.

D.H Lehmer findet eine simple Methode, beliebig viele fermatsche Pseudoprimzahlen zu erzeugen:

Man nehme eine natürliche Zahl mit . Daraus ermittele man zwei natürliche Zahlen und , wobei ein Primfaktor von und ein Primfaktor von ist. Das Prdukt ist eine fermatsche Pseudoprimzahl.

J.Chernik macht die Bemerkung, dass das Produkt eine Carmichael-Zahl ist, wenn alle drei Faktoren Primzahlen sind.

N.G.W.H. Beeger führt den Begriff der Carmichael-Zahl ein. Ein Jahr später findet Beeger einen Beweis für die Existenz von unendlich vielen geraden Pseudoprimzahlen.

Die Mathematiker Alford, Granville und Pomerance finden einen Beweis für die Existenz von unendlich vielen Carmichael-Zahlen.


  1. en:w:Chinese hypothesis#History


Anhänge
Geschichte
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen


Robert Daniel Carmichael

[Bearbeiten]

(* 1. März 1879 in Goodwater, Alabama, USA, † 1967)

Michele Cipolla

[Bearbeiten]

(* 28. Oktober 1880 in Palermo, † 7. September 1947 in Palermo)

Leonhard Euler

[Bearbeiten]

(* 15. April 1707 in Riehen (Schweiz), † 18. September 1783 in St. Petersburg)

Pierre de Fermat

[Bearbeiten]

Pierre de Fermat (* Ende 1607 oder Anfang 1608 in Beaumont-de-Lomagne, † 12. Januar 1665 in Castres) war ein französischer Jurist und Amateurmathematiker. Seine besonderen Leistungen liegen in dem kleinen fermatschen Satz und dem großen fermatschen Satz - der Behauptung, dass es für keine ganzzahlige Lösung der Gleichung gibt. Diese Vermutung wurde erst Ende des 20. Jahrhunderts, also nach mehr als 300 Jahren, bewiesen. Auf Pierre de Fermat geht auch die Vermutung, dass alle Zahlen der Form Primzahlen sind. Diese Vermutung wurde 1732 von Leonhard Euler widerlegt. Nach Fermat heißt diese Art von Zahl Fermat-Zahl. Der deutsche Mathematiker Christian Goldbach verwendete die Fermat-Zahlen in seinem Beweis, dass es unendlich viele Primzahlen geben muss.

Alwin Reinhold Korselt

[Bearbeiten]

(* 17. März 1864 in Mittelherwigsdorf, † 4. Februar 1947 in Plauen)

Der deutsche Mathematiker Alwin Reinhold Korselt hat 1899 ein Kriterium für eine bestimmte Art von Pseudoprimzahlen aufgestellt, von denen er aber kein Exemplar finden konnte. Im Jahr 1910 veröffentlichte der Mathematiker Robert Daniel Carmichael die kleinste Zahl, auf die das Korselt-Kriterium zutrifft.

Anhänge
Geschichte
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen



Anhänge
Geschichte
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen


Formelsammlung

Um die Pseudoprimzahlen zu verstehen, muss man ein paar Dinge wissen.

Der kleine Fermatsche Satz

[Bearbeiten]

Für jede Primzahlund jede natürliche Zahl gilt

  • .

Für jede Primzahl und jede zu teilerfremde natürliche Zahl gilt

  • .

Kongruenz

[Bearbeiten]

Zwei Zahlen, die bei Division durch den gleichen Divisor den gleichen Modulo zurückliefern, sind zueinander kongruent. Bei Addition von ganzzahligen Vielfachen des Divisors bleibt die Kongruenz erhalten:

  • .

Eulersche φ-Funktion

[Bearbeiten]

Die Eulersche φ-Funktion gibt zu jeder natürlichen Zahl die Anzahl der zu teilerfremden Zahlen, die nicht größer als sind, an. Da die Eulersche φ-Funktion auch ein Vielfaches der Carmichael-Funktion ist, gilt für jedes zu teilerfremde .

Die Eulersche φ-Funktion wird wie folgt berechnet:

Satz von Euler

[Bearbeiten]

Carmichael-Funktion

[Bearbeiten]

Der Funktionswert der Carmichael-Funktion einer natürlichen Zahl ist die kleinste natürliche Zahl, mit der für jede zu teilerfremde Basis mit gilt: .

Die Carmichael-Funktion wird wie folgt berechnet:

Die allgemeinen Lucas-Folgen

[Bearbeiten]

Die beiden allgemeinen Lucas-Folgen und , deren jeweilige einzelne Glieder

und

sind, lassen sich aus der quadratischen Gleichung

ableiten, deren beide Lösungen

und sind.

Zwischen den Allgemeinen Lucas-Folgen und den Primzahlen gibt es einen Zusammenhang: Wenn die natürliche Zahl eine Primzahl ist, dann teilt sie für alle Folgen, deren und sind.

Wenn eine zusammengesetze Zahl ist, und trotzdem teilt, ist eine Pseudoprimzahl zu .

Beziehungen zwischen den Folgegliedern

[Bearbeiten]

Einige Beziehungen zwischen den Folgegliedern der allgemeinen Lucas-Folgen, der Fibonacci-Zahlen und der Lucas-Zahlen :[1]

Quellen

[Bearbeiten]
  1. en:w:Lucas_sequence#Other_relations


Anhänge
Geschichte
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen


Irrtümer zu Pseudoprimzahlen

Wer sich mit Pseudoprimzahlen beschäftigt, wird früher oder später in die eine oder andere Falle laufen. Stärker als bei den Primzahlen scheint man immer wieder auf Muster zu stoßen, die sich aber bei genauerer Prüfung sich in Luft auflösen. Um solche Irrtümer geht es hier.

Zu jeder fermatschen Pseudoprimzahl q existiert mindestens eine Primzahl p mit p kleiner als q, so daß q pseudoprim zu p ist

[Bearbeiten]

Die Zahl 39 ist ein Beispiel dafür, das dem nicht so ist. Denn die einzigen Zahlen kleiner 39, zu denen die 39 pseudoprim ist, sind die 14 und die 25. Die erste Primzahl zu der 39 pseudoprim ist, ist die 53.

Glossar

B

  • Beweis

G

  • Der größte gemeinsame Teiler (ggT) wird in Formeln als (greatest common divisor) dargestellt; in der Literatur wird er oft auch nur geschrieben.

M

  • Die multiplikative Ordnung einer positiven ganzen Zahl zu einer teilerfremden Basis ist der kleinste positive ganzzahlige Exponent , mit dem ist.

N

  • Natürliche Zahlen sind je nach Definition die nichtnegativen ganzen Zahlen oder die positiven ganzen Zahlen; als Mengensymbole werden dafür bzw. (ohne die 0) verwendet.

P

  • Primzahl
Eine Primzahl ist eine natürliche Zahl größer 1, die nur durch 1 und sich selber teilbar ist.

S

  • Symbole
Symbol Verwendung Interpretation Artikel
teilt w:Teilbarkeit
teilt exakt, d. h. teilt nicht
teilt nicht
und sind kongruent modulo w:Kongruenz (Zahlentheorie)
für alle w:Allquantor
es existiert mindestens ein w:Existenzquantor

U

  • Umkehrschluss

   

[Bearbeiten]
Legende
n,a - natürliche Zahlen
p - Primzahl
q - Pseudoprimzahl
c - Carmichael-Zahl
PsP(a) - fermatsche Pseudoprimzahl zur Basis a
ePsP(a) - eulersche Pseudoprimzahl zur Basis a
sPsP(a) - starke Pseudoprimzahl zur Basis a
lpsp - Lucas-Pseudoprimzahl
slpsp - starke Lucas-Pseudoprimzahl

   

[Bearbeiten]
Anhänge
Geschichte
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen



Anhänge
Geschichte
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen


Literatur

[Bearbeiten]

Internet

[Bearbeiten]