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.
Taula de continguts |
[edita] Descripció
Siguin a i
dos nombres enters. L'algorisme d'Euclides consisteix a construir la recurrència finita

en la qual di = di − 2 − di − 1qi no és més que el residu de la divisió entera de di − 2 i di − 1 amb quocient qi. La successió és estrictament decreixent i la condició di > 0 obliga a que sigui finita. L'últim terme, posem dk arriba quan hi ha q que fa dk − 1 = dkq. La successió té, doncs, k termes i dk = m.c.d.(a,b).
Però si ara considerem aquestes altres dues recurrències finites:

amb els valors qi de la successió de l'algorisme d'Euclides, resulta que, per i > 2 amb 0 < di < di − 1, es té
di = d1xi + d2yi
com es comprova fàcilment per inducció
Per tant, si dk = m.c.d.(a,b), resulta
m.c.d.(a,b) = | a | xk + | b | yk
i xk i yk, 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 | x3 | x4 | ![]() |
xi − 1 | ![]() |
xk − 1 | xk | |
| 0 | 1 | y3 | y4 | ![]() |
yi − 1 | ![]() |
yk − 1 | yk | |
| q3 | q4 | q5 | ![]() |
qi | ![]() |
qk | q | ||
| | a | | | b | | d3 | d4 | ![]() |
di − 1 | ![]() |
dk − 1 | dk | 0 |
Hom comença obtenint q3 com a quocient de la divisió entera de d1 entre d2, és a dir, | a | entre | b | i d3 a partir de d3 = d1 − d2q3 = | a | − | b | q3. Els termes x3 i y3 resulten de x3 = x1 − x2q3 = 1 i y3 = y1 − y2q3 = − q3. Els termes següents, qi, di, xi i yi s'obtenen de la mateixa manera i en el mateix ordre:

i el procés acaba quan trobem dk − 1 = dkq. Aleshores, m.c.d.(a,b) = dk = | a | xk + | b | yk
[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 | ![]() |
![]() |
![]() |
![]() |
|
| 0 | 1 | ![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
![]() |
![]() |
||
| 763 | 175 | ![]() |
![]() |
![]() |
![]() |
![]() |
(Les divisions
se sobreentenen enteres) Aleshores,
.
[edita] Referències
- PlanetMath: Euclid's algorithm (en anglès)



























