Eulerova faktorizační metoda

Eulerova faktorizační metoda, pojmenovaná po Leonhardu Eulerovi, je metoda hledání prvočíselného rozkladu založená na možnosti zapsat zkoumané přirozené číslo N jako součet dvou čtverců dvěma různými způsoby:

$\ N = a^2+ b^2 = c^2+ d^2$

Odečtením $c^2$ a $b^2$ od obou stran získáváme rozdíl dvou čtverců:

$\ a^2 - c^2 = d^2 - b^2$

a odtud plyne, že

$(a - c)\cdot(a + c) = (d - b)\cdot(d + b)$

Bez újmy na obecnosti lze předpokládat, že $d$ a $b$ jsou buď obě sudá, nebo lichá, tedy že jejich rozdíl bude sudý. Nechť $k$ je největší společný dělitel $(a - c)$ a$(d - b)$, tedy

$(a - c) = kl$, $(d - b) = km$ a $NSD (l, m) = 1$

Dosadíme-li získaný vztah do rovnosti součinů výše, máme $l\cdot(a + c) = m\cdot(d + b)$

Protože jsou $l$ a $m$ nesoudělná, musí být $(a + c)$ dělitelné $m$. Tato myšlenka dává:

$\ (a + c) = mn$ a $\ (d + b) = ln$

Ze získaných rovností plyne $2c=(a+c)-(a-c)=mn-kl$ a $2d=(d-b)+(d+b)=km+ln$, odkud po dosazení do původního zapsání $N$ máme:

$N=\frac{1}{4}\left[\left(mn-kl\right)^2+\left(km+ln\right)^2\right] = \frac{1}{4}\left(m^2n^2+k^2l^2+k^2m^2+l^2n^2\right)=\frac{1}{4}\left(m^2+l^2\right)\left(k^2+n^2\right)$