Primzahlen: naive Ansätze

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Nuvola apps bookcase 1.svg Primzahlen:_III._Kapitel:_Primfaktorzerlegung_und_andere_Methoden

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.