Zum Inhalt springen

Pseudoprimzahlen: Pseudoprimzahlen nach Lehmer

Aus Wikibooks

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