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