El operador módulo (mod)

Podemos decir que básicamente la operación modulo (mod) nos hace obtener el residuo de dos números, sea por ejemplo:

---

Observe que los valores 1, 2 y 0 se repiten continuamente, esto es porque en módulo 3 solo obtendremos valores enteros positivos menores a 3 (esto se puede notar dado que dichos valores son residuos donde el divisor es 3, por lo que lógicamente en la división convencional estos residuos siempre serán menores a 3 y mayores o iguales a 0), a estos valores 1 2 y 3 los llamamos conjunto de residuos modulo n.

De forma general en modulo n nuestro conjunto de residuos son los números enteros positivos menores que n y el 0.

Ejemplo:

N=3 | conjunto_residuos = {0, 1, 2}
N=4 | conjunto_residuos = {0, 1, 2, 3}
N=20 | conjunto_residuos = {0, 1, 2, 3, … , 19}

– Podriamos decir que (Si la operación mod la tomamos como una función Z→Z ) el rango sería conjunto_residuos. –

¿Que ocurre con los demás números?

Todos los números enteros que no estén dentro de conjunto_residuos son congruentes a algún número dentro de conjunto_residuos. De esa forma podemos tener cualquier número entero ya sea muy grande o no al aplicarle mod N el resultado siempre será un valor dentro de conjunto_residuos de N.

13 es congruente con 1 (mod 3)
14 es congruente con 2 (mod 3)
15 es congruente con 0 (mod 3)
1998 es congruente con 0 (mod 3)

Nota : Si A es un múltiplo de N, entonces A es congruente con 0 en módulo N, es decir:

MCD(A, N) ≠ 1 → A ≡ 0 mod N
ó también podemos escribirlo como:
A|N → A≡0 mod N
– OBS: A|N significa «A divide a N» –

---

¿Los enteros negativos pueden ser representador en módulo N?

Un número negativo también pueden ser representado en modulo n, por ejemplo hallemos el congruente con -2 en módulo 3, podemos expresar esto como:

-2 (mod 3)

Recordando la definición del elemento neutro para la suma:

La elemento neutro de la suma es el valor que, cuando está sumado a cualquier otro valor en un conjunto, vuelve el otro valor en el conjunto. Para el conjunto del números reales, la identidad aditiva es 0. Esto es porque para cualquier número real a , 

http://www.allmathwords.org/es/a/additiveidentity.html

Esto puede parecer algo obvio cuando hablamos del 0, pero en aritmética modular podríamos decir -con fin didactico- que ‘existen varios elementos neutros’ los cuales son todos los números congruentes con 0. Por ejemplo podríamos decir que en módulo 3 los neutros son el 0, 3, 6, 18, … ya que todos son congruentes con cero. (en realidad no es que existan ‘varios neutros’ ya que el neutro en la suma es único, y en realidad es solo el 0, los números 0, 3, 6, 18, … son congruentes con 0 por lo que son el mismo 0 en realidad).

Dicho esto y por la definición del neutro podemos sumar el neutro a cualquier número sin alterar nada, por lo que si tenemos -2 en módulo 3 podemos sumarle 0 o 3 o 6 o cualquier múltiplo del módulo sin alterar la expresión original, entonces:

-2 (mod 3) =
-2 + 3 (mod 3) =
1 mod 3 =
1

-2 es congruente con 1 en módulo 3

Congruencia modulo N (≡)

Podemos decir que un número A es congruente modulo N con otro número B cuando ambos dejan el mismo residuo al dividir por N (y en caso A o B sean negativos debemos sumarle un múltiplo de N, como vimos en líneas más arriba, para hallar su congruente). Esto se representa como:

A ≡ B mod (N)

Una condición que siempre se cumple es: N|(A – B)
Esto se nota claramente cuando representamos A y B como:

A = N * q1 + r1 , donde r1 el residuo de A entre N y q1 el cociente
B = N * q2 + r2 , análogamente a A con r2 y q2 para B

Si A ≡ B mod (N) significa que r1 = r2, entonces:

A = N * q1 + r1
B = N * q2 + r1

Ahora hacemos:

A – B = N * q1 + r1 – (N * q2 + r1)
A – B = N * (q1 + q2) + r1 – r1
A – B = N * (q1 + q2)
(A – B) / N = q1 + q2
– Dado que q1 y q2 son cocientes de una división son enteros (Z) y por la Ley de cierre podemos decir que q1 + q2 también es un entero (Z). –

Como el resultado de (A-B) / N es un entero podemos decir que N|(A-B), L.Q.Q.D.

Inverso multiplicativo modulo N

Definición de inverso multiplicativo:

En matemática, el inverso multiplicativo, recíproco o inverso de un número x no nulo, es el número, denotado como ó , que multiplicado por x da 1 como resultado.

