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) = k l$ , $(d - b) = k m$ a $N S D (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) = m n$ a $(d + b) = l n$

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

$N = \frac{1}{4} [{(m n - k l)}^{2} + {(k m + l n)}^{2}] = \frac{1}{4} (m^{2} n^{2} + k^{2} l^{2} + k^{2} m^{2} + l^{2} n^{2}) = \frac{1}{4} (m^{2} + l^{2}) (k^{2} + n^{2})$ Šablona:Autoritní data

Eulerova faktorizační metoda

Navigační menu

Hledat