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.

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   
  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  .
  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.


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.

  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.

  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 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:  .

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 Primzahl und 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]

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