Algorisme d'Euclides ampliat

L'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.

Siguin ${\displaystyle a}$ i ${\displaystyle b\neq 0}$ dos nombres enters. L'algorisme d'Euclides consisteix a construir la recurrència finita

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

Però si ara considerem aquestes altres dues recurrències finites:

${\displaystyle {\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 ${\displaystyle q_{i}}$ de la successió de l'algorisme d'Euclides, resulta que, per ${\displaystyle i>2}$ amb ${\displaystyle 0<d_{i}<d_{i-1}}$, es té

${\displaystyle d_{i}=d_{1}x_{i}+d_{2}y_{i}}$

com es comprova fàcilment per inducció.

Per tant, si ${\displaystyle d_{k}=m.c.d.(a,b)}$, resulta

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

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

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

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

Hom comença obtenint ${\displaystyle q_{3}}$ com a quocient de la divisió entera de ${\displaystyle d_{1}}$ entre ${\displaystyle d_{2}}$, és a dir, ${\displaystyle |a|}$ entre ${\displaystyle |b|}$ i ${\displaystyle d_{3}}$ a partir de ${\displaystyle d_{3}=d_{1}-d_{2}q_{3}=|a|-|b|q_{3}}$. Els termes ${\displaystyle x_{3}}$ i ${\displaystyle y_{3}}$ resulten de ${\displaystyle x_{3}=x_{1}-x_{2}q_{3}=1}$ i ${\displaystyle y_{3}=y_{1}-y_{2}q_{3}=-q_{3}}$. Els termes següents, ${\displaystyle q_{i}}$, ${\displaystyle d_{i}}$, ${\displaystyle x_{i}}$ i ${\displaystyle y_{i}}$ s'obtenen de la mateixa manera i en el mateix ordre:

${\displaystyle {\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 ${\displaystyle d_{k-1}=d_{k}q}$. Aleshores, ${\displaystyle m.c.d.(a,b)=d_{k}=|a|x_{k}+|b|y_{k}}$

Il·lustrem aquest procés amb un exemple: es tracta de calcular ${\displaystyle m.c.d.(763,175)}$:

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

que prové de

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

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

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