Resultados importantes de la teora de congruencias

Oriana Giraldo Arcia*

15 de octubre de 2014

Resumen

La teora de numeros, es una de las disciplinas mas extensivas y ms elegantes en el campo de las ma-temticas, esta se la debe en parte, a la teora de congruencias, originalmente introducida por Carl FriedrichGauss en su Disquisitiones Arithmeticae y posteriormente desarrollada por las siguientes generaciones dematematicos que le siguieron. Estos nos dieron acceso a un gran abanico de nuevos mundo, de los cuales eneste trabajo nos daremos el derecho de estudiar uno de los mas representativos a lo largo de la historia.

1. INTRODUCCION

En este trabajo se presentaran algunas de las definiciones mas importantes de la teora de congruencias,el cual, es un tema fundamental en la teoria de numeros y resulta indispensable al momento dictar un cursobasico, de dicho tema. Estudiaremos el trabajo de cientos de hombre que a lo largo de casi 300 anos dedicaronsus vidas a desentranar los secretos de una ciencia sin limites, para ello tomaremos como base los resultados deltexto [1], el cual complementaremos con los demas libros.

2. Congruencias lineales

Definicion 1 Fijemos un entero positivo n. Dados a y b enteros, diremos que a es congruente con b modulo n,si n|a b. Denotaremos esto por a b (modn), es decir

a b (modn) si y solo si n|a b

2.1. Propiedades de las congruencias

Fijemos un entero positivo n y sean a, b, c, d Z. Entonces, se tiene:a) a a (modn)b) a b (modn) si y solo si b a (modn)c) Si a b (modn) y b c (modn) entonces a c (modn)d) Si a b (modn) y c d (modn) entonces a + c b + d (modn)e) Si a b (modn) y c d (modn) entonces ac bd (modn)f) Si ac bc (modn) entonces a b (mod nd ) donde d = mcd(c, n)g) (caso particular de f) Si mcd(c, n) = 1, entonces, ac bc (modn) si y solo si a b (modn)

Proposicion 1 Dado un entero positivo n. Todo numero entero a es congruente modulo n con uno y solo unode los numeros del conjunto {0, 1, 2 . . . , n 1}(para ser mas exactos a r (modn) si y solo si a y b tienen elmismo residuo al dividir entre n).En particular a b (modn) si y solo si a y b tienen el mismo residuo al dividir entre n.

*Universidad de Cordoba. Email: orianag40@hotmail.com.

1

Prueba

Sea a Z cualquiera.a = qn+ r donde q Z, y r Z tal que 0 r < n, es decir, r {0, 1, 2 . . . , n 1}, por tanto a r = qn, luegon|a r y esto es a r (modn).De otra parte, supongamos que si a s (modn) con s {0, 1, 2 . . . , n 1}, veamos que s = r.Puesto que a s (modn), entonces n|a s, luego a s = qn, para algun q Z, esto es, a = qn + s, con0 s < n. De la unicidad de residuo se sigue que r = s.

Caso particular

=: a b (modn) implica n|ab. Sean r1 y r2 enteros con 0 r1 < n y 0 r2 < n, tales que a = q1n+r1y b = q2n + r2 con q1, q2 Z . Luego

a b = (q1 q2)n + (r1 r2)r1 r2 = a b (q1 q2)n

Como n|a b, se sigue que n|r1 r2, lo cual solo es posible si r1 r2 = 0, esto es, r1 = r2(ya que si r1 r2 > 0entonces n|r1 r2, lo cual es imposible. As mismo, el resultado es analogo si r1 r2 < 0).

=: Supongamos que a = qn + r y b = qn + r, luegoa b = qn qn + r r

= (q q)nas n|a b, luego por definicion a b (modn)

Proposicion 2 Sean n1, n2, . . . , nr numeros narutales tales que mcd(ni, nj) = 1 si i 6= j. Entonces, para cadapar de enteros a, b se tiene que a b (modn) si y solo si a b (modn1), a b (modn2), . . ., a b (modnr).esto es, a b (modni), i {1, 2, . . . , r}

Teorema 1 Sean a, b, n numeros enteros con n > 0 y a 6= 0 y sean d = mcd(a, n), entonces la congruenciaax b (modn) tiene solucion si y solo si d|b y ademas en este caso hay exactamente d soluciones modulo n.

