Aritmética Modular y Aplicaciones

Elena Castilla¹, Pedro J. Chocano^1*

¹Departamento de Matemática Aplicada, CC. e Ingeniería de los Materiales y Tec. Electrónica, URJC, España

^*Autor de correspondencia: pedro.chocano@urjc.es

Resumen

En este artículo hacemos una introducción a la aritmética modular. Para ello empezamos repasando cuestiones básicas como la divisibilidad y el máximo común divisor, así como la identidad de Bézout. Explicamos los conceptos más importantes de aritmética modular y de aritmética en ℤ_m. Finalmente, damos algunos sencillos ejemplos de aplicaciones de la aritmética modular en diferentes campos, como el álgebra, la criptografía o la simulacíon estadística.

Palabras clave
Aritmética Modular — Divisibilidad — Generación de números aleatorios

© 2023 The Author(s). Published by URJC. This is an open access article under the CC BY license.
Cómo citar este artículo: Elena Castilla, Pedro J. Chocano; Aritmética Modular y Aplicaciones; Forum Docentis - AP vol. 2023, (1), e16, 2023

Índice

Introducción

1Divisibilidad y Máximo Común Divisor

1.1 Divisibilidad

1.2 Máximo Común Divisor

1.3 Identidad de Bézout

2Aritmética Modular

3Aritmética en ℤ_m

4Aplicaciones

4.1 Ecuaciones diofánticas

4.2 Reglas de divisibilidad

4.3 Letra del DNI

4.4 Criptografía

4.5 Generación de números aleatorios

5Ejercicios

Referencias

Introducción

En estas breves notas, pensadas para un curso de unas 5 horas en grados de ingeniería o informática, se pretende dar una introducción rápida a algunas cuestiones de aritmética modular haciendo, al final de las mismas, especial énfasis en aplicaciones sencillas que sirvan de motivación al lector para que profundice más a fondo en algunos detalles y contenidos que se escapan por cuestiones de tiempo.

No se asumen conocimientos previos por parte del lector. Empezaremos recordando cuestiones básicas como la divisibilidad y el concepto de máximo común divisor para a continuación introducir la identidad de Bézout, resultado fundamental para abordar el estudio de ecuaciones diofánticas y congruencias lineales. Finalmente se introducen algunas aplicaciones a criptografía o métodos de simulación, entre otros.

1. Divisibilidad y Máximo Común Divisor

1.1 Divisibilidad

Definición 1.1 (Divisibilidad). Dados dos números enteros a y b (con a distinto de 0), se dice que a divide a b, y lo escribimos como a|b, si existe un c ∈ ℤ tal que b = ac. También se dice que a es un factor o divisor de b, y que b es un múltiplo de a.

Veamos en la siguiente proposición algunas propiedades sencillas.

Proposición 1.1. Sean a, b, c ∈ ℤ, tenemos:

◾ 1|a.

◾ a|0.

◾ Si a|b y a|c, entonces a|(b + c).

◾ Si a|b y b|a, entonces a = b o bien a = −b.

Definición 1.2 (Número primo). Diremos que un número p ∈ ℕ es primo si el único divisor de p es 1.

Los números primos tienen gran importancia en áreas como la criptografía. Sin embargo, encontrar números primos no es, en general, un problema sencillo. Como curiosidad, a septiembre de 2023, el número primo más grande encontrado (en diciembre de 2018 ¹) es 2^82,589,933 − 1. Un método clásico para encontrar todos los números primos más pequeños que un número n fijado, con el que posiblemente el lector ya esté familiarizado, es la criba de Eratóstenes:

Paso 1 Escribimos en orden todos los números comprendidos entre 2 y n.

Paso 2 Tomamos el primer número que no se encuentre tachado como número primo.

Paso 3 Tachamos todos los números que sean múltiplos del número que hemos marcado como primo.

Paso 4 Si el cuadrado del primer número que no ha sido tachado es inferior a n, entonces se repite el segundo paso.
Si no, el algoritmo termina, y todos los enteros no tachados son declarados primos.

