Congruencias

Congruencias y polinomios
Mario Pineda Ruelas
Departamento de Matematicas,
Universidad Autonoma Metropolitana-Iztapalapa
correo electronico: mpr@xanum.uam.mx
Gabriel D. Villa Salvador
Departamento de Control Automatico,
Centro de Investigacion y de Estudios Avanzados, IPN
correo electronico gvilla@ctrl.cinvestav.mx
1 Zm
Uno de los conceptos fundamentales en teora de numeros esel de congruencia.
Historicamente las congruencias fueron estudiadas primeramente por Fermat,
Euler, Lagrange y Legendre. Gauss, en su famosa obra Disquisitiones Arith-
metic, es el primer matematico que hace un estudio coherente y sistematico
del tema.
Muchos problemas teorico-practico pueden simplicarse estudiando el residuo
que deja cada entero al ser dividido por un entero jo. Deesta forma, podemos
pensar que la teora de las congruencias es una herramienta poderosa que
nos ayuda a resolver problemas por medio del estudio de residuos. Por ejemplo,
sabemos que el cuadrado de cualquier entero deja residuo 0 o 1 al ser
dividido entre 4. Si queremos averiguar si el numero 505395 es un cuadrado,
entonces un buen indicio es conocer su residuo al ser dividido entre 4.Puesto
que 505395 = 4(126348) + 3, entonces 505395 no es un cuadrado. Si el residuo
hubiera sido 0 o 1, entonces no necesariamente se trata de un cuadrado, simplemente
el numero es un sospechoso de ser un cuadrado.
Sea n cualquier entero diferente de 0. Denimos en Z la siguiente relacion:
a  b si y solo si n j a 􀀀 b. Si los enteros a; b estan relacionados diremos que a
es congruentecon b modulo n y escribiremos a  b (mod n). Es facil vericar
que  satisface:
1. a  a (mod n).
2. Si a  b (mod n), entonces b  a (mod n).
3. Si a  b (mod n) y b  c (mod n), entonces a  c (mod n).
1
De lo anterior se sigue que  es una relacion de equivalencia. Fue Gauss1 el
primero en introducir este concepto as como la notacion.
De la denicion de congruencia se siguefacilmente el siguiente resultado:
Teorema 1.1. Sean a; b; c; d;m; n 2 Z con n 6= 0.
1. Si a  b (mod n) y c  d (mod n), entonces a + c  b + d (mod n).
2. Si a  b (mod n) y c  d (mod n), entonces ax + cy  bx + dy (mod n),
para todo x; y 2 Z.
3. Si a  b (mod n) y c  d (mod n), entonces ac  bd (mod n). En
particular am  bm (mod n) para todo m 2 N.
4. Si d j n y a  b (mod n), entonces a b (mod d).
5. Si f(x) 2 Z[x] y a  b (mod n), entonces f(a)  f(b) (mod n).
Demostracion: Es un ejercicio facil para el lector.

Notemos que por el algoritmo de la division el entero a tiene la forma a =
nq + r donde 0  r < jnj, as que a  r (mod n). En general, dos enteros son
congruentes modulo n si y solo si dejan el mismo residuo al ser divididos por n.
El Teorema 1.1 nos diceque las congruencias se gobiernan casi con las mismas
leyes que una igualdad. En este sentido, el smbolo  es como el smbolo =; los
dos se gobiernan casi bajo las mismas leyes aritmeticas. El siguiente resultado,
es un criterio de cancelacion para el producto bajo el smbolo .
Teorema 1.2. ax  ay (mod m) si y solo si x  y (mod m
mcd(a;m)
):
Demostracion: Si ax  ay (mod m),entonces m j a(x 􀀀 y) y a(x 􀀀 y) = mt,
para algun t 2 Z. Si g = mcd(a;m) tenemos
a
g
(x 􀀀 y) = m
g
t;
y por tanto
1Karl-Friedrich Gauss nace en Gotinga, Alemania el 30 de abril de 1777. Hijo de padres
humildes, ingresa a la Universidad de Gotinga en 1795 recibiendo el apoyo economico del
duque Carlos Guillermo. El 30 de marzo de 1796 obtiene, a partir de ecuaciones ciclotomicas,
laconstruccion del polgono regular de 17 lados usando solo regla y compas. Es en este momento
cuando se decide a ser matematico. En 1798 recibe su doctorado en la Universidad
de Helmsted bajo la direccion del profesor Johann Friedrich Pfa. En 1801 publica su gran
tratado Disquisitiones Aritmetic, en el que presenta un resumen de trabajos de sus predecesores,
formula conceptos y cuestiones...