Méthode de factorisation d'Euler

L'identité de Brahmagupta montre que le produit de deux sommes de deux carrés est une somme de deux carrés. La méthode d'Euler s'appuie sur cette identité : étant donné n = a² + b² = c² + d², on peut exprimer n comme produit de sommes de deux carrés.

On déduit premièrement que

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

et en factorisant des deux côtés

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

Soient k = pgcd(a – c, d – b) et h = pgcd(a + c, d + b). Alors il existe des entiers l, m, l', m' tels que :

• ${\displaystyle a-c=kl}$,
  ${\displaystyle d-b=km}$,
  ${\displaystyle \operatorname {pgcd} (l,m)=1}$;
• ${\displaystyle a+c=hm'}$,
  ${\displaystyle d+b=hl'}$,
  ${\displaystyle \operatorname {pgcd} (l',m')=1}$.

En remplaçant cela dans l'équation (1), on obtient

${\displaystyle klhm'=kmhl'}$,

c'est-à-dire

${\displaystyle lm'=l'm}$.

En utilisant le fait que (l,m) et (l',m') sont des couples de nombres premiers entre eux, on trouve que

${\displaystyle l=l'\ {\textrm {et}}\ m=m'}$

donc

${\displaystyle a-c=kl,\,d-b=km,\,a+c=hm\ {\textrm {et}}\ d+b=hl}$.

En appliquant l'identité de Brahmagupta, on obtient

${\displaystyle \left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=\left(kl-hm\right)^{2}+(km+hl)^{2}=\left((a-c)-(a+c)\right)^{2}+\left((d-b)+(d+b)\right)^{2}=(2c)^{2}+(2d)^{2}=4n}$,

${\displaystyle \left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=(kl+hm)^{2}+(km-hl)^{2}=\left((a-c)+(a+c)\right)^{2}+\left((d-b)-(d+b)\right)^{2}=(2a)^{2}+(2b)^{2}=4n}$.

On en déduit que les facteurs ${\displaystyle k^{2}+h^{2}}$ et ${\displaystyle l^{2}+m^{2}}$ sont tous deux pairs, ou bien que l'un des deux est divisible par 4. Dans le cas où ils sont tous les deux pairs, n se factorise de la façon suivante :

${\displaystyle n=\left({\frac {k^{2}+h^{2}}{2}}\right)\left({\frac {l^{2}+m^{2}}{2}}\right)}$.

Dans le cas où l'un des deux est divisible par 4 (supposons sans perte de généralité qu'il s'agisse de ${\displaystyle k^{2}+h^{2}}$), cela signifie que les deux carrés dont il est la somme sont eux-mêmes divisibles par 4. En effet, une somme de deux carrés ne peut être congrue à 0 modulo 4 que si ces deux carrés sont eux-mêmes congrus à 0 modulo 4, car un carré ne peut être congru qu'à 0 ou 1 modulo 4. On en déduit que k et h sont tous deux pairs. n se factorise donc de la façon suivante : ${\displaystyle n=\left(\left({\frac {k}{2}}\right)^{2}+\left({\frac {h}{2}}\right)^{2}\right)(l^{2}+m^{2})}$.

Puisque 1000009 = 1000² + 3² = 972² + 235²,

on déduit de la formule ci-dessus :

Ainsi,

${\displaystyle {\begin{aligned}1000009&=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\right]\left(7^{2}+58^{2}\right)\\&=\left(2^{2}+17^{2}\right)\left(7^{2}+58^{2}\right)\\&=(4+289)(49+3364)\\&=293\times 3413.\end{aligned}}}$

Méthode de factorisation de Fermat

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Euler's factorization method » (voir la liste des auteurs).
• (en) Oystein Ore, Number Theory and Its History, New York, Dover, 1988, 370 p. (ISBN 978-0-486-65620-5 et 0-486-65620-9, lire en ligne), « Euler's Factorization Method », p. 59-64
• (en) James McKee, « Turning Euler's Factoring Method into a Factoring Algorithm », Bull. London Math. Soc., vol. 4, n^o 28,‎ 1996, p. 351-355 (DOI 10.1112/blms/28.4.351, lire en ligne)