Pseudoprimzahl
Eine Pseudoprimzahl ist eine zusammengesetzte natürliche Zahl, die gewisse Eigenschaften mit Primzahlen gemeinsam hat, selbst aber keine Primzahl ist. Sie wird Pseudoprimzahl bezüglich dieser Eigenschaft genannt. Da es viele Möglichkeiten für solche Eigenschaften gibt, ist der Begriff Pseudoprimzahl ohne Angabe der Eigenschaft nicht sinnvoll.
Ein historisch bedeutendes Beispiel einer Pseudoprimzahl ist die Zahl <math>341 = 11 \cdot 31</math>. Sie ist eine Fermatsche Pseudoprimzahl zur Basis <math>2</math> (und auch einigen anderen Basen).
Hintergrund
Pseudoprimzahlen sind aus dem Bedürfnis entstanden, Algorithmen zu finden, die zuverlässig sagen können, ob eine Zahl eine Primzahl ist oder nicht (siehe Fermatscher Primzahltest, Lucas-Test, Solovay-Strassen-Test und Miller-Rabin-Test). Da diese Algorithmen nicht perfekt sind, bekommt man auch Zahlen, die keine Primzahlen sind, sich aber dennoch, auf einen speziellen Algorithmus bezogen, wie Primzahlen verhalten. Um die Algorithmen zur Primzahlsuche zu optimieren, werden auch diese Pseudoprimzahlen genauer untersucht.
Eine bedeutende Klasse von Pseudoprimzahlen leitet sich vom kleinen Fermat-Satz ab. Die entsprechenden Zahlen werden deshalb auch Fermatsche Pseudoprimzahlen genannt.
Arten von Pseudoprimzahlen
Fermatsche Pseudoprimzahlen
{{#if: Fermatsche Pseudoprimzahl|{{#ifexist:Fermatsche Pseudoprimzahl|
|{{#if: |{{#ifexist:{{{2}}}|
|{{#if: |{{#ifexist:{{{3}}}|
|}}|}}|}}|}}|}}|Einbindungsfehler: Die Vorlage Hauptartikel benötigt immer mindestens ein Argument.}}
Nach dem kleinen Satz von Fermat gilt für jede Primzahl <math>p</math> für jede zu <math>p</math> teilerfremde Basis <math>a</math>, dass <math>a^{p-1} \equiv 1 \mod p</math> ist.
Eine zusammengesetzte natürliche Zahl <math>n</math> wird Fermatsche Pseudoprimzahl zur Basis <math>a</math> genannt, wenn <math>a</math> und <math>n</math> teilerfremd zueinander sind und die gleiche Kongruenz wie bei einer Primzahl erfüllt ist:
- <math>a^{n-1} \equiv 1 \mod n</math>
Das erste Beispiel wurde 1819 von Sarrus gefunden: Die Zahl <math>2^{341-1}-1</math> ist durch <math>341</math> teilbar, obwohl <math>341 = 11\cdot31</math> zusammengesetzt ist.
Verwandte der Fermatschen Pseudoprimzahlen
Zu den Fermatschen Pseudoprimzahlen gehören die Carmichael-Zahlen, Eulerschen Pseudoprimzahlen und die starken Pseudoprimzahlen.
- Carmichael-Zahl:
- Eine Carmichael-Zahl ist eine fermatsche Pseudoprimzahl <math>n</math>, für die für jede zu <math>n</math> teilerfremde Basis <math>a</math> mit <math>1<a<n</math> gilt:
- <math>a^{n-1} \equiv 1 \mod n</math>
- Eine Carmichael-Zahl ist eine fermatsche Pseudoprimzahl <math>n</math>, für die für jede zu <math>n</math> teilerfremde Basis <math>a</math> mit <math>1<a<n</math> gilt:
- Eulersche Pseudoprimzahl:
- Eine ungerade zusammengesetzte natürliche Zahl <math>n</math> wird Eulersche Pseudoprimzahl zur Basis a genannt, wenn <math>a</math> und <math>n</math> teilerfremd zueinander sind und
- <math>a^{\frac{n-1}{2}} \equiv \pm 1 \mod n</math>
- gilt.
- Jede eulersche Pseudoprimzahl zur Basis <math>a</math> ist eine fermatsche Pseudoprimzahl zur gleichen Basis.
- Eine ungerade zusammengesetzte natürliche Zahl <math>n</math> wird Eulersche Pseudoprimzahl zur Basis a genannt, wenn <math>a</math> und <math>n</math> teilerfremd zueinander sind und
- Starke Pseudoprimzahl:
- Eine ungerade zusammengesetzte natürliche Zahl <math>n = d \cdot 2^s+1</math> wird starke Pseudoprimzahl zur Basis <math>a</math> genannt, wenn
- <math>a^d \equiv 1 \mod n</math>
- oder
- <math>a^{d \cdot 2^r} \equiv -1 \mod n</math>
- für ein <math>r</math> mit <math>0 \le r < s</math> gilt.
- Jede starke Pseudoprimzahl zur Basis <math>a</math> ist eine eulersche Pseudoprimzahl zur gleichen Basis.
- Eine ungerade zusammengesetzte natürliche Zahl <math>n = d \cdot 2^s+1</math> wird starke Pseudoprimzahl zur Basis <math>a</math> genannt, wenn
Perrinsche Pseudoprimzahlen
Die rekursiv definierte Perrin-Folge hat die Eigenschaft, dass für jede Primzahl <math>p</math> das <math>p</math>-te Folgenglied <math>P_p</math> durch <math>p</math> teilbar ist. Perrinsche Pseudoprimzahlen sind natürliche Zahlen <math>n</math>, für die das <math>n</math>-te Glied Pn durch <math>n</math> teilbar ist, obwohl <math>n</math> zusammengesetzt ist. Die kleinste Perrinsche Pseudoprimzahl ist <math>271441 = 521^2</math>.
Mersenne-Pseudoprimzahlen
Mersenne-Zahlen sind Vorgänger von 2er-Potenzen. So ist die <math>n</math>-te Mersenne-Zahl <math>M_n</math> wie folgt:
<math>M_n = 2^n - 1</math>
Eine Mersenne-Zahl, die zugleich auch eine Primzahl ist, nennt man Mersenne-Primzahl; allerdings kann eine Mersenne-Zahl <math>M_n = 2^n - 1</math> nur dann eine Primzahl sein, wenn <math>n</math> eine Primzahl ist.
Mersenne-Pseudoprimzahlen sind diejenigen Mersenne-Zahlen der Form <math>M_n = 2^n - 1</math>, die für die für ein primes <math>n</math> zusammengesetzt sind; <math>n</math> ist eine Primzahl, jedoch ist<math>M_n</math> ist eine zusammengesetzte Zahl.
Die kleinste Mersenne-Pseudoprimzahl ist <math>M_{11} = 2^{11} - 1 = 2047 = 23 \cdot 89</math>.
Weitere Pseudoprimzahlen
- Euler-Jacobische Pseudoprimzahlen
- Fibonaccische Pseudoprimzahlen, Lucassche Pseudoprimzahlen, Somer-Lucassche Pseudoprimzahlen und starke Lucassche Pseudoprimzahlen
- Frobeniussche Pseudoprimzahlen und starke Frobeniussche Pseudoprimzahlen
Literatur
- Paul Erdős und Carl Pomerance: On the Number of False Witnesses for a Composite Number. Mathematics of Computation 46, 259–279, 1986.
- Carl Pomerance: The Search for Prime Numbers. Scientific American 12/1982.
Deutsche Übersetzung: Primzahlen im Schnelltest. Spektrum der Wissenschaft 02/1983. Mit Foto eines Nachbaus von Lehmers Fahrradkettencomputer von 1926. - Carl Pomerance: Computational Number Theory. In: Timothy Gowers (Hrsg.): The Princeton companion to mathematics. S. 348–362, Princeton University Press, 2008 (online; PDF; 249 kB).
- Paulo Ribenboim: The New Book of Prime Number Records. Springer-Verlag, 1996.
Weblinks
|1|= – Lern- und Lehrmaterialien |0|-= |X|x={{#switch: 0
|0|4|10|12|14|100=}}
|#default= – {{{suffix}}}
}}{{#if: | ({{#invoke:Multilingual|format|{{{lang}}}|slang=!|shift=m}}) }}{{#invoke:TemplatePar|check
|opt= 1= 2= lang= suffix= |template=Vorlage:Wikibooks |cat=Wikipedia:Vorlagenfehler/Schwesterprojekt }}
- Pseudoprimzahlen. Bei: mathe-schule.de. (PDF; 89 kB).
- Final Answers. Modular Arithmetic. Bei: numericana.com.