Algorithme d'Euclide étendu

En arithmétique et en programmation informatique , l' algorithme d'Euclide étendu est une extension de l' algorithme d'Euclide et calcule, en plus du plus grand commun diviseur (PGCD) des entiers a et b , les coefficients de l'identité de Bézout , qui sont des entiers x et y tels que ${\displaystyle ax+by=\gcd(a,b) <semantics><mrow><mstyle><mi>un</mi><mi>x</mi><mo>+</mo><mi>b</mi><mi>y</mi><mo>=</mo><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle ax+by=\gcd(a,b)}</annotation></semantics></math><img src=$ ${\displaystyle \operatorname {xgcd} (a,b) <semantics><mrow><mstyle><mi>xgcd</mi><mo>⁡</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {xgcd} (a,b)}</annotation></semantics></math><img src=$

Il s'agit d'un algorithme de certification , car le PGCD est le seul nombre qui puisse simultanément satisfaire cette équation et diviser les entrées. Il permet également de calculer, à un coût presque nul, les quotients de a et b par leur plus grand commun diviseur.

algorithme très similaire pour calculer le plus grand commun diviseur polynomial et les coefficients de l'identité de Bézout de deux polynômes univariés .

L'algorithme d'Euclide étendu est particulièrement utile lorsque a et b sont premiers entre eux . Sous cette condition, x est l' inverse multiplicatif modulaire de a modulo b , et y est l'inverse multiplicatif modulaire de b modulo a . De même, l'algorithme d'Euclide étendu polynomial permet de calculer l' inverse multiplicatif dans les extensions de corps algébriques et, en particulier, dans les corps finis d'ordre non premier. Il s'ensuit que ces deux algorithmes d'Euclide étendus sont largement utilisés en cryptographie . En particulier, le calcul de l' inverse multiplicatif modulaire est une étape essentielle de la génération des paires de clés dans la méthode de chiffrement à clé publique RSA .

Description

L'algorithme d'Euclide standard procède par une succession de divisions euclidiennes dont les quotients ne sont pas utilisés. Seuls les restes sont conservés. Pour l'algorithme étendu, les quotients successifs sont utilisés. Plus précisément, l'algorithme d'Euclide standard, avec a et b comme entrées, consiste à calculer une séquence ${\displaystyle q_{1},\ldots ,q_{k <semantics><mrow><mstyle><msub><mi>q</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>q</mi><mrow><mi>k</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle q_{1},\ldots ,q_{k}}</annotation></semantics></math><img src=$ ${\displaystyle r_{0},\ldots ,r_{k+1 <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>r</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle r_{0},\ldots ,r_{k+1}}</annotation></semantics></math><img src=$

${\displaystyle {\begin{aligned}r_{0}&=a\ _{1}&=b\\&\,\,\,\vdots \ _{i+1}&=r_{i-1}-q_{i}r_{i}\quad { ext{and}}\quad 0\leq r_{i+1}<|r_{i}|\quad { ext{(this defines }}q_{i})\\&\,\,\,\vdots \end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msub><mi>r</mi><mrow><mn>0</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mi>un</mi></mtd></mtr><mtr><mtd><msub><mi>r</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mi>b</mi></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mspace></mspace><mspace></mspace><mspace></mspace><mo>⋮</mo></mtd></mtr><mtr><mtd><msub><mi>r</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><msub><mi>r</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub><mspace></mspace><mrow><mtext>et</mtext></mrow><mspace></mspace><mn>0</mn><mo>≤</mo><msub><mi>r</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo><</mo><mrow><mo>|</mo></mrow><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub><mrow><mo>|</mo></mrow><mspace></mspace><mrow><mtext>(ceci définit </mtext></mrow><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mspace></mspace><mspace></mspace><mspace></mspace><mo>⋮</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}r_{0}&=a\ _{1}&=b\\&\,\,\,\vdots \ _{i+1}&=r_{i-1}-q_{i}r_{i}\quad { ext{et}}\quad 0\leq r_{i+1}<|r_{i}|\quad { ext{(ceci définit }}q_{i})\\&\,\,\,\vdots \end{aligned}}}</annotation></semantics></math><img src=$

