Vés al contingut

Algorisme d'Euclides ampliat

De la Viquipèdia, l'enciclopèdia lliure

L'algorisme d'Euclides ampliat o algorisme d'Euclides estès és una millora de l'algorisme d'Euclides de càlcul del màxim comú divisor de dos nombres enters, que dona, 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àctic

[modifica]

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]

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

que prové de

(Les divisions se sobreentenen enteres) Aleshores, .

Referències

[modifica]
  • PlanetMath: Euclid's algorithm (anglès)