congruencias-grupos

7/26/2019 congruencias-grupos

1/26

Captulo VI

Congruencias, Zn y Zn, Etc.

En este captulo se estudian congruencias modulo un entero positivo, y los siste-mas de numeros Zny Z

n. Ademas del teorema chino del residuo, encontramos

de nuevo los teoremas de Fermat, Euler y Wilson. Al final, se dan los primerospasos en el estudio de teora de numeros en el contexto mas general de grupos.

VI.1. Congruencias

Definicion. Sea n un entero positivo. Dos enteros a, b se dicen congruentesmodulo n, simbolizado por

a b (mod n),

si ndividea b, o equivalentemente si existe un entero ktal que a b= kn.

Cuando sea conveniente, escribimos mas brevemente

anb.

Ejemplo: 8 0 (mod 2), 3 24 (mod 7), 11 31 (mod 7), 13 69(mod 14).

Dado un entero positivo n y un entero a, de acuerdo con el algoritmo de ladivision, existen enteros q, r unicos con0 r < ny

a= qn +r;

lo que quiere decir que cualquier entero es congruente a uno de los posiblesresiduos modulo n. De hecho, a y b son congruentes si y solo si tienen elmismo residuo modulo n(de acuerdo con el siguiente teorema).

Teorema 1 Paran, a, b Z, n > 0, las siguientes afirmaciones son equiva-lentes:

1


2/26

2 CAPITULO VI. CONGRUENCIAS, ZNYZN, ETC.

(i) a b (mod n)

(ii) existek Z tal quea= b +kn

(iii) a mod n= b mod n

Prueba. La equivalencia de (i) y (ii) es inmediata de la definicion. Veamos laequivalencia de (ii) y (iii):

() Supongamos que a = b+kn, y sea r = a mod n, es decir, 0 r < ny existe q tal que a = qn+ r. Entonces b+ kn = qn+ r y de aqu queb= (qk)n+r. Esto es b mod n= r = a mod n.

() Ahora supongamos quer = a mod n= b mod n. Entonces por definicion,existenq, q tal quea = qn + ry b = q n + r. De aqu quea b= (q q )ny a= b +kn con k= q q .

Las propiedades en el siguiente teorema son fundamentales.

Teorema 2 Sean, a, b, c, d Z, n > 0. Entonces

(i) a a (mod n)

(ii) sia b (mod n) entoncesb a (mod n)

(iii) sia b (mod n) yb c (mod n) entoncesa c (mod n)

(iv) sia b (mod n) yc d (mod n) entoncesa+c b +d (mod n)

(v) sia b (mod n) yc d (mod n) entoncesac bd (mod n)

(vi) sia b (mod n) entoncesa+c b +c (mod n) yac bc (mod n)

(vii) sia b (mod n) entoncesak bk (mod n) parak 0.

Todas las afirmaciones son de muy facil verificacion. Solo indicamos la verifi-cacion de (v): a b y c d implican que n | a by n | c d. Por lo tanto ndivide (ab)(cd) lo que podemos reescribir como

acbcad+bd= acbd+bdbcad+bd= (acbd)b(cd)(ab)d.

Por lo tanto, ndivide acbd, es decir ac bd.

De acuerdo con (i-iii), congruencia modulon es una relacion de equivalencia.La clase de a Z se denota como ao [a]. As

[a] ={b Z: a b (mod n)}= {a+kn : k Z}.


3/26

VI.1. CONGRUENCIAS 3

Si es importante hacer el modulo explcito, escribimos [a]n. Las propiedades(iv-v) nos permiten definir operaciones de suma y producto entre estas clasespor medio de

[a]n+n[b]ndef= [a+b]n

[a]n n[b]ndef= [a b]n

En adelante omitimos el subndice en +ny n. Estas definiciones no dependendel representante de la clase: si a a (mod n) y b b (mod n) entonces

[a] + [b] def= [a+b]

teo(iv)= [a +b ]

def= [a ] + [b ]

y similarmente para el producto. Ademas, estas operaciones heredan las pro-piedades de las respectivas operaciones en Z. Por ejemplo, la asociatividad dela suma:

([a]+[b])+[c] = [a+b]+[c] = [(a+b)+c]asoc

en Z= [a+(b+c)] = [a]+[b+c] = [a]+([b]+[c]).

Es conveniente contar con la terminologa de estructuras algebraicas para refe-rirnos al conjunto de propiedades que se satisfacen. Estas se introducen en lasiguiente seccion. El conjunto de enteros mod nes

Zn= {[a]n: a Z}.

Este tambien es denotado por Z/nZ o Z/(n).

Propiedad Cancelativa

La propiedad cancelativa de la multiplicacion en general no aplica en Zn. Porejemplo,2 4 2 1(mod 6)pero4 1 (mod 6). El siguiente teorema determinabajo que condiciones se puede cancelar en Zn.

Teorema 3 Si ca cb (mod n), entonces a b (mod n/d) donde d =mcd(c, n).

Prueba. n | c(a b)implica que n/d |(c/d)(a b). Puesto que n/d, c/dsoncoprimos entonces n/d | ab.

Los siguientes corolarios son inmediatos.

Corolario 4 Sica cb (mod n)yc, bson coprimos, entoncesa b (mod n).

