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

en la qual no és més que el residu de la divisió entera de i amb quocient . La successió és estrictament decreixent i la condició obliga a que sigui finita. L'últim terme, posem arriba quan hi ha que fa . La successió té, doncs, termes i .

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

amb els valors de la successió de l'algorisme d'Euclides, resulta que, per amb , es té

com es comprova fàcilment per inducció.

Per tant, si , resulta

i i , amb els signes adequats, són els coeficients de i 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

Hom comença obtenint com a quocient de la divisió entera de entre , és a dir, entre i a partir de . Els termes i resulten de i . Els termes següents, , , i s'obtenen de la mateixa manera i en el mateix ordre:

i el procés acaba quan trobem . Aleshores,

Exemple[modifica | modifica el codi]

Il·lustrem aquest procés amb un exemple: es tracta de calcular :

que prové de

(Les divisions se sobreentenen enteres) Aleshores, .

Referències[modifica | modifica el codi]