Algorisme d'Euclides ampliat

LPlantilla:'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\ne 0$ dos nombres enters. L'algorisme d'Euclides consisteix a construir la recurrència finita

$\{\begin{array}{c}{d}_1=|a|\\ d_2=|b|\\ d_i=d_{i-2}-d_{i-1}{q}_i,i>2,0<d_i<d_{i-1}\end{array}$

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{array}{c}{x}_1=1\\ x_2=0\\ x_i=x_{i-2}-x_{i-1}{q}_i,k\ge i>2\end{array}\{\begin{array}{c}{y}_1=0\\ y_2=1\\ y_i=y_{i-2}-y_{i-1}{q}_i,k\ge i>2\end{array}$

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\dots \dots x_{i-2}$	$x_{i-1}$	$x_i\dots \dots x_{k-2}$	$x_{k-1}$	$x_k$
$0$	$1$	$y_3$	$y_4$	$y_5\dots \dots y_{i-2}$	$y_{i-1}$	$y_i\dots \dots y_{k-2}$	$y_{k-1}$	$y_k$
	$q_3$	$q_4$	$q_5$	$q_6\dots \dots q_{i-1}$	$q_i$	$q_{i+1}\dots \dots q_{k-1}$	$q_k$	$q$
$|a|$	$|b|$	$d_3$	$d_4$	$d_5\dots \dots d_{i-2}$	$d_{i-1}$	$d_i\dots \dots 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{array}{c}{q}_i\acute{\text{e}}\text{s el quocient de la divisi}\acute{\text{o}}\text{ entera de }{d}_{i-2}\text{ entre }{d}_{i-1}\\ d_i=d_{i-2}-d_{i-1}{q}_i(\acute{\text{e}}\text{s el residu de la divisi}\acute{\text{o}}\text{ entera de }{d}_{i-2}\text{ 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{array}$

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÷175$	$2=175÷63$	$1=63÷49$	$3=49÷14$	$2=14÷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÷b$ se sobreentenen enteres) Aleshores, $m.c.d.(763,175)=7=763\cdot (-11)+175\cdot 48$.

Referències

• PlanetMath: Euclid's algorithm Plantilla:En