This site is supported by donations to The OEIS Foundation.

User:Karsten Meyer/Fermat pseudoprimes

From OeisWiki
Jump to: navigation, search

Squarefree, composite, odd numbers with exactly 2 distinct prime factors

This is the easiest way to construct a fermat pseudoprime. You take two different odd prime numbers, and get the product of them. For example you take 7 and 23. The product is . is your fermat pseudoprime. But to which bases is 161 a fermat pseudoprime? To get two bases, you collect every multiple of 7 and 23 between 1 and 161:

7: 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105, 112, 119, 126, 133, 140, 147, 154, 161
23: 23, 46 69, 92, 115, 138, 161

Then you look for Numbers with the difference of 2:

23 and 21 have a difference of two, and so have 140 and 138. There is no other pair of numbers with the difference of 2. No matter which two different odd primes you take, you will get only two pairs of numbers with the difference of two.

With the two pairs of number you have nearly the two bases. The bases are the numbers, which lay in the middle of each pair of number. So 161 is a fermat pseudprime to base 22 and to base 139.

Numbers of the form (6n+1)*(12n+1), where (6n+1) and (12n+1) are prime numbers

Zeisel numbers

Fermat pseudoprimes after Lehmer

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

Example

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

Fermat pseudoprimes to base a after Michele Cipolla

Michele Cipolla hat 1904 ein Verfahren zum Erzeugen beliebiger fermatscher Pseudoprimzahlen zu einer beliebigen, natürlichen Basis gefunden. Dazu benötigt man eine Primzahl, die nicht teilt. Warum, das wird weiter unten erklärt.

Mit der Basis und der Primzahl werden zwei Zahlen und erzeugt:

Das Produkt ist eine fermatsche Pseudoprimzahl zur Basis

Erklärung

Die Bedingung, das teilerfremd zu sein soll, kann auch so formuliert werden: soll eine Primzahl sein, die nicht teilt. ist nichts anderes als die dritte Binomische Formel: . Damit ist sichergestellt, das zu , und teilerfremd ist.

und sind beides geometrische Reihen, nämlich:

und


Aus und

folgt, dass auch ist.

Aus

folgt, dass ist,

so dass n eine Pseudoprimzahl zur Basis a sein muss. Da es unendlich viele Primzahlen gibt, muss es demnach auch unendlich viele Pseudoprimzahlen geben.

eine Liste fermatscher Pseudoprimzahlen zur zur Basis a nach Michele Cipolla

a p n1 n2 n=n1*n2 Faktoren
2 5 31 11 341 11*31
2 7 127 43 5461 43*127
3 5 121 61 7381 11*11*61
3 7 1093 547 597871 547*1093
2 11 2047 683 1398101 23*89*683
7 5 2801 2101 5884901 11*191*2801
2 13 8191 2731 22369621 2731*8191
5 7 19531 13021 254313151 29*449*19531
13 5 30941 26521 809977861 11*2411*30941
3 11 88573 44287 3922632451 23*67*661*3851
2 17 131071 43691 5726623061 43691*131071
17 5 88741 78881 6999978821 11*71*101*88741
2 19 524287 174763 91625968981 174763*524287
3 13 797161 398581 317733228541 398581*797161
11 7 1948717 1623931 3164581946527 43*45319*1623931
2 23 8388608 2796203 23456248059221 47*178481*2796203