« Algorithme d'Euclide » : différence entre les versions
Contenu supprimé Contenu ajouté
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 ?... |
UnePaiRe identifie le premier exemple de valeurs entières données au départ d’une exécution d’Algorithme Balises : Révocation manuelle Révoqué |
||
Ligne 1 :
En [[arithmétique]] un '''PGCD''', [[acronyme]] de “[[plus grand commun diviseur]]”, peut résulter d’un '''[[algorithme]] d’Euclide'''. Ce résultat est le seul commun [[diviseur]] de deux [[entiers naturels]] donnés au départ, qui est aussi [[Multiple (mathématiques)|multiple]] de tous leurs diviseurs communs. L’algorithme calcule ce PGCD par [[Division euclidienne|divisions euclidiennes]] successives, si aucun des entiers initiaux n’est nul. Sinon, l’autre élément de la paire initiale est le PGCD des deux entiers, même si les entiers initiaux sont nuls tous les deux. Les [[itération]]s de l’algorithme s’achèvent par une [[division]] à [[reste]] nul, dont le diviseur est le PGCD recherché. Ce diviseur‑là sert notamment à calculer la [[fraction irréductible]] égale à une [[Fraction (mathématiques)|fraction donnée]], en divisant ses termes par le PGCD de leurs [[Valeur absolue|valeurs absolues]]. L’algorithme ignore toute [[décomposition en produit de facteurs premiers]].
{{anchor|UnePaiRe}}À partir de la paire {{nobr|{ 72, 308 } }} par exemple, l’algorithme produit le PGCD 4 de 72 et 308, après la [[Suite (mathématiques)|suite]] (308, 72, 20, {{nobr|12, 4, 0), }} dont trois termes successifs sont les dividende, diviseur et reste d’une même division. Simplifier par 4 la fraction {{nobr|<sup>72 </sup>/<sub> 308</sub> }} ou la fraction [[inverse]], c’est la remplacer par une fraction égale, dont les {{nobr|1=termes <sup>72 </sup>/<sub> 4</sub> = 18 }} {{nobr|1=et <sup>308 </sup>/<sub> 4</sub> = 77 }} sont [[Nombres premiers entre eux|premiers entre eux]]. Autrement dit, {{nobr|1 est le PGCD}} {{nobr|de 18 et 77, }} leur seul diviseur commun.
== Histoire ==
Ligne 13 ⟶ 15 :
== Présentation ==
===
La somme ou la différence de deux multiples d’un certain entier positif est encore un multiple de cet entier. Par exemple, à partir des valeurs entières choisies [[#UnePaiRe|dans l’introduction]], la première division traduite en quatre soustractions : {{nobr|1=308–72 = 236, et 236 ≥ 72 ; }} {{nobr|1=236–72 = 164, et 164 ≥ 72 ; }} {{nobr|1=164–72 = 92, et 92 ≥ 72 ; }} {{nobr|1= 92–72 = 20, et 20 < 72, }} fournit une suite de quatre paires {{nobr|({308, 72}, {236, 72}, {164, 72}, {92, 72}, {20, 72}), }} qui ont le même ensemble de communs diviseurs.
L’algorithme d’Euclide, ou sa version en soustractions, laisse tomber dans l’oubli le premier quotient 4, ou le nombre 4 de soustractions de la première séquence, qui soustrait constamment 72.
<!-- À suivre… -->
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 254 ⟶ 262 :
=== Articles connexes ===
*[[Liste de sujets portant le nom d'Euclide]]
*[[Algorithme
*[[Constante de Porter]], intervenant dans l'évaluation du nombre moyen d'étapes dans l'algorithme d'Euclide
=== Lien externe ===
| |||