Pseudoprimzahlen: Pseudoprimzahlen nach Lehmer

Pseudoprimzahlen

Mit folgendem Verfahren hat der Mathematiker Lehmer gezeigt, dass unendlich viele fermatsche Pseudoprimzahlen existieren müssen:

Man nimmt eine natürliche Zahl $k$, die größer oder gleich 5 ist. Mit dieser Zahl $k\$ bildet man die beiden Zahlen $2^{k}-1\$ und $2^{k}+1$. Von diesen beiden Zahlen nimmt man jeweils einen Primfaktor. Also je eine Primzahl $p\$ und $q$, so dass 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}$.

Beispiel

Man nimmt $k=6$: $2^{k}\pm 1$ ist dann $2^{6}-1=63=3^{2}\cdot 7$ und $2^{6}+1=65=5\cdot 13$. Wenn man jetzt $p=7\$ und $q=5\$ wählt, bekommt man mit $5\cdot 7$ 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
...	...	...	...