Ejemplo Algoritmo de Euclides

El conocido como Algoritmo de Euclides fue el precursor del Algoritmo de la División, de origen geométrico.Para los pobladores de la Tierra era problemático medir las distancias, no contaban con un sistema métrico, ni con cintas métricas.

Para ello, usaban unas varas o daban pasos y así establecían la distancia entre dos puntos cualesquiera era un determinado número de varas o número de pasos.

Los griegos unos 3 000 años antes de nuestra era sistematizaron este proceso de medición y establecieron un procedimiento que Euclides estableció:

“Dada una vara o patrón de medida la distancia entre dos puntos A y B era un número de veces ese patrón de medida más una pequeña distancia, menor que el patrón de medida”.

Gráficamente, tenemos lo siguiente:Sistema métrico

Hoy día ese procedimiento se llevó a una expresión matemática

D = d x c + r

Donde   D = la distancia a medir entre A y B

d = nuestro patrón de medida

c = el número de veces que el patrón de medida cabe entre los puntos A y B

r = la distancia faltante para alcanzar el punto B

En el caso particular que el patrón de medida “cabe” un número de veces exacto entre el punto A y B, entonces el valor de r = 0

Hoy día este es el algoritmo de la división que se enseña en el sistema escolar, donde:Algoritmo de la división

Algoritmo de Euclides extendido

Los procedimientos para calcula el Máximo Común Divisor para números enteros relativamente grandes puede ser engorroso.

Con base en el Algoritmo de la División diseñado por los griegos, se creó una forma que facilita dicho cálculo.

Sean a y b dos números naturales cualesquiera con a y b ≠ 0 y a > b, podemos representarlos así:

a = q1 x b + r1,         con b > r1 ³ 0 y q1, r1 números naturales

Si r1 ≠ 0, se procede a dividir el divisor entre el resto

b = q2 x r1 + r2,        con r1 > r2 ³ 0 y q2, r2 números naturales

Este paso se repite hasta que el residuo = 0

r1 = q3 x r2 + r3,       con r2 > r3 ³ 0 y q3, r3 números naturales

rn = qn+2 x rn+1 + 0,   con rn+2 = 0 y qn+2 un número natural

El MCD (a, b) = rn+1

Este algoritmo permite, además de encontrar un Máximo Común Divisor de dos números enteros, expresarlo como la combinación lineal, mínima, de estos números.

Calculemos el MCD (703, 399) usando este algoritmo

703 = 1 x 399 + 304

399 = 1 x 304 + 95

304 = 3 x 95 + 19

95 = 5 x 19 + 0

De acá tenemos que MCD (703, 399) = 19

Ejemplos

  • ¿Cuál es el MCD (352, 105)?

352 = 3 x 105 + 37

105 = 2 x 37 + 31

37 = 1 x 31 +6

31 = 5 x 6 + 1

6 = 6 x 1 + 0

El MCD (352, 105) = 1 → entonces los números naturales 352 y 105 son primos relativos

  • ¿Cuál es el MCD (49 896, 26 460)?MCD Algoritmo de Euclides

El MCD (49 896, 26 460) = 756

  • ¿Cuál es el MCD (13 172, 261)?Algoritmo de Euclides MCD

El MCD (13 172, 261) = 1 → entonces los números naturales 13172y 261 son primos relativos

  • ¿Cuál es el MCD (11 823, 11 172)?

11 823 = 1 x 11 172 + 651

11 172 = 17 x 651 + 105

651 = 6 x 105 + 21

105 = 5 x 21 + 0

El MCD (11 823, 11 172) = 21

 

El artículo ha sido realizado por el profesor Licenciado en Matemáticas: Ángel Míguez Álvarez