Tema 6: Aritmetica Modular II
Aritmetica Modular II
Raiz Primitiva
Definicion: Dado un numero natural \(m\), decimos que \(a\) es una raiz primitiva modulo \(m\), si \(a\) genera como grupo a \(\mathbb{Z}^*_m\). Eso es, si para to \(b \in \mathbb{Z}^*_m\), existe \(k\), tal que \(b \equiv a^k \mod(m)\).
Como 7 es primo, todos los elementos de \(\mathbb{Z}_7\) son invertibles, salgo el \([0]\). Por contexto, se entiende \([] = []_7\).
\(\mathbb{Z}^*_m = \{[1], [2], [3], [4], [5], [6]\}\)
- \([1]\) no es raiz primitiva, ya que \([1] \cdot [1] = [1]\)
- \([2]^1 = [2], [2]^2 = [4], [2]^3 = [1], [2]^4 = [2]\). No es raiz primitiva.
- \([3]^1 = [3], [3]^2 = [2], [3]^3 = [6], [3]^4 = [4], [3]^5 = [5], [3]^6 = [1], [3]^7 = [3]\). Es raiz primitiva.
- \([4]^2 = [1]\), no es raiz primitiva.
- \([5]^1 = [5], [5]^2 = [4], [5]^3 = [6], [5]^4 = [2], [5]^5 = [3], [5]^6 = [1], [5]^7 = [5]\). Es raiz primitiva.
- \([6]^2 = [1]\). No es raiz primitiva.
Logaritmo Discreto
Sea \(p\) un numero primo, \(a\) una raiz primitiva y \(b\) un numero entero entre \(1\) y \(p-1\). Entonces llamamos logaritmo discreto de \(b\), modulo \(p\), al exponente \(k \in \{1, \cdots, p - 1\}\), tal que \(a^k = b \mod (p)\).
Por ejemplo: hallar el algoritmo discreto de \(b = 5\) modulo \(p = 11\). Sabiendo que \(2\) es una raiz primitiva modulo 11.
Buscamos \(1 \le k \le 10\) tal que \(2^k \equiv 5 \mod (11)\): \(2^4 = 16, [16] = [5]\)
Congruencias Lineales
En un tratado del siglo IV, Sun Tzu Suan-Ching (Sun Zi Suanjing) escribia el siguiente problema:
Tenemos una coleccion de objetos, pero no sabemos cuantos. Si los contamos de tres en tres, sobran dos; si los contamos de cinco en cinco sobran tres, y si los contamos de siete en siete, sobran dos. Cuantos objetos tenemos?
Este problema se puede escribir en forma de congruencias:
Encontrar \(x \ge 0\) tal que:
\begin{cases} x \equiv 2 \mod (3), \\ x \equiv 3 \mod (5), \\ x \equiv 2 \mod (7), \\ \end{cases}
En general, podemos considerar problemas mas generales:
\begin{cases} x \equiv a_1 \mod(m_1) &\quad \\ \quad \vdots &\quad \\ x \equiv a_n \mod(m_n) \end{cases}
Antes de resolver sistemas, consideramos ecuaciones lineales:
\(ax \equiv b \mod(m)\)
Podemos calcular \([a]^{-1}\) (si existe) y resolverla:
\(x \equiv a^{-1} \cdot b \mod(m)\)
Vlvamos al caso chino de los sistemas:
\begin{cases} x \equiv a_1 \mod(m_1) &\quad \\ \quad \vdots &\quad \\ x \equiv a_n \mod(m_n) \end{cases}
El Teorema Chino del Resto afirma que el sistema tiene una unica solucion \(0 \le x < m\), con \(m = m_1 \cdot m_2 \cdot \cdots \cdot m_n\), si \(m_1, m_, \cdots, m_n\) son primos relativos.
La solucion viene dada por la siguiente formula:
\(x = a_1 \cdot q_1 \cdot r_1 + a_2 \cdot q_2 \cdot r_2 + \cdots + a_n \cdot q_n \cdot r_n \mod(m)\)
Las cantidades \(q_i\) y \(r_i\) vienen dadas por:
\(q_i = \frac{m}{m_i}\) \(r_i = [q_i]^{-1}_{m_i}\)
Podemos resolver la congruencia calculando:
- \(m_i\)
- \(q_i\)
- \(r_i\)
- Haciendo la suma y tomando el modulo.
