www.wikidata.de-de.nina.az

Pseudoprimzahl Eine ist eine zusammengesetzte natürliche Zahl die gewisse Eigenschaften mit Primzahlen gemeinsam hat sel

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 . Sie ist eine Fermatsche Pseudoprimzahl zur Basis (und auch einigen anderen Basen).

Hintergrund Bearbeiten

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 Bearbeiten

Fermatsche Pseudoprimzahlen Bearbeiten

Nach dem kleinen Satz von Fermat gilt für jede Primzahl für jede zu teilerfremde Basis , dass ist.

Eine zusammengesetzte natürliche Zahl wird Fermatsche Pseudoprimzahl zur Basis genannt, wenn und teilerfremd zueinander sind und die gleiche Kongruenz wie bei einer Primzahl erfüllt ist:

Das erste Beispiel wurde 1819 von Sarrus gefunden: Die Zahl ist durch teilbar, obwohl zusammengesetzt ist.

Verwandte der fermatschen Pseudoprimzahlen Bearbeiten

Zu den Fermatschen Pseudoprimzahlen gehören die Carmichael-Zahlen, Eulerschen Pseudoprimzahlen und die starken Pseudoprimzahlen.

  • Carmichael-Zahl:
  • Eulersche Pseudoprimzahl:
    gilt.
    Jede eulersche Pseudoprimzahl zur Basis ist eine fermatsche Pseudoprimzahl zur gleichen Basis.
  • Starke Pseudoprimzahl:
    oder
    für ein mit gilt.
    Jede starke Pseudoprimzahl zur Basis ist eine eulersche Pseudoprimzahl zur gleichen Basis.

Perrinsche Pseudoprimzahlen Bearbeiten

Die rekursiv definierte Perrin-Folge hat die Eigenschaft, dass für jede Primzahl das -te Folgenglied durch teilbar ist. Perrinsche Pseudoprimzahlen sind natürliche Zahlen , für die das -te Glied Pn durch teilbar ist, obwohl zusammengesetzt ist. Die kleinste Perrinsche Pseudoprimzahl ist .

Weitere Pseudoprimzahlen Bearbeiten

Literatur Bearbeiten

  • 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 Bearbeiten

Wikibooks: Pseudoprimzahlen – Lern- und Lehrmaterialien
Primzahl­mengen


formelbasiert

Carol ((2n − 1)2 − 2) | Doppelte Mersenne (22p − 1 − 1) | Fakultät (n! ± 1) | Fermat (22n + 1) | Kubisch (x3 − y3)/(x − y) | Kynea ((2n + 1)2 − 2) | Leyland (xy + yx) | Mersenne (2p − 1) | Mills (A3n) | Pierpont (2u⋅3v + 1) | Primorial (pn# ± 1) | Proth (k⋅2n + 1) | Pythagoreisch (4n + 1) | Quartisch (x4 + y4) | Thabit (3⋅2n − 1) | Wagstaff ((2p + 1)/3) | Williams ((b-1)⋅bn − 1) | Woodall (n⋅2n − 1)

Primzahlfolgen

Bell | Fibonacci | Lucas | Motzkin | Pell | Perrin

eigenschaftsbasiert

Elitär | Fortunate | Gut | Glücklich | Higgs | Hochkototient | Isoliert | Pillai | Ramanujan | Regulär | Stark | Stern | Wall–Sun–Sun | Wieferich | Wilson

basis­abhängig

Belphegor | Champernowne | Dihedral | Einzigartig | Fröhlich | Keith | Lange | Minimal | Mirp | Permutierbar | Primeval | Palindrom | Repunit-Primzahl ((10n − 1)/9) | Schwach | Smarandache–Wellin | Strobogrammatisch | Tetradisch | Trunkierbar | Zirkular

basierend auf Tupel

Ausbalanciert (p − n, p, p + n) | Chen | Cousin (p, p + 4) | Cunningham (p, 2p ± 1, …) | Drilling (p, p + 2 oder p + 4, p + 6) | Konstellation | Sexy (p, p + 6) | Sichere (p, (p − 1)/2) | Sophie Germain (p, 2p + 1) | Vierling (p, p + 2, p + 6, p + 8) | Zwilling (p, p + 2) | Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)

