Pseudoprimzahlen: Die fermatsche Pseudoprimzahl im allgemeinen

Aus Wikibooks

An diesem Kapitel wird gerade gearbeitet. Bitte keine Änderungen vornehmen oder vorher kurz Verbindung mit dem gerade aktiven Autor aufnehmen: Arbol01 16:42, 31. Jul 2006 (UTC).
Hinweis: Dieser Vermerk muss nicht beachtet werden, wenn die Unterschrift schon älter als einen Tag ist.

Pseudoprimzahlen

Inhaltsverzeichnis

1 Die fermatsche Pseudoprimzahl im allgemeinen
2 Ein paar Daten zu den fermatschen Pseudoprimzahlen
3 Die fermatsche Pseudoprimzahl
- 3.1 Wie man, bei Kenntnis einer Basis zu einer fermatschen Pseudoprimzahl, weitere Basen findet

[Bearbeiten] Die fermatsche Pseudoprimzahl im allgemeinen

Wie Ende des vorherigen Kapitels erwähnt ist, sind fermatsche Pseudoprimzahlen zusammengesetzte Zahlen $q\$ , für die gilt, daß $q\$ den Ausdruck $a q - a$ teilt, wobei $a\$ größer, oder aber wenigstens gleich, 2 sein muß. Abgesehen von den Dreierpotenzen, also 3; 9; 27; 81; 243; 729; ... , sind alle ungeraden, zusammengesetzten Zahlen, fermatsche Pseudoprimzahlen. Bei den geraden, zusammengesetzen Zahlen sieht das noch ein wenig anders als. Dort gibt es mehr zusammengesetzte Zahlen, die keine Fermatschen Pseudoprimzahlen sind.

[Bearbeiten] Ein paar Daten zu den fermatschen Pseudoprimzahlen

Zu jeder Basis $a \ge 2$ gibt es eine kleinste fermatsche Pseudoprimzahl. In der folgenden Tabelle sind die kleinsten Pseudoprimzahlen bis zur Basis 121 aufgeführt:

Die kleinste fermatsche Pseudoprimzahl zur Basis a
a	fpsp	a	fpsp	a	fpsp	a	fpsp	a	fpsp	a	fpsp
2:	341	22:	69	42:	205	62:	91	82:	91	102:	133
3:	91	23:	33	43:	77	63:	341	83:	105	103:	133
4:	15	24:	115	44:	65	64:	85	84:	415	104:	145
5:	124	25:	28	45:	76	65:	112	85:	129	105:	451
6:	35	26:	45	46:	133	66:	91	86:	145	106:	133
7:	25	27:	65	47:	65	67:	85	87:	91	107:	133
8:	21	28:	45	48:	91	68:	91	88:	91	108:	341
9:	28	29:	35	49:	66	69:	85	89:	99	109:	117
10:	33	30:	49	50:	119	70:	169	90:	623	110:	259
11:	15	31:	49	51:	65	71:	105	91:	115	111:	190
12:	65	32:	93	52:	85	72:	65	92:	105	112:	121
13:	21	33:	85	53:	65	73:	111	93:	301	113:	133
14:	39	34:	55	54:	265	74:	91	94:	121	114:	205
15:	341	35:	51	55:	63	75:	91	95:	141	115:	133
16:	51	36:	91	56:	95	76:	105	96:	133	116:	195
17:	45	37:	45	57:	65	77:	247	97:	105	117:	145
18:	25	38:	65	58:	133	78:	341	98:	153	118:	121
19:	45	39:	95	59:	87	79:	91	99:	145	119:	177
20:	57	40:	91	60:	341	80:	169	100:	153	120:	187
21:	55	41:	105	61:	91	81:	85	101:	175	121:	133

Wenn man nun alle Pseudoprimzahlen aus der Tabelle, unter der Weglassung der doppelten Pseudoprimzahlen auflistet, bekommt man folgende Folge:

 15,  21,  25,  28,  33,  35,  39,  45,  49,  51,  55,  57,  63,  65,  66,  69,  76,  77,  85,  87,  91,  93,  95,  99,
105, 111, 112, 115, 117, 119, 121, 124, 129, 133, 141, 145, 153, 169, 175, 177, 187, 190, 195, 205, 247, 259, 265, 301,
341, 415, 451, 623

Das sind 52 Zahlen. Zum Vergleich: Bis 10 existieren 4 Primzahlen, hier sind es 0 Pseudoprimzahlen; bis 100 sind es 25 Primzahlen, hier sind es 24 Pseudoprimzahlen; bis 1000 sind es 168 Primzahlen, hier sind es 52. Allerdings muß man zugestehen, das noch gar nicht alle Pseudoprimzahlen berücksichtigt werden konnten. Wie aber verhält sich die Verteilung der Pseudoprimzahlen nun wirklich? Gibt es innerhab bestimmter Grenzen mehr Pseudoprimzahlen als Primzahlen, oder verhält es sich umgekehrt?

