34412300 Algebra Basica

8/6/2019 34412300 Algebra Basica

1/139

lgebra BsicaCurso 2004-2005

Eugenio Miranda Palacios


2/139

2


3/139

ndice general

0. Rudimentos de lgica 7

0.1. El mtodo axiomtico . . . . . . . . . . . . . . . . . . . . . . . . 70.2. Proposiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80.3. Predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100.4. Demostraciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1. Aritmtica entera 131.1. El anillo ordenado de los nmeros enteros . . . . . . . . . . . . . 131.2. Induccin. Principios del mnimo y del mximo . . . . . . . . . . 151.3. Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.4. Algoritmo de la divisin eucldea . . . . . . . . . . . . . . . . . . 171.5. Mximo comn divisor y mnimo comn mltiplo . . . . . . . . . 181.6. Ecuaciones diofnticas . . . . . . . . . . . . . . . . . . . . . . . 251.7. Primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291.8. Congruencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311.9. Sistemas de ecuaciones en congruencias . . . . . . . . . . . . . . 341.10. Teorema chino de los restos . . . . . . . . . . . . . . . . . . . . . 361.11. Los anillos Zn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2. Anillos conmutativos 512.1. Leyes de composicin. Estructuras algebraicas. . . . . . . . . . . 512.2. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

2.2.1. Ejemplos de grupos . . . . . . . . . . . . . . . . . . . . . 542.2.2. Ejemplos de anillos . . . . . . . . . . . . . . . . . . . . . 552.2.3. Ejemplos de mdulos . . . . . . . . . . . . . . . . . . . . 57

2.3. Reglas de clculo . . . . . . . . . . . . . . . . . . . . . . . . . . 582.3.1. Reglas de clculo para grupos . . . . . . . . . . . . . . . 582.3.2. Reglas de clculo para anillos . . . . . . . . . . . . . . . 61

2.4. Homomorfismos . . . . . . . . . . . . . . . . . . . . . . . . . . 622.4.1. Homomorfismos de grupos . . . . . . . . . . . . . . . . . 622.4.2. Homomorfismos de anillos . . . . . . . . . . . . . . . . . 64

3


4/139

4 NDICE GENERAL

2.4.3. Homomorfismos de mdulos . . . . . . . . . . . . . . . . 65

2.5. Subestructuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662.5.1. Subgrupos . . . . . . . . . . . . . . . . . . . . . . . . . 662.5.2. Subanillos e ideales . . . . . . . . . . . . . . . . . . . . . 672.5.3. Submdulos . . . . . . . . . . . . . . . . . . . . . . . . 70

2.6. Anillos cocientes . . . . . . . . . . . . . . . . . . . . . . . . . . 722.7. Dominios de integridad y cuerpos . . . . . . . . . . . . . . . . . 742.8. El cuerpo de fracciones . . . . . . . . . . . . . . . . . . . . . . . 752.9. Factorizacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

2.9.1. Dominios de factorizacin nica . . . . . . . . . . . . . . 792.9.2. Dominios de ideales principales . . . . . . . . . . . . . . 81

3. Dominios Eucldeos 853.1. Definiciones y resultados bsicos . . . . . . . . . . . . . . . . . . 853.2. Ejemplos: Anillos cuadrticos . . . . . . . . . . . . . . . . . . . 87

3.2.1. Cuerpos cuadrticos de nmeros . . . . . . . . . . . . . . 873.2.2. Anillos cuadrticos de enteros . . . . . . . . . . . . . . . 873.2.3. Anillos cuadrticos eucldeos . . . . . . . . . . . . . . . 90

3.3. Aritmtica en dominios eucldeos . . . . . . . . . . . . . . . . . 923.3.1. Factorizacin en primos . . . . . . . . . . . . . . . . . . 923.3.2. Clculo del mximo comn divisor . . . . . . . . . . . . 933.3.3. Resolucin de ecuaciones lineales . . . . . . . . . . . . . 953.3.4. Resolucin de ecuaciones en congruencias . . . . . . . . 96

4. Polinomios 1054.1. Definiciones y primeras propiedades . . . . . . . . . . . . . . . . 1054.2. El algoritmo de la divisin con resto . . . . . . . . . . . . . . . . 1094.3. Factorizacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1114.4. Criterios de irreducibilidad . . . . . . . . . . . . . . . . . . . . . 1144.5. Factorizacin en un nmero finito de pasos . . . . . . . . . . . . 1184.6. Polinomios simtricos . . . . . . . . . . . . . . . . . . . . . . . . 1224.7. La resultante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

4.7.1. Introduccin . . . . . . . . . . . . . . . . . . . . . . . . 1274.7.2. Definicin . . . . . . . . . . . . . . . . . . . . . . . . . . 1274.7.3. Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . 128

4.8. El discriminante . . . . . . . . . . . . . . . . . . . . . . . . . . . 1284.8.1. Definicin . . . . . . . . . . . . . . . . . . . . . . . . . . 1294.8.2. Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . 129

4.9. Mtodos de clculo . . . . . . . . . . . . . . . . . . . . . . . . . 1294.9.1. Clculo directo . . . . . . . . . . . . . . . . . . . . . . . 1294.9.2. Mtodo modular . . . . . . . . . . . . . . . . . . . . . . 132


5/139

NDICE GENERAL 5

4.9.3. Por el algoritmo de Euclides . . . . . . . . . . . . . . . . 133

4.9.4. Determinante de Euler-Sylvester-Cayley . . . . . . . . . . 1344.9.5. Determinante de Bezout . . . . . . . . . . . . . . . . . . 135


6/139

6 NDICE GENERAL


7/139

Captulo 0

Rudimentos de lgica

0.1. El mtodo axiomtico

Matemticas es el estudio de las relaciones entre ciertos objetos ideales comonmeros, funciones y figuras geomtricas. Estos objetos no existen en el mundoreal sino que son modelos abstractos de situaciones fsicas.

Para que un sistema matemtico sirva como modelo de la realidad debemostener en principio un mtodo para reconocer enunciados verdaderos, aunque en laprctica alguno puede ser difcil de demostrar. Cuando los objetos de estudio nos

son intuitivamente familiares (como los nmeros enteros), tomamos como axio-mas ciertas propiedades intuitivamente verdaderas e intentamos deducir a partir deellas todas las restantes propiedades del sistema. Una vez elegidos los axiomas,podemos olvidar la interpretacin intuitiva y vemos a nuestros objetos como enti-dades abstractas sujetas a los axiomas dados. Cuando vayamos a aplicar nuestrosistema a un caso concreto, debemos buscar una interpretacin para cada nocinintroducida y verificar que en esta interpretacin todos los axiomas son verdad.Entonces podemos concluir que todos los enunciados derivados de los axiomastambin son ciertos. Esta consideracin subraya la necesidad de mantener el sis-tema de axiomas lo mas pequeo posible.

Dos ventajas de este mtodo axiomtico es que podemos examinar el efectosobre nuestro sistema de variar los axiomas y que las demostraciones son mastrasparentes cuanto mas abstracto es el sistema. Por otra parte cuesta algn tiempofamiliarizarse con las nociones abstractas. En esto puede ayudar el modelo maso menos concreto en que se basa nuestro sistema, aunque no es estrictamentenecesario y ciertamente no forma parte de la teora.

Estudiar estas nociones abstractas es como aprender un idioma nuevo. Perohay un aspecto en el que este proceso difiere de aprender un lenguaje: Debemosrazonar sobre los nuevos conceptos y esto requiere atencin cuidadosa a la in-

7


8/139

8 CAPTULO 0. RUDIMENTOS DE LGICA

terrelacin lgica de los enunciados. Naturalmente es cierto que an en la vida

cotidiana podemos despreciar la lgica slo bajo nuestra responsabilidad, pero laevidencia patente de lo absurdo de las conclusiones normalmente nos fuerza aabandonar una lnea falsa de razonamiento. Por contra cuando seguimos una lneaabstracta de pensamiento sobre conceptos no familiares, podemos alcanzar porrazonamiento lgico conclusiones que no podemos tamizar por el sentido comn.Por tanto es importante estar totalmente familiarizado con las reglas lgicas quenecesitamos y ser conscientes de que estas reglas pueden aplicarse sin mirar elsignificado actual de los enunciados a los que las aplicamos. Por esta razn empe-zamos describiendo brevemente algunos conceptos y notaciones de la lgica.

0.2. Proposiciones

Para nuestro propsito podemos suponer que cada proposicin es o verdaderao falsa. Usamos V para verdadero y F para falso. El correspondiente valor Vo F se llama el valor de verdadde la proposicin.

La lgica proposicional describe las formas en que podemos combinar enun-ciados (tambin llamados proposiciones) verdaderos para producir otros enuncia-dos verdaderos. Usualmente se consideran cinco operaciones principales de esetipo (llamados conectivos lgicos), aunque tcnicamente podemos derivarlas to-das de una o dos de ellas. Estas operaciones son:

Sean A y B dos enunciados (no necesariamente distintos). Definimos la expre-sin A y B tambin escrito A B, y llamada la conjuncin de A y B medianteuna tabla de verdad

A V V F F

B V F V F

A B V F F F Esta tabla muestra que A B es verdad cuando A y B son ambas verdaderas y esfalso en el resto de los casos.

Una segunda forma en que podemos combinar proposiciones es utilizando ladisjuncin A o B que tambin se escribe como A

B. Su tabla de verdad es:

A V V F F

B V F V F

A B V V V F

Esto quiere decir que A B es verdad si lo es A o B o ambas.A partir de cualquier proposicin podemos formar su opuesta o negacin in-

sertando no en los lugares adecuados. En general si A es una proposicin sunegacin es no A denotada tambin A que es verdadera precisamente cuando


9/139

0.2. PROPOSICIONES 9

A es falsa. Su tabla de verdad es

A V F

A F V

La nocin de implicacin es especialmente importante y su uso en matemti-cas difiere en algo de su uso corriente, aunque naturalmente el significado subya-cente es el mismo.As A implica B o si A entonces B se denota por A B ysignifica que A es falsa o B es verdadera. Su tabla de verdad es

A V V F F

B V F V F

A B V F V V

Ntese que si A es falsa, A B es verdadera para cualquier B, en otras palabras:Un enunciado falso implica cualquier cosa. Esto puede parecer extrao al prin-

cipio, pero tiene su anlogo en el uso ordinario cuando subrayamos lo absurdo deuna afirmacin extrayendo un resultado an mas absurdo.

(Ntese que se puede definir la implicacin en funcin de los otros conectivos:A B es igual a (A)B. Mas generalmente, cualquier proposicin compuestaa partir de dos dadas A y B se puede definir usando slo y ).

El ltimo conectivo de uso frecuente es la biimplicacin o equivalencia lgica

A B que se define como (A B) (B A). Su tabla de verdad es A V V F F

B V F V F

A B V F F V

Algunas proposiciones compuestas son verdaderas para todos los valores deverdad de la proposiciones elementales que aparecen. (Por ejemplo siempre esverdadera A (A)). Tales proposiciones se llaman tautologas. Para comprobarsi una proposicin dada es una tautologa podemos usar tablas de verdad.

Por ejemplo consideremos (A

(A

B))

B:

A V V F F

B V F V F

A B V F V V A (A B) V F F F

(A (A B)) B V V V V

As que (A (A B)) B es una tautologa porque en la ltima fila sloaparecen V.


10/139


0.3. Predicados

Usualmente los enunciados simples discutidos hasta ahora no son suficientespara tratar las situaciones matemticas.

Adems de las proposiciones necesitamos funciones proposicionales o predi-cados. Por ejemplo x es un nmero impar (x recorre los nmeros naturales) ox es mayor que y (x,y son nmeros naturales). En contraste con las proposicio-nes, un predicado ya no es verdadero o falso sino que slo llega a serlo cuando sesustituyen valores particulares para las variables: 2 es un nmero impar, 3 esmayor que 2.

