ÁLGEBRA

ARITMÉTICA MODULAR

grado de congruencia de un polinomio congruente con 0 respecto al módulo m es un número entero tal como se precisa:

1. Sea ${\displaystyle f(x)_{}^{}=}$ ${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x^{1}+a_{0}x^{0},}$. Si a_n no es congruente con 0 respecto del módulo m, el grado de la congruencia f(x)≡ 0 (mod m) es n.
2. Si a_n ≡ 0 (mod), sea j el mayor entero positivo tal que a_j no es congruente con cero respecto del módulo m; entonces el grado de la congruencia es j.
3. Si no hay dicho entero j, esto es, si todos los coeficientes de f(x) son múltiplos de m, no se asigna grado a la congruencia.¹​

Debe advertirse que el grado de congruencia de f(x)≡ 0 (mod m) no es lo mismo que el grado del polinomio f(x). El grado de la congruencia depende del módulo; el grado del polinomio es independiente del módulo.

Ejemplos[editar]

1. g(x)= 6x³ + 3x² + 1, entonces g(x) ≡ 0 (mod 5) es de grado 3 y g(x) ≡ 0 (mod 2) es de grado 2; por su parte g(x), como polinomio en x, es de grado 3.
2. Sea h(x) = 6x³ + 3x² + 9, entonces h(x)≡ 0 (mod 3) no tiene ningún grado como congruencia respecto al módulo 3, pues, todos sus coeficientes son múltiplos de 3.

Congruencias en Z módulo m. La aritmética en Z_m

La relación de congruencia

Definición de congruencia

Dado m ∈ Z , m> 1, se dice que a, b ∈ Z son congruentes módulo m si y sólo si m|(a-b). Se denota esta relación como a ≡ b (mod m). m es el módulo de la congruencia.

Es importante darse cuenta de que si m divide a a-b, esto supone que ambos a y b tienen el mismo resto al ser divididos por el módulo m.

Ejemplos: 23≡2 mod 7 (porque 23=3.7 + 2), y -6≡1 mod 7 (porque -6= -7.1 +1)

La relación de congruencia como equivalencia. El conjunto de residuos.

La relación de congruencia módulo m es una relación de equivalencia para todo m ∈ Z. Es decir, cumple las propiedades reflexiva, simétrica y transitiva. Como en toda relación de equivalencia, podemos definir el conjunto cociente de las clases de equivalencia originadas por la relación de congruencia. En este caso la relación clasifica a cualquier entero a según el resto obtenido al dividirlo por el módulo m.

Llamaremos Z_m al conjunto cociente de Z respecto de la relación de congruencia módulo m. A la clase de equivalencia de un elemento a ∈ Z se la denota por [a]_m o simplemente [a].

Para todo a∈Z se tiene que [a] = [r] en Z_m, donde r es el resto de dividir a entre m.Por lo tanto, el conjunto Z_m es finito y tiene melementos: Z_m = { [0]_m, [1]_m, ... , [m-1]_m}, donde la clase [i]_m representa al conjunto de todos los enteros que son congruentes con imod m. A este conjunto cociente se le conoce como el conjunto de restos o residuos (módulo m)

Ejemplo: siguiendo con el ejemplo anterior, está claro que en Z₇, el número entero 9, el 16 y el 23 pertenecen todos a la clase [2], y que el entero -6, el 1 y el 8 pertenecen a la clase [1]

Compatibilidad de la relación de congruencia con la suma y el producto

Sean m ∈ N y a, b, c, d ∈ Z tales que a ≡ b (mod m) y c ≡ d (mod m). Entonces se cumple que:

1. a + c ≡ b + d (mod m)
2. a . c ≡ b . d (mod m)

Consecuentemente, el resto de la suma es congruente con la suma de restos, y el resto del producto es congruente con el producto de restos. Además podremos sumar y multiplicar clases de equivalencia (residuos) porque es indiferente el representante que se elija de cada clase a la hora de operar: el resultante de la operación siempre será un representante de la misma clase resultado.

Vamos ahora a definir la aritmética módulo m o aritmética en Z_m:

---

Aritmética en Z_m

Definición

En Z_m podemos definir dos operaciones binarias internas:

+ , . : Z_m x Z_m⇒ Z_m

que llamamos suma y producto, y están definidas de la siguiente manera, para cualesquiera a, b ∈ Z:

1. [a] + [b] = [a+b]
2. [a] . [b] = [a.b]

Propiedades

1. Son operaciones cerradas, conmutativas y asociativas
2. Cumplen la propiedad distributiva
3. Tienen elemento neutro. [0] es el elemento neutro para ( Z_m , + ) y [1] es el elemento neutro para ( Z_m , . )
4. En el caso de ( Z_m , + ) existe el elemento opuesto: -[a] = [-a]
5. Propiedad cancelativa para ( Z_m , . ) : si [a].[c] = [b].[c] en Z_m, entonces [a] = [b] en Z_{(m/mcd (m,c))}
   • Un caso especial es cuando mcd (m,c)=1 , ya que entonces se cumple la propiedad cancelativa para el producto en Z_m: si [a][c] = [b][c] en Z_m ⇒ [a] = [b] en Z_m
   • Si m es primo, (Z_m, .) tendrá la propiedad cancelativa del producto para todo c

Elementos invertibles o unidades de Z_m

Se dice que [a] es invertible en Z_m si existe un [b] en Z_m tal que [a][b]=[1]. Ese elemento [b] será el inverso de [a] en Z_m, y se denota como [a]^-1.

Proposición:

• [a] es invertible en Z_m ,si y sólo si
• existe [b] ∈ Z_m tal que [a][b] = [1] en Z_m ,si y sólo si
• existen b, k ∈ Z tales que ab + km = 1 ,si y sólo si
• mcd(a,m)= 1

Si [a] es invertible puede por tanto calcularse su inverso [a]^-1 mediante el algoritmo de Euclides. Además se puede asegurar que si existe el inverso de un elemento en módulo m, es único.

Por ejemplo, en Z₁₂ sólo 1, 5, 7 y 11 son primos relativos al módulo 12, por lo tanto sólo [1], [5], [7] y [11] son los enteros que tienen inverso en aritmética módulo 12. Si queremos, por ejemplo, hallar el inverso del [5], tenemos que mediante Euclides:

12= 5.2 + 2

5= 2.2 + 1

2= 1.2

Luego recorriendo el camino inverso:

1= 5 - 2.2 = 5 - 2(12 - 5.2)= 5 - (2.12 - 5.4)= 5.5 -2.12 ⇒ [5] es el inverso módulo 12 de [5].

http://www.dma.fi.upm.es

hipótesis china afirma que si, y solo si, p es primo, entonces ${\displaystyle 2^{p}\equiv 2{\pmod {p}}}$, pero aunque todos los números primos la cumplen, no se cumple de manera general, o sea, si un número n cumple que ${\displaystyle 2^{n}\equiv 2{\pmod {n}}}$, no es necesariamente primo, con lo cual la hipótesis china es incorrecta. El menor contraejemplo que cumple la condición es n = 341 = 11×31. Estos números corresponden a una clase especial de pseudoprimos.