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:

${\displaystyle \ N=a^{2}+b^{2}=c^{2}+d^{2}}$

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

${\displaystyle \ a^{2}-c^{2}=d^{2}-b^{2}}$

a odtud plyne, že

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

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

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

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

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

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

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

${\displaystyle 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)}$