Pseudoprimzahlen: Meta: Überblick


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:

Wenn eine Primzahl und größer als 3 ist,
  • dann hat die Form   oder   (das gilt für alle ungeraden Zahlen)
  • dann hat die Form   oder   (ungerade und nicht durch 3 teilbar)
  • dann teilt jede Zahl der Form   mit  
  • dann teilt den Ausdruck  , wobei  das p.te Glied der Lucas-Folge ist.
  • dann teilt das 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 Primzahl und jede natürliche Zahl  durch teilbar 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 Primteiler einer 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 Primteiler einer 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 Primteiler einer 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

Weblinks 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 Primzahl und jede natürliche Zahl  durch teilbar 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