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$$a$ i $b\neq 0$$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}}$${\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}$$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}$$d_{i-2}$ i $d_{i-1}$$d_{i-1}$ amb quocient $q_{i}$$q_{i}$. La successió és estrictament decreixent i la condició $d_{i}>0$$d_{i}>0$ obliga a que sigui finita. L'últim terme, posem $d_{k}$$d_{k}$ arriba quan hi ha $q$$q$ que fa $d_{k-1}=d_{k}q$$d_{k-1}=d_{k}q$. La successió té, doncs, $k$$k$ termes i $d_{k}=m.c.d.(a,b)$$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}}$${\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}$$q_{i}$ de la successió de l'algorisme d'Euclides, resulta que, per $i>2$$i>2$ amb $0<d_{i}<d_{i-1}$$0<d_{i}<d_{i-1}$, es té

$d_{i}=d_{1}x_{i}+d_{2}y_{i}$$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)$$d_{k}=m.c.d.(a,b)$, resulta

$m.c.d.(a,b)=|a|x_{k}+|b|y_{k}$$m.c.d.(a,b)=|a|x_{k}+|b|y_{k}$

i $x_{k}$$x_{k}$ i $y_{k}$$y_{k}$, amb els signes adequats, són els coeficients de $a$$a$ i $b$$b$ a la identitat de Bézout.

Càlcul pràctic

Hom sol disposar els càlculs en una graella com aquesta

$1$$1$	$0$$0$	$x_{3}$$x_{3}$	$x_{4}$$x_{4}$	$x_{5}\ldots \ldots x_{i-2}$$x_{5}\ldots \ldots x_{i-2}$	$x_{i-1}$$x_{i-1}$	$x_{i}\ldots \ldots x_{k-2}$$x_{i}\ldots \ldots x_{k-2}$	$x_{k-1}$$x_{k-1}$	$x_{k}$$x_{k}$
$0$$0$	$1$$1$	$y_{3}$$y_{3}$	$y_{4}$$y_{4}$	$y_{5}\ldots \ldots y_{i-2}$$y_{5}\ldots \ldots y_{i-2}$	$y_{i-1}$$y_{i-1}$	$y_{i}\ldots \ldots y_{k-2}$$y_{i}\ldots \ldots y_{k-2}$	$y_{k-1}$$y_{k-1}$	$y_{k}$$y_{k}$
	$q_{3}$$q_{3}$	$q_{4}$$q_{4}$	$q_{5}$$q_{5}$	$q_{6}\ldots \ldots q_{i-1}$$q_{6}\ldots \ldots q_{i-1}$	$q_{i}$$q_{i}$	$q_{i+1}\ldots \ldots q_{k-1}$$q_{i+1}\ldots \ldots q_{k-1}$	$q_{k}$$q_{k}$	$q$$q$
$|a|$$|a|$	$|b|$$|b|$	$d_{3}$$d_{3}$	$d_{4}$$d_{4}$	$d_{5}\ldots \ldots d_{i-2}$$d_{5}\ldots \ldots d_{i-2}$	$d_{i-1}$$d_{i-1}$	$d_{i}\ldots \ldots d_{k-2}$$d_{i}\ldots \ldots d_{k-2}$	$d_{k-1}$$d_{k-1}$	$d_{k}$$d_{k}$	$0$$0$

Hom comença obtenint $q_{3}$$q_{3}$ com a quocient de la divisió entera de $d_{1}$$d_{1}$ entre $d_{2}$$d_{2}$, és a dir, $|a|$$|a|$ entre $|b|$$|b|$ i $d_{3}$$d_{3}$ a partir de $d_{3}=d_{1}-d_{2}q_{3}=|a|-|b|q_{3}$$d_{3}=d_{1}-d_{2}q_{3}=|a|-|b|q_{3}$. Els termes $x_{3}$$x_{3}$ i $y_{3}$$y_{3}$ resulten de $x_{3}=x_{1}-x_{2}q_{3}=1$$x_{3}=x_{1}-x_{2}q_{3}=1$ i $y_{3}=y_{1}-y_{2}q_{3}=-q_{3}$$y_{3}=y_{1}-y_{2}q_{3}=-q_{3}$. Els termes següents, $q_{i}$$q_{i}$, $d_{i}$$d_{i}$, $x_{i}$$x_{i}$ i $y_{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}}$${\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$$d_{k-1}=d_{k}q$. Aleshores, $m.c.d.(a,b)=d_{k}=|a|x_{k}+|b|y_{k}$$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)$$m.c.d.(763,175)$:

$1$$1$	$0$$0$	$1$$1$	$-2$$-2$	$3$$3$	$-11$$-11$
$0$$0$	$1$$1$	$-4$$-4$	$9$$9$	$-13$$-13$	$48$$48$
	$4$$4$	$2$$2$	$1$$1$	$3$$3$	$2$$2$
$763$$763$	$175$$175$	$63$$63$	$49$$49$	$14$$14$	$7$$7$	$0$$0$

que prové de

$1$$1$	$0$$0$	$1=1-4\cdot 0$$1=1-4\cdot 0$	$-2=0-2\cdot 1$$-2=0-2\cdot 1$	$3=1-1\cdot (-2)$$3=1-1\cdot (-2)$	$-11=-2-3\cdot 3$$-11=-2-3\cdot 3$
$0$$0$	$1$$1$	$-4=0-4\cdot 1$$-4=0-4\cdot 1$	$9=1-2\cdot (-4)$$9=1-2\cdot (-4)$	$-13=-4-1\cdot 9$$-13=-4-1\cdot 9$	$48=9-3\cdot (-13)$$48=9-3\cdot (-13)$
	$4=763\div 175$$4=763\div 175$	$2=175\div 63$$2=175\div 63$	$1=63\div 49$$1=63\div 49$	$3=49\div 14$$3=49\div 14$	$2=14\div 7$$2=14\div 7$
$763$$763$	$175$$175$	$63=763-175\cdot 4$$63=763-175\cdot 4$	$49=175-63\cdot 2$$49=175-63\cdot 2$	$14=63-1\cdot 49$$14=63-1\cdot 49$	$7=49-3\cdot 14$$7=49-3\cdot 14$	$0=14-2\cdot 7$$0=14-2\cdot 7$

(Les divisions $a\div b$$a\div b$ se sobreentenen enteres) Aleshores, $m.c.d.(763,175)=7=763\cdot (-11)+175\cdot 48$$m.c.d.(763,175)=7=763\cdot (-11)+175\cdot 48$.

Referències

• PlanetMath: Euclid's algorithm (en anglès)