Corolario 5 Sica cb (modp) conp primo p| c, entoncesa b (modp).


4/26


En el ejemplo de arriba, 2 4 2 1(mod 6), se tiene que mcd(2, 6) =2 y porlo tanto 4 1 (mod 3).

Otra propiedad importante es la posibilidad de, dado que ab= 0, deducir quea = 0 o b = 0. El siguiente teorema caracteriza cuando esto es posible. Por

ejemplo, 4 3 0 (mod 6) pero 40 (mod 6) y 3 (mod 6).

Teorema 6 El entero n > 1 es primo si y solo si para todo par de enterosa, b, ab 0 (mod n) implicaa 0 (mod n) o b 0 (mod n).

Prueba. Supongamos que n es primo y ab (mod n) =0. Es decir n | ab. Peroesto implica (por ser nprimo) que n | aon | b, lo que se puede reescribir comoa 0 (mod n) o b 0 (mod n). Ahora, supongamos que n no es primo.Entonces n = ab para enteros 1 < a,b < n. Entonces ab 0 (mod n), peroa0 (mod n) y b0 (mod n) (por la condicion 1 < a,b < n).

VI.2. Representacion de Enteros Base b

Sea b > 1 un entero. Cualquier entero N 1 se puede escribir en forma unicaen terminos de potencias de bi con coeficientes aital que 0 ai< b:

N= ambm+am1b

m1+ +a1b+a0.

El caso b = 10 es la representacion usual base 10, y el caso b = 2 es larepresentacion binaria que ya hemos encontrado. Como en ese caso, la prueba

es por induccion, y esta puede ser comenzando por la potencia mas alta o porla potencia mas baja. Vamos a usar aqu la segunda opcion: Como base de lainduccion, si 0 < N < b entonces a0 = N y ai = 0 para i > 0. Para el pasode induccion consideramos N b. Entonces, por el algoritmo de la division,existen enteros q y a0con 0 a0< btal que N = qb + a0. Puesto que b > 1,se tieneq < Ny podemos aplicar la hipotesis de induccion aq. Se obtiene queq tiene una representacion de la forma

q= a mbm + +a 1b+a

0

y entonces

N = qb+a0

= (a mbm + +a 1b+a

0)b+a0

= a mbm+1+ +a 1b

2+a 0b+a0

= ambm+am1b

m1+ +a1b+a0,


5/26

VI.2. REPRESENTACION DE ENTEROS BASEB 5

dondem= m+1,ai= ai1parai = 1, 2, . . . , m . Por induccion, esto completa

la existencia. Para la unicidad, tambien por induccion, asumimos (omitiendoel caso base N < b) que N b tiene dos representaciones N = amb

m +

am1bm1+ + a1b + a0y N = a

mbm+ a m1b

m1+ + a 1b + a0. Entonces

((amam)bm1+ + (a1a

1))b= a

0a0.

Si a 0a0= 0 entonces 0 < |a0a0| < b, pero el termino al otro lado de la

igualdad en valor absoluto es 0 o al menos igual a b, lo que es una contradiccion.Por lo tantoa 0= a0. Por hipotesis de induccion, aplicada a q en N = qb + a0,tambien ai= a

ipara i= 1, 2, . . . , m .

Exponenciacion Rapida

Usando la representacion binaria, se obtiene el siguiente metodo de exponen-ciacion rapida:

exp(a, b) =

1 si b= 0exp(a2,b/2) si b es parexp(a2, (b1)/2) a si b es impar

El paso inductivo de la verificacion de este metodo es

ab =ab/22+bmod 2 = (a2)b/2 abmod 2

Ejemplo. Queremos calcular 5110 (mod 31). Las potencias relevantes (en elmetodo de exponenciacion rapida) son

k = 1 2 4 8 16 32 64

5k (mod 13) = 5 25 101 114 27 74 105

Puesto que

110= 64 +32+8+4+2

(la representacion binaria de 11010es 11011102, donde el subndice indica labase) se tiene

5110 =564 532 58 54 52 131105 74 114 101 25 60.


6/26


Veamos la evaluacion recursiva (mod 131):

exp(5, 110) 131 exp(25, 55)

131 exp(252, 27) 25131exp(101, 27) 25

131 exp(1012, 13) 101 25131exp(114, 13) 101 25

131 exp(1142, 6) 114 101 25131exp(27,6) 114 101 25

131 exp(272, 3) 27 114 101 25131exp(74,3) 27 114 101 25

131 exp(742, 1) 74 27 114 101 25131exp(105,1) 74 27 114 101 25

131 exp(1052, 0) 105 74 27 114 101 25

131 105 74 27 114 101 25.

131 60.

Los productos parciales se han dejado indicados, pero se podran llevar a cabo(mod 131) inmediatamente cuando aparece cada nuevo factor.

Reglas de Divisibilidad

El siguiente teorema es consecuencia directa de las propiedades de las con-gruencias.

Teorema 7 SeaP(X) =mk=1ckX

k un polinomio enX con coeficientes enterosyn > 0. Sia b (mod n) entoncesP(a) P(b) (mod n).

Definicion. aes una solucion de P(X) 0 (mod n)si P(a) 0 (mod n).

Corolario 8 Si a es una solucion de P(X) 0 (mod n) y a b (mod n),entoncesb es tambien una solucion deP(X) 0 (mod n).

