Pseudoprimzahlen: Pseudoprimzahlen nach Lehmer

Aus Wikibooks

Wechseln zu: Navigation, Suche
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 k\ , die größer, oder auch gleich Fünf ist. Mit dieser Zahl k\ bildet man die beiden Zahlen 2^k-1\ und 2^k+1\ . Von diesen beider Zahlen nimmt man jeweils einen Primfaktor. Also je eine Primzahl p\ und q\ , so daß gilt: p\ teilt 2^k-1\ und q\ teilt 2^k+1\ . Das Produkt p\cdot q ist dann eine fermatsche Pseudoprimzahl zur Basis 2^k\ .

[Bearbeiten] Beispiel

Man nimmt als k\ die Zahl 6. 2^6-1 = 63 = 3^2\cdot 7 und 2^6+1 = 65 = 5\cdot 13. Wenn man sich jetzt als p\ 7 wählt und als q\ 5, dann bekommt man mit 5\cdot 7 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
... ... ... ...
Von „http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Pseudoprimzahlen_nach_Lehmer“
Persönliche Werkzeuge