Méthode de factorisation d'Euler

La méthode de factorisation d'Euler est une technique de factorisation d'un nombre, du nom de Leonhard Euler, en l'écrivant comme une somme de deux carrés de deux manières différentes. Par exemple, le nombre 1 000 009 peut s'écrire 1000Modèle:2 + 3Modèle:2 ou 972Modèle:2 + 235Modèle:2 et la méthode de factorisation d'Euler donne 1 000 009 = 293 × 3413.

L'idée que deux représentations distinctes d'un entier naturel impair peut conduire à une factorisation aurait été proposée par Marin Mersenne. Cependant, elle n'avait pas été exploitée, jusqu'à Euler, cent ans plus tard. L'utilisation la plus célèbre de la méthode, qui porte maintenant son nom, était de factoriser le nombre 1 000 009, qui était auparavant supposé premier.

La méthode de factorisation d'Euler est plus efficace que celle de Fermat pour les entiers dont les facteurs ne sont pas proches, si l'on peut trouver raisonnablement facilement des représentations de nombres sous la forme de deux carrés. Le développement d'Euler a finalement permis une factorisation beaucoup plus efficace des nombres et, vers les années 1910, le développement de grandes tables allant jusqu'à environ dix millionsModèle:Référence nécessaire. Les méthodes utilisées pour trouver des représentations de nombres sous la forme de sommes de deux carrés sont essentiellement les mêmes que pour trouver des différences de carrés dans la méthode de factorisation de Fermat.

L'inconvénient de la méthode de factorisation d'Euler est qu'elle ne peut pas être appliquée à la factorisation d'un nombre entier Modèle:Mvar avec un facteur premier de la forme Modèle:Math à une puissance impaire dans la décomposition en facteurs premiers de Modèle:Mvar, car un tel nombre premier n'est jamais somme de deux carrés. (Voir le théorème des deux carrés de Fermat). Des nombres impairs de la forme Modèle:Math sont souvent le produit de deux nombres premiers de la forme Modèle:Math (par exemple 3053 = 43 × 71) et donc ne peuvent pas être factorisés par la méthode d'Euler.

Bases théoriques

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é Modèle:Math, on peut exprimer Modèle:Mvar comme produit de sommes de deux carrés.

On déduit premièrement que

$a^2-c^2=d^2-b^2$

et en factorisant des deux côtés

$(a-c)(a+c)=(d-b)(d+b)$ (1)

Soient Modèle:Math et Modèle:Math. Alors il existe des entiers Modèle:Math tels que :

• $a-c=kl$,
  $d-b=km$,
  $\mathrm{pgcd}(l,m)=1$;
• $a+c=h{m}^{\prime }$,
  $d+b=h{l}^{\prime }$,
  $\mathrm{pgcd}(l^{\prime },m^{\prime })=1$.

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

$klh{m}^{\prime }=kmh{l}^{\prime }$,

c'est-à-dire

$l{m}^{\prime }=l^{\prime }m$.

En utilisant le fait que Modèle:Math et Modèle:Math sont des couples de nombres premiers entre eux, on trouve que

$l=l^{\prime }\text{et}m=m^{\prime }$

donc

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

En appliquant l'identité de Brahmagupta, on obtient

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

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

On en déduit que les facteurs $k^2+h^2$ et $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 :

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

Exemple

Puisque Modèle:Math,

on déduit de la formule ci-dessus :

a = 1000	(A) a − c = 28	k = pgcd[A,C] = 4
b = 3	(B) a + c = 1972	h = pgcd[B,D] = 34
c = 972	(C) d − b = 232	l = 7
d = 235	(D) d + b = 238	m = 58

Ainsi,

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

Article connexe

Méthode de factorisation de Fermat

Références

• Modèle:Ouvrage
• Modèle:Article