Primzahlen: Primfaktorzerlegung nach Fermat
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