Como aplicacion de esto se pueden obtener condiciones de divisibilidad de en-teros. Como ejemplo, tenemos condiciones de divisibilidad por 9 y 11.

Teorema 9 N= am10m+am110

m1+ +a110+a0, donde0 ai< 10,es divisible por 9 si y solo siM= am+ am1+ + a1+ a0es divisible por 9.

Prueba. Teniendo en cuenta que10 1 (mod 9), entoncesP(10) P(1) (mod 10).Pero N= P(10)y M= P(1), por lo tanto N M (mod 9). Es decir 9 | NMy por lo tanto 9 | N si y solo si 9 | M.

Teorema 10 N= am10m

+ am110m1

+ + a110 + a0, donde0 ai< 10,es divisible por 11 si y solo si T = a0a1+a2 + (1)mam es divisible

por 11.

Prueba. Se usa que10 1(mod 11)y por lo tantoP(10) P(1) (mod 11).


7/26

VI.3. CONGRUENCIAS LINEALES 7

VI.3. Congruencias Lineales

Recordemos que la ecuacion diofantina lineal ax+by = c tiene solucion si ysolo si d | cdonde d = mcd(a, b). Ademas, si (x0, y0)es una solucion, entoncesel conjunto de todas las soluciones es

T ={(x0+tb/d, y0ta/d) :t Z}.

Ahora consideramos el problema de encontrar soluciones a la congruencia lineal

ax b (mod n)

Esto es equivalente a determinar si existen x y ktal que

axkn = b, ()

la cual es una ecuacion diofantina lineal.

Teorema 11 La congruencia linealax b (mod n) tiene solucion si y solo sid | b donded= mcd(a, n). Sid | b, entonces la congruencia tiene exactamented soluciones incongruentes (mod n):

xt= x0+n

dt

dondex0 es una solucion, yt= 0, 1, 2 , . . . , d1.

Prueba. Ya sabemos que () tiene solucion si d | b. Ahora supongamos que

(x0, k0) es una solucion. Entonces el conjunto de soluciones es

T ={(x0+tn/d, k0+ta/d) :t Z}.

Veamos cuando dos de estas soluciones para x0son congruentes (mod n):

xtxt = n

d(tt ) 0 (mod n)

implica (usando la cancelabilidad para cancelarn/d) que

t t (mod d).

Por lo tanto, se tienen exactamente d soluciones incongruentes xt = x0+ nd

t,t= 0, 1, . . . , d1.

Corolario 12 Si mcd(a, n) = 1 entonces ax b (mod n) tiene una unicasolucion.


8/26


Lo anterior corresponde al caso en que existe el inverso multiplicativo a1 dea (mod n), y entonces la solucion es x a1b(mod n).

Ejemplo. Consideremos la congruencia 18x 30 (mod42). Tiene solucionporque mcd(18, 42) =6. Antes de resolverla, podemos cancelar y obtener 3x 5(mod 7). La ecuacion diofantina correspondiente es

3x7k= 5

que tiene solucionx = 4, k= 1 (a ojo; en general, usando el algoritmo exten-dido de Euclides). Entonces el conjunto de soluciones incongruentes (mod 7)es

x= 4 +7t, t= 0,1,2,3,4,5.

VI.4. Teorema Chino del Residuo

Teorema 13 Seanm1, m2, . . . , m kenteros positivos relativamente primos (enpares), ya1, a2, . . . , ak enteros cualesquiera. Entonces existen una solucion alconjunto de ecuaciones simultaneas

x a1(mod m1)

x a2(mod m2)...

x ak(mod mk)

Si x y x son dos tales soluciones, entonces x x (mod M) donde M =m1m2 mk. Igualmente, six es una solucion yx x

(mod M), entoncesx

tambien es una solucion.

Prueba. SeaM= m1m2 mky para cadai= 1, 2, . . . , k , sea Mi= M/mi.Se tiene que mcd(Mi, mi) =1 y entonces, por la identidad de Bezout, existenenteros ri, sital que

riMi+simi= 1.

Es decir,riMi 1 (mod mi).

Sea xi= riMi. Entonces

xi

1(mod mi)0(mod mj) j=i

()


9/26

VI.4. TEOREMA CHINO DEL RESIDUO 9

Sea

x=

ki=1

aixi.

Con esto,

x mod mj =

ki=1

aixi

mod mj

=

ki=1

ai(ximod mj)

mod mj

= ajmod mj usando ()

Es decir

x aj(mod mj)

para j = 1, 2, . . . , k . Por lo tanto x definido arriba es una solucion al sistemade ecuaciones.Por otra parte, supongamos que existe otra solucion x del sistema de ecua-ciones. Entonces x x (mod mi) para i = 1, 2, . . . , k . De aqu que x x (mod M). Finalmente, si x es solucion y x x (mod M), entonces x x(mod mi) para cada i, y por lo tanto x

tambien es una solucion.

Una prueba alternativa es considerar dos ecuaciones a la vez, las cuales sereducen a una mod el producto de los modulos de estas. De esta manera sepuede resolver cualquier numero de ecuaciones simultaneas. Esto tiene la ven-

taja de poder manejar otros casos, como cuando los modulos no son coprimos.Consideremos las ecuaciones

