Zum Inhalt springen

Pseudoprimzahlen: Fermatsche Pseudoprimzahlen

Aus Wikibooks

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

Für jede Primzahl gilt also

mit  

und

, wenn kein Vielfaches von ist. (1)


Definition

[Bearbeiten]

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

.  


  • Beispiel:
ist eine zusammengesetze Zahl

Anzahl der Basen

[Bearbeiten]

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

Mit der Faktorisierung

 

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

.[1]  

Eigenschaften

[Bearbeiten]

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

Zusammenhänge zwischen den Basen

[Bearbeiten]

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

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

Die 21 ist pseudoprim zur Basis 8.

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

Teiler

[Bearbeiten]

Für alle Primteiler einer Fermatschen Pseudoprimzahl gilt

  • und damit
  • ,

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



Ein paar Daten zu den fermatschen Pseudoprimzahlen

[Bearbeiten]

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

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

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

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

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

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

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

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

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

Quellen

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