Algorisme d'Euclides ampliat

De Viquipèdia
Dreceres ràpides: navegació, cerca

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ó[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]