En los números reales el 0 no tiene inverso multiplicativo porque ningún número real multiplicado por 0 da como resultado 1.

Fuente: Wikipedia

Podemos aplicar el mismo concepto para el inverso módulo N, de esta manera:
El inverso de A mod N (A^-1 mod N) es un número B (en el caso que exista), tal que (A * B) mod N = 1 , dicho de otra manera A * B es congruente con 1 módulo N:

a * b ≡ 1 mod n

El inverso es reciproco, a es el inverso de b y b el inverso de a (en mod n)

Existencia del inverso:

El inverso de un número en cierto modulo siempre existe si y solo si se cumple la condición de que el MCD (a, n) = 1 , en cualquier otro caso el inverso no existe ¿Por que se da esta condición? , recordemos lo dicho en líneas anteriores:

i. (…) El 0 no tiene inverso multiplicativo porque ningún número real multiplicado por 0 da como resultado 1.

ii. Si MCD(A, N) ≠ 1 → A ≡ 0 mod N

De esto notamos que la condición es lógica dado que si afirmamos «El inverso (mod n) de A existe cuando MCD (A, N) ≠ 1 o cuando A es un múltiplo de N» estaríamos afirmando que «El inverso de 0 existe» (ya que si A es múltiplo de N entonces A mod N = 0) lo cual contradice a (i).

En modulo un número primo existen los inversos para todos los enteros positivos menores que dicho numero primo, por ejemplo: en modulo 7 existen inversos para 1, 2, 3, 4, 5 y 6 ya que todos cumplen que el mcd es 1.

Cálculo del inverso:

El cálculo del inverso no siempre es sencillo, aunque muchas veces sí y muchas veces solo puede ser un cálculo mental. Hay diversos teoremas y algoritmos que facilitan el cálculo del inverso modular, uno muy popular es el Teorema de Euler o el Algoritmo Extendido de Euclides (que se explican en otro post en esta misma web: {publicación} ) En este caso calcularemos el inverso usando cálculo mental, esto puede ser muy sencillo y hasta lúdico, pero que de ninguna forma se debe aplicar para números no tan sencillos o muy grandes, una manera es la siguiente:

(*) Llamamos al inverso de 4 en módulo 3 como X:
4 ^ -1 ≡ x (mod 3)

Entonces:
4 * X ≡ 1 (mod 3) , lo que significa:

3 | (4*X – 1)

(*) De esto notamos lo siguiente:

i. (4 * X – 1) es un múltiplo de 3
ii. (4 * X – 1) es un múltiplo de 4 menos 1

Podemos hallar algunos múltiplos de 3 :

{0, 3, 6, 9, 12, 15, …}

(*) Estos números cumplen (i), debemos buscar dentro de estos números un número que cumpla (ii) y vemos que cumplen el 3, el 9, el 15 y más valores, solo necesitamos uno (cualquiera de ellos).

(*) Luego podemos hacer:
4 * X – 1 = 3
X = 1

(*) Recordando que X era el inverso de 4 en módulo 3, podemos decir que:

el inverso de 4 en módulo 3 es 1
(*) Ya que 4 * 1 mod 3 = 1.

Hallar el inverso de 4 es como si halláramos en realidad el inverso de 1 en módulo 3 ya que 4 es congruente con 1 módulo 3, o sea, el inverso de 1 en módulo 3 es 1 también, de hecho el inverso de 1 en cualquier módulo es siempre 1.

Otro ejemplo : Queremos hallar ahora el inverso de 7 en módulo 9, o sea:

7^-1 ≡ X (mod 9)

(*) Procedemos a buscar múltiplos de 9 que cumplan que son múltiplos de 7 menos 1. Algunos múltiplos de 9 son:
{0, 9, 18, 27, 36, 45, 54, 63, 72, …} , de estos números el 27 cumple que es un múltiplo de 7 menos 1 ya que 27 = 28 – 1, entonces podemos hacer:

7 * X – 1 = 27
X = 4

Entonces:
El inverso de 7 en módulo 9 es 4, dicho de otra manera:

7^-1 ≡ 4 (mod 9)
(Ya que 4 * 7 mod 9 = 1)

Esta es una forma sencilla de proceder para calcular el inverso pero es una forma ingenua de resolver cuando los números son grandes, para estos casos son muy útiles otras técnicas como el Algoritmo Extendido de Euclides o aplicar teoremas como el de Euler, si te interesa saber como puedes calcular el inverso para muchos más números te recomiendo leer esta otra publicación.

---

Advertencia: Este post puede contener errores, si encuentra uno puede colocarlo en los comentarios para contribuir a mejorar esta web.
Puede escribir al autor en rogrp6@gmail.com

¡Gracias por visitar este post!