Aritmética modular
Artículo por Vicky Neale
La mejor forma de introducir la aritmética modular es pensar en la carátula de un reloj.
Los números van del 1 al 12 y al llegar a la hora 13, lo que vemos es de nuevo la hora 1 (piensa en cómo trabaja toda la numeración en 24 horas), Así, las 13 horas se vuelve la 1, las 14 horas se vuelve las 2, y así sucesivamente.
Esto puede continuar y cuando llegamos a la “hora 25”, regresamos de hecho al lugar de la hora 1 en la carátula del reloj (y también al lugar de la hora 13).
Así, en el mundo del reloj sólo te relacionas con los números del 1 al 12. En ese mundo, 1, 13, 25, 37,… se piensan como la misma cosa, y otro tanto ocurre con 2, 14, 26, 38,… y así sucesivamente.
Lo que estamos diciendo es que “13=1+algún múltiplo de 12” y “38=2+algún múltiplo de 12”, o de otro modo, el “residuo de dividir 13 entre 12 es 1”, y “el residuo de dividir 38 entre 12 es 2”. La notación matemática para escribir lo anterior es 13 = 1 mod 12, 38 = 2 mod 12 y así sucesivamente. Eso se lee así “13 es congruente con 1 mod (módulo 12)” y “38 es congruente con 2 mod 12”. Pero uno puede trabajar no sólo con mod 12 (éste es el término matemático para ello). Por ejemplo, puedes trabajar mod 7 o mod 46 si quieres (sólo piensa en un reloj numerado del 1 al 7, o del 1 al 46, respectivamente; cada vez que sobrepases el número más grande regresas al 1 otra vez).
Regresemos por un momento al reloj normal cuya carátula tiene los números del 1 al 12. Los matemáticos prefieren poner 0 donde usualmente está 12, así que puedes escribir normalmente 24 = 0 (mod 12) en lugar de 24 = 12 (mod 12), aunque ambas cosas son ciertas. Es decir, pensamos que la carátula de un reloj normal está numerada de 0 a 11. Eso tiene sentido: decimos normalmente que 24 deja residuo 0 cuando dividimos entre 12, en lugar de decir que deja residuo 12 cuando dividimos entre 12!.
Permíteme ser un poco más formal. En general, al estar trabajando módulo n (donde n es cualquier número entero), escribimos a = b mod n si n divide a a-b. (Examina lo que hicimos antes para ver si esta definición empata bien con los ejemplos anteriores.)
Hasta ahora, sólo hemos hablado de notación. Hagamos ahora matemáticas y vemos cómo las congruencias (lo que acabamos de describir) pueden hacer las cosas más claras.
He aquí algunas propiedades útiles. Podemos sumar congruencias, es decir, si a = b mod n y c = d mod n, entonces a+c = b+d mod n. ¿Por qué? Bien, a = b mod n significa que a = b + kn donde k es un número entero. Análogamente, c = d mod n significa que c = d + ln donde l es un número entero. Por tanto, a+c = (b+kn) + (d+ln) = b+d + (k+l) n, y en consecuencia, a+c = b+d mod n.Por ejemplo, 17 = 4 mod 13 y 42 = 3 mod 13, así que 17+42 = 4+7 mod 13. Note que las dos congruencias que sumamos son mod n y también lo es la respuesta– no sumamos los módulos.
Ahora puedes probar que si a = b mod n y c = d mod n, entonces a-c = b-d mod n. Demuestra también que podemos hacer algo similar con la multiplicación: si a = b mod n y c = d mod n, entonces ac = bd mod n. Puedes probarlo de la misma forma que usamos antes para la suma. De nuevo, las dos congruencias que estamos multiplicacndo son mod n y también lo es el resultado, no multiplicamos los módulos. ¿puedes dar un ejemplo para contradecir la afirmación de que a = b mod m y c = d mod n significa que ac = bd mod mn? La división es un poco más complicada: debes ser realmente cuidadoso. He aquí un ejemplo de por qué. 10 = 2 mod 8, pero si “dividimos ambos lados entre 2”, tendríamos 5 = 1 mod 8 lo que claramente no tiene sentido. Para tener una congruencia verdadera tendríamos que dividir también 8 entre 2: 5 = 1 mod 4 es correcto. ¿Por qué? Bien, a = b mod n significa que a = b+kn para algún entero k. Pero como ésta es una ecuación normal, si vamos a dividir a entre 2, también debemos dividir todo el lado derecho entre 2 incluyendo kn. En general, es preferible no dividir congruencias; en su lugar, piense en el significado de la congruencia (en lugar de la notación corta), y trabaje con eso. Las cosas son bastante especiales si trabajamos con congruencias mod p donde p es primo, porque cada número que no es 0 mod p tiene lo que llamamos un inverso (o inverso multiplicativo, si vamos a ser formales). Lo que eso significa es que para cada a =/ 0 mod p hay un b tal que ab = 1 mod p.
Permítanme usar un ejemplo. Trabajemos mod 7. Entonces los únicos números no cero mod 7 son 1, 2, 3, 4, 5, 6 (porque cualquier otro número es equivalente a uno de ellos o a 0). Vamos a encontrar los inversos de ellos. Con 1 es fácil: 1 x 1 = 1 mod 7. ¿Qué ocurre con 2? 2 x 4 = 1 mod 7. Así que 4 es el inverso de 2. Y, de hecho, vemos que 2 es el inverso de 4, así que nos ahorramos trabajo! Y como 3x5 = 1 mod 7, 3 y 5 son inversoso uno del otro.Finlamente, 6 x 6 = 1 mod 7 dice que 6 es su propio inverso. Fue cierto que cada elemento distinto de cero mod 7 tiene un inverso. Ensaya con algunos primos tú mismo, 11 y 13 son conveniente pequeños. Si ya te sientes seguro, mira si puedes descubrir qué números tienen inversos mod 4, o mod 6, o mod 8. ¿Qué ocurre con mod 15? ¿Encuentras algún patrón?
Para averiguar lo anterior, las cosas empiezan a ser un poco más complicadas, así que dejaré las pruebas para el final y primero doy un ejemplo en el que el uso de congruencias es útil en matemáticas.
Supongamos primero que nos dieron el número 11111111 y alguien pregunta si es divisible entre 3. Podemos tratar haciendo la división, pero tú probablemente conoces un método más fácil.: sumas los dígitos y ves si la suma es divisible entre 3. Hay un artículo entero sobre esta prueba de divisibilidad aquí (en inglés). Probemos lo anterior usando notación de congruencias.
Supongamos que nuestro número es an 10n+an-1 10n-1+ …+a1 10+a0, que escribimos como a n an-1 … a 1 a0.Entonces la suma de de los dígitos es an +an-1 + …+a1 +a0. Queremos demostrar que an 10n+an-1 10n-1+ …+a1 10+a0 es divisible entre 3 si y sólo si an +an-1 + …+a1 +a0 lo es. Notamos que 10 = 1 mod 3 , así que 10 x 10 = 1 mod 3 y, más generalmente, 10k = 1 mod 3 para todo k. Si hacemos uso de los resultados anteriores sobre suma y multiplicación de congruencias, descubrimos an 10n+an-1 10n-1+ …+a1 10+a0 = an +an-1 + …+a1 +a0 mod 3.
En consecuencia, si nuestro número es divisible entre 3, es decir, an 10n+an-1 10n-1+ …+a1 10+a0 = 0 mod 3, entonces ciertamente lo es la suma de sus dígitos y viceversa, como queremos! La notación de congruencias realmente no ha hecho matemáticas para nosotros, pero ha hecho más fácil escribir la prueba claramente. Mira si puedes usar la notación de congruencias para demostrar algunas de las pruebas de divisibilidad de este artículo.
Ahora hago la demostración que prometí al principio. Vamos a demostrar que si a y n no tienen factores en común, entonces a tiene inverso multiplicativo mod n. (recuerda: eso significa que hay un número b tal que ab = 1 mod n). En particular, si n es primo, su único divisor además de 1 es él mismo. Así que decir “a y n no tienen factores en común” equivale a decir “a no es divisible entre n”, esto es, a =/ 0 mod n. Esto es lo que teníamos antes. Voy a suponer que conoces el algoritmo de Euclides para resolver ecuaciones de la forma ax + by = 1 donde a y b no tienen factores en común. Aquí hay un artículo realmente bueno (en inglés) que lo explica, así que léelo y después regresa.
Si leíste hasta aquí, entonces convendrás en que si a y n no tienen factores en común, podemos encontrar x y y tales que ax + nby = 1 (el nombre elegante de esto es el teorema de Bezout). Podemos reescribir esto como ax=1 – ny y si permitimos el uso de la notación de congruencias de antes, ax = 1 mod n. Es decir, x es el inverso multiplicativo de a n y ¡ya acabamos! Aquí hay un reto: usa la técnica basada en el algoritmo de Euclides para encontrar el inverso multiplicativo de 14 mod 37. La comprensión de todo esto es el principio de una rama de las matemáticas llamada Teoría de los Números que contiene muchos teoremas bellos, fascinantes y divertidos. ¡Disfrútalos!
Este artículo es una traducción; el original en inglés aparece en http://nrich.maths.org/4350