En la prctica con frecuencia queremos decir que alguna afirmacin P(x) sobre

x es verdadera para todo x (en el universo de discurso). Denotamos esto por(x)P(x)

que se lee Para todo x se verifica P(x). Decimos que la variable x est acotadapor el cuantificador universal .

Para expresar que P(x) se verifica para algn x escribimos

(x)P(x)

que leemos Existe un x tal que P(x). Aqu x est acotado por el cuantificador

existencial .Finalmente para expresar que P(x) se verifica exactamente para un slo valorde x escribimos

(1x)P(x)que leemos Existe un nico x tal que P(x). Ahora x est acotado por el cuanti-ficador existencial especial 1.

Cuando todas las variables que aparecen en un predicado estn acotadas porcuantificadores, tenemos una proposicin. Por ejemplo en el dominio de los n-meros naturales (x)(y)(x + y = y + x) significa que para cualesquiera x,y lasuma x + y es independiente del orden de los trminos. De la misma manera

(x)(y)(x < y) dice que para todo x existe un y mayor que x, es decir que noexiste un nmero mximo. Ntese que si aplicamos los cuantificadores en ordeninverso obtenemos la proposicin (y)(x)(x < y) que dice que existe un y mayorque todo x. Evidentemente esto es falso mientras que lo anteriores verdad, as quese debe prestar atencin al orden en que se aplican los cuantificadores.

Ntese tambin que una variable acotada puede siempre renombrarse sin cam-biar el significado. As (x)P(x) significa exactamente lo mismo que (y)P(y); poresta razn una variable acotada se llama tambin variable muda. Con frecuenciausamos esta libertad para evitar conflictos de notacin.


11/139


12/139


Hay que observar que el recproco no es equivalente al enunciado dado (com-

probar tambin las tablas de verdad), por lo que un razonamiento del tipo A esverdad y B A es verdad, luego B es verdad no es correcto. Por ejemplo, su-pongamos que queremos demostrar (x)(x2 par x es par). No es correctoargumentar Si x es par, x2 es par, de donde el resultado, pero s es correcto decirSi x es impar, x2 es impar, de donde el resultado.

Otra forma de prueba indirecta es por contradiccin tambin llamado reductioad absurdum: Para demostrar A mostramos que (A) F, es decir demostra-mos que (no A) lleva a una contradiccin.

Tambin existe la demostracinpor contraejemplo. Muchos enunciados tienenla forma (x)P(x). Si queremos demostrar que un tal enunciado es falso, debemosdemostrar su negacin, es decir (x)P(x) y esto se hace hallando un c tal queP(c) sea cierto.

Finalmente, en matemticas hay demostraciones de existencia no constructi-vas. Esto puede sonar raro, pero es un tipo de razonamiento que tambin se da enla vida diaria: En un grupo de 400 personas debe haber dos que tengan el mismocumpleaos, aunque para hallar un tal par es preciso un examen mas detallado delgrupo.

Con frecuencia un teorema tiene la forma de una implicacin o una equivalen-cia. Citamos unas cuantas formas de expresarlo:

A

B : Se verifica A slo si se verifica B; A es suficiente para B.

A B : Se verifica A si se verifica B; A es cierto siempre que B sea cierto; A esnecesario para B.

A B : Se verifica A si y slo si se verifica B; A es necesario y suficiente para B.

En la prctica aparece con frecuencia la frase si y slo si. Muchas veces seabrevia por sii (en ingls iff).

Tambin es til tener un signo para indicar el final de una demostracin. Tra-dicionalmente se utilizaban las abreviaturas QED (quod erat demostrandum) oCQD (como queramos demostrar). Pero en la literatura matemtica mas mo-derna se usa o .


13/139


14/139

14 CAPTULO 1. ARITMTICA ENTERA

tiene un inverso multiplicativo. Mas adelante hallaremos inversos para todo entero

no nulo cuando veamos los nmeros racionales.Adems de las propiedades anteriores, existe otra propiedad que relaciona la

suma y el producto:

Ley distributiva x(y +z) = xy + xz.

Un conjunto R con dos operaciones x +y, xy verificando las anteriores propie-dades se llama anillo conmutativo, as que el conjunto Z de todos los enteros esun anillo conmutativo. Sin embargo estas leyes no son suficientes para determinarunvocamente a Z.

Veamos ahora algunas consecuencias de las leyes anteriores: De la ley distri-butiva se sigue que para todo x Z se verifica x0 = 0 = 0x. Por la ley asociativa,la suma de cualquier nmero de trminos es independiente de la manera en queintroduzcamos parntesis, y por la ley conmutativa el orden de los trminos noaltera la suma. Igual ocurre con la multiplicacin. De momento aceptamos todoesto sin demostraciones.

La suma de los nmeros a1, . . . , an se puede escribir a1 + + an. Normalmentese abrevia esta expresin escribiendo el trmino general ai precedido de una sigmamayscula con alguna indicacin del rango en que se suman los enteros (exceptosi esto ltimo est claro del contexto). As que en lugar de a1 + + an podemosescribir

ni=1ai, n1ai, iai, ai

donde en cada caso i es una variable muda. Cuando n = 0 la suma escrita es vacay, por convencin, se toma igual a cero.

Existe una abreviatura similar para productos repetidos usando la pi mayscu-la en lugar de . As que en lugar de a1a2 . . . an podemos escribir

ni=1ai,

n1ai, iai, ai

Por ejemplo, podemos definir la funcin factorial como n! = n1i. Un productovaco se toma igual a uno; as que las sumas vacas y los productos vacos son

respectivamente neutros para la suma y el producto.Una propiedad importante de los enteros es que el producto de dos enteros nonulos no es nunca cero:

Ley de integridad Para cualesquiera enteros a, b, si a 0 y b 0 entoncesab 0. Adems 1 0

Esto tiene una consecuencia muy til:

Ley cancelativa Para cualesquiera a, b, c Z si ca = cb y c 0 entonces a = b.


15/139


16/139


II. Principio de induccin alternativo Sea S un subconjunto de N tal que 1

S

y que n S siempre que para todo m < n m S . Entonces S = N.III. Principio del mnimo o principio de buena ordenacin. Todo conjunto no

vaco de enteros positivos tiene un elemento mnimo.

IV. Principio del mximo Todo conjunto no vaco de enteros negativos tiene unelemento mximo.

El principio del mnimo se suele enunciar diciendo que N est bien ordenadoVeamos la equivalencia de los principios enunciados:

I II : Sea S un conjunto verificando las hiptesis de II. Definimos T = {x N | y(y x y S )}, es decir que x T precisamente cuando todos losnmeros desde 1 hasta x pertenecen a S . Es evidente que T S , as quebasta demostrar que T = N. Como 1 S , tenemos que 1 T. Si n Tentonces y S para todo y n, luego n + 1 S y por tanto y S para todoy n + 1. Pero esto implica que n + 1 T. Por I tenemos que T = N.

II III : Sea S un conjunto de enteros positivos que no tiene elemento mnimo.Vamos a demostrar que S es el conjunto vaco: Llamamos S = {x N | x S } al complemento de S . Como S no tiene primer elemento, 1 S luego1 S . Si para todo m n se verifica que m S , necesariamente n S (porque en otro caso n

S y n sera un elemento mnimo para S ). Por II,

S = N y por tanto S = .III I : El elemento mnimo de N es 1. Sea S un subconjunto de N que verifique

las hiptesis del principio de induccin. Sea S = {x N | x S }. Sabemosque 1 S y si n S entonces n 1 S . Luego S no tiene elementomnimo, por tanto es el conjunto vaco y S = N.

III IV : Sea S un conjunto no vaco de enteros negativos. Entonces T = {x Z | x S } es un conjunto no vaco de elementos positivos. Por III T tieneelemento mnimo, sea n. Entonces n S y para todo m S tenemos que

m

T, luego n

m lo que equivale a

n

m para todo m

T, as que

n es el elemento mnimo de S .IV III : Se demuestra de manera anloga al apartado anterior.

1.3. Divisibilidad

Definicin 1.3.1. Dados a, b Z decimos que b divide a, que a es divisible por by que a es un mltiplo de b si existe un c Z tal que a = bc. Lo denotamos porb | a.


17/139

1.4. ALGORITMO DE LA DIVISIN EUCLDEA 17

Ya que cualquier mltiplo de 0 es 0, se verifica que 0

|a slo cuando a = 0.

Por esta razn en la expresin b | a normalmente se toma b 0. Para todo b Zse verifica que b | 0.

La negacin de b | a se escribe b a que significa que a no es divisible por b.La relacin de divisibilidad en Z satisface las siguientes propiedades:

1. c | b y b | a implican c | a.2. Para todo a Z se verifica que a | a.3. Si a | b y b | a entonces a = b.

Estas tres propiedades muestran que la divisibilidad es un orden parcial enel conjunto de enteros positivos.

4. b | a, a > 0 y b > 0 implican b a5. b | a1 y b | a2 implican que b | (xa1 + ya2) para cualesquiera x,y Z. En

particular b | (a1 a2).6. b | a implica que para todo c Z se verifica b | ac.7. Si c 0, b | a si y slo si cb | ca

Definicin 1.3.2. Dos enteros a, b tales que b | a y a | b se llaman asociados.De la propiedad 3 anterior vemos que todo entero a est asociado a un nico

entero no negativo, que se llama su valor absoluto y se representa por |a|.

1.4. Algoritmo de la divisin eucldea

La primera aplicacin del principio de buena ordenacin es demostrar el algo-ritmo de la divisin:

Teorema 1.4.1. Para cualesquiera enteros a y b, con b > 0, existen enteros nicosq (el cociente) y r (el resto) tales que a = bq + r con 0 r < b.Demostracin. Consideramos el conjunto R = {s = a bq | q Z, s 0}. Comob > 0, el elemento a b(|a|) = a + b |a| es mayor o igual a cero y est en R.Luego R no es vaco.

Por el principio de buena ordenacin R tiene un primer elemento, al que lla-mamos r. Por definicin r = a bq 0, y a = bq + r. Si fuera r b, entoncess = r b = a b(q + 1) 0, luego s R y s < r. Esto contradice la minimalidadde r, luego r < b.


18/139


Para demostrar que q y rson nicos, supongamos que a = bq + r = bp + s con

0 r, s < b. Esto implica que |r s| < b. Pero r s = b(q p) lo que muestra queb | (r s). El nico mltiplo de b con menor valor absoluto que b es el cero, luegor s = 0 y por tanto r = s. Adems bp = bq, lo que implica p = q.

Corolario 1.4.2. Dados dos enteros a y b con b > 0, b | a si y slo si el resto dela divisin de a por b es 0.

Definicin 1.4.3. Para a Z definimos el conjunto de todos los mltiplos de acomo aZ = {aq | q Z}.

Proposicin 1.4.4. El conjunto aZ es cerrado para la suma y la resta.

Teorema 1.4.5. Sea I un conjunto no vaco de enteros que es cerrado para lasuma y la resta. Entonces o I slo contiene al cero o contiene un mnimo elemento

positivo a, en cuyo caso I = aZ.

Demostracin. Ya que I no es vaco, o slo contiene al cero o contiene algn en-tero no nulo b. En el primer caso hemos terminado. En el segundo caso, Icontienea b b = 0 y a 0 b = b. As que I contiene al entero positivo |b|. Luego el con-junto I+ de enteros positivos de Ino es vaco. Por el principio de buena ordenacintiene un elemento mnimo, al que llamamos a.

Cualquier mltiplo de a se obtiene sumando a o a consigo mismo un nmerofinito de veces, luego aZ I.Por otra parte, sea c I arbitrario. Dividimos entre a, as que c = aq + r con

