Eulerova faktorizační metoda

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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:

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

a odtud plyne, že

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

, a

Dosadíme-li získaný vztah do rovnosti součinů výše, máme

Protože jsou a nesoudělná, musí být dělitelné . Tato myšlenka dává:

a

Ze získaných rovností plyne a , odkud po dosazení do původního zapsání máme: