1. Aritmetica modular

La aritmética modular es un sistema aritmético donde los números “se envuelven” al alcanzar un cierto valor, llamado módulo . Es decir, en lugar de trabajar con números infinitos, trabajamos con números dentro de un rango finito definido por el módulo $n$ .

Definición formal

Decimos que dos números enteros $a$ y $b$ son congruentes módulo $n$ si su diferencia $a−b$ es divisible por $n$. Esto se denota como:

$$a≡b \ ( \ mod \ n)$$

Esto significa que $a$ y $b$ tienen el mismo residuo cuando se dividen entre $n$.

Ejemplo :
Verificar si $17≡5 \ ( \ mod \ 6)$:

• Dividimos $17$ y $5$ entre $6$:
  • $17÷6=2$ con residuo $5$.
  • $5÷6=0$ con residuo $5$.

Ambos tienen el mismo residuo ($5$), por lo tanto:$17≡5 \ ( \ mod \ 6)$

1.2 Operaciones básicas en aritmética modular

En aritmética modular, las operaciones básicas (suma, resta, multiplicación) se realizan como en aritmética normal, pero el resultado se reduce módulo n.

• Suma modular:

  $$(a+b) \ mod \ n=[(a \ mod \ n) + (b \ mod \ n)] \ mod \ n$$

  Por ejemplo: $(15+23) \ mod \ 7$

  $15 \ mod \ 7=1$, $23 \ mod \ 7=2$

  $(1+2) \ mod \ 7=3$

  Resultado: $3$

• Resta modular:

  $$(a−b) \ mod \ n=[(a \ mod \ n) − (b \ mod \ n)] \ mod \ n$$

  Por ejemplo: $(18-9) \ mod \ 7$

  $18 \ mod \ 7=4$, $9 \ mod \ 7=2$

  $(4-2) \ mod \ 7=2$

  Resultado: $2$

• Multiplicación modular:

  $$(a⋅b) \ mod \ n=[(a \ mod \ n) ⋅ (b \ mod \ n)] \ mod \ n$$

  Por ejemplo: $(5⋅6) \ mod \ 7$

  $5 \ mod \ 7=5$, $6 \ mod \ 7=6$

  $(5⋅6) \ mod \ 7=30 \ mod \ 7 = 2$

  Resultado: $2$

2. Máximo Común Divisor (MCD)

El máximo común divisor ($MCD$) de dos números enteros $a$ y $b$ es el mayor número entero positivo que divide exactamente a ambos números.

Propiedades importantes :

1. Si $MCD(a,b)=d$, entonces existen enteros $x$ e $y$ tales que: $$d=ax+by$$ (Esta propiedad es clave en el algoritmo de Euclides extendido).
2. Si $MCD(a,b)=1$, decimos que $a$ y $b$ son coprimos .

2.1 Algoritmo de Euclides

El algoritmo de Euclides es un método eficiente para calcular el $MCD$ de dos números. Se basa en la siguiente propiedad:

$$MCD(a,b)=MCD(b,a \ mod \ b)$$

Este proceso se repite hasta que el segundo número sea $0$. En ese caso, el primer número será el $MCD$.

Pasos del algoritmo :

• Divide a entre $b$ y obtén el residuo $r$ ($r=amodb$).
• Reemplaza $a$ por $b$ y $b$ por $r$.
• Repite hasta que $b=0$. El $MCD$ será el último valor no nulo de $a$.

Ejemplo : Calcular $MCD(48,18)$

• $48÷18=2$ con residuo $12$ ($48 \ mod \ 18=12$).
• $18÷12=1$ con residuo $6$ ($18 \ mod \ 12=6$).
• $12÷6=2$ con residuo $0$ ($12 \ mod \ 6=0$).
• Como el residuo es $0$, el $MCD$ es $6$.

Resultado :

$$MCD(48,18)=6$$

3. ¿Como se Relaciona la Aritmetica Modular y el MCD?

El MCD tiene aplicaciones directas en aritmética modular, especialmente en la resolución de ecuaciones modulares y en el cálculo de inversos modulares.

Inverso modular :
Un número $x$ es el inverso modular de $a$ módulo $n$ si:

$$a⋅x≡1(mod \ n)$$

Para que exista un inverso modular, $a$ y $n$ deben ser coprimos ($MCD(a,n)=1$).

Ejemplo : Encontrar el inverso modular de $5$ módulo $7$

• Verificamos que $MCD(5,7)=1$ (son coprimos).
• Usamos el algoritmo de Euclides extendido para encontrar $x$ tal que: $5⋅x≡1(mod \ 7)$
• Solución: $x=3$, ya que: $5⋅3=15≡1(mod \ 7)$