Ir a la página de inicio
Home / Posts
Compartir en Twitter
Go to Homepage

ALGORITMO DE EUCLIDES PARA EL MÁXIMO COMÚN DIVISOR

November 23, 2025

Introducción al Algoritmo de Euclides

El cálculo del máximo común divisor (GCD, por sus siglas en inglés) de dos números enteros es una tarea fundamental en matemáticas y programación. Este valor representa el mayor número que divide exactamente a ambos números sin dejar residuo. El algoritmo de Euclides, uno de los métodos más antiguos y eficientes, permite realizar este cálculo de manera rápida y precisa. Este tutorial explora el algoritmo, su lógica, implementaciones en diferentes lenguajes de programación y aplicaciones prácticas en problemas computacionales.

El algoritmo de Euclides se basa en la observación de que el GCD de dos números también divide el residuo de su división. Este principio permite reducir iterativamente el problema hasta encontrar el divisor común más grande. A lo largo de este artículo, se presentarán ejemplos claros y código funcional para ilustrar su implementación.

Fundamentos del Algoritmo de Euclides

El algoritmo de Euclides se fundamenta en una propiedad matemática: si se tienen dos números enteros positivos (a) y (b), donde (a \geq b), el GCD de (a) y (b) es igual al GCD de (b) y el residuo de (a) dividido por (b). Este proceso se repite hasta que el residuo es cero, momento en el cual el último divisor no nulo es el máximo común divisor.

El procedimiento puede describirse en pasos simples:

  1. Dado dos números enteros positivos (a) y (b), donde (a \geq b).
  2. Dividir (a) entre (b) y obtener el residuo (r).
  3. Si (r = 0), entonces (b) es el GCD.
  4. Si (r \neq 0), reemplazar (a) con (b) y (b) con (r), y repetir desde el paso 2.

Este enfoque es eficiente porque reduce rápidamente el tamaño de los números en cada iteración, convergiendo al resultado en un número de pasos proporcional al logaritmo de los valores iniciales.

Para ilustrar, consideremos el cálculo del GCD de 48 y 18:

  • Dividimos 48 entre 18: (48 \div 18 = 2) con residuo 12 ((48 = 18 \cdot 2 + 12)).
  • Ahora calculamos el GCD de 18 y 12.
  • Dividimos 18 entre 12: (18 \div 12 = 1) con residuo 6 ((18 = 12 \cdot 1 + 6)).
  • Calculamos el GCD de 12 y 6.
  • Dividimos 12 entre 6: (12 \div 6 = 2) con residuo 0 ((12 = 6 \cdot 2)).
  • Como el residuo es 0, el GCD es 6.

Por lo tanto, el GCD de 48 y 18 es 6.

Implementación Iterativa en Python

El algoritmo de Euclides puede implementarse de forma iterativa, lo que resulta en un código compacto y eficiente. A continuación, se presenta una implementación en Python que sigue el procedimiento descrito:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Ejemplo de uso
print(gcd(48, 18))  # Salida: 6

En este código, el bucle while continúa mientras (b) no sea cero. En cada iteración, (a) toma el valor de (b), y (b) toma el residuo de (a \div b). Cuando (b) es cero, (a) contiene el máximo común divisor. Este enfoque es eficiente y fácil de entender, aprovechando la asignación múltiple de Python para simplificar el intercambio de valores.

Para manejar casos con números negativos o cero, se puede modificar la función:

def gcd(a, b):
    a, b = abs(a), abs(b)
    if a == 0 and b == 0:
        return 0
    if a == 0:
        return b
    if b == 0:
        return a
    while b:
        a, b = b, a % b
    return a

# Ejemplos de uso
print(gcd(48, 18))   # Salida: 6
print(gcd(-48, 18))  # Salida: 6
print(gcd(0, 5))     # Salida: 5
print(gcd(0, 0))     # Salida: 0

