Schwache Primzahl

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Schwache Primzahlen (engl. Weakly Prime Numbers oder auch Digitally Delicate Prime[1]) sind Primzahlen, die bei Änderung einer beliebigen einzelnen Ziffer in eine beliebige andere Ziffer immer ihre Primzahl-Eigenschaft verlieren. Als schwache Primzahlen (engl. Weak Prime) werden aber auch zur Verschlüsselung ungeeignete Primzahlen bezeichnet.

Beispiele[Bearbeiten | Quelltext bearbeiten]

  • Die Primzahl ist eine schwache Primzahl, weil gilt:
Wenn man eine einzige der sechs Ziffern verändert, erhält man ausschließlich zusammengesetzte Zahlen, welche somit keine Primzahlen sind:
094001, 194001, 394001, 494001, 594001, 694001, 794001, 894001, 994001
204001, 214001, 224001, 234001, 244001, 254001, 264001, 274001, 284001
290001, 291001, 292001, 293001, 295001, 296001, , 297001, 298001, 299001
294101, 294201, 294301, 294401, 294501, 294601, 294701, 294801, 294901
294011, 294021, 294031, 294041, 294051, 294061, 294071, 294081, 294091
294000, 294002, 294003, 294004, 294005, 294006, 294007, 294008, 294009
Insgesamt muss man in diesem Fall Zahlen untersuchen, ob sie zusammengesetzte Zahlen sind.
  • Die ersten schwachen Primzahlen sind:
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)
  • Die größte momentan bekannte schwache Primzahl lautet (Stand: 10. Dezember 2018):
Diese Zahl hat 496 er, die direkt hintereinander stehen, sie hat Stellen und wurde im März 2007 von Jens Kruse Andersen entdeckt.[2]

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

  • Um festzustellen, ob eine -stellige Primzahl eine schwache Primzahl ist, muss man Zahlen kontrollieren, ob sie zusammengesetzt sind oder nicht. Nur wenn alle Zahlen zusammengesetzt sind, ist die -stellige Primzahl tatsächlich eine schwache Primzahl. (siehe obiges Beispiel)
  • Es gibt unendlich viele schwache Primzahlen.
Beweis: siehe [3] von Terence Tao aus dem Jahr 2011.

Schwache Primzahlen in anderen Zahlensystemen[Bearbeiten | Quelltext bearbeiten]

Obiger Abschnitt behandelte schwache Primzahlen im Dezimalsystem, also zur Basis .

Eine Primzahl ist eine schwache Primzahl zur Basis , wenn sie bei Änderung einer beliebigen einzelnen Ziffer in eine beliebige andere Ziffer ( in der Basis geschrieben), immer ihre Primzahl-Eigenschaft verliert.

Beispiele von schwachen Primzahlen in anderen Zahlensystemen[Bearbeiten | Quelltext bearbeiten]

  • Die Primzahl ist eine schwache Primzahl zur Basis , weil gilt:
Wenn man eine einzige der drei Ziffern in der Basis verändert, erhält man ausschließlich zusammengesetzte Zahlen, welche somit keine Primzahlen sind:
0367, 1367, 2367, 3367, 5367, 6367
4067, 4167, 4267, 4467, 4567, 4667
4307, 4317, 4327, 4337, 4347, 4357
Insgesamt erhält man in obiger Liste zusammengesetzte Zahlen.
Stellvertretend für alle obigen 24 Zahlen wird hier die Zahl auf ihre Primalität geprüft:
ist keine Primzahl. Analog funktioniert die Überprüfung aller anderen 23 obigen Zahlen.
  • Die folgende Tabelle gibt die kleinsten schwachen Primzahlen zur Basis an (Folge A186995 in OEIS):
Basis schwache Primzahlen zur Basis ,
geschrieben zur Basis
Umrechnung ins Dezimalsystem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Eigenschaften von schwachen Primzahlen in anderen Zahlensystemen[Bearbeiten | Quelltext bearbeiten]

  • Um festzustellen, ob eine -stellige Primzahl eine schwache Primzahl zur Basis ist, muss man Zahlen kontrollieren, ob sie zusammengesetzt sind oder nicht. Nur wenn alle Zahlen zusammengesetzt sind, ist die -stellige Primzahl tatsächlich eine schwache Primzahl zur Basis .
  • Sei eine Basis. Dann gibt es unendlich viele schwache Primzahlen zu dieser Basis .
Beweis: siehe [3] von Terence Tao aus dem Jahr 2011.

Ähnliche Konstrukte[Bearbeiten | Quelltext bearbeiten]

Ein ähnliches 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:[4]

  • Linkstrunkierbare Primzahlen (Left-truncatable primes) (Folge A024785 in OEIS), z. B. 1367 – 367, 67 und 7 wären ebenfalls prim.
  • Rechtstrunkierbare Primzahlen (Right-truncatable primes) (Folge A024770 in OEIS), z. B. 3739 – 373, 37 und 3 wären 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

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. 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.
  2. Weakly Primes. primepuzzles.net, 2012, abgerufen am 10. Dezember 2018 (größte bekannte schwache Primzahl).
  3. a b Terence Tao: A remark on primality testing and decimal expansions. In: Journal of the Australian Mathematical Society. 91, Nr. 3, 22. Februar 2008. arxiv:0802.3361. doi:10.1017/S1446788712000043..
  4. Eric W. Weisstein: Truncatable Prime. In: MathWorld (englisch).