Schwache Primzahlen engl Weakly Prime Numbers oder auch Digitally Delicate Prime 1 sind Primzahlen die bei Modifikation des Wertes von genau einer ihrer Dezimalstellen immer ihre Primzahl Eigenschaft verlieren Als schwache Primzahlen engl Weak Prime werden aber im Gegensatz zu starken Primzahlen engl Strong Prime zur Schlusselgenerierung in asymmetrischen Verschlusselungsverfahren ungeeignete Primzahlen bezeichnet Inhaltsverzeichnis 1 Beispiele 2 Eigenschaften 3 Schwache Primzahlen in beliebigen Zahlensystemen 4 Beispiele von schwachen Primzahlen in anderen Zahlensystemen 5 Eigenschaften von schwachen Primzahlen in anderen Zahlensystemen 6 Ahnliche Konstrukte 7 Weblinks 8 EinzelnachweiseBeispiele BearbeitenDie Primzahl p 294001 displaystyle p 294001 nbsp ist eine schwache Primzahl daWenn man eine einzige der sechs Dezimalstellen modifiziert erhalt man ausschliesslich zusammengesetzte Zahlen welche keine Primzahlen mehr sind dd 094001 194001 294001 394001 494001 594001 694001 794001 894001 994001 204001 214001 224001 234001 244001 254001 264001 274001 284001 294001 290001 291001 292001 293001 294001 295001 296001 297001 298001 299001 294001 294101 294201 294301 294401 294501 294601 294701 294801 294901 294001 294011 294021 294031 294041 294051 294061 294071 294081 294091 294000 294001 294002 294003 294004 294005 294006 294007 294008 294009 dd dd Insgesamt sind in diesem Fall 10 1 6 54 displaystyle 10 1 cdot 6 54 nbsp Zahlen zu prufen ob sie zusammengesetzte Zahlen sind Die ersten schwachen Primzahlen zur Basis 10 lauten 294001 505447 584141 604171 971767 1062599 1282529 1524181 2017963 2474431 2690201 3085553 3326489 4393139 5152507 5564453 5575259 6173731 6191371 6236179 6463267 6712591 7204777 7469789 7469797 Folge A050249 in OEIS dd Die grosste momentan bekannte schwache Primzahl Stand 10 Dezember 2018 wurde im Marz 2007 von Jens Kruse Andersen entdeckt 2 Sie lautet 17 10 1000 1 99 2168 6652 1717 1717 3885 8369 displaystyle frac 17 cdot 10 1000 1 99 2168 6652 1717 ldots 1717 3885 8369 nbsp dd Diese Zahl beginnt mit 496 Mal einer 17 displaystyle 17 nbsp und wird durch die Folge 3885 8369 displaystyle 3885 8369 nbsp abgeschlossen Sie besteht aus insgesamt 1000 displaystyle 1000 nbsp Stellen Eigenschaften BearbeitenUm festzustellen ob eine k displaystyle k nbsp stellige Primzahl eine schwache Primzahl ist muss man 9 k displaystyle 9 cdot k nbsp Zahlen kontrollieren ob sie zusammengesetzt sind oder nicht Nur wenn alle 9 k displaystyle 9 cdot k nbsp Zahlen zusammengesetzt sind ist die k displaystyle k nbsp stellige Primzahl tatsachlich eine schwache Primzahl siehe obiges Beispiel Es gibt unendlich viele schwache Primzahlen und ihre Dichte unter den Primzahlen ist echt grosser 0 Beweis siehe 3 von Terence Tao aus dem Jahr 2011 dd Schwache Primzahlen in beliebigen Zahlensystemen BearbeitenObiger Abschnitt behandelte schwache Primzahlen im Dezimalsystem also zur Basis b 10 displaystyle b 10 nbsp Eine Primzahl p P displaystyle p in mathbb P nbsp ist eine schwache Primzahl zur Basis b displaystyle b nbsp wenn sie geschrieben zur Basis b displaystyle b nbsp bei Anderung einer beliebigen einzelnen Ziffer d k displaystyle d k nbsp mit der Wertigkeit b k displaystyle b k nbsp mit 0 k log b p displaystyle 0 leq k leq lfloor log b p rfloor nbsp in eine andere Ziffer d k displaystyle d k nbsp mit d k d k displaystyle d k neq d k nbsp und 0 d k lt b displaystyle 0 leq d k lt b nbsp immer ihre Primzahl Eigenschaft verliert Da p displaystyle p nbsp in der Basis b displaystyle b nbsp aus log b p 1 displaystyle lfloor log b p rfloor 1 nbsp Ziffern besteht sind dazu b log b p displaystyle b cdot lfloor log b p rfloor nbsp Zahlen zu testen Beispiele von schwachen Primzahlen in anderen Zahlensystemen BearbeitenDie Primzahl p 436 7 4 7 2 3 7 1 6 7 0 196 21 6 223 displaystyle p 436 7 underline 4 cdot 7 2 underline 3 cdot 7 1 underline 6 cdot 7 0 196 21 6 223 nbsp ist eine schwache Primzahl zur Basis b 7 displaystyle b 7 nbsp weil gilt Wenn man eine einzige der drei Ziffern in der Basis b 7 displaystyle b 7 nbsp verandert erhalt man ausschliesslich zusammengesetzte Zahlen die keine Primzahlen mehr sind 0367 1367 2367 3367 4367 5367 6367 4067 4167 4267 4367 4467 4567 4667 4307 4317 4327 4337 4347 4357 4367 dd Insgesamt erhalt man in obiger Liste 6 3 24 displaystyle 6 cdot 3 24 nbsp zusammengesetzte Zahlen Stellvertretend fur alle obigen 24 Zahlen wird hier die Zahl 433 7 displaystyle 433 7 nbsp auf ihre Primalitat gepruft 433 7 4 7 2 3 7 1 3 7 0 196 21 3 220 P displaystyle 433 7 underline 4 cdot 7 2 underline 3 cdot 7 1 underline 3 cdot 7 0 196 21 3 220 not in mathbb P nbsp ist keine Primzahl dd Analog funktioniert die Uberprufung aller anderen 23 obigen Zahlen dd Die folgende Tabelle gibt die kleinsten schwachen Primzahlen zur Basis 2 b 16 displaystyle 2 leq b leq 16 nbsp an Folge A186995 in OEIS 4 Basisb displaystyle b nbsp schwache Primzahlen zur Basis b displaystyle b nbsp Umrechnung dieser Primzahl ins Dezimalsystem00 2 1111111 2 displaystyle 1111111 2 nbsp 1 2 6 1 2 5 1 2 4 1 2 3 1 2 2 1 2 1 1 2 0 64 32 16 8 4 2 1 127 displaystyle underline 1 cdot 2 6 underline 1 cdot 2 5 underline 1 cdot 2 4 underline 1 cdot 2 3 underline 1 cdot 2 2 underline 1 cdot 2 1 underline 1 cdot 2 0 64 32 16 8 4 2 1 127 nbsp 00 3 2 3 displaystyle 2 3 nbsp 2 3 0 2 displaystyle underline 2 cdot 3 0 2 nbsp 00 4 11311 4 displaystyle 11311 4 nbsp 1 4 4 1 4 3 3 4 2 1 4 1 1 4 0 256 64 48 4 1 373 displaystyle underline 1 cdot 4 4 underline 1 cdot 4 3 underline 3 cdot 4 2 underline 1 cdot 4 1 underline 1 cdot 4 0 256 64 48 4 1 373 nbsp 00 5 313 5 displaystyle 313 5 nbsp 3 5 2 1 5 1 3 5 0 75 5 3 83 displaystyle underline 3 cdot 5 2 underline 1 cdot 5 1 underline 3 cdot 5 0 75 5 3 83 nbsp 00 6 334155 6 displaystyle 334155 6 nbsp 3 6 5 3 6 4 4 6 3 1 6 2 5 6 1 5 6 0 23328 3888 864 36 30 5 28151 displaystyle underline 3 cdot 6 5 underline 3 cdot 6 4 underline 4 cdot 6 3 underline 1 cdot 6 2 underline 5 cdot 6 1 underline 5 cdot 6 0 23328 3888 864 36 30 5 28151 nbsp 00 7 436 7 displaystyle 436 7 nbsp 4 7 2 3 7 1 6 7 0 196 21 6 223 displaystyle underline 4 cdot 7 2 underline 3 cdot 7 1 underline 6 cdot 7 0 196 21 6 223 nbsp 00 8 14103 8 displaystyle 14103 8 nbsp 1 8 4 4 8 3 1 8 2 0 8 1 3 8 0 4096 2048 64 0 3 6211 displaystyle underline 1 cdot 8 4 underline 4 cdot 8 3 underline 1 cdot 8 2 underline 0 cdot 8 1 underline 3 cdot 8 0 4096 2048 64 0 3 6211 nbsp 00 9 3738 9 displaystyle 3738 9 nbsp 3 9 3 7 9 2 3 9 1 8 9 0 2187 567 27 8 2789 displaystyle underline 3 cdot 9 3 underline 7 cdot 9 2 underline 3 cdot 9 1 underline 8 cdot 9 0 2187 567 27 8 2789 nbsp 0 10 294001 10 displaystyle 294001 10 nbsp 2 10 5 9 10 4 4 10 3 0 10 2 0 10 1 1 10 0 200000 90000 4000 0 0 1 294001 displaystyle underline 2 cdot 10 5 underline 9 cdot 10 4 underline 4 cdot 10 3 underline 0 cdot 10 2 underline 0 cdot 10 1 underline 1 cdot 10 0 200000 90000 4000 0 0 1 294001 nbsp 0 11 2573 11 displaystyle 2573 11 nbsp 2 11 3 5 11 2 7 11 1 3 11 0 2662 605 77 3 3347 displaystyle underline 2 cdot 11 3 underline 5 cdot 11 2 underline 7 cdot 11 1 underline 3 cdot 11 0 2662 605 77 3 3347 nbsp 0 12 6 B 8 A B 77 12 displaystyle mathrm 6B8AB77 12 nbsp 6 12 6 11 12 5 8 12 4 10 12 3 11 12 2 7 12 1 7 12 0 17915904 2737152 165888 17280 1584 84 7 20837899 displaystyle underline 6 cdot 12 6 underline 11 cdot 12 5 underline 8 cdot 12 4 underline 10 cdot 12 3 underline 11 cdot 12 2 underline 7 cdot 12 1 underline 7 cdot 12 0 17915904 2737152 165888 17280 1584 84 7 20837899 nbsp 0 13 2216 13 displaystyle 2216 13 nbsp 2 13 3 2 13 2 1 13 1 6 13 0 4394 338 13 6 4751 displaystyle underline 2 cdot 13 3 underline 2 cdot 13 2 underline 1 cdot 13 1 underline 6 cdot 13 0 4394 338 13 6 4751 nbsp 0 14 C 371 C D 14 displaystyle mathrm C371CD 14 nbsp 12 14 5 3 14 4 7 14 3 1 14 2 12 14 1 13 14 0 6453888 115248 19208 196 168 13 6588721 displaystyle underline 12 cdot 14 5 underline 3 cdot 14 4 underline 7 cdot 14 3 underline 1 cdot 14 2 underline 12 cdot 14 1 underline 13 cdot 14 0 6453888 115248 19208 196 168 13 6588721 nbsp 0 15 9880 E 15 displaystyle mathrm 9880E 15 nbsp 9 15 4 8 15 3 8 15 2 0 15 1 14 15 0 455625 27000 1800 0 14 484439 displaystyle underline 9 cdot 15 4 underline 8 cdot 15 3 underline 8 cdot 15 2 underline 0 cdot 15 1 underline 14 cdot 15 0 455625 27000 1800 0 14 484439 nbsp 0 16 D 2 A 45 16 displaystyle mathrm D2A45 16 nbsp 13 16 4 2 16 3 10 16 2 4 16 1 5 16 0 851968 8192 2560 64 5 862789 displaystyle underline 13 cdot 16 4 underline 2 cdot 16 3 underline 10 cdot 16 2 underline 4 cdot 16 1 underline 5 cdot 16 0 851968 8192 2560 64 5 862789 nbsp Eigenschaften von schwachen Primzahlen in anderen Zahlensystemen BearbeitenUm festzustellen ob eine k displaystyle k nbsp stellige Primzahl eine schwache Primzahl zur Basis b displaystyle b nbsp ist muss man b 1 k displaystyle b 1 cdot k nbsp Zahlen kontrollieren ob sie zusammengesetzt sind oder nicht Nur wenn alle b 1 k displaystyle b 1 cdot k nbsp Zahlen zusammengesetzt sind ist die k displaystyle k nbsp stellige Primzahl tatsachlich eine schwache Primzahl zur Basis b displaystyle b nbsp Sei b N displaystyle b in mathbb N nbsp eine Basis Dann gibt es unendlich viele schwache Primzahlen zu dieser Basis b displaystyle b nbsp Beweis siehe 3 von Terence Tao aus dem Jahr 2011 dd Ahnliche Konstrukte BearbeitenEin ahnliches Konstrukt stellen die trunkierbaren Primzahlen vom englischen truncatable prime dar Von diesen Primzahlen lassen sich beliebig viele Stellen abtrennen ohne dass deren Primeigenschaft verloren ginge 5 Linkstrunkierbare Primzahlen Left truncatable primes Folge A024785 in OEIS z B 1367 367 67 und 7 waren ebenfalls prim Rechtstrunkierbare Primzahlen Right truncatable primes Folge A024770 in OEIS z B 3739 373 37 und 3 waren ebenfalls prim Beidseitig trunkierbare Primzahlen Two sided primes Folge A020994 in OEIS in der strengen Definition der beidseitigen Ziffernabtrennbarkeit existieren nur 15 Primzahlen mit dieser Eigenschaft 2 3 5 7 23 37 53 73 313 317 373 797 3137 3797 739397 dd Es gibt auch eine Kombinationsmoglichkeit Schwache trunkierbare Primzahlen Digitally delicate truncatable primes Folge A347424 in OEIS beginnend mit 7810223 19579907 909001523 984960937 78406036607 welche beide Kriterien erfullen Weblinks BearbeitenEric W Weisstein Weakly Prime In MathWorld englisch Weakly Primes auf Department of Mathematics der Missouri State University englisch Einzelnachweise Bearbeiten N J A Sloane Weakly prime numbers changing any one decimal digit always produces a composite number Also called digitally delicate primes OEIS abgerufen am 10 Dezember 2018 Weakly Primes kommentar primepuzzles net 2012 abgerufen am 10 Dezember 2018 a b Terence Tao A remark on primality testing and decimal expansions In Journal of the Australian Mathematical Society Band 91 Nr 3 2011 S 505 413 doi 10 1017 S1446788712000043 arxiv 0802 3361 Schwache Primzahlen und das Unarsystem sind unvereinbar Schwache Primzahlen arbeiten explizit nur mit Ziffern die kleiner als die Basis sind 0 d k lt b displaystyle 0 leq d k lt b nbsp Dieses ist essentiell fur die Betrachtung von schwachen Primzahlen und ist im Unarsystem prinzipbedingt verletzt Lasst man Ziffern d k b displaystyle d k geq b nbsp zu gibt es keine schwachen Primzahlen Eric W Weisstein Truncatable Prime In MathWorld englisch 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 Schwache Primzahl amp oldid 226784007
