Hasta ahora para calcular el máximo común divisor de dos números cualesquiera se suele utilizar dos métodos muy simples:

1: buscando los divisores de cada número y seleccionando los divisores comunes
2: Factorizando los números para poder obtener el máximo común divisor.

Procedimiento 1

Calcular el Máximo común divisor de 16 y 18.

Divisores de 16: D₁₆ = {1,2,4,8,16}

Divisores de 18: D₁₈ = {1,2,3,6,9,18}

Divisores comunes: {1,2}

Máximo común divisor = 2

Procedimiento 2

Vamos a calcular el Máximo común divisor de 16 y 21.
Factorizamos los números (15 y 21).
Escribimos en factores de cada uno de los números, 15 y 21.

Algoritmo de Euclides extendido

Para calcular el máximo común divisor de dos números enteros positivos a y b, dividimos el mayor, que puede ser a, entre el menor, supongamos b. Esta división nos proporcionará un cociente y un resto. Si aplicamos recursivamente el algoritmo del cociente, se obtiene:

Entonces, el máximo común divisor entre a y b es el último resto distinto de cero que obtengamos en el procedimiento anterior.

Ejemplo:

Determinar el mcd(270, 192)

Aplicando el algoritmo de Euclides, tenemos:

Ejemplo:

Determinar el mcd(231, 1820)

Ejemplo

Utilizando el algoritmo de Euclides calcular mcd(55, 89).

En este ejemplo aplicaremos el algoritmo de Euclides sobre dos números consecutivos de Fibonacci. Este tipo de pares son los que le exigen más en el proceso de dicho algoritmo pues siempre mcd = 1.

El algoritmo de Euclides del menor resto

Como ya hemos visto el algoritmo de Euclides es un método para calcular el máximo común divisor (MCD) de al menos un par de números.

El algoritmo de Euclides extendido es una modificación del algoritmo de Euclides, y nos permite expresar el máximo común divisor como una combinación lineal.

Recordemos que el Máximo Común Divisor de dos números “a” y “b”, es el mayor número posible que divide a los dos.

En el algoritmo de Euclides, el resto r_i está entre 0 y r_i−1, si modificamos el algoritmo para que cada nuevo resto r_i esté entre 0 y r_i−1/2 obtendremos una reducción en el número de divisiones.

Como mcd(a, b) = mcd(|a|,|b|) vamos a suponer que a ≥ 0 y b > 0.

Luego

El algoritmo del mínimo resto consiste en escoger en cada paso el menor resto, es decir

Ejemplo. Con el algoritmo del mínimo resto, obtener el mcd de a = 55 y b = 89

Aplicando el algoritmo del mínimo resto tenemos

Relación de congruencia

Si tenemos el siguiente arreglo matricial, correspondiente a los números del 1 al 25, escritos en filas de 5.

Es posible comprobar los siguiente:

1.      Si elegimos dos números cualesquiera de cualquier columna y los restamos, la diferencia es divisible por 5.

2.      Los números ubicados en una misma columna, siendo esta cualquier columna tienen el mismo resto al ser divididos por 5.

3.      Los residuos resultantes al dividir cualquier número por 5, corresponden consecutivamente a 1, 2, 3, 4 y 0 según la columna en que se encuentren.

El concepto de relaciones de congruencia nos permite agrupar infinitos números enteros bajo una relación de equivalencia llamada congruencia módulo n.

Los resultados comprobados pueden ser generalizados bajo la siguiente condición: Si se colocan n enteros consecutivos en filas constituidas por m elementos con m<n, entonces es válido en dicho arreglo:

1.      Si elegimos dos números cualesquiera de cualquier columna y los restamos, la diferencia es divisible por m.

2.      Los números ubicados en una misma columna, siendo esta cualquier columna tienen el mismo resto al ser divididos por m.

3.      Los residuos resultantes al dividir cualquier número por m, corresponden consecutivamente a 1, 2, 3, … 0 según la columna en que se encuentren.

Dados dos números, p y q, decimos que p y q son congruentes módulo n si (p - q) es divisible por n, en tal caso el resto de dividir p entre n es igual que el resto de dividir q entre n.

Si p y q son congruentes módulo n entonces lo escribimos simbólicamente de la siguiente forma:

Definición: Sea n un número entero positivo. Dos enteros a y b son congruentes módulo n si n divide a la diferencia a – b.

Ejemplos:

Teorema. La relación de congruencia módulo n cumple las siguientes propiedades

Teorema.  Dados a, b, c, d y n enteros con n > 1 y 

Entonces

Clases de equivalencia

Una clase de equivalencia es un conjunto de subconjuntos distintos del conjunto de los números enteros, bajo una relación de congruencia módulo n.

La clase de equivalencia módulo n está conformada por un conjunto infinito de elementos, números enteros congruentes entre sí bajo la relación módulo n.

Ejemplo

La relación de congruencia módulo 5, está formada por 5 clases residuales y sus elementos son números enteros de la forma 0 + 5k, 1 + 5k, 2 + 5k, 3 + 5k y 4 + 5k, donde k es un entero, las cinco clases residuales o clases de equivalencia son:

Cada clase residual módulo n puede ser representada por uno cualquiera de sus miembros; pero, por lo general, se representa cada clase residual por el menor entero no negativo que pertenezca a esta clase. Hay que notar que dos enteros pertenecientes a distintas clases residuales módulo n son incongruentes módulo n. Además, todo entero pertenece a una y sólo una clase residual módulo n.

Definición. Un subconjunto [C]_n de los enteros se dice que es un sistema completo de residuos módulo n, si cada entero es congruente a uno y sólo uno de los elementos del conjunto C.

Ejemplos

{0, 1, 2, 3, 4} es un sistema completo de residuos módulo 5.

{-10, -4, 2, 8, 14} es otro sistema completo de residuos módulo 5.

Ejemplo

Encuentre el residuo de la división de   2³⁰÷15.

Solución.

El problema equivale a encontrar cuál de las quince clases residuales módulo 15, que contienen a {0, 1, 2, 3,…..,14}  respectivamente, contiene a 2³⁰.

Se trata de encontrar un número a entre 0 y 14 tal que cumpla que 2³⁰ ≡ a (mod 15)  o lo que es lo mismo; encontrar un a que sea igual al residuo de dividir  2³⁰ entre 15.

Solución

Por tanto, el residuo de dividir 2³⁰ entre 15 es 4.

Ejemplo

Calcular 102⁸ mod 502.

Ejemplo

Calcular 12⁴³ mod 713.

Para el cálculo de expresiones de la forma a^k mod n cuando k no es una potencia de 2, se debe escribir ese exponente en binario.

Solución.

Código en C++ para obtener el residuo de una potencia dado el módulo