Congruencias y los campos \(\mathbb{Z}/p\)

Los problemas de esta lista no son para entregar.

Sea \(n\) un número entero. Decimos que \(a\) y \(b\) son congruentes módulo \(n\) si \(a-b\) es múltiplo de \(n\). En ese caso escribimos \(a \equiv b \pmod{n}\).

Recuerda que cualquier entero \(a\) se puede dividir por \(n\), es decir, existen enteros \(q\) y \(r\) únicos tales que \(a=nq+r\) y \(0 \le r < n\) —suponiendo que \(n\) es positivo, para fijar ideas. El número \(r\) se llama el residuo de \(a\) módulo \(n\).

1. Demuestra que \(a \equiv b \pmod{n}\) si y solo si \(a\) y \(b\) tienen el mismo residuo módulo \(n\).
2. Demuestra que la congruencia módulo \(n\) es una relación de equivalencia, es decir, que:
   • \(a \equiv a \pmod{n}\);
   • si \(a \equiv b \pmod{n}\), entonces \(b \equiv a \pmod{n}\);
   • y si \(a \equiv b \pmod{n}\), \(b \equiv c \pmod{n}\), entonces \(a \equiv c \pmod{n}\).
3. Demuestra que «la suma, resta y multiplicación respetan las congruencias módulo \(n\)», es decir, que si \(a \equiv b \pmod{n}\) y \(c \equiv d \pmod{n}\) entonces tenemos que \(a+c \equiv b+d \pmod{n}\), \(a-c \equiv b-d \pmod{n}\), y \(ac \equiv bd \pmod{n}\).

Esto último implica que, por ejemplo, si \(a_i \equiv b_i\), entonces \(a_1^3 + 4a_1 a_2 - 7a_2 a_3^2 \equiv b_1^3 + 4b_1 b_2 - 7b_2 b_3^2\) y así para cualquier expresión polinomial.

4. Encuentra las soluciones de las congruencias siguientes:
   • \(2x+3 \equiv 0 \pmod{7}\). Sugerencia: multiplica ambos lados por 4. Nota que todas las soluciones son congruentes entre sí módulo 7.
   • \(2x+3 \equiv 0 \pmod{8}\).
   • \(2x+4 \equiv 0 \pmod{8}\). ¿Todas las soluciones son congruentes entre sí módulo 8?

Resolver esas ecuaciones debería darte la intuición de que al «trabajar módulo \(n\)», la igualdad de números enteros no es tan importante, que importa más la congruencia módulo \(n\). Por eso definimos las clases de congruencia que podemos usar como si fueran números:

La clase de congruencia de \(a\) módulo \(n\) es por definición el conjunto de enteros \(\{a' : a \equiv a' \pmod{n}\} = \{a + qn : q \in \mathbb{Z}\}\). Lo denotaremos \(a + n\mathbb{Z}\), o, para abreviar, \([a]\), dejando implícita la \(n\).

Definimos \(\mathbb{Z}/n\) como el conjunto de estas clases, o sea, \(\mathbb{Z}/n = \{[a] : a \in \mathbb{Z}\}\).

5. Prueba que esos dos conjuntos en la definición de \(a + n \mathbb{Z}\) realmente son iguales.
6. ¿Cuántos elementos tiene \(\mathbb{Z}/n\)?
7. Muestra que las clases de congruencia módulo \(n\) forman una partición de \(\mathbb{Z}\), es decir, que:
   • dadas dos clases de congruencia \([a]\) y \([b]\), o bien \([a]=[b]\), o bien \([a] \cap [b] = \emptyset\) (¿cuándo ocurre cada caso?);
   • y la unión de todas las clases es \(\mathbb{Z}\).

El ejercicio en el que probaste que la suma, resta y multiplicación respetan las congruencias módulo \(n\) se puede interpretar como que esas operaciones están bien definidas en \(\mathbb{Z}/n\). Entonces definimos \([a] + [b] := [a+b]\), \([a] - [b] := [a-b]\) y \([a][b] := [ab]\) y obtenemos así auténticas operaciones binarias en el conjunto \(\mathbb{Z}/n\).

8. Enuncia con cuidado que quiere decir que «\([a]+[b]:=[a+b]\) está bien definida» y asegúrate que entiendas porque es consecuencia directa de que la suma respeta congruencias.
9. La operaciones de suma, resta y multiplicación heredan de los enteros las propiedades usuales: la suma y la multiplicación son asociativas, tienen elemento neutro, para la suma hay inversos aditivos, la multiplicación distribuye sobre la suma. Aségurate de entender por qué.
10. ¿Cuáles clases en \(\mathbb{Z}/5\) tienen inverso multiplicativo? ¿Cuáles clases en \(\mathbb{Z}/6\) tienen inverso multiplicativo?

Recuerda que dados dos enteros \(m\) y \(n\), siempre es posible encontrar enteros \(x\) y \(y\) tales que \(mx+ny\) sea el máximo común divisor de \(m\) y \(n\). Esto se conoce como el teorema de Bezout para el mcd.

11. Usando el teorema de Bezout para el mcd, prueba que si \(p\) es primo, todas las clases de congruencia módulo \(p\), excepto por \([0]\), tienen inverso multiplicativo. Concluye que cuando \(p\) es primo, \(\mathbb{Z}/p\) es un campo.
12. Más generalmente, prueba que \([a]\) tiene inverso multiplicativo módulo \(n\) si y solo si \(\mathrm{mcd}(a,n)=1\). (Lógicamente conviene hacer este ejercicio antes que el anterior, pero nos importa más el resultado del anterior).

Recuerda que la división se define como multiplicar por el inverso multiplicativo, más precisamente, si \([b][x]=[1]\), definimos \([a]/[b] = [a][x] = [ax]\).

13. Prueba que \([2]^{-1} + [3]^{-1} + [6]^{-1} = [1]\) módulo cualquier \(n\) tal que \(\mathrm{mcd}(n,6) = 1\).
14. Prueba que un polimonio de grado \(n\) tiene a lo más \(n\) raíces en \(\mathbb{Z}/p\). Da un ejemplo de un polinomio cuadrático con más de dos ráices en \(\mathbb{Z}/8\).