Hintergrund
Pseudoprimzahl zur Basis a
Eine a-PRP Zahl war entweder eine Primzahl oder nicht. Den zusammengesetzten a-PRP Zahlen geben wir nun einen Namen:
Definition: eine a-PRP Zahl heisst pseudoprim zur Basis a, wenn sie zusammengesetzt ist.
Beispiel: 341 ist eine 2-PRP, denn 2341-1 = 1 (mod 341). Aber 341 = 11 * 31, also zusammengesetzt. Wir sagen 341 ist pseudoprim zur Basis 2.
Zum Glück für den FERMATschen Primzahltest sind die Pseudoprimzahlen eher selten. Unter den ersten 1000 natürlichen Zahlen gibt es nur drei Pseudoprimzahlen zur Basis 2:
341, 561 und 645
Und es gibt nur 245 Pseudoprimzahlen unterhalb von 10^6. In der folgenden Tabelle sind die ersten Pseudoprimzahlen für die Basen von 2 bis 9 eingetragen.
| Basis | Pseudoprimzahlen | OEIS |
| 2 | 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ... | A001567 |
| 3 | 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ... | A005935 |
| 4 | 15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, ... | A020136 |
| 5 | 4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ... | A005936 |
| 6 | 35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713, 6533, 6601, 8029, 8365, 8911, 9331, 9881, ... | A005937 |
| 7 | 6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ... | A005938 |
| 8 | 9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, ... | A020137 |
| 9 | 4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, ... | A020138 |
Wie man sieht, gibt es nach unserer Definition auch gerade Pseudoprimzahlen. Auf der Suche nach Primzahlen, spielen gerade Zahlen >2 natürlich keine Rolle. Manche Autoren nehmen deshalb gerade Zahlen auch aus der Definition von Pseudoprimzahlen heraus.
Fassen wir zusammen:
Pseudoprimzahlen sind relativ selten. Darauf basiert der FERMATsche Primzahltest.