This site is supported by donations to The OEIS Foundation.
User:Karsten Meyer/Fermat pseudoprimes
Contents
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 |