0 r < a. Pero r = c aq I. Por el carcter minimal de a, debe ser r = 0. O sea,que c = aq aZ. Como c era un elemento arbitrario de I, obtenemos que I aZ.Combinando con el prrafo anterior nos queda que I = aZ.

1.5. Mximo comn divisor y mnimo comn mlti-plo

Definicin 1.5.1. Un entero positivo d se llama mximo comn divisor de dosenteros dados a y b si

1. des un divisor de a y b

2. Todo divisor comn de a y b es un divisor de d.

El mximo comn divisor de a y b se representa como d = m. c. d.(a, b) y tambincomo d = (a, b).


19/139

1.5. MXIMO COMN DIVISOR Y MNIMO COMN MLTIPLO 19

El hecho de enunciar una definicin del mximo comn divisor (o de cualquier

otro concepto) no garantiza su existencia. Adems debemos justificar el uso delartculo determinado el, ya que implica su unicidad. Este ltimo punto es fcilde tratar: Si d1 y d2 son mximos comunes divisores de a y b, entonces la defini-cin requiere que d1 | d2 y d2 | d1, luego d2 = d1. Ya que ambos son positivos,d2 = d1.

Definicin 1.5.2. Sean a, b Z. Cualquier entero de la forma ma+nb con m, n Zse llama combinacin lineal de a y b.

El siguiente teorema muestra la existencia del mximo comn divisor de dosenters cualesquiera y su expresin como combinacin lineal de ambos:

Teorema 1.5.3. Dos enteros no nulos arbitrarios a y b tienen un mximo comndvisor, que se puede expresar como la menor combinacin lineal positiva de a y

b.

Adems un entero es una combinacin lineal de a y b si y slo si es un mltiplo

de su mximo comn divisor.

Demostracin. Sea I el conjunto de todas las combinaciones lineales de a y b, esdecir

I = {x Z | x = ma + nb, m, n Z}

El conjunto I no es vaco, porque contiene a los elementos a=

1 a+

0 b yb = 0 a + 1 b. Es fcil comprobar que I es cerrado para la suma y la resta. Porel teorema 1.4.5, I = dZ, siendo del menor entero positivo de I.

Como d I, existen m, n Z tales que d = ma + nb. Como a, b I, necesa-riamente d | a y d | b.

Sea ahora c Z tal que c | a y c | b, as que a = cq1 y b = cq2. Entonces

d = ma + nb = mcq1 + ncq2 = c(mq1 + nq2)

lo que muestra que c | d.La ltima afirmacin se sigue del hecho de que I (el conjunto de todas las

combinaciones lineales de a y b) es igual a dZ (el conjunto de todos los mltiplosde d).

La igualdad d = ma + nb donde d = (a, b) se conoce como igualdad de Bezout.

Corolario 1.5.4. Para cualquier entero positivo c, (ca, cb) = c (a, b).Demostracin. Por el teorema 1.5.3 tenemos que (ca, cb) es el menor valor po-sitivo de cax + cby, que es igual al producto de c por el menor valor positivo deax + by, es decir el producto de c por (a, b).


20/139


Corolario 1.5.5. Si c

|a, c

|b y c > 0, entonces

a

c,

b

c

=

1c

(a, b)

Si (a, b) = d entonces (a/d, b/d) = 1.

Demostracin. La primera afirmacin es consecuencia directa del corolario an-terior reemplazando c, a, b en dicho corolario por c, a/c, b/c respectivamente. Lasegunda afirmacin es un caso particular de la primera.

Definicin 1.5.6. Dos enteros a, b se llaman primos relativos si (a, b) = 1, es decir

si no tienen divisores comunes salvo 1.Teorema 1.5.7. Para cualquier c Z, (a, b) = (b, a) = (a, b) = (a, b + ac).Teorema 1.5.8. 1. Si b | ac, entonces b | (a, b)c.

2. Si b | ac y (a, b) = 1 entonces b | c.3. Si b | a, c | a y (b, c) = 1 entonces bc | a.4. (a, bc) = 1 si y slo si (a, b) = 1 y (a, c) = 1.

Demostracin. 1. Supongamos que b|

ac. Sea ac = bq. Escribimos (a, b) =ma + nb para algunos m, n Z. Multiplicando por c obtenemos (a, b)c =mac + nbc = (mq + nc)b.

2. Simplemente tomamos (a, b) = 1 en el apartado anterior.

3. Sea a = bq. Si c | a = bq y por el apartado anterior c | q, sea q = cq1.Sustituyendo obtenemos a = bcq1, luego bc | a.

4. Sea (a, bc) = 1. Entonces ma + n(bc) = 1 para algunos m, n Z. Podemosescribir esta igualdad de otras dos formas: ma + (nc)b = 1, ma + (nb)c quemuestran que (a, b) = 1 y (a, c) = 1.

A la inversa, existen enteros m1, m2, n1, n2 tales que 1 = m1a + n1b = m2a +n2c. Multiplicando y agrupando trminos queda: 1 = (m1m2)(a + n1m2b +m1n2c)a + n1n2bc, luego (a, bc) = 1.

Probablemente estamos acostumbrados a calcular el mximo comn divisor dea y b mediante el clculo de sus factorizaciones en primos. Esta tcnica es efectivapara nmeros pequeos, y la estudiaremos mas adelante. Pero en la prctica, puedeser muy largo hallar los factores primos de nmeros grandes, mientras que el


21/139

1.5. MXIMO COMN DIVISOR Y MNIMO COMN MLTIPLO 21

mximo comn divisor se encuentra en muchos menos pasos usando el mtodo

que vamos a describir a continuacin.El mximo comn divisor de dos nmeros puede calcularse utilizando un pro-

cedimiento conocido como algoritmo de Euclides (nuestra demostracin del teo-rema 1.4.5 no incluye un mtodo explcito para calcularlo). Para describir el algo-ritmo de Euclides necesitamos las siguientes propiedades:

Lema 1.5.9. 1. Si a 0 y b | a, entonces (a, b) = |b|

2. Si a = bq + r, entonces (a, b) = (b, r).

Demostracin. 1. Todo divisor de b es un divisor de a. Y todo divisor de b

divide a |b|. Aplicando directamente la definicin de mximo comn divisorobtenemos el resultado buscado.

2. El elemento a es una combinacin lineal de b y r, luego (b, r) | a. Ya quetambin (b, r) | b obtenemos que (b, r) | (a, b). Como r = a bq es unacombinacin lineal de a y b, un argumento similar muestra que (a, b) | (b, r)y por tanto (a, b) = (b, r).

Dados enteros a > b > 0 el algoritmo de Euclides utiliza repetidamente elalgoritmo de la divisin para obtener

a = bq1 + r1 con 0 r1 < bb = r1q2 + r2 con 0 r2 < r1

r1 = r2q3 + r3 con 0 r3 < r2etc.

Ya que r1 > r2 > 0, los restos van menguando y tras un nmero finito depasos obtenemos un resto rn+1 = 0. El algoritmo acaba con la ecuacin

rn

1 = rnqn+1 + 0

Esto nos da el mximo comn divisor:

(a, b) = (b, r1) = (r1, r2) = = (rn1, rn) = rn

Ejemplo 1.5.10. Para mostrar que (24, 18) = 6 tenemos:

24 = 18 1 + 6 (24, 18) = (18, 6)18 = 6 3 + 0 (18, 6) = 6


22/139


Ejemplo 1.5.11. Veamos que (126, 35) = 7:

126 = 35 3 + 21 (126, 35) = (35, 21)35 = 21 1 + 14 (35, 21) = (21, 14)21 = 14 1 + 7 (21, 14) = (14, 7)14 = 7 2 + 0 (14, 7) = 7

Ejemplo 1.5.12. Calculamos (83, 38) = 1:

83 = 38 2 + 7 (83, 38) = (38, 7)38 = 7 5 + 3 (38, 7) = (7, 3)

7 = 3

2 + 1 (7, 3) = (3, 1)

3 = 1 3 + 0 (3, 1) = 1Si slo se necesita calcular el mximo comn divisor, paramos en cuanto podamoscalcularlo en la cabeza. Para mostrar que (83, 38) = 1, ntese que ya que 7 no tienedivisores positivos salvo 1 y 7 y no es un divisor de 38, es claro de inmediato que(38, 7) = 1.

Ejemplo 1.5.13. A veces queremos conocer la combinacin lineal de a y b quenos da (a, b). Al calcular (126, 35) en el ejemplo 1.5.11 tenemos las siguientesecuaciones:

a = bq1 + r1 126 = 35 3 + 21b = r1q2 + r2 35 = 21 1 + 14

r1 = r2q3 + r3 21 = 14 1 + 7r2 = dq4 + 0 14 = 7 2 + 0

El siguiente paso es despejar el resto no nulo en cada una de las ecuaciones,omitiendo la ltima y sustituyendo los anteriores para expresarlos como combina-cin lineal de a y b:

r1 = a + (q1)br2 = b + (q2)r1 = (q2)a + (1 + q1q2)bd = r1 + (q3)r2 = (1 + q2q3)a + (q1 q3 q1q2q3)b

es decir:

21 = 126 + (3)3514 = 35 + (1)21 = (1)126 + 4 35

7 = 21 + (1)14 = 2 126 7 35


23/139


24/139


126 1 035 0 121 1 314 1 47 2 70 5 18

y obtenemos que (126, 35) = 7 = 2 126 7 35.La ltima lnea 0 = 5 126 + 18 35 tambin nos da informacin interesante:

Podemos sumar cualquier mltiplo de esta combinacin lineal a la representacinanterior del mximo comn divisor. Por ejemplo, 7 = (3) 126+ 11 35 y tambin7 = (8) 126 + 29 35.Ejemplo 1.5.15. En forma matricial, el clculo de (83, 38) es el siguiente:

83 1 038 0 17 1 23 5 111 11 240 38 83

As que (83, 38) = 1 = 11

83 + (

24)

38.

El nmero (a, b) puede escribirse de infinitas maneras como combinacin li-neal de a y b: El mtodo matricial nos da una combinacin lineal 0 = m1a + n1b,que sumado a la igualdad de la penltima fila nos da d = (m + km1)a + (n + kn1)bpara cualquier k Z.

Dual al concepto de mximo comn divisor es el de mnimo comn mltiplo:

Definicin 1.5.16. Un entero positivo m se llama mnimo comn mltiplo de losenteros no nulos a y b si

1. m es un mltiplo de ambos a y b.

2. Cualquier mltiplo de a y b es un mltiplo de m.

Usamos la notacin m. c. m.(a, b) o bien [a, b] para el mnimo comn mltiplode a y b.

Teorema 1.5.17. El conjunto I de todos los mltiplos de dos enteros no nulos a yb contiene un entero no nulo y es cerrado para la suma y la resta.

Dicho conjunto I es de la forma I = mZ, donde m = m. c. m.(a, b). En parti-cular, dos enteros no nulos cualesquiera tienen un mnimo comn mltiplo.


25/139

1.6. ECUACIONES DIOFNTICAS 25

Demostracin. El entero ab es distinto de cero y pertenece a I. Si c1 = q1a = p1b

y c2 = q2a = p2b, entonces c1 c2 = (q1 q2)a = (p1 p2)b. Por 1.4.5 tenemosel segundo resultado.

Teorema 1.5.18. Si c > 0, [ca, cb] = c[a, b]. Tambin [a, b](a, b) = ab.

Demostracin. Sean [ca, cb] = cq y [a, b] = m. Como a | m y b | m, tenemos queac | mc y bc | mc, luego cq | mc y por tanto q | m. Por otra parte, ca | cq, cb | cqde donde a | q, b | q y por tanto m | q. Como ambos son positivos, m = q.

Para demostrar la segunda parte podemos suponer que a, b > 0 porque [a, b] =[a, b]. Empezamos con el caso especial (a, b) = 1. Ahora [a, b] = ac. Entoncesb

|ac y como (a, b) = 1 necesariamente b