Prueba

ax b (modn)tiene solucion x Z tal que n|ax b x, y Z tales que b ax = ny ax + ny = b () mcd(a, n) = b

Este teorema nos dice que las soluciones de la ecuacion () dependen de un parametro de la forma X = x0 +nd t

donde t {0, 1, . . . , d 1}Y = y0 +

ad t

x0, y0 es una solucion particular, entonces las soluciones de la congruencia ax b (modn) son los enteros x dela forma x x0

(mod

n

d

), entonces x x0 + tn

d(modn), as tenemos d soluciones modulo n.

Teorema 2 (Teorema chino del residuo) Sean n1, n2, . . . , nr numeros enteros positivos tales que mcd(ni, nj) =1 si i 6= j. Entonces,cualquier sistema de conrguencias

x a1 (modn1)... , ai Z i {0, 1, . . . , r}

x ar (modnr)(1)

tiene solucion unica moludo n = n1n2 . . . nr.

2

Prueba

Para cada i {0, 1, . . . , r} definimos Ni tal queNi =

n1n2 . . . nrni

= n1n2 . . . ni1ni+1 . . . nr

Puesto que mcd(ni, nj) = 1 entonces mcd(ni, Ni) = 1. En particular, mcd(ni, Ni)|ai i {0, 1, . . . , r}Por tanto existe xi Z tal que Nixi ai (modni) para cada i {0, 1, . . . , r}

Afirmacion 1 x0 = N1x1 + N2x2 + . . . Nrxr, es solucion del sistema de congruencias (1).

En efecto, para cada i {0, 1, . . . , r} se tiene que Nj 0 (modni) si i 6= j (ya que ni|Nj si i 6= j). Por tanto

x0 =

rj=1

xj Nixi (modxi) ai (modni)

entonces podemos concluir x0 ai (modni) i {0, 1, . . . , r}

Unicidad

Notemos en primer lugar que si x Ztal que x x0 (modn1n2 . . . nr), entonces x tambien es solucion delsistema (1).

Teorema 3 Sea P(x) un polinomio con coeficientes enteros y sea n1. si a b (modn) entonces p(a) P (b) (modn)

Prueba

Sean

P (x) = a0 + a1x + + akxk con ai ZP (a) = a0 + a1a + + akakP (b) = a0 + a1b + + akbk

como a b (modn) entonces ai bi (modn) i {0, 1, . . . , k}, luego aiai aibi, lo que implica

P (a) =

ki=0

aiai

ki=0

aibi (modn) = P (b) (modn)

Aplicacion: Sea N Z tal que su espresion decimal es N = anan1 . . . a1a0 con 0 a1 9, es decir,N = an10

n + an110n1 + . . . + a1101 + a0100. Si P (x) = anxn + an1xn1 + . . . + a1x1 + a0x0, notemos queN = P (10).

Teorema 4 si P (x) es un polinomio con coeficientes enteros. Si para algun n Z, n > 1, se verifica queP (a) 0 (modn) para todo a Zn (cociente de Z mod n) P (x) no tiene races enteras.

Teorema 5 (Pequeno teorema de Fermat) Sea p un numero primo, entonces para cada a Z no divisible porp, es decir mcd(a, p) = 1, se tiene que ap1 1 (mod p)

Prueba

Puesto que mcd(a, p) = 1, entonces el conjunto {0, a, 2a, . . . , (p 1)a} es un sistema completo de residuos.Por tanto, los numeros a, 2a, 3a, . . . , (p 1)a son congruentes modulo p y en cierto orden con los enteros1, 2, 3, . . . , p 1 (kaj j (mod p) para j {1, 2, 3, . . . , p 1} y kaj {1, 2, 3, . . . , p 1}).Ahora, multiplicando todas estas congruencias obtenemos

(p 1)!ap1 (p 1)! (mod p)como p es primo, entonces mcd((p 1), p) = 1, por tanto, podemos cancelar (p 1)! y as ap1 1 (mod p)

Corolario 1 Si p es primo, entonces se tiene que ap a (mod p),a Z

3

Prueba

Sea a Z, vemos los siguientes casos:Caso 1si p - a, por el pequeno teorema de Fermat se tiene que ap1 1 (mod p), entonces multiplicando por a (pues

mcd(p, a) = 1) resulta que

