Algorisme d'Euclides ampliat

L'algorisme d'Euclides ampliat és una millora de l'algorisme d'Euclides de càlcul del màxim comú divisor de dos nombres enters, que dóna, 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 (en anglès)