Pseudoprimzahlen: Pseudoprimzahlen nach Lehmer

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Nuvola apps bookcase 1.svg Pseudoprimzahlen

Über das folgende Verfahren hat der Mathematiker Lehmer gezeigt, das unendlich viele fermatsche Pseudoprimzahlen existieren müssen:

Man nimmt eine natürliche Zahl , die größer, oder auch gleich Fünf ist. Mit dieser Zahl bildet man die beiden Zahlen und . Von diesen beider Zahlen nimmt man jeweils einen Primfaktor. Also je eine Primzahl und , so daß gilt: teilt und teilt . Das Produkt ist dann eine fermatsche Pseudoprimzahl zur Basis .

Beispiel[Bearbeiten]

Man nimmt als die Zahl 6. und . Wenn man sich jetzt als 7 wählt und als 5, dann bekommt man mit die fermatsche Pseudoprimzahl 35.

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