La principale propriété de la division euclidienne est que les inégalités à droite définissent de manière unique ${\displaystyle q_{i <semantics><mrow><mstyle><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle q_{i}}</annotation></semantics></math><img src=$ ${\displaystyle r_{i+1 <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle r_{i+1}}</annotation></semantics></math><img src=$ ${\displaystyle r_{i-1 <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle r_{i-1}}</annotation></semantics></math><img src=$ ${\displaystyle r_{i}. <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub><mo>.</mo></mstyle></mrow><annotation>{\displaystyle r_{i}.}</annotation></semantics></math><img src=$

Le calcul s'arrête lorsqu'on atteint un reste ${\displaystyle r_{k+1 <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle r_{k+1}}</annotation></semantics></math><img src=$ ${\displaystyle r_{k}. <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>k</mi></mrow></msub><mo>.</mo></mstyle></mrow><annotation>{\displaystyle r_{k}.}</annotation></semantics></math><img src=$

L'algorithme euclidien étendu procède de manière similaire, mais ajoute deux autres séquences, comme suit

${\displaystyle {\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\ _{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \ _{i+1}&=r_{i-1}-q_{i}r_{i}&{ ext{and }}0&\leq r_{i+1}<|r_{i}|&{ ext{(this defines }}q_{i}{ ext{)}}\\s_{i+1}&=s_{i-1}-q_{i}s_{i}\ _{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\,\vdots \end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msub><mi>r</mi><mrow><mn>0</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mi>un</mi></mtd><mtd><msub><mi>r</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mi>b</mi></mtd></mtr><mtr><mtd><msub><mi>s</mi><mrow><mn>0</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mn>1</mn></mtd><mtd><msub><mi>s</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mn>0</mn></mtd></mtr><mtr><mtd><msub><mi>t</mi><mrow><mn>0</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mn>0</mn></mtd><mtd><msub><mi>t</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mn>1</mn></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mspace></mspace><mspace></mspace><mspace></mspace><mo>⋮</mo></mtd><mtd></mtd><mtd><mi></mi><mspace></mspace><mspace></mspace><mspace></mspace><mo>⋮</mo></mtd></mtr><mtr><mtd><msub><mi>r</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><msub><mi>r</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub></mtd><mtd><mrow><mtext>et </mtext></mrow><mn>0</mn></mtd><mtd><mi></mi><mo>≤</mo><msub><mi>r</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo><</mo><mrow><mo>|</mo></mrow><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub><mrow><mo>|</mo></mrow></mtd><mtd><mrow><mtext>(ceci définit </mtext></mrow><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><mrow><mtext>)</mtext></mrow></mtd></mtr><mtr><mtd><msub><mi>s</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><msub><mi>s</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><msub><mi>t</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mspace></mspace><mspace></mspace><mspace></mspace><mo>⋮</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\ _{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \ _{i+1}&=r_{i-1}-q_{i}r_{i}&{ ext{et }}0&\leq r_{i+1}<|r_{i}|&{ ext{(ceci définit }}q_{i}{ ext{)}}\\s_{i+1}&=s_{i-1}-q_{i}s_{i}\ _{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\,\vdots \end{aligned}}}</annotation></semantics></math><img src=$

Le calcul s'arrête également lorsque ${\displaystyle r_{k+1}=0 <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle r_{k+1}=0}</annotation></semantics></math><img src=$

${\displaystyle r_{k <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>k</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle r_{k}}</annotation></semantics></math><img src=$ ${\displaystyle a=r_{0 <semantics><mrow><mstyle><mi>un</mi><mo>=</mo><msub><mi>r</mi><mrow><mn>0</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle a=r_{0}}</annotation></semantics></math><img src=$ ${\displaystyle b=r_{1}. <semantics><mrow><mstyle><mi>b</mi><mo>=</mo><msub><mi>r</mi><mrow><mn>1</mn></mrow></msub><mo>.</mo></mstyle></mrow><annotation>{\displaystyle b=r_{1}.}</annotation></semantics></math><img src=$
Les coefficients de Bézout sont ${\displaystyle s_{k <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{k}}</annotation></semantics></math><img src=$ ${\displaystyle t_{k}, <semantics><mrow><mstyle><msub><mi>t</mi><mrow><mi>k</mi></mrow></msub><mo>,</mo></mstyle></mrow><annotation>{\displaystyle t_{k},}</annotation></semantics></math><img src=$ ${\displaystyle \gcd(a,b)=r_{k}=as_{k}+bt_{k <semantics><mrow><mstyle><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>=</mo><msub><mi>r</mi><mrow><mi>k</mi></mrow></msub><mo>=</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub><mo>+</mo><mi>b</mi><msub><mi>t</mi><mrow><mi>k</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \gcd(a,b)=r_{k}=as_{k}+bt_{k}}</annotation></semantics></math><img src=$
Les quotients de a et b par leur plus grand commun diviseur sont donnés par ${\displaystyle s_{k+1}=\pm {\frac {b}{\gcd(a,b) <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mo>±</mo><mrow><mfrac><mi>b</mi><mrow><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mrow></mfrac></mrow></mstyle></mrow><annotation>{\displaystyle s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}}</annotation></semantics></math><img src=$ ${\displaystyle t_{k+1}=\mp {\frac {a}{\gcd(a,b) <semantics><mrow><mstyle><msub><mi>t</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mo>∓</mo><mrow><mfrac><mi>un</mi><mrow><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mrow></mfrac></mrow></mstyle></mrow><annotation>{\displaystyle t_{k+1}=\mp {\frac {a}{\gcd(a,b)}}}</annotation></semantics></math><img src=$ ${\displaystyle \mp <semantics><mrow><mstyle><mo>∓</mo></mstyle></mrow><annotation>{\displaystyle \mp }</annotation></semantics></math><img src=$ ${\displaystyle \pm <semantics><mrow><mstyle><mo>±</mo></mstyle></mrow><annotation>{\displaystyle \pm }</annotation></semantics></math><img src=$

De plus, si a et b sont tous deux positifs et ${\displaystyle \gcd(a,b) eq \min(a,b) <semantics><mrow><mstyle><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>≠</mo><mo>min</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \gcd(a,b) eq \min(a,b)}</annotation></semantics></math><img src=$

${\displaystyle |s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}} ight floor \quad { ext{and}}\quad |t_{i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}} ight floor <semantics><mrow><mstyle><mrow><mo>|</mo></mrow><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub><mrow><mo>|</mo></mrow><mo>≤</mo><mrow><mo>⌊</mo><mrow><mfrac><mi>b</mi><mrow><mn>2</mn><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mrow></mfrac></mrow><mo>⌋</mo></mrow><mspace></mspace><mrow><mtext>et</mtext></mrow><mspace></mspace><mrow><mo>|</mo></mrow><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub><mrow><mo>|</mo></mrow><mo>≤</mo><mrow><mo>⌊</mo><mrow><mfrac><mi>un</mi><mrow><mn>2</mn><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mrow></mfrac></mrow><mo>⌋</mo></mrow></mstyle></mrow><annotation>{\displaystyle |s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}} ight floor \quad { ext{et}}\quad |t_{i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}} ight floor }</annotation></semantics></math><img src=$

pour ${\displaystyle 0\leq i\leq k, <semantics><mrow><mstyle><mn>0</mn><mo>≤</mo><mi>je</mi><mo>≤</mo><mi>k</mi><mo>,</mo></mstyle></mrow><annotation>{\displaystyle 0\leq i\leq k,}</annotation></semantics></math><img src=$ ${\displaystyle \lfloor x floor <semantics><mrow><mstyle><mo>⌊</mo><mi>x</mi><mo>⌋</mo></mstyle></mrow><annotation>{\displaystyle \lfloor x floor }</annotation></semantics></math><img src=$

Cela implique que la paire de coefficients de Bézout fournie par l'algorithme euclidien étendu est la paire minimale de coefficients de Bézout, car il s'agit de la seule paire satisfaisant les deux inégalités ci-dessus.

Cela signifie également que si a et b tiennent dans un type de données entier non signé , un programme informatique peut calculer les coefficients de Bézout dans le type entier signé correspondant sans dépassement d'entier .

Exemples

Le tableau suivant illustre le déroulement de l'algorithme d'Euclide étendu avec les entrées et Le plus grand commun diviseur (PGCD) est la dernière valeur non nulle, soit dans la colonne « reste ». Le calcul s'arrête à la ligne 6, car le reste y est . Les coefficients de Bézout apparaissent dans les deux dernières colonnes de l'avant-dernière ligne. En effet, on vérifie aisément que × 240 + 47 × 46 = 2. Enfin, les deux dernières valeurs, et , de la dernière ligne correspondent, au signe près, aux quotients des entrées et par le PGCD .

L'exemple suivant utilise une notation plus compacte. Le plus grand commun diviseur de ${\displaystyle a=68 <semantics><mrow><mstyle><mi>un</mi><mo>=</mo><mn>68</mn></mstyle></mrow><annotation>{\displaystyle a=68}</annotation></semantics></math><img src=$ ${\displaystyle b=30 <semantics><mrow><mstyle><mi>b</mi><mo>=</mo><mn>30</mn></mstyle></mrow><annotation>{\displaystyle b=30}</annotation></semantics></math><img src=$

${\displaystyle g=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \;\;^{\uparrow }\!\!-\!-\!(-2)}{(68,30)}}=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \!(-3)\!-\!\!-\!^{\uparrow }\;\;}{(8,30) <semantics><mrow><mstyle><mi>g</mi><mo>=</mo><mrow><mi>g</mi><mi>c</mi><mi>d</mi></mrow><mrow><munder><mrow><mo>(</mo><mn>68</mn><mo>,</mo><mn>30</mn><mo>)</mo></mrow><mstyle><mstyle><mspace></mspace><msup><mspace></mspace><mrow><mo>↑</mo></mrow></msup><mspace></mspace><mspace></mspace><mo>−</mo><mspace></mspace><mo>−</mo><mspace></mspace><mo>(</mo><mo>−</mo><mn>2</mn><mo>)</mo></mstyle></mstyle></munder></mrow><mo>=</mo><mrow><mi>g</mi><mi>c</mi><mi>d</mi></mrow><mrow><munder><mrow><mo>(</mo><mn>8</mn><mo>,</mo><mn>30</mn><mo>)</mo></mrow><mstyle><mstyle><mspace></mspace><mo>(</mo><mo>−</mo><mn>3</mn><mo>)</mo><mspace></mspace><mo>−</mo><mspace></mspace><mspace></mspace><mo>−</mo><msup><mspace></mspace><mrow><mo>↑</mo></mrow></msup><mspace></mspace><mspace></mspace></mstyle></mstyle></munder></mrow></mstyle></mrow><annotation>{\displaystyle g=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \;\;^{\uparrow }\!\!-\!-\!(-2)}{(68,30)}}=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \!(-3)\!-\!\!-\!^{\uparrow }\;\;}{(8,30)}}}</annotation></semantics></math><img src=$ ${\displaystyle =\mathrm {gcd} {\underset {\color {Green}\scriptstyle \;^{\uparrow }\!\!-\!\!-\!(-1)\!\!}{(8,\,6)}}=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \!\!(-3)\!-\!\!-\!^{\uparrow }\;}{(2,\,6)}}=\mathrm {gcd} (2,0)=2, <semantics><mrow><mstyle><mo>=</mo><mrow><mi>g</mi><mi>c</mi><mi>d</mi></mrow><mrow><munder><mrow><mo>(</mo><mn>8</mn><mo>,</mo><mspace></mspace><mn>6</mn><mo>)</mo></mrow><mstyle><mstyle><msup><mspace></mspace><mrow><mo>↑</mo></mrow></msup><mspace></mspace><mspace></mspace><mo>−</mo><mspace></mspace><mspace></mspace><mo>−</mo><mspace></mspace><mo>(</mo><mo>−</mo><mn>1</mn><mo>)</mo><mspace></mspace><mspace></mspace></mstyle></mstyle></munder></mrow><mo>=</mo><mrow><mi>g</mi><mi>c</mi><mi>d</mi></mrow><mrow><munder><mrow><mo>(</mo><mn>2</mn><mo>,</mo><mspace></mspace><mn>6</mn><mo>)</mo></mrow><mstyle><mstyle><mspace></mspace><mspace></mspace><mo>(</mo><mo>−</mo><mn>3</mn><mo>)</mo><mspace></mspace><mo>−</mo><mspace></mspace><mspace></mspace><mo>−</mo><msup><mspace></mspace><mrow><mo>↑</mo></mrow></msup><mspace></mspace></mstyle></mstyle></munder></mrow><mo>=</mo><mrow><mi>g</mi><mi>c</mi><mi>d</mi></mrow><mo>(</mo><mn>2</mn><mo>,</mo><mn>0</mn><mo>)</mo><mo>=</mo><mn>2</mn><mo>,</mo></mstyle></mrow><annotation>{\displaystyle =\mathrm {gcd} {\underset {\color {Green}\scriptstyle \;^{\uparrow }\!\!-\!\!-\!(-1)\!\!}{(8,\,6)}}=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \!\!(-3)\!-\!\!-\!^{\uparrow }\;}{(2,\,6)}}=\mathrm {gcd} (2,0)=2,}</annotation></semantics></math><img src=$

où ${\displaystyle \color {Green}\scriptstyle \,^{\uparrow }\!\!-\!-\!(-2) <semantics><mrow><mstyle><mstyle><mstyle><msup><mspace></mspace><mrow><mo>↑</mo></mrow></msup><mspace></mspace><mspace></mspace><mo>−</mo><mspace></mspace><mo>−</mo><mspace></mspace><mo>(</mo><mo>−</mo><mn>2</mn><mo>)</mo></mstyle></mstyle></mstyle></mrow><annotation>{\displaystyle \color {Vert}\scriptstyle \,^{\uparrow }\!\!-\!-\!(-2)}</annotation></semantics></math><img src=$ ${\displaystyle -2 <semantics><mrow><mstyle><mo>−</mo><mn>2</mn></mstyle></mrow><annotation>{\displaystyle -2}</annotation></semantics></math><img src=$ ${\displaystyle 30 <semantics><mrow><mstyle><mn>30</mn></mstyle></mrow><annotation>{\displaystyle 30}</annotation></semantics></math><img src=$ ${\displaystyle 68 <semantics><mrow><mstyle><mn>68</mn></mstyle></mrow><annotation>{\displaystyle 68}</annotation></semantics></math><img src=$

En appliquant les additions de multiples indiquées en vert de manière analogue aux équations, en commençant par ${\displaystyle a=1a+0b <semantics><mrow><mstyle><mi>un</mi><mo>=</mo><mn>1</mn><mi>un</mi><mo>+</mo><mn>0</mn><mi>b</mi></mstyle></mrow><annotation>{\displaystyle a=1a+0b}</annotation></semantics></math><img src=$ ${\displaystyle b=0a+1b, <semantics><mrow><mstyle><mi>b</mi><mo>=</mo><mn>0</mn><mi>un</mi><mo>+</mo><mn>1</mn><mi>b</mi><mo>,</mo></mstyle></mrow><annotation>{\displaystyle b=0a+1b,}</annotation></semantics></math><img src=$ ${\displaystyle g=4a-9b, <semantics><mrow><mstyle><mi>g</mi><mo>=</mo><mn>4</mn><mi>un</mi><mo>−</mo><mn>9</mn><mi>b</mi><mo>,</mo></mstyle></mrow><annotation>{\displaystyle g=4a-9b,}</annotation></semantics></math><img src=$

Preuve

Depuis ${\displaystyle 0\leq r_{i+1}<|r_{i}| <semantics><mrow><mstyle><mn>0</mn><mo>≤</mo><msub><mi>r</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo><</mo><mrow><mo>|</mo></mrow><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub><mrow><mo>|</mo></mrow></mstyle></mrow><annotation>{\displaystyle 0\leq r_{i+1}<|r_{i}|}</annotation></semantics></math><img src=$ ${\displaystyle r_{i <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle r_{i}}</annotation></semantics></math><img src=$ ${\displaystyle i\geq 2 <semantics><mrow><mstyle><mi>je</mi><mo>≥</mo><mn>2</mn></mstyle></mrow><annotation>{\displaystyle i\geq 2}</annotation></semantics></math><img src=$ ${\displaystyle r_{k+1}=0 <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle r_{k+1}=0}</annotation></semantics></math><img src=$

À partir de l'équation ${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><msub><mi>r</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i}}</annotation></semantics></math><img src=$ ${\displaystyle \gcd(r_{i-1},r_{i})=\gcd(r_{i},r_{i+1}) <semantics><mrow><mstyle><mo>pgcd</mo><mo>(</mo><msub><mi>r</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>=</mo><mo>pgcd</mo><mo>(</mo><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub><mo>,</mo><msub><mi>r</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \gcd(r_{i-1},r_{i})=\gcd(r_{i},r_{i+1})}</annotation></semantics></math><img src=$ ${\displaystyle \gcd(a,b)=\gcd(r_{0},r_{1})=\gcd(r_{k},r_{k+1})=\gcd(r_{k},0)=r_{k <semantics><mrow><mstyle><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>=</mo><mo>pgcd</mo><mo>(</mo><msub><mi>r</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><msub><mi>r</mi><mrow><mn>1</mn></mrow></msub><mo>)</mo><mo>=</mo><mo>pgcd</mo><mo>(</mo><msub><mi>r</mi><mrow><mi>k</mi></mrow></msub><mo>,</mo><msub><mi>r</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>=</mo><mo>pgcd</mo><mo>(</mo><msub><mi>r</mi><mrow><mi>k</mi></mrow></msub><mo>,</mo><mn>0</mn><mo>)</mo><mo>=</mo><msub><mi>r</mi><mrow><mi>k</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \gcd(a,b)=\gcd(r_{0},r_{1})=\gcd(r_{k},r_{k+1})=\gcd(r_{k},0)=r_{k}}</annotation></semantics></math><img src=$

Les relations de récurrence, pour ${\displaystyle i\geq 0 <semantics><mrow><mstyle><mi>je</mi><mo>≥</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle i\geq 0}</annotation></semantics></math><img src=$

${\displaystyle {\begin{cases}r_{i}&=as_{i}+bt_{i}\\(-1)^{i}&=s_{i}t_{i+1}-t_{i}s_{i+1}\end{cases <semantics><mrow><mstyle><mrow><mrow><mo>{</mo><mtable><mtr><mtd><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub></mtd><mtd><mo>=</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub><mo>+</mo><mi>b</mi><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub></mtd></mtr><mtr><mtd><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>je</mi></mrow></msup></mtd><mtd><mo>=</mo><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub><msub><mi>s</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub></mtd></mtr></mtable><mo></mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{cases}r_{i}&=as_{i}+bt_{i}\\(-1)^{i}&=s_{i}t_{i+1}-t_{i}s_{i+1}\end{cases}}}</annotation></semantics></math><img src=$

peut être démontré par induction. En fait, pour ${\displaystyle i=0 <semantics><mrow><mstyle><mi>je</mi><mo>=</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle i=0}</annotation></semantics></math><img src=$

${\displaystyle {\begin{cases}r_{0}&=a=as_{0}+bt_{0}\\1&=(-1)^{0}=1\cdot 1-0\cdot 0=s_{0}t_{1}-t_{0}s_{1}\end{cases <semantics><mrow><mstyle><mrow><mrow><mo>{</mo><mtable><mtr><mtd><msub><mi>r</mi><mrow><mn>0</mn></mrow></msub></mtd><mtd><mo>=</mo><mi>un</mi><mo>=</mo><mi>un</mi><msub><mi>s</mi><mrow><mn>0</mn></mrow></msub><mo>+</mo><mi>b</mi><msub><mi>t</mi><mrow><mn>0</mn></mrow></msub></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mo>=</mo><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mn>0</mn></mrow></msup><mo>=</mo><mn>1</mn><mo>⋅</mo><mn>1</mn><mo>−</mo><mn>0</mn><mo>⋅</mo><mn>0</mn><mo>=</mo><msub><mi>s</mi><mrow><mn>0</mn></mrow></msub><msub><mi>t</mi><mrow><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>t</mi><mrow><mn>0</mn></mrow></msub><msub><mi>s</mi><mrow><mn>1</mn></mrow></msub></mtd></mtr></mtable><mo></mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{cases}r_{0}&=a=as_{0}+bt_{0}\\1&=(-1)^{0}=1\cdot 1-0\cdot 0=s_{0}t_{1}-t_{0}s_{1}\end{cases}}}</annotation></semantics></math><img src=$

En supposant qu'ils soient satisfaits pour certains ${\displaystyle i <semantics><mrow><mstyle><mi>je</mi></mstyle></mrow><annotation>{\displaystyle i}</annotation></semantics></math><img src=$ ${\displaystyle i+1 <semantics><mrow><mstyle><mi>je</mi><mo>+</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle i+1}</annotation></semantics></math><img src=$

${\displaystyle {\begin{cases}r_{i+1}&=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{i})q_{i}=(as_{i-1}-as_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1}+bt_{i+1}\\(-1)^{i+1}&=-(s_{i}t_{i+1}-t_{i}s_{i+1})=s_{i+1}(t_{i}-q_{i+1}t_{i+1})-t_{i+1}(s_{i}-q_{i+1}s_{i+1})=s_{i+1}t_{i+2}-t_{i+1}s_{i+2}\end{cases <semantics><mrow><mstyle><mrow><mrow><mo>{</mo><mtable><mtr><mtd><msub><mi>r</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub></mtd><mtd><mo>=</mo><msub><mi>r</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mo>(</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>+</mo><mi>b</mi><msub><mi>t</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>−</mo><mo>(</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub><mo>+</mo><mi>b</mi><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mo>(</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>−</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>+</mo><mo>(</mo><mi>b</mi><msub><mi>t</mi><mrow><mi>je</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>−</mo><mi>b</mi><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>=</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mi>b</mi><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msup></mtd><mtd><mo>=</mo><mo>−</mo><mo>(</mo><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub><msub><mi>s</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>=</mo><msub><mi>s</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>(</mo><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub><mo>−</mo><msub><mi>q</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>−</mo><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>(</mo><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub><mo>−</mo><msub><mi>q</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><msub><mi>s</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>=</mo><msub><mi>s</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>2</mn></mrow></msub><mo>−</mo><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><msub><mi>s</mi><mrow><mi>je</mi><mo>+</mo><mn>2</mn></mrow></msub></mtd></mtr></mtable><mo></mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{cases}r_{i+1}&=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{i})q_{i}=(as_{i-1}-as_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1}+bt_{i+1}\\(-1)^{i+1}&=-(s_{i}t_{i+1}-t_{i}s_{i+1})=s_{i+1}(t_{i}-q_{i+1}t_{i+1})-t_{i+1}(s_{i}-q_{i+1}s_{i+1})=s_{i+1}t_{i+2}-t_{i+1}s_{i+2}\end{cases}}}</annotation></semantics></math><img src=$

En particulier, l'équation ${\displaystyle s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub><msub><mi>s</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>je</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i}}</annotation></semantics></math><img src=$ ${\displaystyle s_{k+1 <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{k+1}}</annotation></semantics></math><img src=$ ${\displaystyle t_{k+1 <semantics><mrow><mstyle><msub><mi>t</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle t_{k+1}}</annotation></semantics></math><img src=$

Multiplication ${\displaystyle 0=r_{k+1}=as_{k+1}+bt_{k+1 <semantics><mrow><mstyle><mn>0</mn><mo>=</mo><msub><mi>r</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mi>b</mi><msub><mi>t</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle 0=r_{k+1}=as_{k+1}+bt_{k+1}}</annotation></semantics></math><img src=$ ${\displaystyle s_{k <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{k}}</annotation></semantics></math><img src=$

${\displaystyle 0=as_{k+1}s_{k}+bt_{k+1}s_{k}=as_{k+1}s_{k}+b((-1)^{k}+t_{k}s_{k+1}) <semantics><mrow><mstyle><mn>0</mn><mo>=</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub><mo>+</mo><mi>b</mi><msub><mi>t</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub><mo>=</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub><mo>+</mo><mi>b</mi><mo>(</mo><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>k</mi></mrow></msup><mo>+</mo><msub><mi>t</mi><mrow><mi>k</mi></mrow></msub><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle 0=as_{k+1}s_{k}+bt_{k+1}s_{k}=as_{k+1}s_{k}+b((-1)^{k}+t_{k}s_{k+1})}</annotation></semantics></math><img src=$

Donc, ${\displaystyle b=(-1)^{k+1}(t_{k}-as_{k})s_{k+1 <semantics><mrow><mstyle><mi>b</mi><mo>=</mo><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msup><mo>(</mo><msub><mi>t</mi><mrow><mi>k</mi></mrow></msub><mo>−</mo><mi>un</mi><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub><mo>)</mo><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle b=(-1)^{k+1}(t_{k}-as_{k})s_{k+1}}</annotation></semantics></math><img src=$ ${\displaystyle s_{k+1 <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{k+1}}</annotation></semantics></math><img src=$ ${\displaystyle b <semantics><mrow><mstyle><mi>b</mi></mstyle></mrow><annotation>{\displaystyle b}</annotation></semantics></math><img src=$ ${\displaystyle d <semantics><mrow><mstyle><mi>d</mi></mstyle></mrow><annotation>{\displaystyle d}</annotation></semantics></math><img src=$ ${\displaystyle b=ds_{k+1 <semantics><mrow><mstyle><mi>b</mi><mo>=</mo><mi>d</mi><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle b=ds_{k+1}}</annotation></semantics></math><img src=$ ${\displaystyle s_{k+1 <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{k+1}}</annotation></semantics></math><img src=$ ${\displaystyle as_{k+1}+bt_{k+1}=0 <semantics><mrow><mstyle><mi>un</mi><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mi>b</mi><msub><mi>t</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle as_{k+1}+bt_{k+1}=0}</annotation></semantics></math><img src=$ ${\displaystyle a=-dt_{k+1}. <semantics><mrow><mstyle><mi>un</mi><mo>=</mo><mo>−</mo><mi>d</mi><msub><mi>t</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>.</mo></mstyle></mrow><annotation>{\displaystyle a=-dt_{k+1}.}</annotation></semantics></math><img src=$ ${\displaystyle s_{k+1 <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{k+1}}</annotation></semantics></math><img src=$ ${\displaystyle -t_{k+1 <semantics><mrow><mstyle><mo>−</mo><msub><mi>t</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle -t_{k+1}}</annotation></semantics></math><img src=$ ${\displaystyle a <semantics><mrow><mstyle><mi>un</mi></mstyle></mrow><annotation>{\displaystyle a}</annotation></semantics></math><img src=$ ${\displaystyle b <semantics><mrow><mstyle><mi>b</mi></mstyle></mrow><annotation>{\displaystyle b}</annotation></semantics></math><img src=$

Pour prouver la dernière assertion, supposons que ${\displaystyle a <semantics><mrow><mstyle><mi>un</mi></mstyle></mrow><annotation>{\displaystyle a}</annotation></semantics></math><img src=$ ${\displaystyle b <semantics><mrow><mstyle><mi>b</mi></mstyle></mrow><annotation>{\displaystyle b}</annotation></semantics></math><img src=$ ${\displaystyle \gcd(a,b) eq \min(a,b) <semantics><mrow><mstyle><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>≠</mo><mo>min</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \gcd(a,b) eq \min(a,b)}</annotation></semantics></math><img src=$ ${\displaystyle a eq b <semantics><mrow><mstyle><mi>un</mi><mo>≠</mo><mi>b</mi></mstyle></mrow><annotation>{\displaystyle a eq b}</annotation></semantics></math><img src=$ ${\displaystyle a<mrow><mstyle><mi>un</mi><mo><</mo><mi>b</mi></mstyle></mrow><annotation>{\displaystyle a<b}</annotation></semantics></math><img src=$ s et t pour ( a , b ) sous l'hypothèse d'égalité des termes (EEA) sont, à 0 et 1 près, les séquences t et s pour ( b , a ). Les définitions montrent alors que le cas ( a , b ) se réduit au cas ( b , a ). Supposons donc que… $b un > b$ b sans perte de généralité .

On peut constater que ${\displaystyle s_{2 <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mn>2</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{2}}</annotation></semantics></math><img src=$ ${\displaystyle s_{3 <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mn>3</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{3}}</annotation></semantics></math><img src=$ ${\displaystyle \gcd(a,b) eq \min(a,b) <semantics><mrow><mstyle><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>≠</mo><mo>min</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \gcd(a,b) eq \min(a,b)}</annotation></semantics></math><img src=$ ${\displaystyle s_{i <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{i}}</annotation></semantics></math><img src=$ ${\displaystyle q_{i}\geq 1 <semantics><mrow><mstyle><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><mo>≥</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle q_{i}\geq 1}</annotation></semantics></math><img src=$ ${\displaystyle 1\leq i\leq k <semantics><mrow><mstyle><mn>1</mn><mo>≤</mo><mi>je</mi><mo>≤</mo><mi>k</mi></mstyle></mrow><annotation>{\displaystyle 1\leq i\leq k}</annotation></semantics></math><img src=$ ${\displaystyle i=1 <semantics><mrow><mstyle><mi>je</mi><mo>=</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle i=1}</annotation></semantics></math><img src=$ $b un > b$ b Il en va de même pour le ${\displaystyle t_{i <semantics><mrow><mstyle><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle t_{i}}</annotation></semantics></math><img src=$ ${\displaystyle q_{k}\geq 2 <semantics><mrow><mstyle><msub><mi>q</mi><mrow><mi>k</mi></mrow></msub><mo>≥</mo><mn>2</mn></mstyle></mrow><annotation>{\displaystyle q_{k}\geq 2}</annotation></semantics></math><img src=$ a et b sont tous deux positifs et ${\displaystyle \gcd(a,b) eq \min(a,b) <semantics><mrow><mstyle><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>≠</mo><mo>min</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \gcd(a,b) eq \min(a,b)}</annotation></semantics></math><img src=$ ${\displaystyle |s_{k+1}|=|s_{k-1}|+q_{k}|s_{k}| <semantics><mrow><mstyle><mrow><mo>|</mo></mrow><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mrow><mo>|</mo></mrow><mo>=</mo><mrow><mo>|</mo></mrow><msub><mi>s</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msub><mrow><mo>|</mo></mrow><mo>+</mo><msub><mi>q</mi><mrow><mi>k</mi></mrow></msub><mrow><mo>|</mo></mrow><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub><mrow><mo>|</mo></mrow></mstyle></mrow><annotation>{\displaystyle |s_{k+1}|=|s_{k-1}|+q_{k}|s_{k}|}</annotation></semantics></math><img src=$ ${\displaystyle |s_{k+1}|=\left|{\frac {b}{\gcd(a,b)}} ight|\geq 2|s_{k}|\qquad { ext{and}}\qquad |t_{k+1}|=\left|{\frac {a}{\gcd(a,b)}} ight|\geq 2|t_{k}|. <semantics><mrow><mstyle><mrow><mo>|</mo></mrow><msub><mi>s</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mrow><mo>|</mo></mrow><mo>=</mo><mrow><mo>|</mo><mrow><mfrac><mi>b</mi><mrow><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mrow></mfrac></mrow><mo>|</mo></mrow><mo>≥</mo><mn>2</mn><mrow><mo>|</mo></mrow><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub><mrow><mo>|</mo></mrow><mspace></mspace><mrow><mtext>et</mtext></mrow><mspace></mspace><mrow><mo>|</mo></mrow><msub><mi>t</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mrow><mo>|</mo></mrow><mo>=</mo><mrow><mo>|</mo><mrow><mfrac><mi>un</mi><mrow><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mrow></mfrac></mrow><mo>|</mo></mrow><mo>≥</mo><mn>2</mn><mrow><mo>|</mo></mrow><msub><mi>t</mi><mrow><mi>k</mi></mrow></msub><mrow><mo>|</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle |s_{k+1}|=\left|{\frac {b}{\gcd(a,b)}} ight|\geq 2|s_{k}|\qquad { ext{and}}\qquad |t_{k+1}|=\left|{\frac {a}{\gcd(a,b)}} ight|\geq 2|t_{k}|.}</annotation></semantics></math><img src=$

Ceci, accompagné du fait que ${\displaystyle s_{k},t_{k <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>k</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{k},t_{k}}</annotation></semantics></math><img src=$ ${\displaystyle s_{i <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{i}}</annotation></semantics></math><img src=$ ${\displaystyle t_{i <semantics><mrow><mstyle><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle t_{i}}</annotation></semantics></math><img src=$

Algorithme d'Euclide étendu polynomial

${\displaystyle 0\leq r_{i+1}<|r_{i}| <mrow><mstyle><mi>deg</mi><mo>⁡</mo><msub><mi>r</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo><</mo><mi>deg</mi><mo>⁡</mo><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \deg r_{i+1}<\deg r_{i}.}</annotation></semantics></math><img src=$
Une seconde différence réside dans la limite de la taille des coefficients de Bézout fournie par l'algorithme euclidien étendu, qui est plus précise dans le cas polynomial, ce qui conduit au théorème suivant.
Si a et b sont deux polynômes non nuls, alors l'algorithme d'Euclide étendu produit la paire unique de polynômes ( s , t ) telle que
${\displaystyle as+bt=\gcd(a,b) <semantics><mrow><mstyle><mi>un</mi><mi>s</mi><mo>+</mo><mi>b</mi><mi>t</mi><mo>=</mo><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle as+bt=\gcd(a,b)}</annotation></semantics></math><img src=$
et
${\displaystyle \deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)). <semantics><mrow><mstyle><mi>deg</mi><mo>⁡</mo><mi>s</mi><mo><</mo><mi>deg</mi><mo>⁡</mo><mi>b</mi><mo>−</mo><mi>deg</mi><mo>⁡</mo><mo>(</mo><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>)</mo><mo>,</mo><mspace></mspace><mi>deg</mi><mo>⁡</mo><mi>t</mi><mo><</mo><mi>deg</mi><mo>⁡</mo><mi>un</mi><mo>−</mo><mi>deg</mi><mo>⁡</mo><mo>(</mo><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>)</mo><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).}</annotation></semantics></math><img src=$
Une troisième différence réside dans le fait que, dans le cas des polynômes, le plus grand commun diviseur est défini à une multiplication près par une constante non nulle. Il existe plusieurs façons de définir sans ambiguïté un plus grand commun diviseur.
En mathématiques, il est courant d'exiger que le plus grand commun diviseur soit un polynôme unitaire . Pour ce faire, il suffit de diviser chaque élément du résultat par le coefficient dominant de ce polynôme. ${\displaystyle r_{k}. <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>k</mi></mrow></msub><mo>.</mo></mstyle></mrow><annotation>{\displaystyle r_{k}.}</annotation></semantics></math><img src=$ a et b sont premiers entre eux, d'obtenir 1 dans le membre de droite de l'inégalité de Bézout. Sinon, on peut obtenir n'importe quelle constante non nulle. En calcul formel , les polynômes ont généralement des coefficients entiers, et cette méthode de normalisation du plus grand commun diviseur introduit trop de fractions pour être pratique.
La deuxième façon de normaliser le plus grand commun diviseur dans le cas des polynômes à coefficients entiers consiste à diviser chaque résultat par le contenu de ${\displaystyle r_{k}, <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>k</mi></mrow></msub><mo>,</mo></mstyle></mrow><annotation>{\displaystyle r_{k},}</annotation></semantics></math><img src=$
Une troisième approche consiste à étendre l'algorithme des suites de pseudo-restes sous-résultants d'une manière similaire à l'extension de l'algorithme d'Euclide à l'algorithme d'Euclide étendu. Ceci permet, en partant de polynômes à coefficients entiers, que tous les polynômes calculés aient des coefficients entiers. De plus, chaque reste calculé ${\displaystyle r_{i <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle r_{i}}</annotation></semantics></math><img src=$
${\displaystyle as+bt=\operatorname {Res} (a,b), <semantics><mrow><mstyle><mi>un</mi><mi>s</mi><mo>+</mo><mi>b</mi><mi>t</mi><mo>=</mo><mi>Res</mi><mo>⁡</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>,</mo></mstyle></mrow><annotation>{\displaystyle as+bt=\operatorname {Res} (a,b),}</annotation></semantics></math><img src=$
où ${\displaystyle \operatorname {Res} (a,b) <semantics><mrow><mstyle><mi>Res</mi><mo>⁡</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {Res} (a,b)}</annotation></semantics></math><img src=$ a et b . Dans cette forme de l'identité de Bézout, la formule ne comporte pas de dénominateur. Si l'on divise tous les termes par le résultant, on retrouve l'identité de Bézout classique, avec un dénominateur commun explicite pour les nombres rationnels qui y figurent.

Pseudocode

${\displaystyle ax+by=\gcd(a,b) <mrow><mstyle><mi>y</mi></mstyle></mrow><annotation>{\displaystyle y}</annotation></semantics></math><img src=$ ${\displaystyle a,b,x,\gcd(a,b) <semantics><mrow><mstyle><mi>un</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>x</mi><mo>,</mo><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle a,b,x,\gcd(a,b)}</annotation></semantics></math><img src=$ ${\displaystyle s_{k <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>k</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle s_{k}}</annotation></semantics></math><img src=$ ${\displaystyle x <semantics><mrow><mstyle><mi>x</mi></mstyle></mrow><annotation>{\displaystyle x}</annotation></semantics></math><img src=$ ${\displaystyle y <semantics><mrow><mstyle><mi>y</mi></mstyle></mrow><annotation>{\displaystyle y}</annotation></semantics></math><img src=$
fonction pgcd_étendu(a, b) s := 0; vieux_s := 1 r := b; vieux_r := a tant que r ≠ 0 faire quotient := ancien_r div r (ancien_r, r) := (r, ancien_r − quotient × r) (ancien_s, s) := (s, ancien_s − quotient × s) si b ≠ 0 alors bezout_t := (old_r − old_s × a) div b sinon bezout_t := 0 sortie "Coefficients de Bézout :", (old_s, bezout_t) sortie "Plus grand commun diviseur :", old_r
Cependant, dans de nombreux cas, il ne s'agit pas réellement d'une optimisation : alors que l'algorithme précédent n'est pas sujet aux dépassements de capacité lorsqu'il est utilisé avec des entiers machine (c'est-à-dire des entiers dont le nombre de chiffres est limité), la multiplication de ` old_s` × `a` dans le calcul de `bezout_t` peut provoquer un dépassement de capacité, limitant ainsi cette optimisation aux entrées pouvant être représentées avec moins de la moitié de la taille maximale. Avec des entiers de taille illimitée, le temps nécessaire aux multiplications et divisions croît quadratiquement avec la taille des entiers. Cela signifie que l'« optimisation » remplace une séquence de multiplications/divisions de petits entiers par une seule multiplication/division, ce qui requiert un temps de calcul supérieur à celui de l'ensemble des opérations remplacées.

Simplification des fractions

Une fraction / b est sous forme simplifiée canonique si et sont premiers entre eux et si positif. Cette forme simplifiée canonique peut être obtenue en remplaçant les trois lignes de sortie du pseudo-code précédent par

Si , afficher « Division par zéro » . Si  s  t pour éviter les dénominateurs négatifs ).  s , alors afficher  ( pour éviter les dénominateurs égaux à 1)  Afficher

La démonstration de cet algorithme repose sur le fait que et sont deux entiers premiers entre eux tels que , et donc ${\displaystyle {\frac {a}{b}}=-{\frac {t}{s <semantics><mrow><mstyle><mrow><mfrac><mi>un</mi><mi>b</mi></mfrac></mrow><mo>=</mo><mo>−</mo><mrow><mfrac><mi>t</mi><mi>s</mi></mfrac></mrow></mstyle></mrow><annotation>{\displaystyle {\frac {a}{b}}=-{\frac {t}{s}}}</annotation></semantics></math><img src=$

Si divise sans reste, l'algorithme n'effectue qu'une seule itération et à la fin. C'est le seul cas où le résultat est un entier.

Calcul des inverses multiplicatifs dans les structures modulaires

L'algorithme d'Euclide étendu est l'outil essentiel pour le calcul des inverses multiplicatifs dans les structures modulaires, notamment les entiers modulaires et les extensions de corps algébriques . Les corps finis d'ordre non premier en sont un exemple notable.

Entiers modulaires

est un entier positif, l' anneau peut être identifié à l'ensemble { des restes de la division euclidienne par , de l'addition et de la multiplication consistant à prendre le reste par du résultat de l'addition et de la multiplication des entiers. Un élément de possède un inverse multiplicatif (c'est-à-dire qu'il est ) s'il est premier avec . En particulier, si est premier , possède un inverse multiplicatif s'il est non nul (modulo ). Ainsi, si et seulement si est premier.
L'identité de Bézout affirme que et sont premiers entre eux si et seulement s'il existe des entiers et tels que
${\displaystyle ns+at=1 <semantics><mrow><mstyle><mi>n</mi><mi>s</mi><mo>+</mo><mi>un</mi><mi>t</mi><mo>=</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle ns+at=1}</annotation></semantics></math><img src=$
La réduction de cette identité modulo donne
${\displaystyle at\equiv 1\mod n. <semantics><mrow><mstyle><mi>un</mi><mi>t</mi><mo>≡</mo><mn>1</mn><mspace></mspace><mi>mod</mi><mspace></mspace><mspace></mspace><mi>n</mi><mo>.</mo></mstyle></mrow><annotation>{\displaystyle at\equiv 1\mod n.}</annotation></semantics></math><img src=$
Ainsi , , ou plus exactement, le reste de la division de par , est l'inverse multiplicatif de modulo .
Pour adapter l'algorithme d'Euclide étendu à ce problème, il convient de noter que le coefficient de Bézout de n'est pas nécessaire et n'a donc pas besoin d'être calculé. De plus, pour obtenir un résultat positif et inférieur à n , on peut utiliser le fait que l'entier fourni par l'algorithme satisfait . Autrement dit, si , il faut lui ajouter à la fin (un exemple est disponible dans l'article « Inverse multiplicatif modulaire »). On obtient ainsi le pseudocode suivant, où n est un entier supérieur à 1.
fonction inverse(a, n) t := 0; newt := 1 r := n; nouveaur := a while newr ≠ 0 do quotient := r div newr (t, triton) := (triton, t − quotient × triton) (r, nouveau) := (nouveau, r − quotient × nouveau) si r > 1 alors retourner « a n'est pas inversible » si t < 0 alors t := t + n retourner t

Extensions de corps algébriques simples

L'algorithme d'Euclide étendu est également l'outil principal pour le calcul des inverses multiplicatifs dans les extensions algébriques simples de corps . Un cas important, largement utilisé en cryptographie et en théorie du codage , est celui des corps finis d'ordre non premier. En effet, si est un nombre premier et , le corps d'ordre est une extension algébrique simple du corps premier à éléments, engendrée par une racine d'un polynôme irréductible de degré .

Une extension algébrique simple d'un corps , engendrée par la racine d'un polynôme irréductible de degré peut être identifiée à l' anneau quotient. ${\displaystyle K[X]/\langle p angle , <semantics><mrow><mstyle><mi>K</mi><mo>[</mo><mi>X</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>⟨</mo><mi>p</mi><mo>⟩</mo><mo>,</mo></mstyle></mrow><annotation>{\displaystyle K[X]/\langle p angle ,}</annotation></semantics></math><img src=$

L'algorithme est très similaire à celui présenté précédemment pour le calcul de l'inverse multiplicatif modulaire. Deux différences principales subsistent : premièrement, l'avant-dernière ligne est inutile, car le coefficient de Bézout fourni est toujours de degré inférieur à . Deuxièmement, le plus grand commun diviseur fourni, lorsque les polynômes d'entrée sont premiers entre eux, peut être n'importe quel élément non nul de ; ce coefficient de Bézout (un polynôme généralement de degré positif) doit donc être multiplié par l'inverse de cet élément de Dans le pseudocode qui suit, est un polynôme de degré supérieur à un, et est un polynôme.

fonction inverse(a, p) t := 0; newt := 1 r := p; nouveaur := a while newr ≠ 0 do quotient := r div newr (r, nouveau) := (nouveau, r − quotient × nouveau) (t, triton) := (triton, t − quotient × triton) si degree(r) > 0 alors retourner "Soit p n'est pas irréductible, soit a est un multiple de p" retour (1/r) × t

Exemple

Par exemple, si le polynôme définissant le corps fini GF(2⁸ ^x⁴ + calcul corps d'ordre 2ⁿ, on a −z = z et z + z 0 ^pour tout élément z du corps . Puisque 1 est le seul élément non nul de GF(2), la modification de la dernière ligne du pseudocode est inutile.

Ainsi, l'inverse est , comme on peut le confirmer en multipliant les deux éléments ensemble et en prenant le reste par ${\displaystyle \gcd(a,b,c)=\gcd(\gcd(a,b),c) <mrow><mstyle><mi>d</mi><mo>=</mo><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle d=\gcd(a,b,c)}</annotation></semantics></math><img src=$ ${\displaystyle d <semantics><mrow><mstyle><mi>d</mi></mstyle></mrow><annotation>{\displaystyle d}</annotation></semantics></math><img src=$ ${\displaystyle a <semantics><mrow><mstyle><mi>un</mi></mstyle></mrow><annotation>{\displaystyle a}</annotation></semantics></math><img src=$ ${\displaystyle b <semantics><mrow><mstyle><mi>b</mi></mstyle></mrow><annotation>{\displaystyle b}</annotation></semantics></math><img src=$ ${\displaystyle \gcd(a,b)=kd <semantics><mrow><mstyle><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>=</mo><mi>k</mi><mi>d</mi></mstyle></mrow><annotation>{\displaystyle \gcd(a,b)=kd}</annotation></semantics></math><img src=$ ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle d <semantics><mrow><mstyle><mi>d</mi></mstyle></mrow><annotation>{\displaystyle d}</annotation></semantics></math><img src=$ ${\displaystyle c <semantics><mrow><mstyle><mi>c</mi></mstyle></mrow><annotation>{\displaystyle c}</annotation></semantics></math><img src=$ ${\displaystyle c=jd <semantics><mrow><mstyle><mi>c</mi><mo>=</mo><mi>j</mi><mi>d</mi></mstyle></mrow><annotation>{\displaystyle c=jd}</annotation></semantics></math><img src=$ ${\displaystyle j <semantics><mrow><mstyle><mi>j</mi></mstyle></mrow><annotation>{\displaystyle j}</annotation></semantics></math><img src=$ ${\displaystyle u=\gcd(k,j) <semantics><mrow><mstyle><mi>vous</mi><mo>=</mo><mo>pgcd</mo><mo>(</mo><mi>k</mi><mo>,</mo><mi>j</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle u=\gcd(k,j)}</annotation></semantics></math><img src=$ ${\displaystyle u <semantics><mrow><mstyle><mi>vous</mi></mstyle></mrow><annotation>{\displaystyle u}</annotation></semantics></math><img src=$ ${\displaystyle ud|a,b,c <semantics><mrow><mstyle><mi>vous</mi><mi>d</mi><mrow><mo>|</mo></mrow><mi>un</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi></mstyle></mrow><annotation>{\displaystyle ud|a,b,c}</annotation></semantics></math><img src=$ ${\displaystyle d <semantics><mrow><mstyle><mi>d</mi></mstyle></mrow><annotation>{\displaystyle d}</annotation></semantics></math><img src=$ ${\displaystyle u <semantics><mrow><mstyle><mi>vous</mi></mstyle></mrow><annotation>{\displaystyle u}</annotation></semantics></math><img src=$ ${\displaystyle ud=\gcd(\gcd(a,b),c) <semantics><mrow><mstyle><mi>vous</mi><mi>d</mi><mo>=</mo><mo>pgcd</mo><mo>(</mo><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>,</mo><mi>c</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle ud=\gcd(\gcd(a,b),c)}</annotation></semantics></math><img src=$

Donc si ${\displaystyle na+mb=\gcd(a,b) <semantics><mrow><mstyle><mi>n</mi><mi>un</mi><mo>+</mo><mi>m</mi><mi>b</mi><mo>=</mo><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle na+mb=\gcd(a,b)}</annotation></semantics></math><img src=$ ${\displaystyle x <semantics><mrow><mstyle><mi>x</mi></mstyle></mrow><annotation>{\displaystyle x}</annotation></semantics></math><img src=$ ${\displaystyle y <semantics><mrow><mstyle><mi>y</mi></mstyle></mrow><annotation>{\displaystyle y}</annotation></semantics></math><img src=$ ${\displaystyle x\gcd(a,b)+yc=\gcd(a,b,c) <semantics><mrow><mstyle><mi>x</mi><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>+</mo><mi>y</mi><mi>c</mi><mo>=</mo><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle x\gcd(a,b)+yc=\gcd(a,b,c)}</annotation></semantics></math><img src=$

${\displaystyle x(na+mb)+yc=(xn)a+(xm)b+yc=\gcd(a,b,c).\, <semantics><mrow><mstyle><mi>x</mi><mo>(</mo><mi>n</mi><mi>un</mi><mo>+</mo><mi>m</mi><mi>b</mi><mo>)</mo><mo>+</mo><mi>y</mi><mi>c</mi><mo>=</mo><mo>(</mo><mi>x</mi><mi>n</mi><mo>)</mo><mi>un</mi><mo>+</mo><mo>(</mo><mi>x</mi><mi>m</mi><mo>)</mo><mi>b</mi><mo>+</mo><mi>y</mi><mi>c</mi><mo>=</mo><mo>pgcd</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo>)</mo><mo>.</mo><mspace></mspace></mstyle></mrow><annotation>{\displaystyle x(na+mb)+yc=(xn)a+(xm)b+yc=\gcd(a,b,c).\,}</annotation></semantics></math><img src=$

Pour appliquer cette méthode à n nombres, on utilise l'induction.

${\displaystyle \gcd(a_{1},a_{2},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n}))),\dots ), <semantics><mrow><mstyle><mo>pgcd</mo><mo>(</mo><msub><mi>un</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>un</mi><mrow><mn>2</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>)</mo><mo>=</mo><mo>pgcd</mo><mo>(</mo><msub><mi>un</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mspace></mspace><mo>pgcd</mo><mo>(</mo><msub><mi>un</mi><mrow><mn>2</mn></mrow></msub><mo>,</mo><mspace></mspace><mo>pgcd</mo><mo>(</mo><msub><mi>un</mi><mrow><mn>3</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><mo>pgcd</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mspace></mspace><mo>,</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>)</mo><mo>)</mo><mo>)</mo><mo>,</mo><mo>…</mo><mo>)</mo><mo>,</mo></mstyle></mrow><annotation>{\displaystyle \gcd(a_{1},a_{2},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n}))),\dots ),}</annotation></semantics></math><img src=$

les équations suivent directement.

Plus d articles de Worldlex Wiki

Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Explorer l index