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^{2}n^{2}+k^{2}l^{2}+k^{2}m^{2}+l^{2}n^{2}\right)={\frac {1}{4}}\left(m^{2}+l^{2}\right)\left(k^{2}+n^{2}\right)$