Pseudoprimzahl

Zum Forum
Passwort vergessen? Noch keinen Account?

lexikon

Hauptseite

Zufälliger Artikel

Diskussion

Diskussion : Pseudoprimzahl

Links

Forum

Portale

Reisen

Versicherung

Inhaltsverzeichnis

Hauptmenü

Home

Bildung

Wissen

--------------------------

Reisen

Lexikon

Versicherung

Suchen

News

Treffpunkt

Chat

Forum

Suche

Schnellsuche

Sitemap

Kontakt

Impressum

Pseudoprimzahl

Stichpunkte

Allgemein
	selbst aber keine Primzahl ist
	natÃ¼rliche Zahl
	die gewisse Eigenschaften mit Primzahlen gemeinsam hat
	Eine Pseudoprimzahl ist eine zusammengesetzte
	Sie wird Pseudoprimzahl bezÃ¼glich dieser Eigenschaft genannt
	leitet sich vom kleinen Fermat-Satz ab
	Die bedeutendste Klasse von Pseudoprimzahlen
	um die sich dieser Artikel hauptsÃ¤chlich dreht
	Die entsprechenden Zahlen werden deshalb auch Fermatsche Pseudoprimzahlen genannt
	1904 7 Zeisel-Zahlen 8 Pseudoprimzahlen der Form (6n+1)*(12n+1) 9 Beweise fÃ¼r die Existenz unendlich vieler Pseudoprimzahlen 10 Weitere Pseudoprimzahlen 11 Liste von fermatschen Pseudoprimzahlen (mit ihren lÃ¼genden Primbasen) 12 Literatur 13 Weblinks [Bearbeiten]
	Eine echte Teilmenge der Fermatschen Pseudoprimzahlen sind die Carmichael-Zahlen. Inhaltsverzeichnis showTocToggle("Anzeigen"
	Carmichaelzahlen und Pseudoprimzahlen 4 Pseudoprimzahlen nach Fermat zur Basis 2 5 Eulersche Pseudoprimzahl 6 Pseudoprimzahlen zur Basis a nach Michele Cipolla
	"Verbergen") 1 Definition einer Pseudoprimzahl 1.1 Vorbemerkung zur Kongruenz und zum Modulo 1.2 Die Primzahl und der kleine Fermatsche Satz 1.2.1 Beispiel p = 5 1.3 Definition 1.3.1 Beispiel 1.4 Carmichael-Zahl 2 Die kleinsten Pseudoprimzahlen zu bestimmten Primbasen 3 Qualitative Unterschiede zwischen den Primzahlen
Definition einer Pseudoprimzahl
	[Bearbeiten]
Vorbemerkung zur Kongruenz und zum Modulo
	<math>a equiv b mod c<math> wird "a ist kongruent zu b in Bezug auf modulo von c" gesprochen. [Bearbeiten]
Die Primzahl und der kleine Fermatsche Satz
	dann gilt fÃ¼r alle a mit <math>2 le a < n<math>
	dass <math>a^{p-1} - 1 equiv 0 mod p<math> ist
	Aus dem kleinen Fermatschen Satz folgt: Wenn p eine Primzahl ist
	dann gilt fÃ¼r alle a mit <math>2 le a < n<math>
	dass <math>a^{p-1} - 1<math> durch p teilbar sein muÃŸ. [Bearbeiten]
	Oder anders ausgedrÃ¼ckt: Wenn p eine Primzahl ist
Beispiel p = 5
	2 <math>2^4 - 1 = 15<math> durch 5 teilbar 3 <math>3^4 - 1 = 80<math> durch 5 teilbar 4 <math>4^4 - 1 = 255<math> durch 5 teilbar [Bearbeiten]
Definition
	die aber keine Primzahl ist
	fÃ¼r die bei bestimmten Basen a mit <math>2 le a < n<math> gilt: <math>a^{n-1} equiv 1 mod n<math>
	Eine (Fermatsche) Pseudoprimzahl ist eine natÃ¼rliche Zahl n
	Man sagt zu diesen Zahlen auch: "n ist pseudoprim zur Basis a"
	das n eine Primzahl sei
	Umgekehrt gaukelt die Basis a vor
	obwohl sie es nicht ist
	Die Basis lÃ¼gt also. [Bearbeiten]
