Algorisme d'Euclides ampliat

De Viquipèdia

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.

[edita] 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.

[edita] 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$

[edita] 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\cdot(-3)$
$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$