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 <math>a</math> i <math>b \neq 0</math> dos nombres enters. L'algorisme d'Euclides consisteix a construir la recurrència finita

<math> \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} </math>

en la qual <math>d_i = d_{i-2} - d_{i-1} q_i</math> no és més que el residu de la divisió entera de <math>d_{i-2}</math> i <math>d_{i-1}</math> amb quocient <math>q_i</math>. La successió és estrictament decreixent i la condició <math>d_i > 0</math> obliga a que sigui finita. L'últim terme, posem <math>d_k</math> arriba quan hi ha <math>q</math> que fa <math>d_{k-1} = d_k q</math>. La successió té, doncs, <math>k</math> termes i <math>d_k = m.c.d.(a, b)</math>.

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

<math> \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} </math>

amb els valors <math>q_i</math> de la successió de l'algorisme d'Euclides, resulta que, per <math>i > 2</math> amb <math>0 < d_i < d_{i-1}</math>, es té

com es comprova fàcilment per inducció

Per tant, si <math>d_k = m.c.d.(a, b)</math>, resulta

i <math>x_k</math> i <math>y_k</math>, amb els signes adequats, són els coeficients de <math>a</math> i <math>b</math> a la identitat de Bézout.

Càlcul pràctic

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

<math>1</math>	<math>0</math>	<math>x_3</math>	<math>x_4</math>	<math>x_5 \ldots\ldots x_{i-2}</math>	<math>x_{i-1}</math>	<math>x_i \ldots\ldots x_{k-2}</math>	<math>x_{k-1}</math>	<math>x_k</math>
<math>0</math>	<math>1</math>	<math>y_3</math>	<math>y_4</math>	<math>y_5 \ldots\ldots y_{i-2}</math>	<math>y_{i-1}</math>	<math>y_i \ldots\ldots y_{k-2}</math>	<math>y_{k-1}</math>	<math>y_k</math>
	<math>q_3</math>	<math>q_4</math>	<math>q_5</math>	<math>q_6 \ldots\ldots q_{i-1}</math>	<math>q_{i}</math>	<math>q_{i+1} \ldots\ldots q_{k-1}</math>	<math>q_{k}</math>	<math>q</math>
a\|</math>	b\|</math>	<math>d_3</math>	<math>d_4</math>	<math>d_5 \ldots\ldots d_{i-2}</math>	<math>d_{i-1}</math>	<math>d_i \ldots\ldots d_{k-2}</math>	<math>d_{k-1}</math>	<math>d_k</math>	<math>0</math>

Hom comença obtenint <math>q_3</math> com a quocient de la divisió entera de <math>d_1</math> entre <math>d_2</math>, és a dir, <math>|a|</math> entre <math>|b|</math> i <math>d_3</math> a partir de <math>d_3 = d_1 - d_2 q_3 = |a| - |b| q_3</math>. Els termes <math>x_3</math> i <math>y_3</math> resulten de <math>x_3 = x_1 - x_2 q_3 = 1</math> i <math>y_3 = y_1 - y_2 q_3 = -q_3</math>. Els termes següents, <math>q_i</math>, <math>d_i</math>, <math>x_i</math> i <math>y_i</math> s'obtenen de la mateixa manera i en el mateix ordre:

<math> \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} </math>

i el procés acaba quan trobem <math>d_{k-1} = d_k q</math>. Aleshores, <math>m.c.d.(a, b) = d_k = |a| x_k + |b| y_k</math>

Exemple

Il·lustrem aquest procés amb un exemple: es tracta de calcular <math>m.c.d.(763,175)</math>:

<math>1</math>	<math>0</math>	<math>1</math>	<math>-2</math>	<math>3</math>	<math>-11</math>
<math>0</math>	<math>1</math>	<math>-4</math>	<math>9</math>	<math>-13</math>	<math>48</math>
	<math>4</math>	<math>2</math>	<math>1</math>	<math>3</math>	<math>2</math>
<math>763</math>	<math>175</math>	<math>63</math>	<math>49</math>	<math>14</math>	<math>7</math>	<math>0</math>

que prové de

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

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

Referències

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