fermats faktoriseringsmetode

[cecilia]

hvorfor fungerer denne faktoriseringsmetoden?

[Gustav]

Hvis du skal faktorisere f.eks 9991 observerer du at 9991=10000-9

Begge disse tallene er kvadrattall: 10000=100^2 og 9=3^2,

så $9991={100}^2-3^2$

Vi vet at for alle x og y er $x^2-y^2=(x+y)(x-y)$. Derfor er

$9991={100}^2-3^2=(100-3)(100+3)$ Så vi har faktorisert 9991 på en lettvint måte.

Alternativet er mye mer tungvint. f.eks. systematisk å sjekke om hvert primtall fra og med 2 deler 9991