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\cdot0$	$-2=0-2\cdot1$	$3=1-1\cdot(-2)$	$-11=-2-3\cdot3$
$0$	$1$	$-4=0- 4\cdot1$	$9=1-2\cdot(-4)$	$-13=-4-1\cdot9$	$48=9-3\cdot(-13)$
	$4=763\div 175$	$2=175\div63$	$1=63\div49$	$3=49\div14$	$2=14\div7$
$763$	$175$	$63=763-175\cdot4$	$49=175-63\cdot2$	$14=63-1\cdot49$	$7=49-3\cdot14$	$0=14-2\cdot7$

(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)