x a1(mod n1)

x a2(mod n2)

Unx que es solucion a estas congruencias debe ser simultaneamente de la formaa1+kn1y a2+n2. Es decir, buscamos enteros ky tal que

a1+kn1= a2+n2

y entonceskn1n2= a2a1,

la cual es una euacion diofantina lineal con incognitasky . Si mcd(n1, n2) =1(la condicion en el teorema chino del residuo), entonces esta ecuacion siempretiene solucion. Mas en general, si d = mcd(n1, n2) y d | a2 a1 entonces la


10/26


ecuacion tiene solucion. Digamos quek0, 0es una solucion, entonces el conjuntode soluciones es

T ={(k0+tn2/d,0+tn1/d) :t Z}.

Entonces

x= a1+kn1= a1+ (k0+tn2/d)n1= a1+k0n1+tn1n2

d

Entonces, la solucion para x es unica (mod M) donde M= n1n2/d:

x a1+k0n1(mod M).

En el caso d= 1, esto es

x a1+k0n1(mod n1n2).

En cualquier caso, las dos ecuaciones iniciales se han reducido a una sola. Estoda una prueba alternativa del teorema chino del residuo.

Ejemplo. Vamos a resolver el sistema

x 3(mod 11)

x 6(mod 8)

x 1(mod 15)

usando ambos metodos. Note que 11, 8 y 15 son coprimos en pares.

Metodo 1. Primero, resolvemos los 3 sistemas

x 1 (mod 11) x 0 (mod 11) x 0 (mod 11)x 0 (mod 8) x 1 (mod 8) x 0 (mod 8)x 0 (mod 15) x 0 (mod 15) x 1 (mod 15)