|c, luego ab

|ac = [a, b]. Siempre se

cumple que [a, b] | ab y como ambos son positivos, son iguales.En el caso general sea d = (a, b). Tenemos (a/d, b/d) = 1. Aplicando el

resultado del caso particular se obtiene

a

d,

b

d

a

d,

b

d

=

a

d

b

d

Multiplicando por d2 obtenemos [a, b](a, b) = ab.

1.6. Ecuaciones diofnticas

El estudio de la aritmtica elemental de los enteros se divide en varias partes:Divisibilidad y factorizacin, congruencias, funciones aritmticas y ecuacionesdiofnticas. Vamos a introducir estas ltimas.

Una ecuacin diofntica es una ecuacin polinmica con coeficientes y racesenteros. De la misma forma un sistema de ecuaciones diofnticas es un conjuntofinito de ecuaciones diofnticas simultneas. Resolver una ecuacin diofntica (oun sistema de ellas) es hallar explcitamente sus races enteras.

Ejemplo 1.6.1. Consideremos la ecuacin x2 +y2 = z2. Las soluciones enteras deesta ecuacin se llaman ternas pitagricas por motivos obvios. Algunas solucio-

nes conocidas desde antiguo son (4, 3, 5), (12, 5, 13) y (20, 21, 29). Si exigimosque m. c. d.(x,y,z) = 1, la solucin general viene dada por (2uv, u2 v2, u2 + v2)con u, v de distinta paridad, u > v y m. c. d.(u, v) = 1

Ejemplo 1.6.2. Una generalizacin de la anterior es la ecuacin de Fermat: xn +yn = zn con n 3. El llamado ltimo teorema de Fermat establece que estaecuacin no tiene solucin entera con xyz 0. Para dar una idea de la dificultadde la aritmtica, este teorema fu enunciado a mediados del siglo XVII por Fermaty su demostracin se remat slo a finales del siglo XX por Wiles, mas de 300aos despus.


26/139


Si una ecuacin (o sistema) es determinada, es decir tiene un nmero finito de

soluciones en Q o en R, podemos resolverla en uno de estos cuerpos y comprobarsus races una a una para ver cuales son enteras. Por ello, las ecuaciones diofn-ticas interesantes son las indeterminadas, que admiten infinitas soluciones en Q ydebemos caracterizar cuales de ellas son enteras.

Vamos a discutir un mtodo para resolver los sistemas diofnticos lineales. Elcaso mas sencillo es el de una ecuacin con dos incgnitas:

ax + by = c (1.6.1)

Teorema 1.6.3. 1. La ecuacin 1.6.1 tiene solucin si y slo si m. c. d.(a, b) |c.

2. Una solucin particular de 1.6.1 se obtiene por el algoritmo extendido de

Euclides.

3. Sea d = m. c. d.(a, b) y sea (x0,y0) una solucin particular de 1.6.1. Lasolucin general (x,y) viene dada por

x = x0 + kb

d, y = y0 k

a

d

con k Z arbitrario.

Demostracin. 1. Supongamos que 1.6.1 tiene una solucin (x0,y0) y sea d =m. c. d.(a, b). Entonces

c = ax0 + by0 = d(a

dx0 +

b

dy0)

y por tanto d | c.A la inversa, sea c = dc1. Por el teorema de Bezout existen m, n Z talesque am + bn = d. Entonces (x0,y0) = (mc1, nc1) es una solucin de 1.6.1.

2. Por el algoritmo extendido de Euclides encontramos m, n Z tales queam + bn = d. El ltimo prrafo del punto anterior termina la demostracin.

3. Sea (x0,y0) una solucin particular, es decir ax0 + by0 = c. Llamamos x =x0 + k

bd

, y = y0 kad y calculamos ax + by = a(x0 + kbd) + b(y0 kad) = c.A la inversa, sea ax + by = c. Restando la solucin particular tenemos que(x x0)a + (y y0)b = 0. Dividimos por d = m. c. d.(a, b) y despejamos:(xx0)(a/d) = (yy0)(b/d). Como m. c. d.(a/d, b/d) = 1, necesariamentex x0 = k b/d y (y y0) = h a/d. Sustituyendo y simplificando vemosque k = h. Finalmente despejando vemos que x = x0 + kbd y y = y0 kad


27/139

1.6. ECUACIONES DIOFNTICAS 27

Las ideas subyacentes al algoritmo de Euclides pueden aplicarse tambin para

hallar una solucin general en enteros de cualquier conjunto de ecuaciones linea-les con coeficientes enteros. El procedimiento es el siguiente:

1. Buscamos un coeficiente no nulo c de mnimo valor absoluto en el sistemade ecuaciones. Supongamos que este coeficiente aparece en una ecuacinque tiene la forma

cx0 + c1x1 + + ckxk = d;y por sencillez supongamos c > 0.

2. Si c = 1, usamos esta ecuacin para eliminar la variable x0 de las otras ecua-ciones del sistema. Si no quedan mas ecuaciones, el clculo acaba y hemosobtenido una solucin general en trminos de las variables no eliminadas.

3. Si c > 1, entonces

Si c | c1, . . . , c | ck, comprobamos si c den cuyo caso no hay solucinen enteros.

Si c | ddividimos ambos miembros por c y eliminamos x0 como en elcaso c = 1.

4. Si c > 1 y existe un ci no divisible por c, dividimos los ci entre c: ci = qic+ri.Introducimos una nueva variable

x0 + q1x1 + + qkxk = t;eliminamos la variable x0 de las otras ecuaciones en favor de ty reemplaza-mos la ecuacin original por

ct+ r1x1 + + rkxk = d

Este proceso debe terminar ya que cada paso reduce el nmero de ecuacioneso el valor absoluto del mnimo coeficiente no nulo del sistema.

Cuando se aplica este proceso a la ecuacin ax + by = 1 para a, b dados, el

proceso anterior es esencialmente el algoritmo de Eulides extendido.Ejemplo 1.6.4. Queremos resolver el sistema

10w + 3x + 3y + 8z = 1

6w 7x 5z = 2El coeficiente de menor valor absoluto es 3 que multiplica a y en la primera

ecuacin y es positivo. Como 3 10, introducimos una nueva variable

10/3w + 3/3x + 3/3y + 8/3z = 3w + x +y + 2z = t1


28/139


y la usamos para eliminar y. La primera ecuacin se convierte en

(10 mod 3)w + (3 mod 3)x + 3t1 + (8 mod 3)z = w + 3t1 + 2z = 1

y la segunda ecuacin queda igual.Ahora el coeficiente de w en la primera ecuacin es 1. Usamos dicha ecuacin

para eliminar w y la segunda ecuacin se convierte en

6(1 3t1 2z) 7x 5z = 2

esto es7x + 18t1 + 17z = 4

.Introducimos una nueva variable

x + 2t1 + 2z = t2

y eliminamos x:7t2 + 4t1 + 3z = 4.

Introducimos otra variable para eliminar z, que tiene el menor coeficiente:

2t2 + t1 +z = t3

Eliminando z nos quedat2 + t1 + 3t3 = 4

y finalmente utilizamos esta ecuacin para eliminar t2. Nos quedan dos variablesindependientes t1 y t3. Sustituyendo hacia atrs en las variables originales obtene-mos la solucin general:

w = 17 5t1 14t3x = 20 5t1 17t3y = 55 + 19t1 + 45t3z =

8 + t1 + 7t3

En otras palabras, todas las soluciones enteras (w, x,y,z) del sistema originalse obtienen de las ltima igualdades cuando t1 y t2 recorren independientementetodos los enteros.

El proceso de eliminacin de variables descrito (que es reminiscente del m-todo de eliminacin de Gauss para sistemas lineales en un cuerpo) es sencillo ydirecto pero no es el mejor mtodo disponible para este problema. El mtodo quequiz sea el mas elegante y sistemtico se basa en la teora de mdulos sobredominios de ideales principales, teora general que no se estudia en este curso.


29/139

1.7. PRIMOS 29

1.7. Primos

Definicin 1.7.1. Un entero p > 1 se llama nmero primo si sus nicos divisoresson 1 y p. Un entero a > 1 se llama compuesto si no es primo.

Lema 1.7.2 (Euclides). Un entero p > 1 es primo si y slo si satisface la siguientepropiedad: Si p | ab para a, b Z, entonces o p | a o p | b.

Demostracin. Supongamos que p es un primo y p | ab. Si a = 0 el resultado esclaro. Si a 0 sabemos que o (p, a) = p o (p, a) = 1 porque (p, a) siempre es undivisor de p y p es primo. En el primer caso p | a y ya est. En el segundo casoaplicamos el segundo punto del teorema 1.5.8 para mostrar que p

|ab implica

p | b.A la inversa, supongamos que p verifica la condicin dada. Si p = ab la con-

dicin implica que o p = a (ya que p | a y p > a) o p = b y por tanto p esprimo.

Teorema 1.7.3 (Teorema fundamental de la aritmtica). Todo entero a > 1 sefactoriza de manera nica como producto de primos en la forma

a = pe11 p

e22 . . . p

enn

donde p1 < p2 1, como s < a y s tiene dos factorizaciones obtenemos otra vez unacontradiccin con la eleccin de a.

Podemos considerar a los primos como los elementos a partir de los cualesse obtienen por multiplicacin todos los dems nmeros enteros positivos, de lamisma forma en que todo nmero entero positivo se obtiene a partir del 1 mediantesuma reiterada.

Proposicin 1.7.4. Sean a = pe11 pe22 . . . p

enn y b = p

f11 p

f22 . . . p

fnn dos enteros posi-

tivos descompuestos en factores primos. Entonces b | a si y slo si fi e1 paratodo i = 1, . . . , n.

La factorizacin en primos permite escribir directamente el mximo comndivisor y el mnimo comn mltiplo de dos enteros dados:

Proposicin 1.7.5. Sean a, b enteros positivos con factorizaciones primas

a = pe11 p

e22 . . . p

enn y b = p

f11 p

f22 . . . p

fnn

con ei, fi 0 para todo i.Para cada i sean gi = mn(ei, fi) y hi = max(ei, fi). Entonces

m. c. d.(a, b) = pg11 pg22 . . . p

gnn

m. c. m.(a, b) = ph11 ph22 . . . p

hnn

Demostracin. La demostracin se sigue inmediatamente del teorema fundamen-tal de la aritmtica y las definiciones de mximo comn divisor y mnimo comnmltiplo.

Para nmeros pequeos probablemente es mas fcil usar sus factorizacionesprimas para hallar el mximo comn divisor y el mnimo comn mltiplo. Peropara nmeros grandes hallar su factorizacin en primos es muy lento, an usandoalgoritmos sofisticados sobre ordenadores potentes. En contraste, el algoritmo de

Euclides es mucho mas rpido y eficiente para calcular el mximo comn divisorde grandes nmeros.

Ejemplo 1.7.6. Calculamos una vez mas (126, 35). Descomponemos en factoresprimos: 126 = 21325071 y 35 = 20305171. As que (126, 35) = 20305071 = 7y [126, 35] = 21 32 51 71 = 630

Si conocemos la factorizacin de un entero es fcil listar todos sus divisores:Si a = pe11 p

e22 . . . p

enn entonces b es un divisor de a si y slo si b = p

f11 p

f22 . . . p

fnn con

fi ei para todo i. As que podemos listar todos los divisores de a disminuyendosistemticamente los exponentes de cada uno de sus factores primos.


31/139

1.8. CONGRUENCIAS 31

Teorema 1.7.7 (Euclides). Existen infinitos primos

Demostracin. Supongamos que slo hubiese un nmero finito de primos, seanp1, p2, . . . , pn. Formamos el nmero a = p1p2 . . . pn +1. Por el teorema 1.7.3 existeun divisor primo de a, sea p. Este debe estar en la lista as que p | (p1p2 . . . pn),luego p | (a p1 . . . pn) = 1. Pero un primo no puede dividir a 1.

