# 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.

## [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)

Obtingut de "http://ca.wikipedia.org../../../a/l/g/Algorisme_d%27Euclides_ampliat_246f.html"

Categories: Teoria de nombres | Aritmètica

##### Views

- Article
- Discussió
- Revisió actual

##### Cerca