nach Größe

Titanisch (1.000+ Stellen) | Gigantisch (10.000+ Stellen) | Mega (1.000.000+ Stellen) | Beva (1.000.000.000+ Stellen)

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine Pseudoprimzahl ist eine zusammengesetzte naturliche Zahl die gewisse Eigenschaften mit Primzahlen gemeinsam hat selbst aber keine Primzahl ist Sie wird Pseudoprimzahl bezuglich dieser Eigenschaft genannt Da es viele Moglichkeiten fur solche Eigenschaften gibt ist der Begriff Pseudoprimzahl ohne Angabe der Eigenschaft nicht sinnvoll Ein historisch bedeutendes Beispiel einer Pseudoprimzahl ist die Zahl 341 11 31 displaystyle 341 11 cdot 31 Sie ist eine Fermatsche Pseudoprimzahl zur Basis 2 displaystyle 2 und auch einigen anderen Basen Inhaltsverzeichnis 1 Hintergrund 2 Arten von Pseudoprimzahlen 2 1 Fermatsche Pseudoprimzahlen 2 2 Verwandte der fermatschen Pseudoprimzahlen 2 3 Perrinsche Pseudoprimzahlen 3 Weitere Pseudoprimzahlen 4 Literatur 5 WeblinksHintergrund BearbeitenPseudoprimzahlen sind aus dem Bedurfnis entstanden Algorithmen zu finden die zuverlassig sagen konnen 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 BearbeitenFermatsche Pseudoprimzahlen Bearbeiten Hauptartikel Fermatsche Pseudoprimzahl Nach dem kleinen Satz von Fermat gilt fur jede Primzahl p displaystyle p nbsp fur jede zu p displaystyle p nbsp teilerfremde Basis a displaystyle a nbsp dass a p 1 1 mod p displaystyle a p 1 equiv 1 mod p nbsp ist Eine zusammengesetzte naturliche Zahl n displaystyle n nbsp wird Fermatsche Pseudoprimzahl zur Basis a displaystyle a nbsp genannt wenn a displaystyle a nbsp und n displaystyle n nbsp teilerfremd zueinander sind und die gleiche Kongruenz wie bei einer Primzahl erfullt ist a n 1 1 mod n displaystyle a n 1 equiv 1 mod n nbsp Das erste Beispiel wurde 1819 von Sarrus gefunden Die Zahl 2 341 1 1 displaystyle 2 341 1 1 nbsp ist durch 341 displaystyle 341 nbsp teilbar obwohl 341 11 31 displaystyle 341 11 cdot 31 nbsp zusammengesetzt ist Verwandte der fermatschen Pseudoprimzahlen Bearbeiten Zu den Fermatschen Pseudoprimzahlen gehoren die Carmichael Zahlen Eulerschen Pseudoprimzahlen und die starken Pseudoprimzahlen Carmichael Zahl Eine Carmichael Zahl ist eine fermatsche Pseudoprimzahl n displaystyle n nbsp fur die fur jede zu n displaystyle n nbsp teilerfremde Basis a displaystyle a nbsp mit 1 lt a lt n displaystyle 1 lt a lt n nbsp gilt a n 1 1 mod n displaystyle a n 1 equiv 1 mod n nbsp dd Eulersche Pseudoprimzahl Eine ungerade zusammengesetzte naturliche Zahl n displaystyle n nbsp wird Eulersche Pseudoprimzahl zur Basis a genannt wenn a displaystyle a nbsp und n displaystyle n nbsp teilerfremd zueinander sind unda n 1 2 1 mod n displaystyle a frac n 1 2 equiv pm 1 mod n nbsp dd gilt Jede eulersche Pseudoprimzahl zur Basis a displaystyle a nbsp ist eine fermatsche Pseudoprimzahl zur gleichen Basis Starke Pseudoprimzahl Eine ungerade zusammengesetzte naturliche Zahl n d 2 s 1 displaystyle n d cdot 2 s 1 nbsp wird starke Pseudoprimzahl zur Basis a displaystyle a nbsp genannt wenna d 1 mod n displaystyle a d equiv 1 mod n nbsp dd odera d 2 r 1 mod n displaystyle a d cdot 2 r equiv 1 mod n nbsp dd fur ein r displaystyle r nbsp mit 0 r lt s displaystyle 0 leq r lt s nbsp gilt Jede starke Pseudoprimzahl zur Basis a displaystyle a nbsp ist eine eulersche Pseudoprimzahl zur gleichen Basis Perrinsche Pseudoprimzahlen Bearbeiten Die rekursiv definierte Perrin Folge hat die Eigenschaft dass fur jede Primzahl p displaystyle p nbsp das p displaystyle p nbsp te Folgenglied P p displaystyle P p nbsp durch p displaystyle p nbsp teilbar ist Perrinsche Pseudoprimzahlen sind naturliche Zahlen n displaystyle n nbsp fur die das n displaystyle n nbsp te Glied Pn durch n displaystyle n nbsp teilbar ist obwohl n displaystyle n nbsp zusammengesetzt ist Die kleinste Perrinsche Pseudoprimzahl ist 271441 521 2 displaystyle 271441 521 2 nbsp Weitere Pseudoprimzahlen BearbeitenEuler Jacobische Pseudoprimzahlen Fibonaccische Pseudoprimzahlen Lucassche Pseudoprimzahlen Somer Lucassche Pseudoprimzahlen und starke Lucassche Pseudoprimzahlen Frobeniussche Pseudoprimzahlen und starke Frobeniussche PseudoprimzahlenLiteratur BearbeitenPaul Erdos 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 Ubersetzung 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 Bearbeiten nbsp Wikibooks Pseudoprimzahlen Lern und Lehrmaterialien Pseudoprimzahlen Bei mathe schule de PDF 89 kB Final Answers Modular Arithmetic Bei numericana com V DPrimzahl mengenformelbasiert Carol 2n 1 2 2 Doppelte Mersenne 22p 1 1 Fakultat n 1 Fermat 22n 1 Kubisch x3 y3 x y Kynea 2n 1 2 2 Leyland xy yx Mersenne 2p 1 Mills A3n Pierpont 2u 3v 1 Primorial pn 1 Proth k 2n 1 Pythagoreisch 4n 1 Quartisch x4 y4 Thabit 3 2n 1 Wagstaff 2p 1 3 Williams b 1 bn 1 Woodall n 2n 1 Primzahlfolgen Bell Fibonacci Lucas Motzkin Pell Perrineigenschaftsbasiert Elitar Fortunate Gut Glucklich Higgs Hochkototient Isoliert Pillai Ramanujan Regular Stark Stern Wall Sun Sun Wieferich Wilsonbasis abhangig Belphegor Champernowne Dihedral Einzigartig Frohlich Keith Lange Minimal Mirp Permutierbar Primeval Palindrom Repunit Primzahl 10n 1 9 Schwach Smarandache Wellin Strobogrammatisch Tetradisch Trunkierbar Zirkularbasierend auf Tupel Ausbalanciert p n p p n Chen Cousin p p 4 Cunningham p 2p 1 Drilling p p 2 oder p 4 p 6 Konstellation Sexy p p 6 Sichere p p 1 2 Sophie Germain p 2p 1 Vierling p p 2 p 6 p 8 Zwilling p p 2 Zwillings Bi Kette n 1 2n 1 nach Grosse Titanisch 1 000 Stellen Gigantisch 10 000 Stellen Mega 1 000 000 Stellen Beva 1 000 000 000 Stellen Abgerufen von https de wikipedia org w index php title Pseudoprimzahl amp oldid 237090874