Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 25. Oktober 2014 

Pseudoprimzahl


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Dieser Artikel enthält mathematische Symbole die der Tabelle mit mathematischen Symbolen erklärt werden.


Eine Pseudoprimzahl ist eine zusammengesetzte natürliche Zahl die gewisse Eigenschaften mit Primzahlen gemeinsam selbst aber keine Primzahl ist. Sie wird Pseudoprimzahl bezüglich dieser genannt.

Die bedeutendste Klasse von Pseudoprimzahlen leitet vom Kleinen Fermatschen Satz ab. Die entsprechenden werden deshalb Fermatsche Pseudoprimzahlen genannt. Eine echte der Fermatschen Pseudoprimzahlen sind die Carmichael-Zahlen .

Inhaltsverzeichnis

Pseudoprimzahl Definition

Eine (Fermatsche) Pseudoprimzahl ist eine natürliche Zahl  n für die bei bestimmten Basen  b mit

<math>b \ge 2</math> gilt: <math>b^{n-1}-1 \equiv 0 n</math>
die aber keine Primzahl ist. Man sagt zu diesen Zahlen " n ist pseudoprim zur Basis  b ".

Die kleinste Pseudoprimzahl ist die Zahl Sie ist pseudoprim zur Basis 11. Die Pseudo-Primzahl zur Basis 2 ist die Zahl
Eine Carmichael-Zahl ist eine solche Pseudoprimzahl  n das für jede zu  n teilerfremde Basis  b mit <math>1 < b < n</math> <math>b^{n-1}-1 \equiv 0 \mod n</math>.

Beispiele

kleinste Pseudoprimzahl zu den Basen
15 11
341 2
2701 2 3
29341 2 3 5 7 11
162401 2 3 5 7 11 13

Liste aller Pseudoprimzahlen bis 1729 1

Es gibt absolut gesehen mehr Pseudoprimzahlen Primzahlen. Die Mehrheit aller Pseudoprimzahlen ist allerdings besonderes. Die unten stehende Tabelle steht als stellvertretend für die Gesamtheit aller Pseudoprimzahlen. Die Pseudoprimzahlen werden weiter unten behandelt.

15 21 25 33 35 45 49 52 57 65 66 69 70 77 85 87 91 93 99
105 111 117 121 123 124 130 133 135 143 145 147 148 153 154 155 159 161 165
169 171 175 176 185 186 187 190 195 205 208 217 221 225 231 237 238 244 245
246 247 249 255 259 261 265 267 268 273 275 276 285 286 287 289 291 292 297
301 305 310 315 316 322 325 329 333 335 339 341 343 344 345 351 357 361 363
364 365 366 369 370 371 375 377 385 388 391 393 396 399 403 405 406 412 415
417 418 425 426 427 429 430 435 436 437 441 445 448 451 455 459 465 469 471
475 477 481 483 485 493 495 496 505 506 507 511 513 519 525 527 529 532 533
537 539 545 549 553 555 556 559 561 565 568 573 581 585 589 592 595 597 598
603 604 605 606 609 615 616 625 627 629 633 635 637 638 645 646 649 651 652
657 663 665 670 671 676 679 682 685 687 688 689 693 697 699 700 703 705 711
715 717 721 724 725 726 730 735 741 742 745 749 753 754 759 763 765 772 775
777 781 782 785 786 790 793 795 801 803 804 805 806 813 817 819 825 826 833
836 837 841 843 844 845 847 855 861 865 867 868 871 873 874 875 879 885 889
891 895 897 901 903 904 905 906 909 910 913 916 921 925 931 945 946 949 952
957 959 961 965 969 970 973 975 976 981 985 987 988 993 994 999 1001 1005 1011
1015 1016 1017 1023 1025 1027 1030 1035 1036 1037 1044 1045 1053 1055 1056 1057 1065 1066 1068
1071 1073 1075 1077 1078 1085 1086 1090 1095 1099 1101 1102 1105 1106 1107 1111 1113 1116 1120
1121 1125 1128 1131 1132 1133 1136 1137 1141 1145 1146 1147 1155 1157 1159 1161 1162 1165 1166
1173 1175 1177 1179 1183 1185 1189 1195 1197 1204 1205 1209 1215 1216 1221 1222 1225 1228 1233
1235 1239 1240 1241 1245 1246 1247 1251 1252 1257 1258 1261 1265 1267 1270 1271 1273 1275 1276
1281 1285 1288 1293 1295 1300 1305 1309 1311 1313 1315 1317 1325 1329 1330 1333 1335 1339 1341
1349 1351 1353 1355 1357 1365 1369 1377 1378 1385 1386 1387 1390 1391 1393 1395 1403 1405 1407
1411 1413 1414 1417 1419 1425 1426 1431 1435 1441 1443 1444 1445 1446 1449 1450 1455 1456 1462
1463 1465 1469 1473 1476 1477 1480 1485 1491 1492 1495 1496 1497 1501 1505 1506 1510 1513 1515
1516 1517 1519 1521 1525 1527 1533 1535 1537 1539 1541 1545 1547 1548 1551 1552 1558 1561 1562
1565 1573 1575 1576 1581 1585 1586 1588 1591 1593 1595 1599 1603 1605 1606 1611 1612 1615 1617
1624 1625 1626 1629 1630 1631 1635 1636 1641 1643 1645 1647 1648 1649 1651 1653 1655 1659 1661
1665 1672 1675 1681 1683 1684 1685 1686 1687 1688 1690 1695 1702 1705 1708 1716 1717 1725 1729
fett Carmichel-Zahlen
grün Quadratzahlen
rot Pseudoprimzahlen der Form p 1 *p 2 *p 3
(1) Für alle aufgeführten Pseudoprimzahlen n das sie mindestens zu einer beliebigen Primzahl für die 1 < p < n
pseudoprim sind.

