Algorisme d'Euclides

De Viquipèdia

L'algorisme d'Euclides és un mètode eficaç per a calcular el màxim comú divisor (mcd) entre dos nombres enters.

L'algoritme consistix en diverses divisions enteres successives. En la primera divisió, es pren com a dividend el major dels números i com divisor l'altre . Després, el divisor i el residu serveixen respectivament de dividend i divisor de la següent divisió. El procés es para quan s'obté un residu nul. El mcd és llavors el penúltim residu de l'algoritme.
Formalment, si anomenem a, b els enters inicials, r₁, r_n ... r_n-1 i r_n = 0 els residus successius, llavors:

mcd (a, b) = mcd (b, r₁), amb r₁ = a - b·q (q és el quocient de a per b)

Després el menor dels divisors comuns és el mateix, i repetint l'operació:

mcd (b, r₁) = mcd (r₁, r₂) = mcd (r₂, r₃) = ... = mcd (r_n-1, r_n) = mcd (r_n-1, 0) = r_n-1.

Això permet detallar l'algoritme efectiu:

dades d'entrada a i b   -  si fa falta, canviar-los a positius l'algoritme: mentres b ≠ 0 repetir les tres instruccions següents: r ← residu de a per b     (donar a r el valor del residu de a per b)       a ← b     (el nou valor de a és l'antic valor de b) b ← r     (el nou valor de b és el valor de r) el resultat és a (el seu últim valor).

Aquest algorisme dóna com resultat 0 si a i b són nuls, mentres que en matemàtiques, el major divisor de zero no existix.

[edita] Exemples

Es busca el màxim comú divisor de a = 945 i b = 651, nombres triats a l'atzar:

945 = 1×651 + 294
651 = 2×294 + 63
294 = 4×63 + 42
 63 = 1×42 + 21
 42 = 2×21 + 0        llavors mcd(945; 651) = 21 (l'últim residu no nul).

Com a segon exemple, prenguem nombres de grandàries semblants als anteriors: a = 987 i b = 610:

987 = 1×610 + 377
610 = 1×377 + 233
377 = 1×233 + 144
233 = 1×144 + 89
144 = 1×89 + 55
 89 = 1×55 + 34
 55 = 1×34 + 21
 34 = 1×21 + 13
 21 = 1×13 + 8
 13 = 1×8 + 5
  8 = 1×5 + 3
  5 = 1×3 + 2
  3 = 1×2 + 1        llavors mcd(987; 610) = 1

El segon exemple és més llarg que el primer, i açò se deu al fet que tots els quocients valen 1. Ací a i b no van ser triats a l'atzar: són dos termes consecutius de la successió de Fibonacci; és el pitjor dels casos per a este algoritme.

[edita] Generalització als polinomis

Aquest algoritme només precisa de la divisió euclidiana, i per consegüent s'estén a tots els dominis on hi ha tal divisió: és el cas de les àlgebres de polinomis, com Q[X] o R[X], (polinomis amb coeficients racionals o reals). Òbviament, els càlculs es tornen molt més llargs.

Un exemple no massa complicat, però tampoc trivial:

Siga un polinomi que e que té una arrel doble.

com resoldre una equació de tercer grau no és evident, per a trobar l'arrel múltiple emprem la propietat que diu les arrels múltiples són les comunes entre el polinomi i el seu polinomi derivat.

Per a simplificar les divisions, ens permetem multiplicar-los per factors constants no nuls, en fi de comptes el mcd de dos polinomis està definit mòdul un factor multiplicador, així que esta manipulació no altera el resultat.

El polinomi derivat de P és que es pot simplificar per 3, segons el que s'ha dit anteriorment.

Prenguem llavors i efectuem l'algoritme amb P i Q.

. La resta es factoritza en : prenguem llavors

el que implica que el mcd buscat és llavors 7 és l'arrel doble de P.

En efecte: i de pas