Aritmética modular

Fecha de primera versión: 04-12-04
Fecha de última actualización: 19/04/2010

Los números con los que trabajamos habitualmente se extienden sin fin. El caso más sencillo de explicar es el de los números naturales, en los que, después de un número n, le sigue el n + 1, para cualquire valor de n.

Supongamos unos números que fuesen asi: 0, 1, 2, 3, ..., (n - 3), (n - 2), (n - 1), 0, 1, 2, 3, ..., (n - 3), (n - 2), (n - 1), 0, ... o sea, unos números que cuando debieran alcanzar n, volviese a comenzar en el cero y así indefinidamente.

A este número que no se alcanza nunca, n, se le llama módulo y por eso esta aritmética se llama modular.

Veamos cómo se opera con estos números.

La suma es fácil. Lo vamos a ver con un ejemplo, supongamos que n = 35. 

15 + 5 = 20
32 + 3 = 35 == 0
28 + 10 = 38 == 3
126 + 3 = 129 == 94 == 59 == 24

15 - 5 = 10
45 - 10 = 35 == 0
45 - 5 = 40 == 5
126 - 3 = 123 == 88 == 53 == 18
5 - 15 = -10 == 25

Lo que hemos hecho es que cuando el resultado supera 35, restamos o sumamos 35 al resultado, hasta que el número que nos resulte esté comprendido entre 0 y 34.

La multiplicación también es fácil. El truco es el mismo: si el resultado supera 35 se le resta 35 tantas veces como sea necesario para que el resultado final esté comprendido entre 0 y 34. Si el resultado es negativo se le suma 35 hasta que consigamos el mismo objetivo.

La división no es tan fácil.

Si el resultado de la división es un número entero no plantea problemas, actuamos igual.

25/5 = 5
250/5 = 50 == 15

Pero ¿qué ocurre si el resultado no es entero, como por ejemplo 4/3?

Para resolver esta dificultad, la división, en aritmética modular, se define como multiplicar por el inverso. 

¿Y cuál es el inverso de un número? El inverso de un número es otro número que multiplicado por el primero dé 1.

Continuando con nuestro ejemplo, el inverso de 3, módulo 35, es 12, porque 3 * 12 = 36 == 1. Entonces, la operación 4/3, se convierte en 4*12 = 48 == 13. El resultado de dividir 4 entre 3, módulo 35, es 13.

Comprobémoslo. Si 4 dividido entre 3 es 13, 13 por 3 debe ser 4. Efectivamente 13 * 3 = 39 == 4.

Calcular el inverso de un número x módulo n es fácil si n es primo. En este caso, el inverso de x, que representamos por x^-1 = x^{phiEuler(n - 1)} .

¿Qué es la función phiEuler? La función phiEuler de un número n, es el cardinal (el número de elementos) del conjunto de los números primos relativos (sin factores comunes) con n. 

Supongamos que n = 17. Como 17 es un número primo, ninguno de los números anteriores a 17 tiene factores comunes con él y el conjunto de los número primos relativos con 17 es {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,16} y el cardinal de este conjunto es 16, luego la función phiEuler es 16.  Cuando n es primo, la funcion phiEuler es (n - 1).

Si n es el producto de dos números primos, p y q (como es nuestro caso 35 = 5 * 7), calcular el inverso de un número x, también es fácil, x^-1 = x^{phiEuler(p - 1)(q - 1) - 1}  

El conjunto de los números que son primos relativos (sin factores comunes) con 35 es:
{1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34} El número de elementos de este conjunto (el cardinal del conjunto o función phi de Euler) es 24. Cuando p y q son primos, la funcion phi de euler es igual a (p-1)·(q-1). 
En nuestro ejemplo 3²³ = 94143178827, que se convierte en 12.

Si no conocemos los factores del número n, hallar el inverso de un número módulo n, es una tarea árdua, pues tenemos que probar todos los números entre 2 y (n -1) cuál de ellos cumple que multiplicado por el número del que queremos conocer el inverso, el resultado sea 1, módulo n. 

Todas las propiedades de las operaciones aritméticas se conservan en la aritmética modular.