ap1a 1a (mod p)ap a (mod p)

Caso 2si p|a, entonces p|ap, por tanto a 0 (mod p), y ap 0 (mod p), luego por transitividad ap a (mod p)

3. Numeros pseudoprimos

Definiciones 1 Sea 0 6= a Z.* Un numero entero n se dice pseudoprimo en base a si n es un numero compuesto tal que an a (modn).* Diremos que n es un pseudoprimo si a = 2, es decir, 2n 2 (modn).* Se llama pseudoprimo absoluto o numero de Carmichael a un numero compuesto n tal que an a (modn)

para cualquier n Z.

Proposicion 3 Sea n = p1p2 . . . pr un producto de r numeros primos distintos, con r > 1. Si para cadai {1, 2, . . . , r} se cumple que pi 1|n 1, entonces n es un numero de Carmichael.

Prueba

Claramente n es un numero compuesto, ya que r > 1. Debemos mostrar que an a (modn) para cualquiera Z, esto es, an a (mod pi), i {1, 2, . . . , r}.Veamos los siguientes casos:

Caso 1si pi|a, entonces es claro que an a (mod pi).Caso 2si p - a,, entonces mcd(pi, a) = 1, luego por el pequeno teorema de Fermat, se tiene que api1 1 (mod pi).

Como pi 1|n 1, entonces se sigue lo siguiente

an1 = (api1)k (1)k (mod pi) = 1 (mod pi) i {1, 2, . . . , r}

multiplicando por a: an a (mod pi), i {1, 2, . . . , r}

Teorema 6 (Wilson) p es primo si y solo si (p 1)! 1 (mod p)

Prueba

=: si p = 2 o p = 3 es claro que (p 1)! 1 (mod p).Supongamos que p > 3 para cada a = 1, 2, 3, . . . , p1. Consideremos la congruencia ax 1 (mod p), que tendraexactamente una solucion modulo p ya que el mcd(p, a) = 1, a {1, 2, . . . , p 1}.Sea a la solucion de la congruencia linea, notemos que a {1, 2, . . . , p 1} (a 6= 0 ya que es la solucion de lacongruencia ax 1 (mod p), pues si lo fuera 0 1 (mod p), lo que implica p| 1 y esto es absurdo).Por tanto tenemos una aplicacion biyectiva

{1, 2, . . . , p 1} {1, 2, . . . , p 1}a 7 a

que asocia a cada a el elemento a. Observese que si a = a, entonces a2 1 (mod p), es decir p|a2 1, esto esp|a 1 o p|a + 1. Ahora, como a {1, 2, . . . , p 1}; se sigue que a = p 1 o a = 1, por lo tanto el conjunto{2, 3, . . . , p 1} se descompone en pares {a, a} tales que aa 1 (mod p).Agrupando segun estos pares, el

4

producto de todos los elementos del conjunto {2, 3, . . . , p 1}, se sigue entonces 2 3 4 . . . (p 2) 1 (mod p),por tanto

(p 1)! = (1 2 3 4 . . . (p 2))(p 1) 1 1 (p 1) = (p 1) (mod p) 1 (mod p)

As (p 1)! 1 (mod p).

=: Supongamos (p 1)! 1 (mod p). Supongamos que p es compuesto, es decir, p = ab con a, b Z+,tales que 1 < a < p y 1 < b < p. Por hipotesis tenemos que (p 1)! 1 (mod p), esto es, p|(p 1)! + 1, peroa|p, por tanto a|(p 1)! + 1.Notemos que 1 < a < p 1, entonces a es un factor de (p 1)!, luego a|(p 1)! y a|(p 1)! + 1, lo que implicaque a|1, es decir, a = 1, lo cual es absurdo ya que 1 < a. As p no puede ser compuesto, es decir, p es primo.

Referencias

[1] T. Koshy, Elementary Number Theory with Applications. Second edition, Elsevier. San Diego, California2007.

[2] D. M. Burton, Elementary Number Theory. Allyn and Bacon, Boston, Massachussets 1980.

[3] A. Adler, AND J. E. Coury, The Theory of Numbers. Jones and Bartlett Publishers, London, UK 1995.

5