Para el primer sistema, debemos encontrar x1de la forma x1= 8 15 r(as sesatisfacen la segunda y tercera ecuaciones y tal que

8 15 r+11s = 1

de tal manera que se satisface la primera ecuacion. En general, esta ecuaciondiofantina se resuelve con el metodo ya estudiado. Aqu, a ojo, r0 = 1 ys0= 11 es una solucion. La solucion general para res

r= 1+11t


11/26

VI.4. TEOREMA CHINO DEL RESIDUO 11

de donde

x1= 8 15 r= 120+ (8 15 11)t 120(mod 8 15 11).

Similarmente, para el segundo sistema, x2= 11 15 ry tal que

11 15 r+8s = 1.

Una solucion (a ojo) es r0 = 3 y s0 = 62, lo que da una solucion generalr= 3+8t

x2= 11 15 r= 495+ (8 15 11)t 495(mod 8 15 11).

Para el tercer sistema, x3= 11 8 r y tal que

11 8 r+15s = 1.

Una solucion (a ojo) es r0 = 7 y s0 = 41, lo que da una solucion generalr= 7 +15t

x3= 11 8 r= 616 + (8 15 11)t 616 (mod 8 15 11).

Finalmente, la solucion (mod 8 15 11) = (mod 1320) es

x= 3x1+6x2x3 3 (120) +6 (495) 616 3946 14 (mod 1320)

Metodo 2. Para satisfacer las dos primeras ecuaciones, debemos encontrarx de la forma 3+11r y 6+8s simultaneamente. Es decir

3+11r = 6 +8s

de donde11r8s = 3.

Esta ecuacion tiene solucion, a ojo, r0= s0= 1, de donde la solucion generales

r= 1 +8t, s= 1 +11t

De aqu,x= 3 +11r = 3 +11(1+8t) =14 +88t.

Es decir

x 14 (mod 88)

Ahora nos queda por resolver esta nueva congruencia junto con la tercera ori-ginal. Para esto x debe ser de la forma 14+88r y 1+15s simultaneamente,lo que lleva a

15s88r = 15.


12/26


A ojo, una solucion ess0= 1,r0= 0, de donde se obtiene la solucion generalr= 15t y entonces

x= 14 +88(15t) =14 +1320t.

Es decir x 14 (mod 1320).

Ejemplo. Si alguna de las congruencias a resolver es de la forma ax b (mod n), entonces como primer paso, si es posible, se debe cancelar a parallevar la congruencia a la forma x b/a(mod n/d) donde d =mcd(a, n) (bdebe ser divisible por a). Si no es posible, se puede determinar la solucion,si existe, usando el metodo para ecuaciones diofantinas lienales. Por ejemplo,consideremos el sistema

3x 2(mod 5)

x 8(mod 7)

De la segunda ecuacion, buscamos x de la forma 8+7r, de tal manera que

3(8+7r) =2 +5s

para satisfacer la primera. Esto es igual a la ecuacion diofantina

21r5s = 22.

VI.5. Teoremas de Fermat y Wilson

Teorema 14 (Fermat)Seap primo ya tal quep| a, entonces

ap1 1 (modp).

Prueba. Los enteros

1 a, 2 a, 3 a, . . . , (p1) a

son incongruentes (modp) porque si

jaia = (ji)a= kp

para 1 i < j < p y algun k, entonces p | i j (puesto que p es primo y

p| a) lo que no es posible. porque ji < p. En lenguaje de congruencias: Siia ja (modp)entonces(j i)a 0 (modp), y puesto quea0 (modp)sedebe tener que ji 0 (modp) y i j (modp); como 0 < i, j < pentoncesi= j. Entonces

(1 a) (2 a) (3 a) . . . ((p1) a) 1 2 3 (p1) (modp)


13/26

VI.5. TEOREMAS DE FERMAT Y WILSON 13

y por lo tanto, aplicando cinmutatividad y asociatividad,

(p1)! ap1 (p1)! (p1)! (modp).

Puesto quep|(p1)!, podemos cancelar ese termino y obtener

ap1 1 (modp).

Una version alternativa es que para todo a,

ap a (modp),

donde ya no se requiere que p | a (la cual se obtiene multiplicando por aen ambos lados). Esta version tambien se puede probar por induccion sobrea: Para el caso base 1p 1 (modp) y para el paso de induccion, usando elteorema binomial

(a+1)p = ap+

p

1

ap1+

p

2

ap2+ +

p

p1

a+1

ap+1 porquepi

0 (modp) para i= 1, 2, . . . , p1

a+1 por hipotesis de induccion.

Teorema 15 (Wilson)Seap primo, entonces(p1)! 1(modp).

Prueba. Para cada a = 1, 2, . . . , p 1 existe un elemento inverso a1 talque aa1 1 (modp) (esto se deduce de la identidad de Bezout, ya quemcd(a, p) = 1 y por lo tanto existen enteros s, t tal que sa+tp = 1 y sa =1tp). Veamos cuando puede ser a1 = a: la ecuacion a2 1 (modp) llevaa a21 0 (modp) y

(a1)(a+1) 0 (modp)

que tiene como soluciones a 1 (modp) (note que 1 p 1 (modp)).As que excepto a 1(modp), los otros elementos tienen a1 a (modp).As que el producto 2 3 (p 2)se puede reescribir como un producto deparesaa1 y se concluye que

2 3 (p2) 1 (modp).

Multiplicando por (p1) se obtiene

(p1)! (p1) 1(modp).


14/26


VI.6. Funcion y Teorema de Euler

Ya hemos encontrado la funcion (n) de Euler, el numero de coprimos con nmenores que n:

(n) =|{a : 1 a n, mcd(a, n) =1}|.

Antes usamos el principio de inclusion-exclusion para determinar (n) y dela expresion para (n) se verifico que (n) es una funcion multiplicativa.Aqu, vamos a proceder en la otra direccion, primero verificamos que esmultiplicativa, y entonces determinamos (n).Primero un teorema que usamos mas adelante (para probar que existen racesprimitivas de pprimo).

Teorema 16 Paran entero se tiene quen=d|n

(d).

Prueba. Tenemos que

{1 , 2 , 3 , . . . , n}=d|n

{k : 1 k n, mcd(k, n) =d}

donde la union es de conjuntos disyuntos (puesto que mcd(k, n) es un divisorde n). Pero

{k : 1 k n, mcd(k, n) =d}

= {k : d k n, mcd(k, n) =d} porque k < d no es posible

si mcd(k, n) =d

= {(k/d) d : 1 k/d n/d, mcd(k/d, n/d) =1} dividiendo por d

= {jd : 1 j n/d, mcd(j, n/d) =1} substituyendo k/d con j

Por lo tanto

{1 , 2 , 3 , . . . , n}=d|n

{jd : 1 j n/d, mcd(j, n/d) =1}

y de aqu quen=

d|n

(n/d)

lo cual es equivalente a la identidad que se quiere probar (porque si d | n en-toncesn/d | n).


15/26

VI.6. FUNCION Y TEOREMA DE EULER 15

Por ejemplo, si p es primo entonces p= (1) +(p) y, de hecho, (1) =1 y(p) =p 1. Recordemos que una funcion f(n) es multiplicativa si f(mn) =f(m)f(n) para m, ncoprimos (es decir mcd(m, n) =1).

Teorema 17 (n) es multiplicativa.

Prueba. Sean n, m coprimos. Vamos a verificar que (mn) = (m)(n).Primero, notamos que

mcd(a, n) =1 sii mcd(a mod n, n) =1

y entonces

() mcd(a,mn) =1 si y solo si mcd(a, m) =1 y mcd(a, n) =1 por ser m, n coprimos

si y solo si mcd(a mod m, m) =1 y mcd(a mod n, n) =1

Es decir, a es coprimo con mn si y solo si a mod m es coprimo con m ya mod nes coprimo con n. Ademas, por el teorema chino del residuo, sabemosque la funcion

f: Zmn Zm Zna (a mod m, a mod n)

es una biyeccion: dado (x, y) Zm Zn, las ecuaciones a mod m = x ya mod n = y tienen una solucion unica a Zmn. Por lo tanto, () implicaque la restriccion

f: Zmn Zm Zna (a mod m, a mod n)

es tambien una biyeccion. De aqu que

(mn) =(m)(n).

Parap primo, (p) =p 1. Mas general, para determnar (pk), notamos quelos numeros que no son coprimos con pk deben ser multiplos de p. Es decir losno coprimos menores que pk son

p, 2p, 3p, . . . , (pk11)p

As que el numero de coprimos con pk menores que pk es

(pk1) (pk11) =pkpk1 =pk1(p1) =pk(11/p).


16/26


Finalmente, usando el teorema anterior, y la factorizacion prima den podemosdeterminar(n) para cualquier n:

(n) =p | n

p primo

pk(11/p)

= n p |n

p primo

(11/p)

donde la potencia kde p es la potencia de pen la factorizacion prima de n.

Teorema de Euler

Los enteros ay n son coprimos (o relativamente primos) si mcd(a, n) =1. Elteorema de Euler generaliza el teorema de Fermat.

Teorema 18 (Euler)Seana, n coprimos, entoncesa(n) 1 (mod n).

Prueba. Sean a1, a2, . . . , a(n) los enteros positivos menores que n y copri-mos con n (as que a es uno de estos). Tenemos que aa1, aa2, . . . , a a(n) sonincongruentes (mod n) porque si

aai aaj(mod n)

entonces, puesto que mcd(a, n) = 1, la propiedad cancelativa es aplicable yresulta en

ai aj(mod n).

Mas aun, ai = aj (y i = j) porque los ai son incongruentes (mod n). Por lotanto, para cada i existe un g(i), donde g: {1 , 2 , . . . , (n)} {1 , 2 , . . . , (n)}es una biyeccion, tal que

aai ag(i)(modp).

Entonces

(aa1)(aa2) (aa(n)) ag(1)ag(2) ag((n))(mod n)

y

a(n) (a1a2 a(n)) a1a2 a(n)(mod n).

Puesto que nes coprimo con cadaaientonces nes coprimo con a1a2 a(n)y por lo tanto este termimo se puede cancelar, lo que resulta en

a(n) 1 (mod n).


17/26

VI.7. GRUPOS 17

VI.7. Grupos

Definicion. El par (G, ), donde G es un conjunto y : G G G es unaoperacion binaria, es ungrupo si

para todo a, b, c G, (a b) c= a (b c) (asociatividad)

existee (elemento identidad) t.q. para todo a G, a e= e a= a

para todo a G, existe a G t.q. a a= a a =e (elemento inverso)

(G, )es ungrupo abeliano si satisface ademas

para todo a, b G, a b= b a (conmutatividad)

Ejemplos.

(N, +) no es un grupo porque, excepto 0, no existen elementos inversos.

(Z, +) es un grupo abeliano, pero (Z, ) no es un grupo porque, excepto 1,no existen elementos inversos.

(Pn, ), donde Pnes el conjunto de permutaciones (biyecciones) p: In Iny la operacion es la composicion de funciones, es un grupo no abeliano.

VI.8. Grupos Cclicos

Consideremos la secuencia de potencias de 2: 21, 22, 23, 24, 25, 26, . . . Los resi-duos modulo7 son 2, 4, 1, 2, 4, 1, . . ., mientras que modulo6 y 8 son respectiva-mente: 2, 4, 2, 4, 2, 4, . . .y 2, 4, 0, 0, 0, 0, . . .Nos interesa en particular el primercaso en el cual para cierta potencia el residuo es 1 y entonces la secuencia serepite. Formalmente, primero recordamos el principio del palomar (se deducede que si f: In Ines inyectiva entonces es sobreyectiva).Teorema 19 (Principio del palomar)

(i) Sim > n, entoncesf: Im

Inno es inyectiva

(ii) Si A, B son conjuntos finitos con |A| > |B|, entonces f : A B no esinyectiva.

Lema 20 Si a y n son coprimos, entonces a 1 (mod n) para algun con1 < n.


18/26


Prueba. Puesto que mcd(a, n) = 1, para cualquier k > 0, ak no es multiplode n y por lo tanto ak 0 (mod n). Consideremos entonces

[a0]n, [a1]n, [a2]n, [a3]n, . . . , [a

n1]n

Estas nclases de congruencia estan en el conjunto

{[1]n, [2]n, . . . , [n1]n}

Por el principio del palomar entonces existen 0 s < t n 1 tal queas at (mod n). Sea tal que t = s+ . Entonces 1 < n y en as as+ (mod n) podemos cancelar as (porque a y n son coprimos). Se obtieneque a 1 (mod n) con 1 < n.

Definicion. Si a y n son coprimos, el ordende a en Zn es el mnimo talque a 1 (mod n), y lo denotamos por ordn(a).

Mas en general, si ges un elemento de un grupo G (con una operacion para lacual usamos notacion multiplicativa), entonces podemos formar las potenciasgk con k Z. Informalmente, g0 =e (la unidad) y

gk =g g g kveces

y gk =g1 g1 g1 kveces

donde g1 es el inverso de g. Mas formalmente, usando recursion,

g0 =e, y gk+1 =gk g, g(k+1) =gk g1 para k 0

Con esta definicion, de pueden probar las propiedades que se espera de lapotenciacion.

Teorema 21 (i) gm+n =gm gn

(ii) (gm)n =gmn

(iii) gn = (gn)1.

Entonces, el conjunto de las potencias gk, k Z forman un grupo contenidoen G que se llama el grupo generado porgy el cual denotamos porg:

g= {gk : k Z}.

Tambien se dice que g es un grupo cclico.

Si existe un entero > 0 tal que g = e entonces el mnimo tal se llamael orden de g en G y lo denotamos por ordG(g). Si no existe tal , entoncesordG(g) = .


19/26

VI.8. GRUPOS CICLICOS 19

Teorema 22 Si ordG(g)


20/26


Corolario 25 Sea g G con ordG(g) = 1 entero y consideramos el conjunto Zn de clases de congruenciamod n.

Proposicion 26 Para [a] Zn, existe [a]1 si y solo simcd(a, n) =1.

Prueba. Si [b] = [a]1 entonces [ab] 1 (mod n), es decir existe q Ztal que ab = 1+ qn y entonces ab qn = 1. Por la identidad de Bezout,mcd(a, n) =1. Las mismas implicaciones son validas en la direccion opuesta,lo que nos da el recproco.

Definicion. Un elemento [a] Zn para el que existe elemento inverso, esdecir mcd(a, n) = 1, se llama una unidadde Zn. El conjunto de unidades deZnse denota por Z

n. Es decir,

Zn= {[a]n : a Z, mcd(a, n) =1}.


21/26

VI.10. SUBGRUPOS 21

Usando los representantes de los residuos menores que n, podemos escribir

Zn= {[a]n : 0 < a < n, mcd(a, n) =1}.

Entonces

|Zn|= (n)

donde (n)es la funcion de Euler.

Lema 27 Zn con la operacion multiplicacion definida enZn forma un grupo.

Prueba. [1] Zny si [a]n, [b]n Znentonces [a]n[b]n= [ab]n Z

nporque

mcd(a, n) = 1 y mcd(b, n) = 1 implica que mcd(ab,n) = 1. Si [a]n Zn

entonces [a]1n Zn.

El elemento inverso de un a Zn se puede determinar usando el algoritmo

extendido de Euclides. Alternativamente, de acuerdo con el teorema de Euler,puesto quea(n) 1 (modp), se concluye que

a1 a(n)1 (mod n).

As el problema de determinar el inverso se convierte en un problema de expo-nenciacion (que se puede realizar con el metodo descrito anteriormente).

VI.10. Subgrupos

Definicion. Sea G, un grupo. Si H G y H, es un grupo donde laoperacion es la restriccion a H de la operacion en G, se dice que H, esun subgrupo de G, . Si se entiende la operacion, se dice simplemente que Hes un subgrupo de G.

Lema 28 SeaG, un grupo. H es subgrupo deG si y solo si (1) H G, (2)Hes cerrado bajo la operacion, y (3) para cadaa H, se tiene quea1 H.

Teorema 29 Si H es un subgrupo de un grupo G finito, entonces |H| divide|G| (el orden deH divide el orden deG).

Prueba. La prueba usa una construccion importante, la cual es una generaliza-cion de la construccion de Zna partir de Z, y que recordamos por convenienciacon el lenguaje de grupos. Sea

nZ= {nk: k Z}= {. . . , 3n, 2n, n,0,n,2n,3n,...}


22/26


nZ, +es un subgrupo de Z, +. Definimos entonces la relacion congruenciamod n, denotadan, como

anb sii n| a b

Sabemos ya que

anb sii existe q Z tal que ab = qn

y entoncesanb sii ab nZ,

por la definicion de nZ. La clase de equivalencia de Z, la cual ya hemosdenotado por []n, es entonces igual a +nZdonde

+nZ= {+k: k nZ}

En terminologa de grupos, + nZes la clase de en nZ. Es claro que existeuna biyeccion entre nZy +nZ: kn +kn.Ahora describimos la construccion general para un grupo G y subgrupo H deG. Utilizamos como es usual notacion multiplicativa. Se define una relacionHsobre G como

aHb sii ab1 H.

Hes una relacion de equivalencia en G:

- para a G, aHa porque aa1 =e H.

- para a, b G, si a H b entonces ab1

H. Puesto que (ab1

)1

=ba1, se concluye que ba1 H y por lo tanto bHa

- para a, b, c G, si a H b y b H c, entonces ab1 H y bc1 H.

Puesto que (ab1)(bc1) = ac1, se concluye que ac1 H y por lotanto aHc.

Como antes, la clasede b G es entonces

Hb= {hb: h H}

Tambien aqu se tiene una biyeccion fentre Hy Hbdada por h hb:inyectiva: si f(h1) = f(h2), entonces h1b = h2b y cancelando se tiene que

h1= h2

sobreyectiva: si x Hb entonces existe h H tal que x = hb y por lo tantof(b) =hb = x


23/26

VI.11. RAICES PRIMITIVAS 23

Se concluye entonces que las clasesHb tienen la misma cardinalidad|H|. Comoademas estas clases forman una particion de G (si g G entonces g Hgporque eg= g), entonces de obtiene que |H|divide |G|.

El cociente |G|/|H| se llama el ndicede H enG y se denota (G: H). En otras

palabras, el ndice de Hen G es el numero de clases de HenG.

Teorema 30 (Fermat)Para todo [a] Zn, [a](n)n = [1]n.

Prueba. Sea[a] Zn. Entonces ordn([a])< y|a|= ordn([a])(el subgru-po generado poratiene ordn([a])elementos. Como|Z

n|= (n), por el teorema

de Lagrange, se tiene que ordn([a])| (n). Por lo tanto (n) = q ordn([a]) yentonces

[a](n) = [a]q ordn([a]) = ([a]ordn([a]))q = [1]q = [1].

VI.11. Races PrimitivasTeorema 31 (Lagrange)Sip es primo y

f(x) =anxn+ +a1x+a0

es un polinomio de grado n con coefficientes en Z con an 0 (modp)), en-toncesf(x) 0 (modp) time a lo masn soluciones incongruentes (modp).

Prueba. Por induccion sobre n. Para n= 1,

a1x+a0 0 (modp)

tiene una raz unica: si x1, x2 son soluciones, entonces a1(x1x2) (modp)y puesto que a1 0 (modp) entonces x1x2 0 (modp). Para el paso deinduccion, sea f(x) = anx

n + + a1x+ a0 un polinomio de grado n concoeficientes enteros. Supongamos que c es una solucion de f(x) 0 (modp).Entonces, dividiendo por xc, se obtiene que

f(x) = (xc)q(x) +r

donde q(x) es un polinomio de grado menor que n y r es una constante (estoes analogo a algoritmo de la division para los enteros y se puede probar porindiuccion). Puesto que f(c) 0 (modp), se tiene que f(a) =r 0 (modp).Por lo tanto sic es otra solucion def(x) 0 (modp),c c (modp), se tiene

quef(c ) = (c c)q(c ) 0 (modp).

Puersto que cc (modp), se concluye que q(c ) 0(modp). Por hipotesisde induccion existen a los mas n 1 tales soluciones c , y por lo tanto laecuacion f(x) 0 (modp)tiene a lo mas nsoluciones.


24/26


Corolario 32 Seap primo yd |p1. Entonces la ecuacionxd1 0 (modp)tiene exactamented soluciones incongruentes (modp).

Prueba. Puersto qued |p 1, existektal quep 1= dkSea f(x) =xp1 1.Entonces f(x) =xdk1 y factorizando se tiene que

xp11 = (xd1)g(x)

dondeg(x) =xd(k1) +xd(k2) + +xd+1.

Por el teorema anterior f(x) 0 (modp), xd 1 0 (modp) y g(x) 0 (modp) tienen a lo mas p 1 = dk, d y dk d soluciones incongruentes(modp), respectivamente. Por otra parte, por el teorema de Fermat, sabemosque

ap1 0 (modp)

para a= 1,2, , p1. Por lo tanto f(x)tiene exactamente p1= dksolu-ciones incongruentes. Por lo tanto xd1 0 (modp)debe tener exactamented soluciones incongruentes.

Teorema 33 Seap primo yd |p 1. Entonces existen exactamente(d) en-teros incongruentesa tal queordp(a) =d.

Prueba. Sea

(d) =|{a : 1 a p 1, ordp(a) =d}|.

Recordemos que para 1 a p 1, si ordp(a) =d entonces d | (p) =p 1

(esto de debe a que por el teorema de Fermat, ap1 1 (modp)). Por lo tanto

p1 =d|p1

(d).

Por otra parte sabemos que

p1 =d|p1

(d).

De aqu que

d|p1(d) = d|p1(d). ()

Veamos que si (d) > 0 entonces (d) =(d): Si (d) > 0 entonces existea con 1 a p 1 con ordp(a) =d. Por lo tanto

a, a2, a3, . . . , ad


25/26

VI.11. RAICES PRIMITIVAS 25

son incongruentes (modp). Para cada uno de estos ak se tiene que

(ak)d = (ad)k 1k =1 (modp).

Por lo tanto estas deben ser lasd soluciones de la ecuacionxd 1 0 (modp)

(por el corolario anterior deben ser exactamente d). As que para determinarlos acon 1 a p 1 tal que ordp(a) =d, es suficiente considerar estosa

k,1 k d. Pero sabemos que ordp(a

k) =d si y solo si mcd(k, d) = 1. Por lotanto

(d) = |{a : 1 a p 1, ordp(a) =d}|

= |{ak : 1 k d, mcd(k, d) =1}|

= (d).

Asumiendo que(d)> 0, hemos concludo que (d) =(d). Pero esto quiere

decir que(d) (d)para todod. Por lo tanto, si existed

tal que(d

) =0,entonces (d)< (d), y entonces

d|p1

(d) 0y por lo tanto (d) =(d).

Corolario 34 Si p es primo, entonces existen exactamente (p 1) racesprimitivas incongruentes dep.

Prueba. Una raz primitiva de p es un entero positivo menor que p con ordenp1. Por el teorema anterior, existen (p1) tales enteros.

Corolario 35 Zp es un grupo cclico.

Prueba. Por el corolario anterior, existe un r con ordp(r) = p 1. Por lotanto los elemento r, r2, r3, . . . , rp1 son diferentes y necesariamente son losp1 elementos de Zp. Es decir Z

p=r.

Ejemplo. Hemos encontrado en un ejemplo anterior que 2, 6 ,7 11 son racesprimitivas de 13. Mas general, los divisores de13 1= 12 son 1,2,3,4,6,12y(1) =1, (2) =1, (3) =2, (4) =2, (6) =2, y (12) =4. As,

d|12

(d) =(1)+ (2)+ (3)+ (4)+ (6)+ (12) =1 +1+2+2+2+4= 12.


26/26


Los ordenes son los siguientes:

k = 1 2 3 4 5 6 7 8 9 10 11 12

ord13(k) = 1 12 3 6 4 12 12 4 3 6 12 2

Por ejemplo,k = 1 2 3 4

5k = 5 12 8 1

Documents

congruencias-grupos