A continuación mostramos un listado de los números primos que hay entre 1 y 100:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97.

1.2 Máximo Común Divisor

Definición 1.3. Dados dos enteros a y b distintos de 0, decimos que el entero d > 1 es un máximo común divisor de a y b, ó mcd(a, b), de a y b si d|a, d|b y para cualquier otro c ∈ ℤ tal que c|a y c|b se tiene que c|d.

Es común asumir que dados dos enteros distintos de cero siempre existe el máximo común divisor. Sin embargo, demostrarlo no es trivial, pues involucra el principio de buena ordenación. En estas breves notas no lo probaremos pero animamos al lector interesado que consulte [1] para ver una demostración completa. Recogemos en la siguiente proposición algunas propiedades básicas del máximo común divisor.

Proposición 1.2. Sean a, b, c, k enteros.

1. mcd(ka, kb) = |k|mcd(a, b).

2. Si a|bc y mcd(a, b) = 1, entonces a|c.

3. mcd(a, b) = d sí y sólo sí d|a, d|b y mcd(a/d, b/d) = 1.

Demostración.

2. Trivial.

3. Basta con aplicar la primera propiedad. Tenemos que $d \cdot mcd (\frac{a}{d}, \frac{b}{d}) = mcd (d \frac{a}{d}, d \frac{b}{d}) = mcd (a, b)$ . Esto nos dice que $mcd (\frac{a}{d}, \frac{b}{d}) = mcd (a, b) / d$ . Por tanto, $1 = mcd (\frac{a}{d}, \frac{b}{d})$ si y solo si mcd(a, b) = d.

□

Por ahora, solamente hemos enunciado propiedades, pero dados dos enteros no sabemos calcular el máximo común divisor. La próxima proposición será fundamental para el desarrollo de un algoritmo que nos permita tal fin.

Proposición 1.3. Sean a, b enteros positivos 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 significa que r es el resto de la división de a por b).

