$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Algorithme d'Euclide

L'algorithme d'Euclide est une méthode pour trouver pratiquement le PGCD de deux nombres sans avoir besoin de faire leur décomposition en produit de facteurs premiers. Il est basé sur la propriété suivante.

Proposition : Si $a$ et $b$ sont deux entiers naturels avec par exemple $a\geq b$, si $r$ est le reste de $a$ par $b$, alors le pgcd de $a$ et $b$ vaut le pgcd de $b$ et $r.$

On fait donc des divisions euclidiennes, jusqu'à ce qu'on trouve un reste nul. Le dernier reste non nul est le pgcd de a et b.

Exemple : On souhaite calculer le pgcd de 255 et 141. On effectue les divisions euclidiennes successives suivantes : $$255=1×141+114$$ $$141=1×114+27$$ $$114=4×27+6$$ $$27=4×6+3$$ $$6=2×3+0$$ Le pgcd de 255 et 141 est donc 3.

L'algorithme d'Euclide permet aussi de calculer des coefficients de Bézout de $a$ et $b$ (on l'appelle algorithme d'Euclide étendu). Rappelons que si $d$ est le PGCD de $a$ et $b$, il existe des entiers $u$ et $v$ tels que $au+bv=d$. L'algorithme d'Euclide permet de calculer une valeur possible pour ces entiers $u$ et $v$. Il suffit pour cela, dans les calculs, d'exprimer à chaque étape le dernier reste en fonction des nombres $a$ et $b$.

Exemple : On cherche $u$ et $v$ tels que $255 u+141 v=3$. \begin{align*} 255=1×141+114&\implies 114=1\times 255-1\times 141\\ 141=1×114+27&\implies 27=-1\times 255+2\times 141\\ 114=4×27+6&\implies 6=5\times 255-9\times 141\\ 27=4×6+3&\implies 3=-21\times 255+38\times 141. \end{align*} L'algorithme d'Euclide étendu permet donc en particulier de calculer les inverses dans les anneaux d'entiers modulaires $\mathbb Z/n\mathbb Z$.

Exemple :
Premier nombre :
Deuxième nombre :
Consulter aussi...
Recherche alphabétique
Recherche thématique