Zum Inhalt springen

Primzahlen: Primfaktorzerlegung nach Fermat

Aus Wikibooks

Die Primzahlzerlegung nach Fermat ist ein recht einfach zu verstehendes Verfahren, das allerdings nicht besonders effektiv ist; jedoch wesentlich effektiver als das konsequente Testen.

Die Folge der Quadratzahlen

[Bearbeiten]

Um die Folge der Quadratzahlen zu bekommen gibt es eine einfache Methode: Man addiert alle ungeraden, natürlichen Zahlen.

Die allgemeine Formel lautet:

Da gilt, läßt sich jede ungerade, natürliche Zahl auf mindestens eine Art als Differenz zweier Quadratzahlen darstellen.

Die dritte Binomische Formel

[Bearbeiten]

Da sich jede ungerade, natürliche Zahl auf mindestens eine Art als Differenz zweier Quadratzahlen darstellen läßt, kann man die dritte Binomische Formel anwenden. Die Terme und sind dabei Faktoren von , da wegen auch gilt.

Einschränkung

[Bearbeiten]

Die Primzahlzerlegung nach Fermat funktioniert nur für ungerade, natürliche Zahlen. Der Faktor 2 muß also vorher entfernt werden.

Verfahren

[Bearbeiten]

Man will eine ungerade natürliche Zahl faktorisieren. Dazu nimmt man die Quadratzahl die am nächsten an liegt. Nun ermittelt man die Differenz . Wenn die Differenz eine Quadratzahl ist, kann man zwei Faktoren von bestimmen. Falls nicht, nimmt man die nächst höhere Quadratzahl.

Beispiel

[Bearbeiten]

51

Treffer: und sind beides Quadratzahlen.

Mit der Anwendung des dritten binomischen Satz bekommt man die beiden Faktoren.

Der schlimmste Fall

[Bearbeiten]

Im schlimmsten Fall ist die zu prüfende Zahl eine Primzahl. In diesem Fall sind die einzigen Teiler und 1. Die dabei zugehörigen und sind und .

Beispiel

[Bearbeiten]

43