Demostración. Supongamos que d|a, b, luego a = da′ y b = db′ para ciertos enteros positivos a′ y b′. Por otro lado, como a = bq + r tenemos que r = a − bq = d(a′− b′q). Por tanto, d|b, r. En concreto, como mcd(a, b)|a, b, acabamos de probar que mcd(a, b)|mcd(b, r). Supongamos ahora que d|b, r, así que también tenemos que d|bq. Usando las propiedades de divisibilidad tenemos que d|(bq +r), pero a = bq +r, luego d|a. En concreto, tenemos que mcd(b, r)|a, b y esto implica que mcd(b, r)|mcd(a, 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. El algoritmo de Euclides utilizará esta propiedad para el cálculo recursivo del máximo común divisor de dos números enteros.

Algoritmo de Euclides: Dados dos enteros a y b, el algoritmo de Euclides para encontrar mcd(a, b) es como sigue:

Paso 1 Si a = 0 entonces mcd(a, b) = b, ya que el mcd(0, b) = b, y podemos detenernos.

Paso 2 Si b = 0 entonces mcd(a, b) = a, ya que el mcd(a, 0) = a, y podemos detenernos.

Paso 3 Escribe a como cociente por b: a = bq + r.

Paso 4 Encuentra mcd(b, r). Para ello repite los anteriores pasos cambiando a por b y b por r.

Ejemplo 1.4. Calculemos mcd(42, 24). Dado que ninguno de los términos es cero, aplicamos el Paso 3 del algoritmo:

$42 = 24 \times 1 + 18 .$

Si usamos la Proposición 1.3, es decir, el Paso 3, tenemos que mcd(42, 24) = mcd(24, 18). De nuevo como 24 y 18 son distintos de cero volvemos al Paso 3:

$24 = 18 \times 1 + 6 .$

Por el Paso 4 tenemos mcd(24, 18) = mcd(18, 6). Volvemos de nuevo al Paso 3:

$18 = 6 \times 3 + 0 .$

Aplicando el Paso 4, mcd(18, 6) = mcd(6, 0). Por el Paso 2 podemos detener el algoritmo y hemos llegado a que mcd(42, 24) = 6.

1.3 Identidad de Bézout

En esta sección vamos a enunciar un resultado fundamental que necesitaremos más adelante. La demostración del resultado no es complicada e instamos al lector interesado que la vea con detalles por ejemplo en [2].

Teorema 1.5 (Identidad de Bézout). Sean a y b números enteros con d = mcd(a, b). Entonces existen enteros x e y tales que d = ax + by.

Veamos cómo obtener los enteros x e y de la identidad de Bézout. Para ello, solamente tenemos que aplicar el algoritmo de Euclides para calcular el máximo común divisor y deshacer las operaciones. Veamos un sencillo ejemplo a modo de ilustración.

Ejemplo 1.6. Vamos a encontrar una identidad de Bézout para 42 y 24. Previamente, habíamos obtenido que mcd(42, 24) = 6. Así pues, el objetivo es encontrar enteros x e y tales que 6 = 42x + 24y. Escribimos las distintas iteraciones del Paso 3 de algoritmo de Euclides.

$42 = 24 \times 1 + 18 (1)$

$24 = 18 \times 1 + 6 (2)$

$18 = 6 \times 3 + 0 (3)$

Si en la ecuación (2) despejamos el 6 tenemos:

$6 = 24 - 18 \times 1 .$

Ahora vamos a despejar 18 de la ecuación (1)

$18 = 42 - 24 \times 1$

y vamos sustituir el 18 que acabamos de obtener en la forma que teníamos de expresar 6:

$6 = 24 - (42 - 24) = 2 \times 24 - 42 .$

De esta manera acabamos de obtener que x = 2 e y = −1.

De manera general tenemos que dados dos números enteros a y b tales que ni a divide a b, ni b divide a a, si aplicamos el algoritmo de Euclides obtenemos denotando por r₀ = a y r₁ = b la siguiente secuencia de restos:

$\begin{matrix} r_{0} = r_{1} q_{1} + r_{2} \\ r_{1} = r_{2} q_{2} + r_{3} \\ r_{2} = r_{3} q_{3} + r_{4} \\ ⋮ \\ r_{k - 2} = r_{k - 1} q_{k - 1} + r_{k} \\ r_{k - 1} = r_{k} q_{k} \end{matrix}$

Tenemos que r_k = mcd(a, b). Despejando r_k en la penúltima ecuación, a continuación sustituyendo r_k−1 por el resultado de despejarlo en la antepenúltima igualdad, y recorriendo todo el camino otra vez desde abajo hasta arriba obtenemos una identidad de Bézout.

2. Aritmética Modular

Definición 2.1. Sean a y b enteros y m un entero positivo. Se dice que a es congruente a b módulo m, y se expresa

$a \equiv b (\mod m),$

si (a − b) es múltiplo de m. Es decir, da resto b si dividimos a entre m.

Ejemplo 2.1. Veamos algunos sencillos ejemplos de congruencias:

5 ≡ 1 (mod 2)	5 ≡ −1 (mod 3)	100 ≡ 24 (mod 76)
5 ≡ 2 (mod 3)	23 ≡ 1 (mod 11)	6 ≡ 0 (mod 2)

Propiedades: Sean a, b, c ∈ ℤ y m un entero positivo, entonces se cumple

◾ Reflexividad: a ≡ a (mod m).

◾ Simetría: Si a ≡ b (mod m), entonces b ≡ a (mod m).

◾ Transitividad: Si a ≡ b (mod m) y b ≡ c (mod m), entonces a ≡ c (mod m).

Queda como un sencillo ejercicio para el lector probar las anteriores propiedades.

La relación de congruencia se trata por tanto de una relación de equivalencia en ℤ, que descompone este conjunto en m clases de equivalencia:

$ℤ_{m} = {[0], [1], \dots, [m - 1]},$

donde [i] = {k ∈ ℤ|k ≡ i (mod m)} para i = 0, …, m − 1. Por tanto, la clase [i] está representando el conjunto de números que tienen por resto i al dividir por m. Cuando tenemos una relación de equivalencia y consideramos sus clases, estamos de alguna manera clasificando a los elementos del conjunto original siguiendo alguna propiedad concreta que viene determinada por la relación. A pesar de que [i] es un conjunto con infinitos elementos vamos a tratarlo como si se tratara de un único elemento y cuando no haya dudas en la notación simplemente denotaremos a los elementos de ℤ_m como {0, 1, …, m − 1}.

Ejemplo 2.2. Supongamos que tomamos la relación de congruencia con m = 2. En ese caso, estamos distinguiendo si los números son pares e impares, ℤ₂ = {0, 1}. La clase 0 representa a los números pares y la clase 1 representa los números impares.

Notación: Como norma general, se tiende a expresar las congruencias con un elemento 0 ≤ b ≤ m. Así, por ejemplo, aunque las identidades

$5 \equiv 2 (\mod 3) y 5 \equiv - 1 (\mod 3)$

son ambas ciertas, se prefiere la primera expresión. Podemos decir que, en ℤ₃: −1 = 2 ó 3 = 0.

A continuación enunciamos sin demostración algunas propiedades sencillas de demostrar que quedan como ejercicio propuesto.

Proposición 2.3. Sean a, b, c, d, λ ∈ ℤ y m, k ∈ ℕ tal que a ≡ b (mod m) y c ≡ d (mod m), entonces:

◾ λa ≡ λb (mod m).

◾ a + c ≡ b + d (mod m).

◾ ac ≡ bd (mod m).

◾ a^k ≡ b^k (mod m).

Proposición 2.4. Sean a, b, c ∈ ℤ y m ∈ ℕ. Si ac ≡ bc (mod m) y mcd(c, m) = 1, entonces:

$a \equiv b (\mod m) .$

Hay distintas demostraciones del siguiente resultado, el lector interesado puede encontrar alguna de ellas en [1].

Teorema 2.5 (Pequeño teorema de Fermat). Si p es primo y a no es múltiplo de p, entonces:

$a^{p - 1} \equiv 1 (\mod p) . (4)$

Observación 2.6. La ecuación (4) se cumple si p es primo, pero también puede darse en caso de no serlo. Por ejemplo:

$2^{340} \equiv 1 (\mod 341), p e r o 341 n o e s p r i m o : 341 = 31 \times 11 .$

Veamos cómo podemos utilizar los resultados previos en un problema de obtener restos.

Ejemplo 2.7. Supongamos que queremos calcular el resto de dividir 2³⁹3³⁸entre 37, evidentemente sin usar calculadora. Este problema es equivalente a obtener x donde

$2^{39} 3^{38} \equiv x (\mod 37) .$

Tenemos que 37 es primo (ya lo vimos en la criba de Eratóstenes). Vamos a aplicar el pequeño teorema de Fermat dos veces. Sabemos que

$2^{36} \equiv 1 (\mod 37),$

$3^{36} \equiv 1 (\mod 37) .$

Aplicamos la primera propiedad de la Proposición 2.3 a la primera ecuación multiplicando por 2³y lo mismo a la segunda ecuación multiplicando por 3²:

$2^{39} \equiv 2^{3} (\mod 37),$

$3^{38} \equiv 3^{2} (\mod 37) .$

Utilizando la propiedad 3 de la Proposición 2.3 a las dos anteriores congruencias tenemos:

$2^{39} 3^{38} \equiv 3^{2} 2^{3} (\mod 37) .$

Así pues, nuestro problema original se ha traducido en el problema de obtener el resto de dividir 3²2³entre 37 que claramente es 35.

Otra manera sencilla de resolver el problema también puede ser considerando 2³⁹3³⁸ = 2³3²(2³⁶3²⁶) = 2³3²6³⁶. De nuevo podemos aplicar el pequeño teorema de Fermat:

$6^{36} \equiv 1 (\mod 37) .$

Y de nuevo, aplicando la primera propiedad de la proposición 2.3 tenemos:

$2^{39} 3^{38} \equiv 2^{3} 3^{2} 6^{36} \equiv 3^{2} 2^{3} (\mod 37) .$

3. Aritmética en ℤ_m

Hemos visto que ℤ_m era el resultado de clasificar o agrupar los números de ℤ en función del resto obtenido al dividir por m. Pero ℤ es un anillo conmutativo si consideramos la suma y producto usuales. Estas operaciones se trasladan de manera natural a ℤ_m, es algo que ya vimos en la sección previa con la Proposición 2.3.

Ejemplo 3.1. Tenemos que en ℤ₂la suma y producto nos queda como sigue:

Por tanto, si trabajásemos en ℤ₂, sí que se cumple uno de los errores más comunes entre los estudiantes de escribir (a + b)² = a² + b². Ya que en ℤ₂el término 2ab es congruente con 0 módulo 2.

Ejemplo 3.2. Otro sencillo ejemplo con aritmética modular lo encontramos en el día a día con las horas. Si tenemos un reloj digital, cuando vemos que la hora marca las 15, no decimos las 15 sino las 3. Esto se debe a que de manera inconsciente estamos trabajando en ℤ₁₂y lo que acabamos de hacer es obtener el resto de dividir 15 entre 12.

En ℤ_m, tenemos algunas peculiaridades que no ocurren en ℤ. Por ejemplo, en ℤ, a × b = 0 si y solo si alguno de los dos términos es cero. Sin embargo, en ℤ₁₂, tenemos que 3 × 4 = 0, pero ninguno de los dos términos es cero. Además, mientras que en ℤ no tenemos inversos para el producto (nos tendríamos que ir a el conjunto de los racionales ℚ), si consideramos ℤ₃ tenemos que 2 × 2 = 1. Estas cuestiones motivan las dos siguientes definiciones:

Definición 3.1. Diremos que a ∈ ℤ_m es un divisor de cero si existe x ∈ ℤ_m distinto de 0 tal que a × x = 0.

Por ejemplo, en ℤ₁₂ tenemos que 3 es un divisor de cero. Veamos una caracterización muy útil que emplea herramientas previas:

Teorema 3.3. Supongamos que a ∈ ℤ_m. Tenemos que a es divisor de cero si y solo si mcd(a, m) ≠ 1.

Definición 3.2. Diremos que a ∈ ℤ_m es un elemento invertible de ℤ_m si existe b ∈ ℤ_m tal que ab = 1.

Por ejemplo, en ℤ₇ tenemos que 2 es un elemento invertible porque 2 × 4 = 1. De nuevo, enunciamos una importante caracterización:

Teorema 3.4. Supongamos que a ∈ ℤ_m. Tenemos que a es invertible si y solo si mcd(a, m) = 1.

Cuando trabajamos con los números reales el tipo de ecuaciones más sencillas a resolver son las de la forma ax + b = 0. Veamos su equivalente en ℤ_m.

Definición 3.3. Llamaremos congruencia lineal a una ecuación de la forma

$a x \equiv b (\mod m),$

donde a, b ∈ ℤ, a ≠ 0 y m ∈ ℕ.

Una observación interesante es que si α es solución a una congruencia lineal y β ≡ α (mod m), entonces β también es solución.

Ejemplo 3.5. 2x ≡ 1 (mod 6) no tiene solución en ℤ₆. Mientras que 2x ≡ 2 (mod 8) tiene dos soluciones en ℤ₈(x = 1 y x = 5).

Con el siguiente resultado vamos a caracterizar cuándo una congruencia lineal tiene solución. Además, en la propia demostración vamos a ver los pasos a seguir para poder hallarla.

Teorema 3.6. La congruencia lineal ax ≡ b (mod m) tiene solución si y solo si mcd(a, m)|b.

Demostración. Supongamos primero que la congruencia tiene solución y la denotaremos por α, esto significa que m|aα − b y a su vez que existe k tal que km = aα − b. Despejando b, tenemos b = aα − km como mcd(a, m)|aα y mcd(a, m)|km, entonces mcd(a, m)|b. Supongamos ahora que mcd(a, m)|b y veamos que hay solución. Como d = mcd(a, m)|b, tenemos que b = db′ para cierto entero b′. Usando la identidad de Bézout sabemos que existen enteros u y v tales que d = au + mv. Multiplicando esta última igualdad por b′ tenemos

$b = d b' = b' a u + b' m v .$

Esto significa que b ≡ b′ua (mod m) y b′u es solución.

□

Ejemplo 3.7. En este ejemplo veremos cómo usar la identidad de Bézout para hallar una solución a una congruencia lineal. Considera la congruencia lineal definida por

$56 x \equiv 42 (\mod 105) .$

Aplicamos el algoritmo de Euclides para calcular mcd(105, 56):

$105 = 56 \times 1 + 49$

$56 = 49 \times 1 + 7$

$49 = 7 \times 7 + 0$

Tenemos pues que mcd(105, 56) = 7. Vamos a hallar una identidad de Bézout. Despejando, tenemos que 7 = 56−49×1 y 49 = 105 − 56 × 1. Finalmente: 7 = 56 − 105 + 56 = 2 × 56 + (−1)105. Multiplicando dicha identidad por 42/7 = 6 tenemos

$42 = 12 \times 56 - 5 \times 105,$

lo que me da la solución x = 12.

Observa que si en la congruencia ax ≡ b (mod m) tenemos que mcd(a, m) = 1, entonces hay solución. Además, como mcd(a, m) = 1, significa que a es invertible. Así que el problema de resolver la congruencia se puede convertir en un problema de encontrar el inverso de a. También al revés, el problema de encontrar el inverso de un elemento a se puede ver como el de resolver la congruencia lineal ax ≡ 1 (mod m).

4. Aplicaciones

4.1 Ecuaciones diofánticas

Las ecuaciones diofánticas son ecuaciones en dos o más variables con coeficientes reales donde se buscan soluciones que sean números enteros de manera que la solución no sea trivial (por ejemplo todo ceros). Posiblemente una de las ecuaciones diofánticas más importantes sea la generalización de la ecuación pitagórica ( x² + y² = z²) dada por:

$x^{n} + y^{n} = z^{n} .$

Nótese que para el caso n = 2 tenemos infinitas soluciones si tenemos en cuenta un resultado básico de geometría: Teorema de Pitágoras. Este teorema nos dice que en un triángulo rectángulo, la hipotenusa al cuadrado es igual a la suma de los catetos al cuadrado.

El problema general planteado previamente con n ≥ 3 es lo que se conoce como el último teorema de Fermat. Dicho problema fue planteado en 1637 por el matemático francés Pierre de Fermat y no fue hasta 1994 cuando Andrew Wiles consiguió demostrar que no hay soluciones triviales para n ≥ 3. Se recomienda al lector interesa- do en dicho problema el libro divulgativo [3] donde se hace un repaso general a la apasionante historia de este problema.

En esta sección abordaremos una familia de ecuaciones diofánticas muy sencillas

$a x + m y = b,$

donde a, b, m ∈ ℤ. Realmente el problema de encontrar x e y se puede abordar como el problema de encontrar soluciones a una congruencia lineal. Veamos cómo ambos problemas son equivalentes:

◾ Si ax ≡ b (mod m) tiene solución, significa que existe x tal que ax − b = −my para cierto y ∈ ℤ pues que haya solución implica que m divide a ax − b. En concreto, tenemos ax + my = b.

◾ Por otro lado, supongamos que ax + my = b tiene solución. Esto significa que ax − b es divisible por m y en concreto ax ≡ b (mod m).

Por tanto, podemos establecer

Teorema 4.1. La ecuación diofántica ax + my = b tiene solución si y solamente si mcd(a, m)|b.

Además, para encontrar la solución basta con proceder como hicimos previamente para resolver una congruencia lineal, pero teniendo en cuenta los dos términos encontrados en la identidad de Bézout.

Ejemplo 4.2. Considera la ecuación diofántica dada por

$42 = 56 x + 105 y .$

Como mcd(56, 105) = 7|42, tenemos que dicha ecuación tiene solución. Si repetimos los pasos seguidos en el Ejemplo 3.7 llegamos a que

$42 = 12 \times 56 - 5 \times 105$

y por tanto una solución es x = 12 e y = −5.

Una vez se han estudiado las ecuaciones más sencillas el paso natural es estudiar sistemas de congruencias lineales. Para aquellos interesados en profundizar en esta cuestión recomendamos [1].

4.2 Reglas de divisibilidad

Vamos a ver algunas reglas de divisibilidad conocidas. Para ello, nos apoyaremos en el siguiente teorema de sencilla demostración:

Teorema 4.3. Si p(x) es un polinomio con coeficientes en ℤ y tenemos dos enteros a y b tales que a ≡ b (mod m) para algún entero positivo m, entonces p(a) ≡ p(b) (mod m).

Si n = a_ka_k−1…a₁a₀ es la expresión decimal de n, entonces n = a_k10^k + a_k−110^k−1 + … + a₁10 + a₀. Esta última expresión la podemos ver como un polinomio evaluado en 10, es decir, p(x) = a_kx^k + a_k−1x^k−1 + … + a₁x + a₀ y n = p(10).

Criterio de divisibilidad por 9 Como 10 ≡ 1 (mod 9), usando el anterior teorema tenemos que

$n = p (10) \equiv p (1) = a_{k} + a_{k - 1} + \dots + a_{1} + a_{0} (\mod 9) .$

Por tanto, n es divisible por 9 si la suma de sus cifras es múltiplo de 9.

Criterio de divisibilidad por 11 Podemos repetir el mismo esquema usado previamente, tenemos que 10 ≡ −1 (mod 11) y entonces

$n = p (11) \equiv p (1) = a_{k} {(- 1)}^{k} + a_{k - 1} {(- 1)}^{k - 1} + \dots - a_{1} + a_{0} (\mod 11) .$

Por tanto, n es divisible por 11 si lo es la suma alternada de sus cifras.

Queda como ejercicio para el lector que obtenga otras reglas de divisibilidad que conozca aplicando este esquema.

4.3 Letra del DNI

Si el lector alguna vez se ha preguntado de donde se obtiene la letra final de su DNI, esta se obtiene tras un pequeño ejercicio con congruencias. En concreto, ha de dividirse el número completo del DNI entre 23. El resto de la división (que siempre estará comprendido entre 0 y 22) será el que se obtenga para obtener la letra según la siguiente tabla:

RESTO

LETRA

RESTO

LETRA

4.4 Criptografía

En este apartado vamos a ver, a modo de ejemplo, una de las técnicas de cifrado en criptografía más usadas, el cifrado César o cifrado por desplazamiento:

Cifrado César Consideramos el alfabeto español, con 27 símbolos. Otorgamos a cada una en orden un número: A = 0, B = 1, C = 2,…, Z = 26. Codificamos la letra x con un desplazamiento n como sigue

$E_{n} (x) = x + n (\mod 27) .$

La descodificación de una letra será deshacer este proceso, simplemente valdría con

$D_{n} (x) = x - n (\mod 27) .$

Evidentemente, este es un tipo de codificación demasiado simple y muy poco seguro, pero bastante ilustrativo. Veamos un sencillo ejemplo, tomemos un desplazamiento de n = 4. De esta manera tenemos que la palabra “HOLA” queda codificada como “LSOE”. Como ejercicio descodifica la siguiente palabra donde hemos tomado n = 2 “XC-KUCUWURGPFGT” (Consejo: hay calculadoras en línea ² que resuelven el problema conociendo el desplazamiento n).

4.5 Generación de números aleatorios

El desarrollo de los métodos de simulación así como la aparición de ordenadores de alta velocidad a mitad del siglo XX, promovió el desarrollo de métodos de generación de números pseudoaleatorios. A continuación presentamos el generador congruencial lineal introducido por Lehmer en el 1951 [4].

Método congruencial para la generación de números aleatorios Dados a, b, m ∈ ℕ:

Paso 1 Elegir un número x₀ inicial (semilla).

Paso 2 Para i ≥ 1 obtener de manera recursiva

$x_{i} \equiv a x_{i - 1} + b (\mod m) . (5)$

Si además queremos que los números se encuentren en el intervalo [0, 1] (muy útil en caso de querer simular más adelante otras distribuciones estadísticas), debemos dividir la secuencia de números obtenidos entre m,

$u_{i} = \frac{x_{i}}{m} .$

Si b = 0, se dice que es un generador multiplicativo, en caso contrario se dice que es un generador mixto. Por otra parte, aunque hablemos de generar números “aleatorios”, estos quedan completamente determinados por nuestro algoritmo. La pseudoaleatoriedad de los métodos congruenciales se refleja en la siguiente proposición:

Proposición 4.4. Si se aplica un método congruencial como el definido en (5), se verifica

$x_{i} \equiv a^{i} x_{0} + b \frac{a^{i} - 1}{a - 1} (\mod m)$

Un gran inconveniente de este método es que los valores u_i sólo pueden tomar valores i/m, i = 0, …, m. Además, es inevitable que se produzcan ciclos, ya que el periodo nunca puede exceder al módulo. Así, se tiene que tomar un valor suficiente grande de m para que el conjunto de posibles valores de la sucesión se asemeje a la de una variable continua uniforme en el intervalo [0, 1] y que el ciclo no sea demasiado corto. En concreto, el siguiente teorema nos dice cómo elegir los parámetros para que el ciclo sea completo.

Teorema 4.5. Un generador congruencial tiene periodo completo si y sólo si se cumplen las siguientes condiciones:

1. m y b son primos entre sí.

2. Si q es un número primo que divide a m, entonces q divide a (a − 1).

3. Si 4 divide a m, entonces 4 divide a (a − 1).

Recomendamos [5] al lector interesado en otros aspectos y cuestiones relacionados con la simulación para que pueda comprobar el impacto que tiene la generación de números aleatorios en las matemáticas actuales.

5. Ejercicios

1. Escribe un programa para cada una de las siguientes tareas:

a) Calcular el máximo común divisor entre dos números enteros.

