# Algorisme d'Euclides ampliat

L'algorisme d'Euclides ampliat o algorisme d'Euclides estès és una millora de l'algorisme d'Euclides de càlcul del màxim comú divisor de dos nombres enters, que dona, a més del màxim comú divisor dels dos nombres, els coeficients de cadascun d'aquests dos nombres a la identitat de Bézout.

## Descripció

Siguin $a$ i $b\neq 0$ dos nombres enters. L'algorisme d'Euclides consisteix a construir la recurrència finita
${\begin{cases}d_{1}=|a|\\d_{2}=|b|\\d_{i}=d_{i-2}-d_{i-1}q_{i}\,,\quad i>2\,,\quad 0<d_{i}<d_{i-1}\end{cases}}$
en la qual $d_{i}=d_{i-2}-d_{i-1}q_{i}$ no és més que el residu de la divisió entera de $d_{i-2}$ i $d_{i-1}$ amb quocient $q_{i}$. La successió és estrictament decreixent i la condició $d_{i}>0$ obliga a que sigui finita. L'últim terme, posem $d_{k}$ arriba quan hi ha $q$ que fa $d_{k-1}=d_{k}q$. La successió té, doncs, $k$ termes i $d_{k}=m.c.d.(a,b)$.
Però si ara considerem aquestes altres dues recurrències finites:
${\begin{cases}x_{1}=1\\x_{2}=0\\x_{i}=x_{i-2}-x_{i-1}q_{i}\,,\quad k\geq i>2\end{cases}}\qquad {\begin{cases}y_{1}=0\\y_{2}=1\\y_{i}=y_{i-2}-y_{i-1}q_{i}\,,\quad k\geq i>2\end{cases}}$
amb els valors $q_{i}$ de la successió de l'algorisme d'Euclides, resulta que, per $i>2$ amb $0<d_{i}<d_{i-1}$, es té
$d_{i}=d_{1}x_{i}+d_{2}y_{i}$
com es comprova fàcilment per inducció.
Per tant, si $d_{k}=m.c.d.(a,b)$, resulta
$m.c.d.(a,b)=|a|x_{k}+|b|y_{k}$
i $x_{k}$ i $y_{k}$, amb els signes adequats, són els coeficients de $a$ i $b$ a la identitat de Bézout.

## Càlcul pràctic

Hom sol disposar els càlculs en una graella com aquesta
| $1$ | $0$ | $x_{3}$ | $x_{4}$ | $x_{5}\ldots \ldots x_{i-2}$ | $x_{i-1}$ | $x_{i}\ldots \ldots x_{k-2}$ | $x_{k-1}$ | $x_{k}$ |
| $0$ | $1$ | $y_{3}$ | $y_{4}$ | $y_{5}\ldots \ldots y_{i-2}$ | $y_{i-1}$ | $y_{i}\ldots \ldots y_{k-2}$ | $y_{k-1}$ | $y_{k}$ |
| | $q_{3}$ | $q_{4}$ | $q_{5}$ | $q_{6}\ldots \ldots q_{i-1}$ | $q_{i}$ | $q_{i+1}\ldots \ldots q_{k-1}$ | $q_{k}$ | $q$ |
| $|a|$ | $|b|$ | $d_{3}$ | $d_{4}$ | $d_{5}\ldots \ldots d_{i-2}$ | $d_{i-1}$ | $d_{i}\ldots \ldots d_{k-2}$ | $d_{k-1}$ | $d_{k}$ | $0$ |
Hom comença obtenint $q_{3}$ com a quocient de la divisió entera de $d_{1}$ entre $d_{2}$, és a dir, $|a|$ entre $|b|$ i $d_{3}$ a partir de $d_{3}=d_{1}-d_{2}q_{3}=|a|-|b|q_{3}$. Els termes $x_{3}$ i $y_{3}$ resulten de $x_{3}=x_{1}-x_{2}q_{3}=1$ i $y_{3}=y_{1}-y_{2}q_{3}=-q_{3}$. Els termes següents, $q_{i}$, $d_{i}$, $x_{i}$ i $y_{i}$ s'obtenen de la mateixa manera i en el mateix ordre:
${\begin{cases}q_{i}{\mbox{ }}{\acute {\mbox{e}}}{\mbox{s el quocient de la divisi}}{\acute {\mbox{o}}}{\mbox{ entera de }}d_{i-2}{\mbox{ entre }}d_{i-1}\\d_{i}=d_{i-2}-d_{i-1}q_{i}{\mbox{ }}({\acute {\mbox{e}}}{\mbox{s el residu de la divisi}}{\acute {\mbox{o}}}{\mbox{ entera de }}d_{i-2}{\mbox{ entre }}d_{i-1})\\x_{i}=x_{i-2}-x_{i-1}q_{i}\\y_{i}=y_{i-2}-y_{i-1}q_{i}\end{cases}}$
i el procés acaba quan trobem $d_{k-1}=d_{k}q$. Aleshores, $m.c.d.(a,b)=d_{k}=|a|x_{k}+|b|y_{k}$

## Exemple

Il·lustrem aquest procés amb un exemple: es tracta de calcular $m.c.d.(763,175)$:
| $1$ | $0$ | $1$ | $-2$ | $3$ | $-11$ |
| $0$ | $1$ | $-4$ | $9$ | $-13$ | $48$ |
| | $4$ | $2$ | $1$ | $3$ | $2$ | |
| $763$ | $175$ | $63$ | $49$ | $14$ | $7$ | $0$ |
que prové de
| $1$ | $0$ | $1=1-4\cdot 0$ | $-2=0-2\cdot 1$ | $3=1-1\cdot (-2)$ | $-11=-2-3\cdot 3$ |
| $0$ | $1$ | $-4=0-4\cdot 1$ | $9=1-2\cdot (-4)$ | $-13=-4-1\cdot 9$ | $48=9-3\cdot (-13)$ |
| | $4=763\div 175$ | $2=175\div 63$ | $1=63\div 49$ | $3=49\div 14$ | $2=14\div 7$ | |
| $763$ | $175$ | $63=763-175\cdot 4$ | $49=175-63\cdot 2$ | $14=63-1\cdot 49$ | $7=49-3\cdot 14$ | $0=14-2\cdot 7$ |
(Les divisions $a\div b$ se sobreentenen enteres) Aleshores, $m.c.d.(763,175)=7=763\cdot (-11)+175\cdot 48$.

## Referències

* PlanetMath: Euclid's algorithm (anglès)