1.8. Congruencias

Para muchos problemas aritmticos, la informacin importante est en los res-tos obtenidos al dividir por un entero fijo n. Como slo son posibles los n restosdiferentes 0, 1, , n1, pueden producirse considerables simplificaciones. Paravalores pequeos de n es posible incluso utilizar el mtodo de prueba y error.

Ejemplo 1.8.1. Un teorema de Lagrange establece que todo entero positivo puedeescribirse como suma de cuatro cuadrados. Vamos a ver que si n es un enteropositivo que al dividirlo por 8 da de resto 7, no puede expresarse como suma detres cuadrados, por lo que el teorema de Lagrange es el mejor posible:

Sea n = a2 + b2 + c2. Al dividir ambos miembros por 8 los restos deben seriguales. Por la proposicin 3.3.12 podemos calcular el resto de a2 + b2 + c2 calcu-lando los restos de a, b y c, elevndolos al cuadrado y sumndolos (y dividiendopor 8 si es necesario). Los posibles valores para a2, b2, c2 son 0, 1, 4. Para com-probar los posibles valores del resto de a2 + b2 + c2 slo tenemos que sumar tresde tales valores. Un estudio de todos los casos muestra que no podemos obtener7como resto de a2 + b2 + c2. Luego si n da de resto 7 al dividirlo por 8, no puedeser suma de tres cuadrados.

La tcnica de prueba y error puede usarse para ver que una ecuacin polin-mica no tiene races enteras:

Ejemplo 1.8.2. Sea f(x) = x3 + 3412x2 1235x + 678443. Supongamos queexistiese un n Z tal que f(n) = 0. Al tomar los restos mdulo 2 nos quedan3 + n + 1 = 0. Pero n3 + n + 1 es impar para cualquier valor de n, luego f(n) 0

para todo valor de n.Una situacin familiar en la que efectuamos los clculos tras dividir por un

valor fijo es en la suma de horas, donde el entero fijo es 12. Las reglas de los signoses hacer el clculo con los restos al dividir por 2. Gauss introdujo la notacin decongruencia que simplifica los clculos de este tipo:

Definicin 1.8.3. Sea n un entero positivo. Los enteros a y b se llaman congruen-tes mdulo n si tienen el mismo resto al dividirlos por n. Esto se denota por a b(mod n) o a b mod n


32/139


Si utilizamos el algoritmo de la divisin para escribir a = nq + r donde 0

r < n entonces r = n 0 + r. Es inmediato de la definicin precedente que a r (mod n). En particular cualquier entero es congruente mdulo n a uno de losenteros 0, 1, 2, . . . , n 1.

La definicin 3.3.9 proporciona la mejor visin intuitiva del concepto de con-gruencia, pero en casi todas las demostraciones es mas fcil utilizar la siguientecaracterizacin, que permite usar los hechos sobre divisibilidad que ya hemos es-tudiado:

Proposicin 1.8.4. Sean a, b, n Z con n > 0. Entonces a b (mod n) si y slosi n | (a b).

Demostracin. Si a b (mod n), entonces a = nq1 +ry b = nq2 +r. Despejandoel resto tenemos r = a nq1 = b nq2. Trasponiendo trminos a b = n(q1 q2),luego n | (a b).

A la inversa sea n | (a b), as que a b = nq. Por el algoritmo de la divisinb = nq1 + r con 0 r < n. Sumando ambas igualdades tenemos que a = n(q +q1) + r, luego los restos de dividir a por n y b por n son iguales y por tanto a b(mod n).

Esta proposicin nos dice que a b (mod n)siyslosi ab = nq para algnentero q, lo que podemos escribir como a = b + nq. Esta observacin proporcionaun mtodo muy til de reemplazar una congruencia por una ecuacin diofntica.

Proposicin 1.8.5. La relacin a b (mod n) es una relacin de equivalencia.Proposicin 1.8.6. Sea n > 0 un entero. Cualesquiera a, b, c, d Z verifican lassiguientes propiedades:

1. Si a c (mod n) y b d (mod n), entonces a + b c + d (mod n),a b c d (mod n) y ab cd (mod n).

2. Si a + c a + d (mod n) entonces c d (mod n). Si ac ad (mod n)y (a, n) = 1 entonces c d (mod n).

Demostracin. Sean a c (mod n) y b d (mod n). Entonces n | (a c) yn | (bd). Sumando tenemos que n | ((a+b)(c+d)) y restando n | ((ab)(cd)).Tambin tenemos que n | (a c)b = ab cb y n | c(b d) = cb cd. Sumandotenemos n | (ab cd).

Sea ahora a + c a + d (mod n). Entonces n | ((a + c) (a + d)) = c d.Si ac ad (mod n) tenemos que n | (ac ad) = a(c d) y como (a, n) = 1, sesigue que n | (c d).

Las principales consecuencias de esta proposicin son:


33/139

1.8. CONGRUENCIAS 33

1. Podemos sustituir cualquier entero de la congruencia por un entero con-

gruente. Por ejemplo para mostrar que 992 1 (mod 100) lo mas fcil essustituir 99 por 1 y calcular (1)2 = 1.

2. Podemos sumar o restar el mismo entero a ambos miembros de una con-gruencia.

3. Podemos multiplicar ambos miembros de una congruencia por el mismoentero.

4. Hay que tener mucho cuidado al simplificar o dividir ambos miembros dela congruencia por el mismo entero a: Slo puede hacerse cuando (a, n) =

1. Por ejemplo 30 6 (mod 8) pero al dividir ambos miembros por 6tenemos 5 1 (mod 8), lo cual es falso. Pero al dividir por 3 tenemos10 2 (mod 8) lo que es correcto porque (3, 8) = 1.

5. Cualquier ecuacin diofntica puede convertirse a una congruencia mdulon simplemente cambiando el signo = por y cualquier trmino congruentea 0 puede sencillamente omitirse. Este proceso se conoce como reduccinmdulo n. Por ejemplo la ecuacin x3 + 5x2 + 6x 11 = 0 se convierte enx3 + x2 + 1 0 (mod 2).

Ejemplo 1.8.7. La proposicin 3.3.12 muestra que para calcular el resto de dividira + b o ab por n podemos calcular los restos de dividir a y b entre n y sumarloso multiplicarlos, dividiendo otra vez por n si es necesario. Por ejemplo, 101 5(mod 8) y 142 6 (mod 8), as que 101 142 5 6 6 (mod 8).Ejemplo 1.8.8. Vamos a calcular las potencias de 2 mdulo 7. En vez de calcularcada potencia y entonces dividir por 7, reducimos mdulo 7 en cada paso delclculo:

22 4 (mod 7),23 222 4 2 1 (mod 7),24 232 1 2 2 (mod 7),25 242 2 2 4 (mod 7)

Tal como hemos hecho los clculos, est claro que las potencias se repiten. Dehecho como slo hay un nmero finito de posibles restos mdulo n, las potenciasmdulo n de cualquier entero siempre acaban repitindose.

Proposicin 1.8.9. Sean a, n Z con n > 1. Existe un entero b tal que ab 1(mod n) si y slo si (a, n) = 1.


34/139


35/139

1.9. SISTEMAS DE ECUACIONES EN CONGRUENCIAS 35

Las distintas soluciones estn entre los restos 0, 1, . . . , n

1. Dada una de las

soluciones, todas las otras se hallan sumando mltiplos de n/d, lo que nos da untotal de dsoluciones distintas.

Vamos a describir un algoritmo para resolver congruencias lineales de la forma

ax b (mod n) (1.9.1)

1. Calculamos d = (a, n). Si d b, la ecuacin no tiene solucin.

2. Si d | b escribimos la congruencia 1.9.1 como una ecuacin diofntica ax =b + qn.

3. Ya que d es un divisor comn de a, b y n podemos tomar a = da1, b = db1y n = dn1. Dividiendo la anterior ecuacin por dnos queda a1x = b1 + qn1.

4. La congruencia 1.9.1 es por tanto equivalente a

a1x b1 (mod n1)

donde ahora (a1, n1) = 1.

5. Por la proposicin 1.8.9 hallamos un entero c tal que ca1 1 (mod n1).

Multiplicando ambos miembros por c obtenemosx cb1 (mod n1)

6. Finalmente, ya que la congruencia original era mdulo n, debemos dar nues-tra respuesta mdulo n. La solucin mdulo n1 determina dsoluciones dis-tintas mdulo n: x b1c + kn1 con k = 0, . . . , d 1.

Ejemplo 1.9.3 (Congruencias lineales homogneas). Vamos a considerar el casoespecial de una ecuacin homognea lineal

ax 0 (mod n)En este caso siempre existe una solucin, x 0 (mod n), pero puede que no

sea la nica.En el segundo paso de la solucin obtenemos a1x 0 (mod n). Ya que

(a1, n1) = 1, por la proposicin 3.3.12 podemos cancelar a1 y nos queda x 0(mod n)1, luego las dsoluciones son x 0, n1, 2n1, . . . , (d 1)n1 (mod n).

Por ejemplo la congruencia 28x 0 (mod 48) tiene cuatro soluciones dis-tintas mdulo 48: x 0, 12, 24, 36 (mod 48)


36/139


Ejemplo 1.9.4. Para resolver la congruencia 60x

90 (mod 105) primero calcu-

lamos D = (60, 105) = 15. Como 15 | 90, la ecuacin tiene solucin. Dividiendopor dobtenemos la ecuacin

4x 6 (mod 7) (1.9.2)

Buscamos un entero c tal que 4c 1 (mod 7), a saber c = 2. Multiplicamosambos miembros de 1.9.2 por c y obtenemos 8x 12 (mod 7), que se reduce ax 5 (mod 7).

La ecuacin original tiene pues quince soluciones:

x

5 + 7k (mod 105) con k = 0, 1, . . . 14

1.10. Teorema chino de los restos

Vamos a estudiar ahora la resolucin de sistemas de ecuaciones en congruen-cias. Empezamos por el caso de dos congruencias:

Teorema 1.10.1. Dos congruencias simultneas

x a (mod m) x b (mod n) (1.10.1)

tienen solucin si y slo si a b (mod (m, n)). En este caso la solucin es nicamdulo [m, n].Demostracin. De la primera congruencia de 1.10.1 se sigue que x = a + mt.Sustituyendo en la segunda obtenemos que tdebe verificar la ecuacin a + mt b(mod n) lo que es lo mismo que mt (b a) (mod n). Hemos visto anterior-mente que esta ecuacin tiene solucin si y slo si d = (m, n) divide a (b a), yen ese caso es equivalente a la congruencia

m

dt b a

d(mod

n

d)

Sea t0 una solucin particular de esta congruencia. La solucin general es

t t0 (modn

d)

as que t = t0 + u(n/d) con u Z. La solucin general de la congruencia originales

x a + m

t0 +n

du

= x0 + u

mn

d

o sea x x0 (mod [m, n]).


37/139


38/139


Demostracin. Sea p un primo arbitrario y sean pi, pj, pk las mximas potencias

de p que dividen respectivamente a a, b, c. Como el enunciado es simtrico parab y c, podemos tomar j k. Entonces la mxima potencia de p que divide a[b, c] es pj y el exponente de la mxima potencia de p que divide a (a, [b, c])es mn(i, j). Por otra parte los exponentes de las mximas potencias de p quedividen a (a, b) y (a, c) son respectivamente mn(i, j) y mn(i, k). Como j k,tenemos que mn(i, j) mn(i, k). Luego el exponente de la mxima potencia dep que divide a [(a, b), (a, c)] es mn(i, j). As que (a, [b, c]) y [(a, b), (a, c)] tienenla misma descomposicin en primos y por tanto son iguales.

La demostracin de la segunda propiedad es anloga.

