Máximo común divisor. El algoritmo de Euclides

Máximo común divisor. El algoritmo de Euclides

http://www.dma.fi.upm.es/recursos/aplicaciones/matematica_discreta/web/aritmetica_modular/divisibilidad.html

Máximo común divisor. El algoritmo de Euclides.

El máximo común divisor de dos enteros

Dados dos enteros a y b distintos de 0, decimos que el entero d>1 es un máximo común divisor, o mcd, de a y b si

d|a, d|b y para cualquier otro c ∈ Z tal que c|a y c|b, entonces c|d

Es decir, d es un entero positivo, divisor común de a y b, y cualquier otro divisor común es también un divisor de d.

Con estas condiciones, el máximo común divisor es único. Se denota por d= mcd(a,b)

Algunas propiedades del máximo común divisor

1. mcd(a,b) = mcd(|a|,|b|)
2. mcd (ka,kb) = |k| mcd(a,b)
3. Si a|b.c y mcd (a,b) =1, entonces a|c
4. mcd(a,b) = d ⇔ d|a, d|b y mcd(a/d , b/d)=1

El algoritmo de Euclides

Proposición

Sean a,b enteros no nulos. Entonces mcd(a,b) = mcd(b,r) donde r es el único 0<r<b tal que existe un entero q con a= bq + r(esto es, que r es el resto de la división de a por b)

Esta proposición nos indica que es igual de válido calcular el mcd(a,b) que el mcd(b,r), con la ventaja de que r es un entero de menor tamaño que el original a. Esto es aprovechado por el algoritmo de Euclides para el cálculo del máximo común divisor de dos números enteros.

El algoritmo de Euclides

Para calcular el mcd de dos enteros a y b (ambos >0, suponemos a > b) se definen q_i y r_i recursivamente mediante las ecuaciones:

a = bq₁ + r₁  (0<r₁<b)

b = r₁q₂ + r₂  (0<r₂<r₁)

r₁ = r₂q₃ + r₃  (0<r₃<r₂)

....

r_k-3 = r_k-2q_k-1 + r_k-1  (0<r_k-1<r_k-2)

r_k-2 = r_k-1q_k  (r_k=0)

Y de la proposición anterior, se sigue que:

mcd(a,b) = mcd(b,r₁) = mcd(r₁,r₂) = ... = mcd(r_k-2,r_k-1) = r_k-1

Además se puede demostrar que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.

A continuación, figura una posible implementación en pseudocódigo del algoritmo de Euclides:

Observación

Sean a,b enteros no nulos, y sea d = mcd(a,b). Entonces d es el menor entero positivo (no nulo) que puede expresarse en la forma ax + by con x,y∈ Z

Una propiedad del algoritmo de Euclides:

El algoritmo de Euclides también nos proporciona un método para calcular dos valores enteros x e y tales que mcd(a,b) = ax + by. Este método consiste en ir despejando el resto de la última división, el que nos da el valor mcd(a,b), hacia atrás hasta llegar a los valores a y b de partida.