Dabei muß man Unterscheiden. Meint man die fermatschen Pseudoprimzahlen zu einer bestimmten Basis $a\$ , so sind es, in definierten Grenzen, weniger Pseudoprimzahlen als Primzahlen:

Basis	Fermatsche Pseudoprimzahlen
2	341, 561, 645, 949, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, ...
3	91, 121, 286, 671, 703, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, ...
4	15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, ...
5	124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5611, 5662, 5731, 7449, 7813, 8029, ...
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, ...
7	25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, ...
8	21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, ...
9	28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, ...
10	33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, ...

Meint man dagegen die Menge aller fermatschen Pseudoprimzahlen, die zu irgendeiner Basis $a \ge 2$ pseudoprim ist, dann gibt es, in definierten Grenzen mehr Pseudoprimzahlen als Primzahlen:

  15    21    25    28    33    35    39    49    51    52    55    57    63    65    66    69    70    75
  76    77    85    87    91    93    95    99   105   111   112   115   117   119   121   123   124   125
 129   130   133   135   141   143   145   147   148   153   154   155   159   161   165   169   171   172
 175   176   177   183   185   186   187   189   190   195   196   201   203   205   207   208   209   213
 215   217   219   221   225   231   232   235   237   238   244   245   246   247   249   253   255   259
 261   265   267   268   273   275   276   279   280   285   286   287   289   291   292   295   297   299
 301   303   304   305   309   310   315   316   319   321   322   323   325   327   329   333   335   339
 341

Wenn man sich jetzt unterschiedliche fermatsche Pseudoprimzahlen anschaut

[Bearbeiten] Die fermatsche Pseudoprimzahl

Eine zusammengesetzte Zahl $q\$ gilt dann als fermatsche Pseudoprimzahl, wenn es mindestens eine natürliche Zahl $a\$ mit $\operatorname{ggT}(a,q) = 1$ gibt, so dass für $a\$ und $q\$ gilt: $a^{q-1} \equiv 1 \mod q$ .

Beispiel:

$15 = 3 \cdot 5$ ist eine zusammengesetze Zahl

$4^{15-1}\$	$\equiv 1 \mod 15$
$11^{15-1}\$	$\equiv 1 \mod 15$

[Bearbeiten] Wie man, bei Kenntnis einer Basis zu einer fermatschen Pseudoprimzahl, weitere Basen findet

Natürlich gibt es zu einer fermatschen Pseudoprimzahl $q\$ niemals nur eine Basis $a\$ , zu der $q\$ pseudoprim ist.

Das läßt sich an einer Pseudoprimzahl, sagen wir beispielsweise mal 21, zeigen:

Die 21 ist pseudoprim zur Basis 13 pseudoprim.

Wenn eine ungerade, fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ pseudoprim ist, so ist $q\$ auch zu der Basis $(q - a)\$ pseudoprim.

Da 21 pseudoprim zur 13 ist, ist 21 auch pseudoprim zu (21-13) = 8.

Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ pseudoprim ist, so ist $q\$ auch zu der Basis $a^n\$ mit einer natürlichen Zahl $n \ge 1\$ pseudoprim.

Da 21 pseudoprim zu 8 und 13 ist, ist 21 auch zu $8^2=64, \ 13^2=169, \ 8^3=512, \ 13^3=2197, \ ...\$ pseudoprim.

Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis der Form $a^n\$ mit $n \ge 1\$ pseudoprim ist, so ist $q\$ auch pseudoprim zu $a^n \mod q\$ mit $n \ge 1\$

An diesem Kapitel wird gerade gearbeitet. Bitte keine Änderungen vornehmen oder vorher kurz Verbindung mit dem gerade aktiven Autor aufnehmen: Arbol01 16:42, 31. Jul 2006 (UTC).
Hinweis: Dieser Vermerk muss nicht beachtet werden, wenn die Unterschrift schon älter als einen Tag ist.

Pseudoprimzahlen: Die fermatsche Pseudoprimzahl im allgemeinen

Aus Wikibooks

Inhaltsverzeichnis

[Bearbeiten] Die fermatsche Pseudoprimzahl im allgemeinen

[Bearbeiten] Ein paar Daten zu den fermatschen Pseudoprimzahlen

[Bearbeiten] Die fermatsche Pseudoprimzahl

[Bearbeiten] Wie man, bei Kenntnis einer Basis zu einer fermatschen Pseudoprimzahl, weitere Basen findet

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Mitmachen

Werkzeuge

Drucken/exportieren