Esta versión considera casos especiales, como cuando uno o ambos números son cero, y maneja números negativos tomando sus valores absolutos.

Implementación Recursiva en Python

El algoritmo de Euclides también puede implementarse recursivamente, lo que refleja directamente la naturaleza matemática del procedimiento. A continuación, se muestra una implementación recursiva en Python:

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

# Ejemplo de uso
print(gcd(48, 18))  # Salida: 6

En esta implementación, la función se llama a sí misma con (b) y el residuo de (a \div b) hasta que (b) es cero. El caso base ocurre cuando (b = 0), en cuyo caso el GCD es (a). Aunque la versión recursiva es elegante, puede ser menos eficiente para números muy grandes debido al uso de la pila de llamadas.

Para manejar números negativos y casos especiales, se puede ajustar la función:

def gcd(a, b):
    a, b = abs(a), abs(b)
    if a == 0 and b == 0:
        return 0
    if a == 0:
        return b
    if b == 0:
        return a
    if b == 0:
        return a
    return gcd(b, a % b)

# Ejemplos de uso
print(gcd(48, 18))   # Salida: 6
print(gcd(-48, 18))  # Salida: 6
print(gcd(0, 5))     # Salida: 5
print(gcd(0, 0))     # Salida: 0

Esta versión recursiva incluye las mismas validaciones que la iterativa, asegurando robustez en todos los casos.

Implementación en JavaScript

El algoritmo de Euclides también es fácil de implementar en otros lenguajes, como JavaScript. A continuación, se muestra una versión iterativa:

