Eulersche Pseudoprimzahlen

Die Menge der Eulerschen Pseudoprimzahlen ist eine Teilmenge der fermatschen Pseudoprimzahlen.

Definition

Eine ungerade zusammengesetzte natürliche Zahl n wird Eulersche Pseudoprimzahl zur Basis a genannt, wenn a und n teilerfremd zueinander sind und entweder
an−12≡1mod  n a^{\frac{n-1}{2}} \equiv 1 \mod n
oder
an−12≡−1mod  na^{\frac{n-1}{2}} \equiv -1 \mod n bzw. an−12≡(n−1)mod  na^{\frac{n-1}{2}} \equiv (n-1) \mod n
gilt.

Die Eulersche Formel und der kleine Fermatsche Satz

Eine Eulersche Pseudoprimzahl ist auch eine Fermatsche Pseudoprimzahl
Aus
an−12⋅an−12=(an−12)2=a2⋅n−12=an−1a^{\frac{n-1}{2}} \cdot a^{\frac{n-1}{2}} = (a^{\frac{n-1}{2}})^2 = a^{2\cdot \frac{n-1}{2}} = a^{n-1}
und
1⋅1=(−1)⋅(−1)=1 1 \cdot 1 = (-1) \cdot (-1) = 1
folgt, dass wenn nn eine Eulersche Pseudoprimzahl ist, nn auch eine Fermatsche Pseudoprimzahl sein muss.
Da es aber auch möglich ist, dass es für an−12mod  na^{\frac{n-1}{2}} \mod n einen Rest gibt, der nicht 1 oder (n-1) ist, aber dennoch zum Quadrat als Rest ein 1mod  n1 \mod n zurückliefert, kann man nicht sagen, dass wenn nn eine Fermatsche Pseudoprimzahl ist, sie auch zwangsläufig eine Eulersche Pseudoprimzahl sein muss.

Eine Fermatsche Pseudoprimzahl muss keine Eulersche Pseudoprimzahl sein

Ein Beispiel für eine Fermatsche Pseudoprimzahl, die keine Eulersche Pseudoprimzahl ist, ist die Zahl 15:
1114≡1mod  1511^{14} \equiv 1 \mod 15
aber
117≡11mod  1511^7 \equiv 11 \mod 15
da 112=12111^2 = 121, und 121≡1mod  15121 \equiv 1 \mod 15 ist, ergibt sich daraus kein Widerspruch.

Arten von eulerschen Pseudoprimzahlen

Pseudoprimzahlen nach Fermat zur Basis 2 (Poulet-Zahl)

Eine Poulet-Zahl ist eine fermatsche Pseudoprimzahl zur Basis 2.
341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033
4369 4371 4681 5461 6601 7957 8321 8481 8911 10261 10585 11305 12801
13741 13747 13981 14491 15709 15841 16705 18705 18721 19951 23001 23377 25761
29341 30121 30889 31417 31609 31621 33153 34945 35333 39865 41041 41665 42799
46657 49141 49981 52633 55245 57421 60701 60787 62745 63973 65077 65281 68101
72885 74665 75361 80581 83333 83665 85489 87249 88357 88561 90751 91001 93961
101101 104653 107185 113201 115921 121465 123251 126217 129889 129921 130561 137149 149281
150851 154101 157641 158369 162193 162401 164737 172081 176149 181901 188057 188461 194221
196021 196093 204001 206601 208465 212421 215265 215749 219781 220729 223345 226801 228241
233017 241001 249841 252601 253241 256999 258511 264773 266305 271951 272251 272251 275887
Alle Pseudoprimzahlen nach Fermat zur Basis 2 (von 341 bis 275887). Die fett gedruckten Zahlen sind Carmichaelzahlen.
Die Zahl 341 als Pseudoprimzahl zur Basis 2 wurde 1819 von P.F.Sarrus entdeckt.
 
 

Im großen Garten der Geometrie kann sich jeder nach seinem Geschmack einen Strauß pflücken.

David Hilbert

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Eulersche Pseudoprimzahl aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Mehr über Primzahlen