Conceptos Fundamentales de Aritmética Modular
Clasificado en Matemáticas
Escrito el en 
español con un tamaño de 5,53 KB
Congruencias y Divisibilidad
Proposición 2
Sean a y b dos números naturales. Entonces **a es congruente a b módulo m** si ambos dan el mismo **resto** al dividirlos por m.
Demostración
Si a = q₁m + r y b = q₂m + r, entonces a - b = (q₁ - q₂)m, así a 
b (mod m).
Recíprocamente, si a
b (mod m), entonces a = b + km. Si b = qm + r, se sigue que a = qm + r + km = (q + k)m + r y ambos dan el mismo resto al dividirlos por m.
Lema 1
Sea x un entero positivo. 9 divide a x si y solo si 9 divide a la **suma de las cifras** de x.
Demostración
Observamos que 10r
1 (mod 9) para todo r > 0.
Entonces
x = xn10n + xn-110n-1 + ... + x₂10² + x₁10 + x₀
xn + xn-1 + ... + x₂ + x₁ + x₀
Proposición 3
La ecuación ax
1 (mod m) tiene solución si y solo si **a y m son primos relativos**.
Demostración
La ecuación es equivalente a ax = 1 + km, o ax - km = 1, y aplicamos la Proposición 2 de la lección 7.
2 Clases de Restos
La relación de **congruencia módulo m** es una **relación de equivalencia**. Sus clases de equivalencia son las **clases de restos módulo m**, las denotamos [a].
Entonces el **conjunto cociente** lo denotamos
Z/mZ = {[0], [1],...,[m-1]}
En este conjunto cociente se pueden definir las operaciones suma y producto:
- [a] + [b] = [a + b]
- [a] ⋅ [b] = [ab]
Supongamos que [a] = [a'] y [b] = [b'], entonces a
a' y b
b' (mod m). Se sigue que a + b
a' + b', i.e. [a + b] = [a' + b'].
Análogamente para el producto.
El conjunto Z/mZ se denomina el **anillo de enteros módulo m**.
Definición 2
Un elemento [u] de un anillo se dice que es una **unidad** si existe un elemento [v] tal que [u][v] = [v][u] = [1]. A [v] se le denomina el **inverso** de [u] y se denota [u]⁻¹.
Teorema 2
En Z/mZ, [a] es una unidad si y solo si **a y m son primos relativos**.
Demostración
[ab] = [1] es equivalente a ab 
1 (mod m).
Corolario 1
El número de **unidades** de Z/mZ es igual al número de enteros x, 1 ≤ x ≤ a que son **primos relativos con m**.
El número de enteros x, 1
x %IMAGE_11% a que son **primos relativos con m** se denota **φ(x)**, la **función fi de Euler**.
Corolario 2
Si p es primo, todos los elementos no cero de Z/pZ son **unidades**, i.e. es un **cuerpo**.
En particular φ(p) = p - 1.
No es difícil ver que φ(pr) = pr - pr-1.