Dos números \( a, b \in \mathbb{Z} \) se dice que son congruentes módulo p si
$$a\;-\;b = n·p, n \in \mathbb{Z} . $$
En otras palabras: a y b son congruentes si su diferencia es multiplo de m.
Cuando a es congruente b módulo p se denota de varias maneras
$$ a \equiv b\; (p) $$
También
$$ a \equiv_{p} b $$
Ejemplos
- Tomamos p = 9, a = 3, b = 8 entonces $$a\;-\;b = 3\;-\;8 =\;-5\equiv 4\;(9) $$ asi, 3 no es congruente con 8 modulo 9.
- \(13 \equiv 4 \;(9)\) porque \(13\;-\;4 = 9 \).
Concruencias y clases de equivalencia
Las congruencias proporcionan una relación de equivalencia, de este modo el conjunto original sobre el que opera la congruencia puede ser dividido en clases de equivalencia. Las definimos como sigue:
$$ \mathbb{Z}_{p} = \frac{\mathbb{Z}}{\equiv_{p}} . $$
Por ejemplo, el conjunto \(\mathbb{Z} \) con p=3, el número 19 pertenece a la clase de equivalencia \( \{ \bar{1}\} \) sobre el conjunto de clases \( \mathbb{Z}_{3}\), esto es debido a que
$$ 19\;-\;1 = 18 = 6 · 3 \equiv 0 \;(3) $$
Otro ejemplo, tomamos p = 9,
$$ \mathbb{Z}_{9} = \{ \bar{0},\bar{1},\bar{2},\bar{3},\bar{4},\bar{5},\bar{6},\bar{7},\bar{8} \} $$
por ejemplo la clase \({\bar{2}}\) está formada por todos aquellos números tales que cuando lo dividimos por 9 sale como resto 2, es decir el conjunto de números \(\{ 2, 11, 20, …\} \).
En general \( \mathbb{Z}_{p} = \{ \bar{0},\bar{1},\bar{2}, …\bar{p-1} \} \).
Congruencias y las grandes estructuras
Congruencias y teoría de grupos
Lo que hace interesante las congruencias es que \(\mathbb{Z}_{n}\) dotado de la operación ‘+’, suma, tiene estructura de grupo y la denotamos por
$$ (\mathbb{Z}_{n}, +) $$
Ejemplo, el grupo \( (\mathbb{Z}_{3}, +) \)
| + | 0 | 1 | 2 |
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 0 |
| 2 | 2 | 0 | 1 |
Congruencias y anillos
Otro uso importante de las congruencias que que \(\mathbb{Z}_{n}\) dotado de las operaciones suma ‘+’ y muliplicación ‘·’ tiene estructura de anillo. Este anillo se denota por
$$ (\mathbb{Z}_{n}, +, ·) $$
Un caso de especial importancia es cuando n=p, un número primo. En este caso todo elemento no nulo de \(\mathbb{Z}_{p}\) tiene inverso para la operación producto. En este caso el anillo es en particular un cuerpo.
El pequeño teorema de Fermat es importante en test de primalidad, en particular nos da una condición necesaria para que un número dado sea primo.
Sea p un número primo y sea \(a \in \mathbb{Z} \) tal que p no divide a a. Entonces
$$a^{p-1} \equiv 1 (p) $$
El Teorema de Fermat es en realidad corolario de un teorema mas general:
Sea n un número natural y sea \(a \in \mathbb{Z} \) tal que n y a son primos entre sí. Entonces
$$a^{\varphi (n)} \equiv 1 (n) $$
El pequeño teorema de Fermat es, como hemos dicho usado en test de primalidad, el teorema es una condición necesaria pero no suficiente. Todo número primo verifica el pequeño teorema de Fermat, sin embargo el recíproco no es cierto, si un número verifica el pequeño teorema de Fermat no necesariamente es primo. Este es el caso de números pseudoprimos o números de Charmichael, es decir aquellos números no primos que verifican el pequeño teorema de Fermat.
Ejemplo
El caso del número 561.
561 = 3 x 11 x 17, entonces queremos demostrar que
$$a^{560} \equiv 1 (561) $$
para todo número a primo relativo con 561.
como \( m.c.d(a, 561) = 1\), entonces \(m.c.d(a, 3) = m.c.d(a, 11) = m.c.d(a, 17) = 1\).
Entonces, debido al pequeño teorema de Fermat
$$ a^{2} \equiv 1 (3) $$ $$ a^{10} \equiv 1 (11) $$ $$ a^{16} \equiv 1 (17) $$
Entonces podemos hacer lo siguiente
$$a^{560} \equiv (a^{2})^{280} \equiv 1 (3) $$ $$a^{560} \equiv (a^{10})^{56} \equiv 1 (11) $$ $$a^{560} \equiv (a^{16})^{35} \equiv 1 (17) $$
Por tanto
$$a^{560} \equiv 1 (561)$$
Por tanto 561 es un número pseudoprimo o de Carmichael.
Ejemplo
El caso del número 91.
$$a^{90} \equiv 1 (91) $$, Se tiene que 91 = 7 x 13.
como m.c.d(a, 91) = 1, entonces m.c.d(a, 7) = m.c.d(a, 13) = 1.
para todo número a primo relativo con 91.
Por el teorema de fermat, tenemos que:
$$a^{6} \equiv 1 (7) $$ $$a^{12} \equiv 1 (13) $$
Entonces
$$a^{90} \equiv 1 (91) $$
Por tanto 91 también verifica el pequeño teorema de Fermat a pesar de no ser primo.
El pequeño teorema de Fermat suele usarse también para cálculos de números grandes, como vemos en el siguiente ejemplo
Ejemplo
Calcular .
$$246^{218} \equiv x (11) $$
Lo primero es notar que 246=22 x 11 + 4.
$$246^{218} \equiv x (11) \equiv (2^{2})^{218} \equiv 16^{109} \equiv 5^{109} (11)$$
Usando que 109 = 9 x 11 + 10, obtenemos, usando el pequeño teorema de Fermat
$$ 5^{109} = 5^{9.11+10} = 5^{9.11}$$ .
así, usando de nuevo el pequeño teorema de Fermat:
$$ (5^{11})^{9} = 5^{9} (11)$$ .
De nuevo aplicando el pequeño teorema de Fermat
$$ 5^{9} (11) = 5^{-1} (11)$$ .
Así todo nuestro problema consiste en hallar el inverso de 5 en \( \mathbb{Z}_{11} \)
Haciendo los cálculos vemos que es 9, así concluimos que
$$246^{218} \equiv 9 (11) $$
Sé el primero en comentar