Primzahlen: naive Ansätze

Einleitung

Bearbeiten

Wenn man testen möchte, ob eine natürliche Zahl   eine Primzahl ist, kommt einem vielleicht als erstes das Konsequente Durchtesten auf Teilbarkeit in den Sinn. Dabei testet man, ob es eine natürliche Zahl zwischen   und   gibt, die   teilt. Existiert keine natürliche Zahl zwischen   und   gibt, die   teilt, so ist   eine Primzahl. Findet sich wenigstens eine Zahl zwischen   und   die   teilt, so ist   keine Primzahl.

Beispiele

Bearbeiten
  • 7
 
 
 
 
 

Keine Zahl zwischen 2 und 6 teilt 7 (ohne Rest), also ist 7 eine Primzahl.

  • 9
 
  Teiler!
 
 
 
 
 

Die 3 teilt 9 (ohne Rest), also kann 9 keine Primzahl sein.

Balast und Verbesserungen

Bearbeiten

Wenn man sich den naiven Ansatz des konsequenten Durchtestens durch Teilung so ansieht, fallen einem einige Überflüssigkeiten und Verbesserungsmöglichkeiten auf.

  •   kann nie durch   geteilt werden.
Es ist einfach nicht möglich, und daher fällt   als Teilerkriterium weg. Korrekt wäre also: Existiert keine natürliche Zahl zwischen   und   gibt, die   teilt, so ist   eine Primzahl!
  • Wenn aus einem beliebigen Produkt   mit   der Faktor   schon als Teiler getestet wurde, so ist es nicht mehr nötig, Faktor   auch noch zu testen.
Angenommen ich teste die Zahl   auf ihre primalität. Wenn ich die 5 getestet und festgestellt habe, das sie ein Teiler von 35 ist, kann ich aufhören, weitere Zahlen darauf zu testen, ob sie Faktoren der 35 sind oder nicht. Um mal den Extremfall zu zeigen: Angenommen ich will 49 auf ihre primalität testen. Dann muß ich das nur bis zur 7 machen, weil 7 die Quadratwurzel von 49 ist:  .
Wie sieht das nun bei einer Primzahl aus? Wie weit muß ich da testen? Bis  ? Nein, es reicht, bis   zu testen. Warum?
Angenommen, es gibt keinen Teiler kleiner  , der   teilt. Dann kann es auch keinen Teiler größer   geben, der   teilt. Warum?
Nehmen wir mal an, wir haben zwei natürliche Zahlen   für die gilt   teilt   und   teilt  . Daraus würde folgen, das   ist. Das ist ein Widerspruch, und deshalb muß man auch nur bis maximal   testen.
  • Primzahlen größer 3 haben die Form   oder  
Aus diesem Grund braucht man Primzahlen, die nicht dieser Form entsprechen nicht kosequent auf alle mögliche Teiler zu testen. Es reicht, einen Vortest auf die Formen   und   zu machen. Zahlen die nicht diesen Formen entsprechen, fallen als Kandidaten für Primzahlen gleich raus. Das sind   aller natürlichen Zahlen.
  • Primzahlen größer 5 haben die Form   mit einem   aus der Menge  . Da für alle   aus   gilt, daß sie teilerfremd zu 30 sind, für alle   aus   aber nicht, muß für einen Vortest nur getestet werden, ob für die zu testende Zahl   gilt:  . Ist der  , so ist n mit Sicherheit zusammengesetzt. Ist der   aber 1, und ist  , dann ist   in jedem Falle eine Primzahl, und für den Fall   doch mit größerer Wahrscheinlichkeit.
Fehltreffer: 49, 77, 91, 119, 121, 133, ...

Eine Variation des naiven Ansatzes

Bearbeiten

Statt auf die Teilbarkeit läßt sich auf die Teilerfremdheit testen. Wie in Kapitel Ib. schon beschrieben gilt für alle natürlichen Zahlen   und  , in die sich eine Primzahl additiv zerlegen läßt, das   und   zueinander Teilerfremd sind. das also gilt:  . Dabei können wir den Fall   aussen vor lassen, da er wie   ist kein Teiler von   immer war ist, egal ob die zu testende Zahl   eine Primzahl ist, oder nicht. Existieren zu einer Zahl   zwei Zahlen   und  , die nicht zueinander teilerfremd sind, dann handelt es sich bei   um keine Primzahl. Sind dagegen alle   und   von einer Zahl   zueinander teilerfremd, so ist   eine Primzahl.

Identisch

Bearbeiten

Diese Form des Primzahltests ist nicht unabhängig von dem Primzahltest durch konsequentes Testen auf Teilbarkeit. Die eine Form läßt sich in die andere Form überführen. Das läßt sich wie folgt zeigen:

Der Primzahltest durch konsequentes Testen auf Teilbarkeit läßt sich als   auffassen. Es gilt  . Also gilt auch  . Weiterhin gilt  .
Und genau das ( ) ist ja der Primzahltest auf Teilerfremdheit.
Genauso läßt sich zeigen, das   ist.