Pseudoprimzahlen nach Fermat zur Basis 2

Im Gegensatz zu den Pseudoprimzahlen zur a (nach Fermat) mit allen a<n (selbst der Einschränkung das die Basis a eine Primzahl sein muß) sind die 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 341 bis 275887). Die fett gedruckten Zahlen sind Carmichaelzahlen .

Die Zahl 341 als Pseudoprimzahl zur 2 wurde 1819 von P.F.Sarrus entdeckt.

Eulersche Pseudoprimzahl

Eine ungerade zusammengesetzte natürliche Zahl n Eulersche Pseudoprimzahl zur Basis a genannt wenn und n teilerfremd zueinander sind und

<math>\left(\frac{a}{n}\right) = a^{\frac{n-1}{2}} \equiv 1 \mod beziehungsweise <math>\left(\frac{a}{n}\right) = a^{\frac{n-1}{2}} \equiv -1 \mod gilt.

Berechnet wird dabei das Jacobi-Symbol von a und n .

Pseudoprimzahlen zur Basis a nach M. Cipolla 1904

 Für ein <math>a \ge 2</math> und ungerade Primzahl  p  die <math>a(a^2-1)</math> nicht teilt bekommt man  
<math>n_1=\frac{a^p-1}{a-1} \ \ n_2=\frac{a^p+1}{a+1} \ \ n=n_1n_2</math>
 drei Zahlen n 1  n 2  und n wobei n 1  und n 2  ungerade sind und n zusammengesetzt ist. 
Aus <math>n_1 \equiv 1 \mod 2p und \ n_2 \equiv 1 \mod 2p</math> das auch <math>n \equiv 1 \mod 2p</math>
Aus <math>a^{2p} \equiv 1 \mod n</math> daß <math>a^{n-1} \equiv 1 \mod n</math> ist das n eine Pseudoprimzahl zur Basis a muß. Da es unendlich viele Primzahlen gibt es demnach auch unendlich viele Pseudoprimzahlen geben.

a p n 1 n 2 n=n 1 *n 2 Faktoren
2 5 31 11 341 11*31
2 7 127 43 5461 43*127
3 5 121 61 7381 11*11*61
3 7 1093 547 597871 547*1093
2 11 2047 683 1398101 23*89*683
7 5 2801 2101 5884901 11*191*2801
2 13 8191 2731 22369621 2731*8191
5 7 19531 13021 254313151 29*449*19531
13 5 30941 26521 809977861 11*2411*30941
3 11 88573 44287 3922632451 23*67*661*3851
2 17 131071 43691 5726623061 43691*131071
17 5 88741 78881 6999978821 11*71*101*88741
2 19 524287 174763 91625968981 174763*524287
3 13 797161 398581 317733228541 398581*797161
11 7 1948717 1623931 3164581946527 43*45319*1623931
2 23 8388608 2796203 23456248059221 47*178481*2796203

Beweise für die Existenz unendlich vieler

  • Beweis von E. Malo 1903
  • Beweis von M. Cipolla 1904

Weitere Pseudoprimzahlen

  • Eulersche Pseudoprimzahlen
  • Eulersche Pseudoprimzahlen zur Basis 2
  • Euler-Jacobische Pseudoprimzahlen
  • Euler-Jacobi Pseudoprimzahlen zur Basis 2
  • Euler-Jacobi Pseudoprimzahlen zur Basis 3
  • Extrastarke Lucas'sche Pseudoprimzahlen
  • Fibonaccische Pseudoprimzahlen
  • Frobenius'sche Pseudoprimzahlen
  • Lucas'sche Pseudoprimzahlen
  • Perrinsche Pseudoprimzahlen
  • Somer-Lucas'sche Pseudoprimzahlen
  • Starke Frobenius'sche Pseudoprimzahlen
  • Starke Lucas'sche Pseudoprimzahlen
  • Starke Pseudoprimzahlen



Bücher zum Thema Pseudoprimzahl

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Pseudoprimzahl.html">Pseudoprimzahl </a>