function gcd(a, b) {
    a = Math.abs(a);
    b = Math.abs(b);
    while (b) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Ejemplo de uso
console.log(gcd(48, 18)); // Salida: 6

En este caso, se utiliza una variable temporal para realizar el intercambio de valores, ya que JavaScript no soporta asignación múltiple como Python. La función maneja números negativos mediante Math.abs y sigue el mismo procedimiento iterativo.

Una versión recursiva en JavaScript sería:

function gcd(a, b) {
    a = Math.abs(a);
    b = Math.abs(b);
    if (b === 0) {
        return a;
    }
    return gcd(b, a % b);
}

// Ejemplo de uso
console.log(gcd(48, 18)); // Salida: 6

Ambas versiones son funcionales y adecuadas para aplicaciones web donde se requiera calcular el máximo común divisor.

Implementación en C++

Para entornos donde el rendimiento es crítico, como en aplicaciones de bajo nivel, C++ es una opción común. A continuación, se presenta una implementación iterativa:

#include <cstdlib>

int gcd(int a, int b) {
    a = std::abs(a);
    b = std::abs(b);
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

#include <iostream>

int main() {
    std::cout << gcd(48, 18) << std::endl;  // Salida: 6
    return 0;
}

Esta implementación utiliza la biblioteca cstdlib para std::abs y sigue el mismo enfoque iterativo. La salida se muestra en consola para verificar el resultado.

Una versión recursiva en C++ sería:

#include <cstdlib>

int gcd(int a, int b) {
    a = std::abs(a);
    b = std::abs(b);
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

#include <iostream>

int main() {
    std::cout << gcd(48, 18) << std::endl;  // Salida: 6
    return 0;
}

Ambas versiones son robustas y adecuadas para sistemas donde se prioriza el rendimiento.

Aplicaciones del Algoritmo de Euclides

El algoritmo de Euclides tiene numerosas aplicaciones en programación y matemáticas computacionales. Algunas de las más comunes incluyen:

  • Simplificación de fracciones: Para reducir una fracción a su forma más simple, se divide el numerador y el denominador por su GCD. Por ejemplo, para la fracción (36/48), el GCD de 36 y 48 es 12, por lo que la fracción se reduce a (3/4).
def simplify_fraction(numerator, denominator):
    d = gcd(numerator, denominator)
    return numerator // d, denominator // d

# Ejemplo de uso
print(simplify_fraction(36, 48))  # Salida: (3, 4)
  • Cálculo del mínimo común múltiplo (MCM): El MCM de dos números se calcula como el producto de los números dividido por su GCD. Esto es útil en problemas como sumar fracciones o sincronizar eventos.
def lcm(a, b):
    return abs(a * b) // gcd(a, b)

# Ejemplo de uso
print(lcm(12, 18))  # Salida: 36

  • Criptografía: En algoritmos como RSA, el GCD se utiliza para verificar propiedades de números primos y garantizar la seguridad de las claves.

  • Resolución de ecuaciones diofánticas: El algoritmo de Euclides extendido permite encontrar soluciones a ecuaciones de la forma (ax + by = gcd(a, b)).

Algoritmo de Euclides Extendido

El algoritmo de Euclides extendido no solo calcula el GCD, sino que también encuentra coeficientes enteros (x) y (y) que satisfacen la ecuación (ax + by = gcd(a, b)). Este método es particularmente útil en criptografía y teoría de números.

El procedimiento sigue los mismos pasos que el algoritmo estándar, pero mantiene un registro de los coeficientes en cada iteración. A continuación, se presenta una implementación en Python:

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

# Ejemplo de uso
a, b = 48, 18
gcd, x, y = extended_gcd(a, b)
print(f"GCD: {gcd}, x: {x}, y: {y}")  # Salida: GCD: 6, x: -1, y: 3

En este ejemplo, el algoritmo devuelve el GCD (6) y los coeficientes (x = -1) y (y = 3), que satisfacen (48 \cdot (-1) + 18 \cdot 3 = 6).

Eficiencia del Algoritmo

El algoritmo de Euclides es notablemente eficiente. Su complejidad temporal es (O(\log \min(a, b))), lo que significa que el número de iteraciones es proporcional al logaritmo del menor de los dos números. Esto se debe a que cada iteración reduce al menos a la mitad el tamaño del número más pequeño, convergiendo rápidamente al resultado.

Por ejemplo, para números grandes como 123456 y 7890, el algoritmo sigue siendo rápido:

print(gcd(123456, 7890))  # Salida: 6

Esta eficiencia hace que el algoritmo sea ideal para aplicaciones donde se manejan números grandes, como en criptografía.

Consideraciones Prácticas

Al implementar el algoritmo de Euclides, es importante considerar algunos aspectos:

  • Validación de entrada: Asegúrese de manejar casos especiales, como números negativos o cero, para evitar errores.

  • Elección entre iterativo y recursivo: La versión iterativa es generalmente más eficiente en términos de uso de memoria, especialmente para números grandes.

  • Precisión numérica: En lenguajes con limitaciones de precisión, como JavaScript para números muy grandes, considere usar bibliotecas especializadas como BigInt.

Por ejemplo, en JavaScript, para números extremadamente grandes:

function gcd(a, b) {
    a = BigInt(a);
    b = BigInt(b);
    while (b) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

console.log(gcd(12345678901234567890n, 9876543210987654321n));

Este código utiliza BigInt para manejar números grandes con precisión.

Conclusiones

El algoritmo de Euclides es una herramienta poderosa y eficiente para calcular el máximo común divisor de dos números. Su simplicidad, combinada con su rapidez, lo hace indispensable en áreas como la programación, las matemáticas computacionales y la criptografía. A través de implementaciones iterativas y recursivas en lenguajes como Python, JavaScript y C++, este tutorial ha demostrado cómo aplicar el algoritmo en diversos contextos. Además, el algoritmo extendido amplía su utilidad al resolver ecuaciones diofánticas, abriendo puertas a aplicaciones avanzadas. Al dominar este algoritmo, los programadores pueden abordar problemas complejos con confianza, aprovechando una técnica que ha resistido la prueba del tiempo desde su descubrimiento hace más de dos mil años.