« Algorithme d'Euclide » : différence entre les versions
Contenu supprimé Contenu ajouté
→Principes : continuation Balise : Révoqué |
Révocation des modifications de Arthur Baelde (retour à la dernière version de Dfeldmann) ; vos modifications ne vont pas, à commencer par WP:RI ; qu'est ce que ces ancres et commentaires dans le code, lien remplacé par une redirection dans articles connexes ?... |
||
Ligne 1 :
En [[mathématiques]], l''''algorithme d'Euclide''' est un [[algorithme]] qui calcule le [[plus grand commun diviseur]] (PGCD) de deux [[entier relatif|entiers]], c'est-à-dire le plus grand entier qui divise les deux entiers, en laissant un [[reste]] nul. L'algorithme ne requiert pas de connaître la [[décomposition en produit de facteurs premiers|factorisation]] de ces deux nombres.
== Histoire ==
Ligne 15 ⟶ 13 :
== Présentation ==
===
Le PGCD (plus grand commun diviseur) de deux entiers relatifs est égal au PGCD de leurs valeurs absolues : de ce fait, on se restreint dans cette section aux [[Entier naturel|entiers positifs]]. L'algorithme part du constat suivant : le PGCD de deux nombres n'est pas changé si on remplace le plus grand d'entre eux par leur différence. Autrement dit, {{math|§=pgcd(''a'', ''b'') = pgcd(''a''−''b'', ''b'')}}. Par exemple, le PGCD de 252 et 105 vaut 21, mais c'est aussi le PGCD de 252 − 105 = 147 et 105. Ainsi, comme le remplacement de ces nombres diminue strictement le plus grand d'entre eux, on peut continuer le processus, jusqu'à obtenir deux nombres égaux. On peut effectuer plusieurs soustractions successives, ce qui revient à une division euclidienne. Par exemple, le PGCD de 252 et 105 est aussi égal au PGCD de 105 et 252 − 105 = 147, puis au PGCD de 105 et 147 − 105 = 42.
Ligne 262 ⟶ 254 :
=== Articles connexes ===
*[[Liste de sujets portant le nom d'Euclide]]
*[[Algorithme binaire de calcul du PGCD
*[[Constante de Porter]], intervenant dans l'évaluation du nombre moyen d'étapes dans l'algorithme d'Euclide
* [[Anneau euclidien]]
=== Lien externe ===
|