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óModifica

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àcticModifica

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,  

ExempleModifica

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

           
           
         
             

que prové de

           
           
         
             

(Les divisions   se sobreentenen enteres) Aleshores,  .

ReferènciesModifica