Zahlentheorie Fermat Faktorisierung

Question

Aufgabe:

$$\text{Finde zwei Teiler a,b von n=8633 mit 1<a<b<n.}$$

Ich habe die Fermat-Faktorisierung verwendet um die beiden Teiler a und b zu finden. Gibt es noch eine weitere Methode, um ohne Hilfsmittel die Teiler bestimmen zu können?

Answer 1

Zunächst würde man evtl. die Teilbarkeitsregeln bis 10 nutzen, weil die noch recht simpel sind. Wenn das nicht geht, denke ich, ist das Faktorisierungsverfahren nach Fermat schon das schnellste.

√8633 <= 93

93^2 - 8633 = 16

ops. Sehr zufällig gilt jetzt

8633 = (93 - 4)·(93 + 4) = 89·97

Das geht jetzt allerdings nur so schnell, weil das eine sehr einfache Aufgabe vermutlich genau zum Thema ist. Wenn die Zahlen nicht so dicht beieinander liegen, ist das leider auch deutlich aufwendiger.