Beispiel
	23
	53
	43
	61 und 79) den kleinen Fermatschen Satz erfÃ¼llt
	17
	ist sie keine Primzahl. [Bearbeiten]
	FÃ¼r die Zahl 91 gilt: 17 <math>17^{90}-1 <math> ist durch 91 teilbar 29 <math>29^{90}-1 <math> ist durch 91 teilbar 61 <math>61^{90}-1 <math> ist durch 91 teilbar Obwohl die 91 fÃ¼r bestimmte a (3
	29
Carmichael-Zahl
	so dass fÃ¼r jede zu n teilerfremde Basis b mit <math>1 < b < n<math> gilt: <math>b^{n-1}-1 equiv 0 mod n<math>. [Bearbeiten]
	Eine Carmichael-Zahl ist eine solche Pseudoprimzahl n
Die kleinsten Pseudoprimzahlen zu bestimmten Primbasen
	Die kleinste Pseudoprimzahl ist die Zahl 15
	Sie ist pseudoprim zur Basis 11
	ist die 21
	Sie erfÃ¼llt allerdings nicht das Kriterium fÃ¼r Eulersche Pseudoprimzahlen. die auch das Kriterium fÃ¼r eine Eulersche Pseudoprimzahl erfÃ¼llt
	Sie ist pseudoprim zur Basis 13. zur Basis 3 ist die Zahl 91
	3 29341 2
	5
	5
	13 [Bearbeiten]
	3
	7
	Sie ist zu insgesamt 8 Primbasen pseudoprim. zur Basis 2 ist die Zahl 341. die sowohl zur Basis 2
	11
	als auch zur Basis 3 pseudoprim ist
	3
	11 162401 2
	ist die Zahl 2701. Beispiele fÃ¼r kleinste Pseudoprimzahlen kleinste Pseudoprimzahl zu den Basen 15 11 21 13 91 3 341 2 2701 2
	7
Qualitative Unterschiede zwischen den Primzahlen, Carmichaelzahlen und Pseudoprimzahlen
	Carmichael-Zahlen und Pseudoprimzahlen
	Es gibt Abstufungen zwischen den Primzahlen
	Diese Abstufungen kann man in Kriterien einteilen: FÃ¼r eine Zahl n gilt: F1
	FÃ¼r alle a mit <math>2 le a < n<math> gilt
	dass <math>a^{n-1} mod n = 1<math> ist. F2
	dass <math>a^{n-1} mod n = 1<math> ist. F3
	gilt
	FÃ¼r alle a mit <math>2 le a < n<math> und a teilerfremd zu n
	gilt
	dass <math>a^{n-1} mod n = 1<math> ist. E1
	FÃ¼r manche a mit <math>2 le a < n<math> und a teilerfremd zu n
	FÃ¼r alle a mit <math>2 le a < n<math> gilt
	dass <math>a^{frac{n-1}{2}} mod n = 1<math> oder <math>a^{frac{n-1}{2}} mod n = (n-1)<math> ist. E2
	FÃ¼r alle a mit <math>2 le a < n<math> und a teilerfremd zu n gilt
	dass <math>a^{frac{n-1}{2}} mod n = 1<math> oder <math>a^{frac{n-1}{2}} mod n = (n-1)<math> ist. E3
	dass <math>a^{frac{n-1}{2}} mod n = 1<math> oder <math>a^{frac{n-1}{2}} mod n = (n-1)<math> ist. L1
	FÃ¼r manche a mit <math>2 le a < n<math> und a teilerfremd zu n gilt
	dass <math>left(frac{a}{n}right) equiv a^{frac{n-1}{2}} mod n<math> ist. Primzahl F1
	FÃ¼r alle a mit <math>2 le a < n<math> gilt
	E1
	L1. Absolute Eulersche Pseudoprimzahl F2
	E2. Carmichael-Zahl F2
	E3. Pseudoprimzahl F3
	mehr Pseudoprimzahlen als Primzahlen
	E3. Es gibt
	absolut gesehen
	Die Mehrheit aller Pseudoprimzahlen ist allerdings nichts besonderes
	Die interessanteren Pseudoprimzahlen folgen jetzt. [Bearbeiten]
Pseudoprimzahlen nach Fermat zur Basis 2
	das die Basis a eine Primzahl sein muÃŸ)
	Im Gegensatz zu den Pseudoprimzahlen zur Basis a (nach Fermat)
	mit allen a<n (selbst mit der EinschrÃ¤nkung
	sind die Pseudoprimzahlen nach Fermat zur Basis 2 rar gesÃ¤t: 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. [Bearbeiten]
Eulersche Pseudoprimzahl
	wenn a und n teilerfremd zueinander sind und <math>left(frac{a}{n}right) = a^{frac{n-1}{2}} equiv 1 mod n<math> beziehungsweise <math>left(frac{a}{n}right) = a^{frac{n-1}{2}} equiv -1 mod n<math> gilt. [Bearbeiten]
	Eine ungerade zusammengesetzte natÃ¼rliche Zahl n wird Eulersche Pseudoprimzahl zur Basis a genannt
Pseudoprimzahlen zur Basis a nach Michele Cipolla, 1904
	n2 und n
	die <math>a(a^2-1)<math> nicht teilt
	FÃ¼r ein <math>a ge 2<math> und eine ungerade Primzahl p
	bekommt man mit <math>n_1=frac{a^p-1}{a-1} n_2=frac{a^p+1}{a+1} n=n_1n_2<math> drei Zahlen n1
	wobei n1 und n2 ungerade sind und n zusammengesetzt ist
	Aus <math>n_1 equiv 1 mod 2p <math> und <math> n_2 equiv 1 mod 2p<math> folgt
	dass auch <math>n equiv 1 mod 2p<math> ist. Aus <math>a^{2p} equiv 1 mod n<math> folgt
	dass <math>a^{n-1} equiv 1 mod n<math> ist
	so dass n eine Pseudoprimzahl zur Basis a sein muss
	muss es demnach auch unendlich viele Pseudoprimzahlen geben. a p n1 n2 n=n1n2 Faktoren 2 5 31 11 341 1131 2 7 127 43 5461 43127 3 5 121 61 7381 111161 3 7 1093 547 597871 5471093 2 11 2047 683 1398101 2389683 7 5 2801 2101 5884901 111912801 2 13 8191 2731 22369621 27318191 5 7 19531 13021 254313151 2944919531 13 5 30941 26521 809977861 11241130941 3 11 88573 44287 3922632451 23676613851 2 17 131071 43691 5726623061 43691131071 17 5 88741 78881 6999978821 117110188741 2 19 524287 174763 91625968981 174763524287 3 13 797161 398581 317733228541 398581797161 11 7 1948717 1623931 3164581946527 43453191623931 2 23 8388608 2796203 23456248059221 471784812796203 [Bearbeiten]
	Da es unendlich viele Primzahlen gibt
Zeisel-Zahlen
	Unter den Zeisel -Zahlen finden sich Pseudoprimzahlen: a b zn 1 2 105 357 1 6 1729 71319 2 3 1885 51329 3 2 4505 51753 2 5 5719 71943 2 9 24211 113171 [Bearbeiten]
*Pseudoprimzahlen der Form (6n+1)(12n+1)**
	scheinen die Pseudoprimzahlen der Form (6n+1)*(12n+1) eine besondere Bedeutung zu haben
	die der Form (6n+1)(12n+1)(18n+1) entsprechen
	Ã„hnlich den Carmichael-Zahlen nach Chernick
	93% 6 37 73 2701 393 191 48
	Abgesehen von den Carmichael-Zahlen
	60% 13 79 157 12403 1480 739 49
	die fÃ¤lschlicherweise den Anschein erwecken
	93% 16 97 193 18721 2137 1070 50
	07% ApP = Anzahl aller Primzahlen kleiner als (6n+1)(12n+1) AalP = Anzahl der lÃ¼genden Primzahlbasen * Primzahlen
	44% 5 31 61 1891 290 139 47
	33% 3 19 37 703 126 56 44
	die zu testende Zahl (6n+1)*(12n+1) sei eine Primzahl [Bearbeiten]
	haben sie die meisten Primbasen: n 6n+112n+1(6n+1)*(12n+1)AaP AalP Ratio 1 7 13 91 24 8 33
Beweise fÃ¼r die Existenz unendlich vieler Pseudoprimzahlen
	Beweis von E
	Malo 1903 Beweis von Michele Cipolla 1904 [Bearbeiten]
Weitere Pseudoprimzahlen
	Euler-jacobische Pseudoprimzahlen Euler-Jacobi-Pseudoprimzahlen zur Basis 2 Euler-Jacobi-Pseudoprimzahlen zur Basis 3 Extrastarke lucassche Pseudoprimzahlen fibonaccische Pseudoprimzahlen frobeniussche Pseudoprimzahlen lucassche Pseudoprimzahlen perrinsche Pseudoprimzahlen Somer-lucassche Pseudoprimzahlen Starke frobeniussche Pseudoprimzahlen Starke lucassche Pseudoprimzahlen Starke Pseudoprimzahlen [Bearbeiten]
Liste von fermatschen Pseudoprimzahlen (mit ihren lÃ¼genden Primbasen)
	wikisource:Pseudoprime_numbers bis 15.000 inklusive der lÃ¼genden Primbasen wikisource:Euler pseudoprime_numbers bis 15.000 inklusive der lÃ¼genden Primbasen [Bearbeiten]
Literatur
	Februar 1983 S
	Carl Pomerance: The Search for Prime Numbers in: Scientific American
	December 1982 Carl Pomerance: Primzahlen im Schnelltest in: Spektrum der Wissenschaft
	ISBN 0-387-94457-5 [Bearbeiten]
	Springer Verlag 1996
	80-92. (Es handelt sich um die Ãœbersetzung des vorerwÃ¤hnten Artikels) mit Foto eines Nachbaus von Lehmers Fahrradkettencomputers von 1926! The New Book of Prime Number Records
	Paolo Ribenboim
Weblinks
	Vorlage:Wikisource1 Final Answers Modular Arithmetic (http://home.att.net/~numericana/answer/modular.htm) ErgÃ¤nzungen und IrrtÃ¼mer (http://www.utm.edu/research/primes/notes/errata/) zu dem Buch "The new Book of Prime Number Records" von Paolo Ribenboim en:Pseudoprime fr:Nombre pseudopremier sl:PsevdopraÅ¡tevilo zh:ä¼ªç´ æ•°

[X] Schliessen

Dieser Artikel basiert auf dem Artikel Pseudoprimzahl aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.

Donatien Alphonse Francois Marquis de Sade Roxy Music Mijailo Mijailovic Nalanda Marienheide in Deutschland.png Leitungsgebundene Telekommunikationsverfahren Softwarepiraterie Szenarien BfA

[ Zurück ]

Inhalt Lexikon:

Allgemein

Definition einer Pseudoprimzahl

Vorbemerkung zur Kongruenz und zum Modulo

Die Primzahl und der kleine Fermatsche Satz

Beispiel p = 5

Definition

Beispiel

Carmichael-Zahl

Die kleinsten Pseudoprimzahlen zu bestimmten Primbasen

Qualitative Unterschiede zwischen den Primzahlen, Carmichaelzahlen und Pseudoprimzahlen

Pseudoprimzahlen nach Fermat zur Basis 2

Eulersche Pseudoprimzahl

Pseudoprimzahlen zur Basis a nach Michele Cipolla, 1904

Zeisel-Zahlen

Pseudoprimzahlen der Form (6n+1)*(12n+1)

Beweise fÃ¼r die Existenz unendlich vieler Pseudoprimzahlen

Weitere Pseudoprimzahlen

Liste von fermatschen Pseudoprimzahlen (mit ihren lÃ¼genden Primbasen)

Literatur

Weblinks