b) Dados dos números enteros, calcular una identidad de Bézout.

c) Dada una congruencia lineal, determinar si existe solución y en caso de que existe hallar una posible solución.

d) Dada una ecuación diofántica, hallar una solución en caso de que exista.

2. Mediante el algoritmo de Euclides, calcular el máximo común divisor de los siguientes pares de números

a) mmcd(721, 448).

b) mcd(25134, 19185).

3. Demostrar que sean a, b, c, d, λ ∈ ℤ y m ∈ ℕ tal que a ≡ b (mod m) y c ≡ d (mod m), entonces:

a) λa ≡ λb (mod m).

b) a + c ≡ b + d (mod m).

c) ac ≡ bd (mod m).

4. Calcular el resto de la división 2⁹⁸ por 101.

5. Demostrar que los posibles restos de la división por 7 de un cubo perfecto son 0, 1 ó 6.

6. Si p es primo demuestra que (x + y)p = xp+ yp en ℤ_p.

7. Si x ∈ ℤ, entonces 4x² + x + 3 no es divisible por 5.

8. Resuelve la congruencia 6x + 1 ≡ 2(x + 2) (mod 7).

9. ¿Qué elementos tienen inverso en ℤ₁₂?

10. Encuentra, si es posible, el inverso de 47 en ℤ₆₁.

Referencias

¹D. M. Burton, Elementary Number Theory, 7.^a ed. (McGraw Hill, 2010).

²T. M. Apostol, Introduction to Analytic Number Theory (Springer, 1976).

³S. Singh, Fermat’s Last Theorem (Harper Collins, 1997).

⁴D. H. Lehmer, “Mathematical models in large-scale computing units”, Ann. Comput. Lab. (Harvard University) 26, 141–146 (1951).

⁵E. Castilla y P. J. Chocano, “Introducción al Método de Montecarlo”, Gaceta de la Real Sociedad Matemática Española 26, 87–109 (2023).

_______________________________

¹ “GIMPS Project Discovers Largest Known Prime Number: 282,589,933-1”. Mersenne Research, Inc. 21 December 2018. Retrieved 21 December 2018. https://www.mersenne.org