Recuerda que el máximo común divisor (MCD) de dos enteros A y B es el entero más grande que divide tanto a A como a B.
El algoritmo de Euclides es una técnica para encontrar rápidamente el MCD de dos enteros.

El algoritmo

El algoritmo de Euclides para encontrar MCD(A,B) es como sigue:
  • Si A = 0 entonces MCD(A,B)=B, ya que el MCD(0,B)=B, y podemos detenernos.  
  • Si B = 0 entonces MCD(A,B)=A, ya que el MCD(A,0)=A, y podemos detenernos.  
  • Escribe A en la forma cociente y residuo (A = B ⋅Q + R).
  • Encuentra MCD(B,R) usando el algoritmo de Euclides ya que MCD(A,B) = MCD(B,R).

Ejemplo:

Encuentra el MCD de 270 y 192.
  • A=270, B=192.
  • A ≠0
  • B ≠ 0
  • Usa división larga para encontrar que 270/192 = 1 con un residuo de 78. Podemos escribir esto como: 270 = 192 * 1 + 78
  • Encuentra MCD(192,78), ya que MCD(270,192)=MCD(192,78).
A=192, B=78.
  • A ≠0
  • B ≠ 0
  • Usa división larga para encontrar que 192/78 = 2 con un residuo de 36. Podemos escribir esto como:
  • 192 = 78 * 2 + 36
  • Encuentra MCD(78,36), ya que MCD(192,78)=MCD(78,36).
A=78, B=36.
  • A ≠0
  • B ≠ 0
  • Usa división larga para encontrar que 78/36 = 2 con un residuo de 6. Podemos escribir esto como:
  • 78 = 36 * 2 + 6
  • Encuentra MCD(36,6), ya que MCD(78,36)=MCD(36,6).
A=36, B=6.
  • A ≠0
  • B ≠ 0
  • Usa división larga para encontrar que 36/6 = 6 con un residuo de 0. Podemos escribir esto como:
  • 36 = 6 * 6 + 0
  • Encuentra MCD(6,0), ya que MCD(36,6)=MCD(6,0).
A=6, B=0.
  • A ≠0
  • B =0, MCD(6,0)=6.
Así que hemos mostrado:
MCD(270,192) = MCD(192,78) = MCD(78,36) = MCD(36,6) = MCD(6,0) = 6.
MCD(270,192) = 6.

Entender el algoritmo de Euclides

Si examinamos el algoritmo de Euclides podemos ver que hace uso de las siguientes propiedades:
  • MCD(A,0) = A.
  • MCD(0,B) = B.
  • Si A = B⋅Q + R y B≠0, entonces MCD(A,B) = MCD(B,R) , donde Q es un entero y R es un entero entre 0 y B-1.
Las primeras dos propiedades nos permiten encontrar el MCD si cualquiera de los dos números es 0. La tercera propiedad nos permite tomar un problema más grande y más difícil de resolver, y reducirlo a un problema más pequeño y más fácil de resolver.
El algoritmo de Euclides hace uso de estas propiedades al reducir rápidamente el problema en problemas más y más fáciles, usando la tercera propiedad, hasta que se resuelve fácilmente mediante el uso una de las dos primeras propiedades.
Podemos entender por qué funcionan estas propiedades al demostrarlas.
Podemos demostrar que MCD(A,0)=A como sigue:
  • El entero más grande que puede dividir uniformemente a A es A.
  • Todos los enteros dividen uniformemente a 0, puesto que para cualquier número entero, C, podemos escribir C ⋅ 0 = 0. Así que podemos concluir que A debe dividir uniformemente a 0.
  • El número más grande que divide tanto a A como a 0 es A.
La demostración para MCD(0, B)=B es similar. (Misma demostración, pero reemplazamos A con B).
Para demostrar que MCD(A,B)=MCD(B,R) lo primero que tenemos que mostrar es que MCD(A,B)=MCD(B,A-B).
Supón que tenemos tres números enteros A, B y C tales que A-B=C.
Demostración de que MCD(A,B) divide uniformemente a C
El MCD(A,B), por definición, divide uniformemente a A. Como resultado, A debe ser algún múltiplo de MCD(A,B). Es decir, X⋅MCD(A,B)=A, donde X es algún número entero.
El MCD(A,B), por definición, divide uniformemente a B. Como resultado, B debe ser algún múltiplo de MCD(A,B). Es decir, Y⋅MCD(A,B)=B, donde Y es algún número entero.
A-B=C nos da:
  • X⋅MCD(A,B) - Y⋅MCD(A,B) = C
  • (X - Y)⋅MCD(A,B) = C
Así que podemos ver que MCD(A,B) divide uniformemente a C.
Una ilustración de esta demostración se muestra en la parte izquierda de la siguiente figura:
Demostración de que MCD(B,C) divide uniformemente a A
El MCD(B,C), por definición, divide uniformemente a B. Como resultado, B debe ser algún múltiplo de MCD(B,C). Es decir, M⋅MCD(B,C)=B, donde M es algún número entero.
El MCD(B,C), por definición, divide uniformemente a C. Como resultado, C debe ser algún múltiplo de MCD(B,C). Es decir, N⋅MCD(B,C)=C, donde N es algún número entero.
A-B=C nos da:
  • B+C=A.
  • M⋅MCD(B,C) + N⋅MCD(B,C) = A
  • (M + N) ⋅ GCD(B,C) = A
Así que podemos ver que MCD(B,C) divide uniformemente a A.
Una ilustración de esta demostración se muestra en la siguiente figura:
Demostración de que MCD(A,B)=MCD(A,A-B)
  • MCD(A,B) por definición, divide uniformemente a B.
  • Ya demostramos que MCD(A,B) divide uniformemente a C.
  • Como el MCD(A,B) divide uniformemente tanto a B como a C, es un divisor común de B y de C.
MCD(A,B) debe ser menor que o igual a, MCD(B,C), porque MCD(B,C) es el “máximo” común divisor de B y de C.
  • MCD(B,C) por definición, divide uniformemente a B.
  • Ya demostramos que MCD(B,C) divide uniformemente a A.
  • Como el MCD(B,C) divide uniformemente tanto a A como a B, es un divisor común de A y de B.
MCD(B,C) debe ser menor que o igual a, MCD(A,B), porque MCD(A,B) es el “máximo” común divisor de A y de B.
Dado que MCD(A,B)≤MCD(B,C) y MCD(B,C)≤MCD(A,B) podemos concluir que:
MCD(A,B)=MCD(B,C).
Que es equivalente a:
MCD(A,B)=MCD(B,A-B).
Una ilustración de esta demostración se muestra en la parte derecha de la siguiente figura.
Demostración de que MCD(A,B) = MCD(B,R)
Ya demostramos que MCD(A,B)=MCD(B,A-B).
El orden de los términos no importa, así que podemos decir que MCD(A,B)=MCD(A-B,B).
Podemos aplicar repetidamente MCD(A,B)=MCD(A-B,B) para obtener:
MCD(A,B)=MCD(A-B,B)=MCD(A-2B,B)=MCD(A-3B,B)=...=MCD(A-Q⋅B,B).
Pero A= B⋅Q + R, así que A-Q⋅B=R.
Por lo tanto MCD(A,B)=MCD(R,B).
El orden de los términos no importa, así que:
MCD(A,B)=MCD(B,R).
En el siguiente artículo mostraremos cómo podemos extender el algoritmo de Euclides para encontrar inversos modulares.