Teorema 1.10.7. Un sistema de r congruencias simultneas

x ai (mod mi) i = 1, 2, . . . , r (1.10.2)tiene solucin si y slo si para todo par de ndices i, j se verifica

ai aj (mod (mi, mj)) (1.10.3)y en este caso la solucin es nica mdulo Mr = [m1, . . . , mr].

Demostracin. En primer lugar hay que observar que si las congruencias 3.3.4tienen solucin, dos cualesquiera de ellas tambin la tienen, as que por el teorema1.10.1, deben verificarse las condiciones 3.3.5.

Demostramos por induccin que estas condiciones son suficientes: El teore-ma 1.10.1 es el caso r = 2. Supongamos que el resultado es cierto para r 1congruencias. Con esta hiptesis existe una solucin

x0 ai (mod mi) i = 1, 2, . . . , r 1 (1.10.4)y cualquier otra solucin x debe ser de la forma x x0 (mod Mr1), Mr1 =[m1, . . . , mr1]. Para que x sea solucin de todas las ecuaciones 3.3.4 debe sa-tisfacer adems x ar (mod mr). Por el teorema 1.10.1 concluimos que esteconjunto de congruencias tiene solucin slo cuando

x0 ar (mod (Mr1, mr)) (1.10.5)

y que en este caso existe una solucin nica mdulo [Mr1, mr] = Mr.Queda por comprobar que el x0 hallado verifica las condiciones 1.10.5. Por el

lema 1.10.6 tenemos que

(Mr1, mr) = ([m1, . . . , mr1], mr) = [(m1, mr), . . . , (mr1, mr)]

por lo que el sistema de congruencias 1.10.5 es equivalente al sistema

x0 ar (mod (mi, mr)), i = 1, 2, . . . , r 1Pero estas ltimas se derivan fcilmente de las hiptesis.


39/139


40/139


41/139

1.10. TEOREMA CHINO DE LOS RESTOS 41

En la frmula 1.10.7 para calcular los multiplicadores biM/mi slo hacen falta

los nmeros mi. Por tanto, si hay que resolver varios sistemas de congruencias conlos mismos mdulos, la expresin 1.10.7 es particularmente adecuada porque hayque calcular los multiplicadores slo una vez.

Ejemplo 1.10.12. Leonardo discute en el Liber Abaci la siguiente cuestin: Se lepide a alguien que piense un nmero. Entonces se le piden los restos del nmero

al dividirlo por5, 7 y 9 y con esta informacin se adivina el nmero pensado.Vamos a denotar como x al nmero desconocido y por a1, a2, a3 a los tres

restos de forma que

x a1 (mod 5) x a2 (mod 7) x a3 (mod 9)

Los mdulos son primos relativos y M = 5 7 9 = 315,M

m1= 63,

M

m2= 45,

M

m3= 35

Las congruencias lineales

63b1 1 (mod 5), 45b2 1 (mod 7), 35b1 1 (mod 9)tienen las soluciones b1 = 2, b2 = 5, b3 = 8 as que la frmula 1.10.7 nos da

x 126a1 + 225a2 + 280a3 (mod 315)

De esta expresin obtenemos x segn los restos conocidos a1, a2, a3. La solucines nica slo si se exige que el nmero requerido sea menor que 315.

