Méthode de factorisation d'Euler

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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  peut s'écrire  ou  et la méthode de factorisation d'Euler donne .

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 , 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 millions[réf. 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 n avec un facteur premier de la forme 4k + 3 à une puissance impaire dans la décomposition en facteurs premiers de n, car un tel nombre premier n'est jamais somme de deux carrés. Des nombres impairs de la forme 4k + 1 sont souvent le produit de deux nombres premiers de la forme 4k + 3 (par exemple 3053 = 43 × 71) et donc ne peuvent pas être factorisés par la méthode d'Euler.

Bases théoriques[modifier | modifier le code]

L'identité de Brahmagupta indique 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é , on peut exprimer  comme produit de sommes de deux carrés.

On déduit premièrement que

et en factorisant des deux côtés

(1)

Soient  et . Alors, il existe des entiers  tels que :

  • , ,  ;
  • , , .

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

,

c'est à dire

.

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

et

donc

, , et .

En appliquant l'identité de Brahmagupta, on obtient

,
.

Comme chaque facteur est une somme de deux carrés, l'un d'entre eux doit contenir deux nombres pairs[pourquoi ?] : soit soit . Sans perte de généralité, supposons que  sont pairs. La factorisation devient

.

Exemple[modifier | modifier le code]

Puisque ,

on déduit de la formule ci-dessus :

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

Ainsi,

Article connexe[modifier | modifier le code]

Méthode de factorisation de Fermat

Références[modifier | modifier le code]