Ejemplo 1.10.13. ((Regiomontanus). Hallar un nmero x tal que

x 3 (mod 10), x 11 (mod 13), x 15 (mod 17)Ejemplo 1.10.14. ((Euler). Hallar un nmero x tal que

x 3 (mod 11), x 5 (mod 19), x 10 (mod 29)Concluimos con una observacin que se aplicar despus: Supongamos que

al resolver un problema hay que determinar un nmero x que para un mdulo m1

tiene s1 valores admisiblesx a1, . . . , as1 (mod m1)

y para otro mdulo m2 hay s2 valores admisibles

x b1, . . . , bs2 (mod m2)Cuando (m1, m2) = 1 cada valor mi puede combinarse con cada valor bj, as queen total hay s1 s2 soluciones mdulo m1m2. Esta observacin puede generalizarsea rmdulos primos relativos dos a dos.


42/139


Ejemplo 1.10.15. Vamos a resolver la ecuacin

x2 1 (mod 40)Es inmediato comprobar que esa ecuacin equivale al sistema

x2 1 (mod 5) x2 1 (mod 8)Como los mdulos son pequeos, por prueba y error vemos que las soluciones deestas ecuaciones son

x 1, 4 (mod 5) x 1, 3, 5, 7 (mod 8)El algoritmo de Euclides nos dice que (

3)

5 + 2

8 = 1. El teorema chino de los

restos nos dice que x 16ai 15bj (mod 40) donde ai = 1, 4 y bj = 1, 3, 5, 7.Despus de reducir mdulo 40 obtenemos todas las soluciones:

x 1, 11, 21, 31, 9, 19, 29, 39 (mod 40)Resulta bastante mas dificil resolver congruencias del tipo akxk + + a1x +

a0 0 (mod n). Utilizando el teorema chino de los restos el problema se reducea resolver congruencias mdulo pe para factores primos de n. Y las solucionesmdulo pe se determinan a partir de las soluciones mdulo primo p. Si el primop es pequeo, estas ltimas pueden obtenerse por prueba y error, sencillamentesustituyendo sucesivamente 0, 1, . . . , p 1 en la congruencia. Adems podemosutilizar el teorema de Fermat que hay mas adelante para reducir el problema a unodonde el grado del polinomio sea menor que p

1.11. Los anillos ZnAl trabajar con congruencias hemos visto que en cualquier clculo los n-

meros congruentes son intercambiables. Vamos a formalizar este punto de vista.Consideramos como un ente individual a toda una clase de enteros congruentesy trabajamos con estas clases igual que con los enteros ordinarios. El motivo deintroducir la notacin que viene a continuacin es permitirnos usar nuestra ex-

periencia con los enteros ordinarios como una gua para trabajar con congruen-cias. Muchas de las propiedades de la aritmtica entera se verifican tambin en laaritmtica de congruencias. La excepcin mas notable es que el producto de dosclases de congruencia no nulas puede ser cero.

Definicin 1.11.1. San a, n Z con n > 0. Llamamos clase de congruencia de amdulo n al conjunto de todos los enteros que son congruentes con a mdulo n.La denotamos por a + nZ o por [a]n:

a + nZ = [a]n = {x Z | x a (mod n)}


43/139

1.11. LOS ANILLOS ZN 43

El conjunto de todas las clases de congruencia mdulo n se llama conjunto de los

enteros mdulo n y se representa por Zn.Ntese que [a]n = [b]n si y slo si a b (mod n). Cuando el mdulo n est

claro del contexto suprimimos el ndice y escribimos slo [a].Una clase de congruencia puede designarse de infinitas maneras. Por ejemplo,

[5]3 = [83] = [1]3 = . . . . A un elemento a de la clase [a]n le llamamos repre-sentante de la clase. Toda clase de congruencia [a]n tiene un nico representanter tal que 0 r < n (a saber, r es el resto de dividir a entre n). Esto demuestraque hay exactamente n clases de congruencias mdulo n distintas. Por ejemplo,los elementos de Z3 son

[0]3 = {. . . , 9, 6, 3, 0, 3, 6, 9, . . . }[1]3 = {. . . , 8, 5, 2, 1, 4, 7, 10, . . . }[2]3 = {. . . , 7, 4, 1, 2, 5, 8, 11, . . . }

Cada entero pertenece exactamente a una clase de congruencia mdulo 3, por-que el resto de dividir por 3 es nico. En general, cada entero pertenece a unanica clase de congruencia mdulo n, luego

Zn = {[0]n, [1]n, . . . , [n 1]n}El conjunto Z2 tiene exactamente dos elementos: [0]2 es el conjunto de los enteros

pares y [1]2 es el de los impares. Con esta notacin las conocidas reglas par +par = par, impar + par = impar, impar + impar = par se expresan como[0]2 + [0]2 = [0]2, [1]2 + [0]2 = [1]2, [1]2 + [1]2 = [0]2. De la misma forma,las reglas par par = par, impar par = par, impar impar = impar seexpresan como [0]2 [0]2 = [0]2, [1]2 [0]2 = [0]2, [1]2 [1]2 = [1]2. Estas reglaspueden resumirse dando una tabla de adicin y una tabla de multiplicacin paraZn:

+ 0 10 0 11 1 0

0 10 0 01 0 1

En estas tablas hemos utilizado una simplificacin habitual al tratar con con-gruencias: Omitimos el subindice e incluso los corchetes y escribimos a en lugarde [a]n.

Para Zn se introducen una suma y un producto anlogos: Dados [a]n, [b]n Zndefinimos

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


44/139


Proposicin 1.11.2. Sea n un entero positivo y sean a, b, a1, b1Z tales que

[a]n = [a1]n y [b]n = b1]n. Entonces [a + b]n = [a1 + b1]n y [a b]n = [a1 b1]n.Esta proposicin dice que la suma y multiplicacin de clases de congruencia

estn bien definidas, es decir que son independientes de los representantes queescojamos en cada clase.

Las leyes asociativas y conmutativas de la suma y el producto, la ley distribu-tiva y la existencia de neutros son vlidas en Zn. Si [a]n + [b]n = [0]n, la clase [b]nse llama opuesta a la clase [a]n. El opuesto de una clase es nico. Es fcil ver quede hecho el opuesto de [a]n es [a]n. Se denota por [a]n = [a]n. En general nose verifican las leyes de integridad y cancelativa.

Definicin 1.11.3. Sean [a]n, [b]n Zn con [b]n [0]n y [a]n[b]n = [0]n. Entonces[a]n se llama divisor de cero.

Proposicin 1.11.4. Sea [a]n un no divisor de cero y sea [a]n[b]n = [a]n[c]n.Entonces [b]n = [c]n.

Definicin 1.11.5. Sean [a]n, [b]n Zn tales que [a]n[b]n = [1]n. Entonces de-cimos que [a]n, [b]n son elementos invertibles o unidades de Zn y que [b]n es uninverso de [a]n. Denotamos [b]n = [a]1n .

Obsrvese que si [a] es invertible, no puede ser divisor de cero.

Proposicin 1.11.6. Sea n un entero positivo.

1. La clase [a]n tiene un inverso multiplicativo en Zn si y slo si (a, n) = 1.

2. Un elemento no nulo de Zn o es invertible o es divisor de cero.

Demostracin. 1. Supongamos que [a] tiene un inverso [a]1 = [b]. Entonces[ab] = [a][b] = [1], luego ab 1 (mod n), lo que implica que ab = qn + 1para algn entero q. O sea que ab + (q)n = 1 y por tanto (a, n) = 1.A la inversa sea (a, n) = 1. Entonces existen b, c Z tales que ab + cn = 1.Reduciendo mdulo n vemos que ab

1 (mod n) y por tanto [a][b] =

[ab] = [1].2. Sea [a] 0 lo que equivale a n a. Si (a, n) = 1 entonces[a] tiene un

inverso, En otro caso (a, n) = d > 1 Como d | a y d | n existen enteros k, btales que n = kd y a = bd. Entonces [k] [0] pero [a][k] = [ak] = [bdk] =[bn] = [0], lo que muestra que [a] es un divisor de cero.

Corolario 1.11.7. Para un mdulo n > 0 las siguientes condiciones son equiva-lentes:


45/139


1. El nmero n es primo.

2. Zn no tiene divisores de cero no nulos.

3. Todo elemento no nulo de Zn tiene un inverso multiplicativo.

La demostracin de la proposicin 1.11.6 muestra que si (a, n) = 1 entoncespodemos calcular el inverso multiplicativo de a utilizando el algoritmo extendidode Euclides:

Ejemplo 1.11.8. Para hallar [11]1 Z16 realizamos el siguiente clculo:

16 0 1

11 1 05 1 11 3 20 16 11

luego 11 3 + 16 (2) = 1, lo que muestra que [11]1 = [3].Hay otros dos mtodos para hallar el inverso multiplicativo de [a]n en Zn: Si

el mdulo n es pequeo, a veces es mas corto hacerlo por prueba y error. La otraforma es calculando las potencias sucesivas de [a]. Si (a, n) = 1, entonces [a] no esdivisor de cero en Zn y por tanto ninguna potencia [a]k puede ser cero. El conjunto

{[a], [a]2, [a]3, . . .

}tiene menos de n elementos distintos, luego en algn punto

debe repetirse. Sean k < m tales que [a]m = [a]k. Entonces [a]mk = [a]0 = [1].Esto muestra que en la primera repeticin debe ser k = 0 y por tanto [a]m = [1].De aqu vemos que [a]m1 = [1].

Ejemplo 1.11.9. Volvamos a calcular [11]116 . Para ello listamos las potencias su-cesivas de [11]16:

[11]2 = [5]2 = [25] = [9][11]3 = [11]2[11] = [9][11] = [99] = [3]

[11]4 = [11]3[11] = [3][11] = [33] = [1]

luego [11]1 = [11]3 = [3].Podemos ahora estudiar ecuaciones en Zn. La congruencia lineal ax b

(mod n) puede verse ahora como una ecuacin lineal [a]n[x]n = [b]n en Zn. Si[a]n tiene inverso, esta ecuacin tiene solucin nica [x] = [a]1n [b]n. Ntese quesin la nocin de clase de congruencia tenemos que modificar la afirmacin de uni-cidad para decir que si x0 es una solucin de ax b (mod n), tambin lo esx0 + qn para cualquier entero q.

Vamos a ver finalmente dos teoremas que permiten rebajar el grado de lasecuaciones polinmicas en Zn.


46/139


Definicin 1.11.10. Sea n un entero positivo. El nmero de enteros positivos me-

nores o iguales que n y que son primos relativos con n se denota (n). Esta funcinse llama funcin de Eulero funcin tociente.

Ntese que (1) = 1. Para n > 1 el valor de (n) puede obtenerse de lafactorizacin en primos:

Lema 1.11.11. Sea n = pe. Entonces (n) = pe pe1 = n(1 1/p)Demostracin. Un entero m es primo relativo con pe si y slo si es primo conp. Como p es primo, esto quiere decir que m no es primo relativo con pe si yslo si es un mltiplo de p. El nmero de todos los enteros entre 1 y pe es pe. El

nmero de mltiplos de p entre 1 y pe

es pe

1

. Restando obtenemos el resultadodel lema.

Lema 1.11.12. Sean m, n enteros positivos primos relativos. Entonces (mn) =(m)(n).

Demostracin. Definimos una aplicacin f : Zmn Zm Zn (el producto carte-siano mediante f([a]mn) = ([a]m, [a]n). Por el teorema chino de los restos, f s unabiyeccin. Es fcil comprobar que f[a]mn[b]mn) = f([a]mn)f([b]mn). En particular[a]mn ser invertible si y slo si lo son ambas [a]m y [a]n. Pero para cualquier kla clase [a]k es invertible si y slo si (a, k) = 1. As que por restriccin, f esta-

blece una biyeccin entre los enteros positivos menores o iguales que mn primosrelativos con mn con el conjunto de pares de enteros positivos donde la primeracomponente sea menor o igual que m y primo relativo con m y la segunda seamenor o igual que n y primo relativo con n. Contando estos pares obtenemos elresultado buscado.

Proposicin 1.11.13. Sea n = pe11 pe22 . . . p

ekk

la factorizacin en primos de n. En-

tonces

(n) = n

1 1

p1

1 1

p2

. . .

1 1

pk

Demostracin. Consecuencia inmediata de los dos lemas anteriores:

(n) = (pe11 ) . . . (pekk

)

por el lema 1.11.12 y aplicando a cada factor el lema 1.11.11 obtenemos el resul-tado final.

Ejemplo 1.11.14. Las frmulas de la proposicin anterior nos dicen que

(10) = 10

1 1

2

1 1

5

= 4


47/139


y que

(36) = 361 1

2

1 1

3

= 12

Definicin 1.11.15. El conjunto de unidades de Zn, es decir el conjunto de clases[a]n con (a, n) = 1 se denota por Zn .

Proposicin 1.11.16. El conjunto Zn es cerrado para la multiplicacin.

Demostracin. Es inmediato comprobar que ([a][b])1 = [b]1[a]1.

El conjunto Zn tiene (n) elementos. El siguiente teorema debe verse como un

resultado sobre potencias de elementos de Zn :Teorema 1.11.17 (Euler). Sea (a, n) = 1. Entonces a(n) 1 (mod n).

Demostracin. En el conjunto Zn existen (n) elementos que tienen un represen-tante primo relativo a n. Sean estos {a1, . . . , a(n)}. Las clases representadas por{aa1, . . . , aa(n)} son todas distintas porque (a, n) = 1. Como cada producto aaies primo relativo con n, tenemos un representante de cada una de las clases departida. Por tanto

a1a2 . . . a(n) (aa1)(aa2) . . . (aa(n)) a(n)a1a2 . . . a(n) (mod n)

Ya que el producto a1a2 . . . a(n) es primo relativo con n podemos simplificarlo ynos queda la congruencia

1 a(n)

Corolario 1.11.18 (Teorema de Fermat). Sea p un primo. Entonces ap a paratodo entero a.

Demostracin. Si p | a, entonces ap 0 a (mod p). Si p a entonces(a, p) = 1 y el teorema de Euler nos dice que a(p)

1 (mod p). Pero (p) =

p 1. Multiplicando ambos miembros por a tenemos el resultado buscado.

El teorema de Fermat proporciona un criterio de nmero compuesto: Sea nun nmero del que queremos averiguar si es primo o compuesto. Tomamos un aprimo relativo con n (por ejemplo, a = 2) y calculamos b an1 (mod n). Sib 1, el nmero n es compuesto. Pero si b = 1 no sabemos si el nmero n esprimo o compuesto. Naturalmente podemos probar con otra base a distinta, peroaunque para varios a se verifique que an1 1 (mod n), no podemos concluirque n sea primo. De hecho existen nmeros n tales que an1 1 (mod n) para


48/139


todo a primo relativo con n. Tales nmeros se llaman nmeros de Carmichael, hay

2163 entre 1 y 25 109 y el mas pequeo es 561 = 3 11 17.El criterio anterior se puede afinar (vase cualquier libro sobre teora de n-

meros), pero an los criterios mejorados no son concluyentes (existen nmeroscompuestos que los pasan). Para finalizar vamos a ver un criterio de primalidadde inters terico, aunque poco prctico.

Lema 1.11.19. Sea p un primo. Entonces a2 1 (mod p) si y slo si a 1(mod p) o a 1 (mod p)Demostracin. La hiptesis es que p | (a2 1) = (a 1)(a + 1). Por ser p primotiene que dividir a uno de los factores.

En trminos de clases de restos este lema dice que [a]1p = [a]p si y slo si[a]p = [1].Teorema 1.11.20 (Teorema de Wilson). Un entero positivo p es primo si y slosi (p 1)! 1 (mod p)Demostracin. Supongamos que (p 1)! 1 (mod p). Entonces existe unentero q tal que qp (p 1)! = 1, as que m. c. d.(p, (p 1)!) = 1 y p no esdivisible por ningn entero menor que p y mayor que 1 (todos ellos dividen a(p 1)!. Luego p es primo.

A la inversa sea p primo distinto de 2 (el caso p = 2 se comprueba fcilmente).Multiplicamos todas las clases [1]p [2]p [p1]p. Por el lema 1.11.19, para cadaclase [a]p en este producto, salvo la primera y la ltima, tambin [a]1p est en elproducto. Y el producto vale [a]p[a]1p = 1. Luego [(p 1)!]p = [p 1]p = [1]p.Pero este es el resultado buscado.


49/139

Bibliografa

[1] J. A. Beachy and W. D. Blair, Abstract Algebra, Waveland Press 1996

[2] P. M. Cohn, Algebra I, Wiley and sons 1977[3] D. S. Dummit and R. M. Foote, Abstract Algebra, Prentice-Hall 1991

[4] O. Ore, Number Theory and its History, Academic Press

49


50/139

50 BIBLIOGRAFA


51/139


52/139

52 CAPTULO 2. ANILLOS CONMUTATIVOS

Ejemplo 2.1.4. Sea Xun conjunto y sea A =

{f : X

X

}el conjunto de todas las

aplicaciones de X en s mismo. Podemos definir una operacin A A A por(f, g) f g donde f g : X X viene dada por composicin de aplicaciones, esdecir que para todo x X se define (f g)(x) = f(g(x)).Ejemplo 2.1.5. Para cualquier K-espacio vectorial V la multiplicacin de un esca-lar por un vector define una accin K V VEjemplo 2.1.6. Sea M = Mn(R) el conjunto de todas las matrices cuadradas deorden n con coeficientes reales. En M hay definidas dos operaciones internas, lasuma y el producto, y una operacin externa, el producto de un escalar por unamatriz.

Ejemplo 2.1.7. Dada una ley de composicin a b, se define la ley de composi-cin opuesta como a o b = b a para todo a, b. Si la ley de partida es internaA A A, tambin lo es la opuesta. Si la ley es una accin por la izquierda, laopuesta es una accin por la derecha y viceversa.

Una estructura algebraica se define por datos de tres tipos:

Un conjunto A, que se llama conjunto subyacente.

Una o varias leyes de composicin (internas o externas) definidas sobre A.

Unos axiomas que deben verificar dichas leyes.

En rigor la estructura algebraica est formada por el conjunto A junto con lasoperaciones. Pero por abuso de lenguaje, se suele designar con la misma letra a laestructura y al conjunto subyacente.

Existen muchas estructuras algebraicas, pero las mas importantes son las tressiguientes:

Definicin 2.1.8. Un grupo (G, ) es un conjunto G junto con una ley de compo-sicin interna G G G denotada por (a, b) a b que verifica:

Asociatividad: a, b, c G a (b c) = (a b) c

Existencia de neutro: e G a G e a = a = a e

Existencia de opuesto: a G a G a a = e = a a


53/139

2.1. LEYES DE COMPOSICIN. ESTRUCTURAS ALGEBRAICAS. 53

El elemento e se llama elemento neutro para la operacin y el elemento a se

llama opuesto de a.En el caso particular en que la operacin se denote por a + b, el elemento

neutro se llama elemento nulo o cero y se denota por 0. El opuesto de a se denotapor a

Si la operacin se denota por ab, a b o a b, el elemento neutro se llamaunidad o uno y se denota por 1. Y el opuesto de a se llama inverso y se denota pora1.

Un grupo se llama conmutativo o abeliano si verifica el axioma adicional

Conmutatividad: a, b G a b = b a.

Definicin 2.1.9. Un anillo (A, +, ) es un conjunto A junto con dos operacionesbinarias A A A denotadas por suma a + b y producto ab que verifican losaxiomas:

Asociatividad de la suma: a, b, c A a + (b + c) = (a + b) + cExistencia de cero: 0 A a A 0 + a = a = a + 0Existencia de opuesto:

a

A

a

A a + (

a) = 0 = (

a) + a

Conmutatividad de la suma: a, b A a + b = b + a.Estos cuatro primeros axiomas se resumen en uno: (A, +) es un grupo abe-liano.

Asociatividad del producto: a, b, c A a(bc) = (ab)cDistributividad: a, b, c A a(b + c) = ab + ac, (b + c)a = ba + caExistencia de uno: 1 A a A 1a = a = a1

Un anillo se llama conmutativo o abeliano si verifica el axiomaConmutatividad del producto: a, b A ab = ba.

Un anillo de divisin es un anillo que verifica el axioma adicional

Existencia de inverso: a A a1 A aa1 = 1 = a1aUn cuerpo es un anillo de divisin conmutativo.


54/139


Definicin 2.1.10. Sea A un anillo. Un mdulo por la izquierda sobre A o A-

mdulo (M, +, ) es un conjunto M junto con una ley de composicin internaM M M dada por (x,y) x + y y una ley de composicin externaA M M denotada (a, x) ax que verifican los axiomas:

Asociatividad: x,y,z M x + (y +z) = (x +y) +zExistencia de cero: 0 M x M0 + x = x = x + 0Existencia de opuesto: x M x M x + (x) = 0 = (x) + xConmutatividad: x,y M x +y = y + x.

Estos cuatro primeros axiomas pueden resumirse en uno: (M, +) es un grupoabeliano.

Distributividad respecto a escalares: a, b A x M(a + b)x = ax + bxDistributividad respecto a vectores: a A x,y M a(x +y) = ax + ayPseudoasociatividad: a, b A x M a(bx) = (ab)xAccin trivial del uno: x M1x = x

Los elementos de M se llaman vectores y los elementos de A se llaman esca-

lares.En el caso particular en que A es un cuerpo, M se llama espacio vectorialsobre A.

De manera anloga se define el concepto de mdulo por la derecha sobre A.

2.2. Ejemplos

El que una estructura algebraica resulte interesante depende del nmero e im-

portancia de los ejemplos que posea. Veamos ejemplos de las estructuras que he-mos definido:

2.2.1. Ejemplos de grupos

Ejemplo 2.2.1. Sea G = {e} un conjunto con un nico elemento. Slo hay unaoperacin binaria posible, e e = e. Este grupo (G, ) es el mas pequeo posibley se llama grupo trivial. Cualquier grupo con mas de un elemento es un grupo notrivial.


55/139

2.2. EJEMPLOS 55

Ejemplo 2.2.2. Para cualquier grupo (G,

),el grupo opuesto Go eselgrupo(G,

o)

donde o es la operacin opuesta de . En particular, G es abeliano si y slo siG = Go.

Ejemplo 2.2.3. Los ejemplos mas sencillos de grupos son los numricos. Los ca-sos mas evidentes son:

1. Z, Q, R y C son grupos para +, siendo 0 el elemento neutro y a el opuestode cada a.

2. Q = {a Q | a 0}, R = {a R | a 0}, C = {a C | a 0},Q+ = {a Q | a > 0} y R+ = {a R | a > 0} son grupos para con 1 comoelemento neutro y siendo el opuesto de a su inverso a

1= 1/a. (Nteseque {a Z | a 0} no es un grupo para , ya que no todo elemento tiene

inverso).

3. Generalizamos el ejemplo anterior: Sea A un anillo arbitrario y sea A =U(A) el conjunto de elementos a A que tienen un inverso a1 A. En-tonces (A, +) es un grupo (el grupo aditivo de A), y (A, ) tambin es ungrupo (el grupo multiplicativo de A), .

4. Los axiomas para un espacio vectorial V sobre un cuerpo K incluyen enparticular el hecho de que (V, +) es un grupo abeliano. En particular, Rn es

un grupo aditivo.

5. Para todo nmero n Z, n > 0, Z/nZ es un anillo, as que (Z/nZ, +)y ((Z/nZ), ) son grupos, donde (Z/nZ) = U(Z/nZ) = {a Z/nZ |(m. c. d.(a, n) = 1}.

No deben confundirse los grupos Z/nZ (bajo la suma) y (Z/nZ) (bajo multi-plicacin), aunque el ltimo sea un subconjunto del primero, no es un subgrupo.

2.2.2. Ejemplos de anillos

Ejemplo 2.2.4. Sea A = {a} un conjunto con un nico elemento. En este caso slohay una operacin binaria posible, y por tanto la suma y el producto coinciden:a + a = a = aa y 0 = a = 1. Este anillo (A, +, ) es el mas pequeo posible yse llama anillo trivial. Cualquier anillo con mas de un elemento es un anillo notrivial.

Ejemplo 2.2.5. Para cualquier anillo (A, +, ), definimos el anillo opuesto Ao comoel anillo (A, +, o) donde o es la operacin opuesta de ; en particular, A es abelianosi y slo si A = Ao.


56/139


Ejemplo 2.2.6. Z,Q,R y C son anillos conmutativos respecto a la suma y producto

usuales. En todos los casos el neutro para la suma es el nmerol 0 y el neutro parael producto es el nmero 1. Adems Q,R y C son cuerpos.

Ejemplo 2.2.7. Para todo natural positivo n las clases de restos mdulo n, Zn conla suma y producto de clases es tambin un anillo conmutativo. Este anillo es uncuerpo si y slo si n es primo.

Ejemplo 2.2.8. Sea J = {a + bi | a, b Z, i2 = 1} C. Para cualesquieraa + bi, c + di J se verifica

(a + bi) + (c + di) = (a + c) + (b + d)i J,

(a+

bi)(c+

di)=

(ac bd)+

(ad+

bc)i J,0, 1 J,(a + bi) = (a) + (b)i J.

Como la suma y el producto de nmeros complejos son asociativas y conmutativasy verifican la distributividad, tenemos un anillo conmutativo (J, +, ) que se llamaanillo de los enteros de Gauss.

Ejemplo 2.2.9. Sea Q(

2) = {a + b

2 R | a, b Q}. Es obvio que esteconjunto es cerrado para la suma y el producto, y como estas operaciones sonasociativas y conmutativas en R, tambin lo son en Q(

2). De la misma manera se

comprueba que el producto es distributivo respecto a la suma. Adems 0 = 0+0 2y 1 = 1 + 0

2 pertenecen a Q(

2), y para todo x = a + b

2 Q(

2) se verifica

que x = (a) + (b)

2 Q(

2). En resumen, Q(

2) es un anillo.Para ver que es un cuerpo, observamos que para todo a + b

2 Q distinto de

cero se verifica que a2 2b2 0 (porque en otro caso,

2 sera racional). As que

1

a + b

2=

a b

2

(a + b

2)(a b

2)=

a b

2a2 2b2 =

a

a2

2b2

+b

a2

2b2

2 Q(

2)

luego es un cuerpo.

Ejemplo 2.2.10. Un subconjunto interesante del ejemplo anterior es

Z[

2] = {m + n

2 | m, n Z}

que obviamente es cerrado para la suma, el producto, el cero y el uno. Para unelemento u = m + n

2 Z[

2] el inverso u1 pertenece a Z[

2] si y slo si

m2 2n2 = 1.


57/139

2.2. EJEMPLOS 57

Ejemplo 2.2.11. Un tipo de anillos importantes son los anillos de funciones. Sea

X cualquier conjunto no vaco y sea A un anillo arbitrario. Sea B = {f : X A}. Definimos en B una suma y un producto punto apunto: (f + g)(x) = f(x) +g(x) y (f g)(x) = f(x)g(x). De cada axioma de anillo de A se deduce el axiomacorrespondiente en B. El anillo B es conmutativo si y slo si lo es A.

Si X y A tienen mas estructura podemos formar otros anillos de funcionesque respetan esta estructura. Por ejemplo si A = R y X es el intervalo cerradoX = [0, 1] R podemos formar el anillo conmutativo B de las funciones continuas[0, 1] R. Los teoremas bsicos sobre lmites nos garantizan que la suma y elproducto de funciones continuas son tambin funciones continuas.

Ejemplo 2.2.12. Sea A un anillo arbitrario y sea n > 0 un entero. Sea Mn(A) el

conjunto de todas las matrices n n con coeficientes en A. Este conjunto es unanillo para las operaciones usuales de suma y producto de matrices. Si n > 1, elanillo Mn(A) no es conmutativo

Ejemplo 2.2.13. Sea A un anillo conmutativo. El conjunto A[X] de todos los po-linomios en una indeterminada con coeficientes en A junto con la suma y el pro-ducto es un anillo conmutativo.

2.2.3. Ejemplos de mdulos

Ejemplo 2.2.14. El grupo abeliano Zn es un Z-mdulo con la accin Z Zn Zndefinida por a[b]n = [ab]n.Ejemplo 2.2.15. Todo grupo abeliano M es un Z-mdulo de manera nica, defi-niendo la accin Z M M por induccin:

ax =

0 si a = 0

(a 1)x + x si a > 0(ax) si a < 0

Ejemplo 2.2.16. El conjunto de vectores libres (del plano o del espacio) con lasuma por la regla del paralelogramo y el producto escalar usual forman un es-pacio vectorial sobre R (De hecho la nomenclatura y las propiedades intuitivasprovienen de este ejemplo).Ejemplo 2.2.17. Sean K un cuerpo, M un espacio vectorial sobre K y t : M Muna aplicacin lineal. Definimos una ley externa K[X] M M como

(amXm

+ am1Xm1

+ + a2X2 + a1X + a0) u =amt

m(u) + am1tm1(u) + + a2t2(u) + a1t(u) + a0u

Con esta operacin, M pasa a ser un K[X]-mdulo (de hecho, todos los K[X]-mdulos se obtienen de esta manera).


58/139


2.3. Reglas de clculo

De los axiomas de cada estructura algebraica se deducen unas cuantas conse-cuencias sencillas pero importantes para manipular expresiones y realizar clcu-los en la estructura, y por ello se llaman reglas de clculo. Vamos a estudiar lascorrespondientes a grupos y anillos.

2.3.1. Reglas de clculo para grupos

Proposicin 2.3.1. Sea G un grupo con unidad e.

1. La unidad de un grupo es nica

2. El inverso de cualquier elemento es nico

3. (Propiedad cancelativa): Para x,y,z G,

xy = xz y = z yx= zx y = z

4. e1 = e

5. Para todo elemento x G se verifica (x1)1 = x

6. Para cualesquiera x,y G se verifica (xy)1

= y1x

1

7. Para cualesquiera x,y G existen nicos u, v G tales que xu = y y vx = y.Demostracin. 1. Sean e, f G dos unidades. Entonces e = e f = f

2. Sean x, x1 dos inversos para x G. Entonces x = xe = x(xx1) =(xx)x1 = ex1 = x1

3. Sea xy = xz. Multiplicamos ambos miembros por x1 por la izquierda: y =ey = (x1x)y = x1(xy) = x1(xz) = (x1x)z = ez = z. Igual por el otro lado.

4. De la misma definicin: ee = e, luego e = e1

5. Por definicin, xx1 = e = x1x, luego de la misma definicin de inversoobtenemos que (x1)1 = x

6. Un simple clculo: (y1x1)(xy) = y1(x1x)y = e, luego (xy)1 = y1x1

7. Otro simple clculo muestra que u = x1y y v = yx1 verifican las condicio-nes pedidas y son los nicos que las verifican.


59/139

2.3. REGLAS DE CLCULO 59

Las propiedad asociativa garantiza que en un clculo podemos introducir pa-

rntesis arbitrariamente: Sean x1, . . . xn G. Definimos por recurrencia:

ni=1 xi =(n1

i=1 xi)xn.

Proposicin 2.3.2 (Ley asociativa general). Sea G un conjunto con una ope-racin interna asociativa. Para cualesquiera enteros m > n > 0 sean x1, . . . xmelementos de G. Se verifica

n

i=1

xi

mi=n+1

xi

=m

i=1

xi

Demostracin. Por induccin sobre m

n (el nmero de factores del segundoproducto). Si m n = 1, la expresin dada es

n

i=1

xi

xn+1 =n+1i=1

xi

Sea ahora m n = k > 1 y suponemos cierto el resultado cierto siempre queel segundo producto del primer miembro tenga menos de k factores. Calculamosusando la propiedad asociativa:

n

i=1xi

mi=n+1

xi =

ni=1

xi

m1

34412300 Algebra Basica

Documents

Transcript of 34412300 Algebra Basica