Curso de conjuntos y n´umeros. Guiones de clase Claudi Busqu´e Roca Manuel Saor´ın Casta˜ no Juan Jacobo Sim´on Pinero

´Indice general I

Conjuntos

3

1. Conjuntos y elementos 1.1. Sobre el concepto de conjunto y elemento. . . . . . . . . . . 1.2. Pertenencia, contenido e igualdad. . . . . . . . . . . . . . . 1.3. Operaciones con subconjuntos . . . . . . . . . . . . . . . . 1.3.1. Familias de conjuntos y operaciones . . . . . . . . . 1.4. Pares ordenados, producto cartesiano y relaciones binarias

. . . . .

. . . . .

. . . . .

4 4 4 6 8 9

2. Aplicaciones 2.1. Relaciones y aplicaciones . . . . . . . . . . . . 2.2. Tipos de aplicaciones . . . . . . . . . . . . . . 2.3. Im´ agenes directas e inversas . . . . . . . . . . 2.4. Composici´ on . . . . . . . . . . . . . . . . . . 2.5. Aplicaci´ on inversa de una aplicaci´on biyectiva

. . . . .

. . . . .

. . . . .

12 12 13 13 14 16

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3. Orden 18 3.1. Conjuntos ordenados y sus elementos distinguidos . . . . . . . . 18 3.2. Axioma de elecci´ on y algunos equivalentes. Buena ordenaci´on . . 21 3.2.1. Ap´endice: conjuntos ordenados finitos. . . . . . . . . . . . 23 4. Relaciones de equivalencia 4.1. Conceptos b´ asicos . . . . 4.2. Clases de equivalencia . . 4.3. Conjunto cociente . . . . 4.4. Relaciones de equivalencia

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

25 25 26 27 27

5. Conjuntos num´ ericos 5.1. Cardinalidad. Conjuntos finitos e infinitos . . . . 5.2. N´ umeros naturales . . . . . . . . . . . . . . . . . 5.3. Conjuntos numerables y no numerables . . . . . 5.4. N´ umeros enteros . . . . . . . . . . . . . . . . . . 5.5. N´ umeros racionales . . . . . . . . . . . . . . . . . 5.5.1. Escritura decimal de n´ umeros racionales. 5.6. N´ umeros reales . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

29 29 31 32 34 36 38 43

. . . y

. . . . . . . . . . . . . . . . . . . . . particiones

1

. . . .

. . . .

. . . .

. . . .

5.7. N´ umeros complejos . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7.1. Forma exponencial de un n´ umero complejo. . . . . . . . .

II

N´ umeros y polinomios

44 47

49

6. Los n´ umeros enteros. 6.1. Artim´etica de los enteros. . . . . . . . . . . . . . . 6.1.1. Divisi´ on entera y m´aximo com´ un divisor. . 6.1.2. M´ınimo com´ un m´ ultiplo . . . . . . . . . . . 6.1.3. La ecuaci´ on diof´antica lineal . . . . . . . . 6.1.4. M´ umeros primos. Teorema fundamental de la aritm´etica . . . 6.2. Congruencias. . . . . . . . . . . . . . . . . . . . . . 6.2.1. Propiedades aritm´eticas de las congruencias 6.2.2. Algunas aplicaciones . . . . . . . . . . . . . 6.3. Congruencias de Euler y Fermat . . . . . . . . . . 6.4. Teorema chino de los restos . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

50 50 50 56 57

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

58 60 61 64 67 68

7. Polinomios 7.1. Polinomios con coeficientes en un cuerpo. . . . . . 7.2. Ra´ıces de polinomios. . . . . . . . . . . . . . . . . 7.3. Polinomios irreducibles en R[X] y C[X]. Teorema del ´ algebra. . . . . . . . . . . . . . . . . . . . . . . 7.4. Factores m´ ultiples. . . . . . . . . . . . . . . . . . . 7.5. Polinomios irreducibles en Q[X]. . . . . . . . . . .

. . . . . . . . . . . . . . . . fundamental . . . . . . . . . . . . . . . . . . . . . . . .

2

72 72 77 79 81 82

Parte I

Conjuntos

3

Cap´ıtulo 1

Conjuntos y elementos 1.1.

Sobre el concepto de conjunto y elemento.

Comenzamos con la definici´on de conjunto de G. Cantor: Un conjunto es una colecci´ on (dentro de un todo) de distintos objetos definidos por nuestra intuici´ on o pensamiento Esta forma de abordar los conjuntos se llama concepci´on intuitiva de los conjuntos. La noci´ on formal de conjunto corresponde con fundamentos de la matem´ atica que quedan fuera del alcance de nuestro curso. Tambi´en queda fuera del nuestro alcance el concepto de pertenencia. Vamos a asumir entonces que hay unos objetos que llamamos conjuntos que poseen unos objetos que llamamos elementos.

1.2.

Pertenencia, contenido e igualdad.

Las colecciones con las que construiremos conjuntos ser´an por lo pronto de dos formas. 1. Por extensi´ on: haciendo la lista de objetos. Por ejemplo A = {X1 , . . . , Xn , . . . } o A = {a, b, c, . . . }. 2. Por comprehensi´ on: a trav´es de una f´ormula proposicional que siempre tendr´ a, a su vez, un conjunto de referencia. Por ejemplo, si B es un conjunto, A = {X ∈ B | p(X) (es verdadera) } . Cuando B est´ a claro por el contexto podemos no escribirlo. 4

Asumimos (por axioma) que cualquiera de las dos escrituras anteriores determina un u ´nico conjunto. 1.2.1. Ejemplo. Las siguientes colecciones son conjuntos. 1. A = {a, e, i, o, u} o A = {x | x es una vocal }. 2. A = {2, 4, . . . } o A = {x ∈ N | x es par }. ´ EJEMPLOS PARA PONER EN EL ZALDIVAR pp. 21-22. HAY MAS ´ LOS DE LA HOJA 1 TAMBIEN 1.2.2. Notaci´ on. Si a es un elemento del conjunto A, escribiremos a ∈ A. En caso contrario escribimos a ∈ / A. 1.2.3. Inclusi´ on. Sean A y B conjuntos. Decimos que A est´a contenido en B, o que A es subconjuntos de B si para todo elemento a ∈ A se tiene que a ∈ B. Se denota A ⊂ B y se expresa a ∈ A ⇒ a ∈ B Si A no est´ a contenido en B entonces escribimos A 6⊂ B. 1.2.4. Observaci´ on. Es claro que A 6⊂ B si y solo si existe a ∈ A tal que a 6∈ B. 1.2.5. Ejemplo. Sea I = {x ∈ N | x es impar } = {x ∈ N | x = 2n + 1, con n ∈ N}, que a veces, para abreviar, escribimos {2n + 1 | n ∈ N} (aunque no estaba contemplada, se usa mucho y se entiende perfectamente, as´ı que podemos introducirla). Entonces I ⊂ N. 1.2.6. Notaci´ on. Sean A y B conjuntos, tales que A ⊂ B. Si queremos destacar la posibilidad de que A y B sean iguales podemos escribir A ⊆ B. Cuando queremos poner ´enfasis en justo lo contrario, escribimos A ( B; lo expresamos como a ∈ A ⇒ a ∈ B pero ∃ b ∈ B tal que b 6∈ A. 1.2.7. Igualdad. Diremos que dos conjuntos A y B son iguales cuando tengan exactamente los mismos elementos. Lo expresamos a ∈ A ⇔ a ∈ B. EN EL ZALD´IVAR NO VIENE SEPARADA LA SIGUIRENTE PROP. 1.2.8. Proposici´ on. Sean A y B conjuntos. A = B si y s´ olo si A ⊂ B y B ⊂ A Demostraci´ on. DEM. Conjunto vac´ıo. 1.2.9. Definici´ on. Un conjunto vac´ıo es aquel que no tiene elementos. 1.2.10. Proposici´ on. Sean A y B conjuntos. Si A es vac´ıo entonces A ⊂ B. Demostraci´ on. Se puede comentar el argumento de vacuidad o hacerla por reducci´ on al absurdo. La clave es heber asumido que una colecci´on vac´ıa es conjunto. Por reducci´ on al absurdo: Sea A un conjunto vac´ıo y supongamos que existe B, conjunto tal que A * B. Entonces existe a ∈ A tal que a 6∈ B. Luego A no es vac´ıo lo cual es imposible. 5

1.2.11. Corolario. Solo hay un conjunto vac´ıo. Notaci´ on. El conjunto vac´ıo se denota ∅ 1.2.12. Partes de un conjunto. Sea A un conjunto. La colecci´on P(A) = {B | B ⊂ A} se conoce como el conjunto de las partes de A o el conjunto potencia de A. 1.2.13. Ejemplo. Ejemplo de la Hoja 1. Discutirlo con cuidado.

1.3.

Operaciones con subconjuntos

1.3.1. Uni´ on. Sean A y B conjuntos. El conjunto A ∪ B = {X | X ∈ A o X ∈ B} se conoce como la uni´ on de A y B. Se escribe x ∈ A ∪ B si y s´olo si x ∈ A o x ∈ B. El contrario es x ∈ / A ∪ B si y s´olo si x ∈ /Ayx∈ / B. 1.3.2. Ejercicio. Ejercicios HOJA 1 1.3.3. Intersecci´ on. Sean A y B conjuntos. El conjunto A ∩ B = {X | X ∈ A y X ∈ B} se conoce como la intersecci´ on de A y B. Se escribe x ∈ A ∩ B si y s´olo si x ∈ A y x ∈ B. El contrario es x ∈ / A ∩ B si y s´olo si x ∈ /Aox∈ / B. Diagramnas de Venn En 1880 John Venn introdujo los diagramas para una mejor comprensi´on de los conjuntos y sus operaciones. U

U A B '$ '$

A B '$ '$

&% &% Uni´ on

&% &% Intersecci´on

1.3.4. Ejemplo. Consid´erense los conjuntos A = {X ∈ R | 0 ≤ 2 B = {X ∈ R | X2 < 8}. Se pide:

x 2

≤ 6} y

1. Representar estos conjuntos en la recta real. 2. Determinar los conjuntos A ∪ B, A ∩ B, A \ B y B \ A, escribi´endolos de forma comprehensiva y gr´aficamente en la recta real. 6

Leyes distributivas.(Quitados de la Hoja 1) 1.3.5. Proposici´ on. Sean A, B y C conjuntos. Entonces 1. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). 2. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Demostraci´ on. Hacer una de las dos. La otra, ejercicio. 1.3.6. Diferencia de conjuntos. Sean A y B conjuntos. La diferencia de conjuntos es la colecci´ on A \ B = {X | X ∈ A y X 6∈ B}. Expresado como diagrama de Venn U A B '$ '$

&% &% Diferencia 1.3.7. Ejercicio. HOJA 1. 6c 1.3.8. Complemento. Sean A y U conjuntos, con A ⊂ U . Se conoce como complemento de A en U a la colecci´on A{ = U \ A = {X ∈ U | X 6∈ A}. Leyes de De Morgan. Augustus De Morgan 1806 (India)-1871(Londres). Hijo de un militar brit´anico. Contribuciones importantes en ´algebra, geometr´ıa. Cofundador de la London MS y primer presidente. 1.3.9. Proposici´ on. Sean A y B conjuntos. 1. (A ∩ B){ = A{ ∪ B { . 2. (A ∪ B){ = A{ ∩ B { . Expresado como diagrama de Venn U A B '$ '$ (A ∩ B){ = A{ ∪ B { &% &%

7

1.3.1.

Familias de conjuntos y operaciones

Algunas veces queremos hacer colecciones de objetos y no podemos o no nos interesa garantizar que todos ellos sean distintos. Vamos a ver un par de ejemplos. Sean N el conjunto de los n´ umeros naturales, P el conjunto de los n´ umeros naturales pares y definimos, para cada n ∈ N, An como el conjunto de los m´ ultiplos pares de n; es decir An = {x ∈ P | n | x}. Entonces, la colecci´ on C = {An }n∈N no es conjunto porque, por ejemplo, Ap = A2p , para todo primo impar. En este caso, decimos que C es una familia (de conjuntos). A´ un as´ı, es claro que podemos considerar su uni´on e intersecci´on y respetar´ a las leyes habituales de conjuntos. Otro ejemplo puede ser el siguiente. Consid´erese p1 (X) = X 3 − X 2 + X − 1 y p2 = X 3 + 3X 2 − 2. Sean R1 y R2 los conjuntos de ra´ıces reales de p1 (X) y p2 (X) respectivamente, y R = {R1 , R2 }. En principio, no podemos asegurar que R sea o no conjunto, pero es inmediato comprobar que, visto como familia 1 ∈ R1 ∪ R2 . 1.3.10. Definici´ on. Una familia de conjuntos es una colecci´ on {Ai | i ∈ I}, donde I es un conjunto y Ai son conjuntos. Si todos los objetos son diferentes, tendremos un conjunto, si no, una familia. Uniones e intersecciones arbitrarias en conjuntos y familias Al ser una operaci´ on binaria y asociativa, podemos extenderla a una colecci´ on finita de uniendos. As´ı, si A1 , . . . , An son conjuntos se tiene que n [

Ai = {x | x ∈ Ai para alguna i ∈ {1, . . . , n}} .

i=1

Cuando la colecci´ on sea infinita, tambi´en habr´a uni´on, pero ya no es una consecuencia de propiedades de operaciones binarias. Es otra definici´on. Veamos la versi´ on m´ as general. Nos viene a decir que las uniones m´as generales ser´ an conjuntos, siempre y cuando los uniendos pertenezcan a su vez, a un conjunto. 1.3.11. Uni´ on arbitraria. Sea C un conjunto, cuyos elementos son, a su vez, conjuntos. La uni´ on arbitraria es el conjunto ∪C = {x | x ∈ A, para alg´ un A ∈ C} . En el caso de las familias, si I es un conjunto de ´ındices y C = {Ai | i ∈ I} = {Ai }i∈I , entonces escribimos ∪C =

[

Ai = {x | x ∈ Ai para alg´ un i ∈ I} .

i∈I

8

Al igual que sucede con la uni´on, podemos definir la intersecci´on arbitraria en conjuntos y familias. La intersecci´on de los conjuntos A1 , . . . , An es n \

Ai = {x | x ∈ Ai para todo i ∈ {1, . . . , n}} .

i=1

1.3.12. Intersecci´ on arbitraria. Sea C un conjunto, cuyos elementos son, a su vez, conjuntos. La intersecci´on arbitraria es el conjunto ∩C = {x | x ∈ A, para todo A ∈ C} . En el caso de las familias, si I es un conjunto de ´ındices y C = {Ai | i ∈ I} = {Ai }i∈I , entonces escribimos ∩C =

\

Ai = {x | x ∈ Ai para todo i ∈ I} .

i∈I

1.3.13. Ejemplo. Sea P el conjunto de todos los n´ umeros primos positivos. Para cada primo, p ∈ P, definimos el conjunto Ap = {x ∈ N | p | x}, o sea, los m´ ultiplos naturales de p. Entonces: 1. La familia {Ap }p∈P es un conjunto. S 2. p∈P Ap = N. 3. Si p1 , . . . , pn son primos cualesquiera entonces m ∈ N} T 4. p∈P Ap = ∅.

Tn

i=1

Api = {m·(p1 · · · pn ) |

Otro ejemplo 1.3.14. Ejemplo. Sea A = {a, b, c} y consideramos P(A). Sea C = {{a, b}, {b, c}}. Entonces S 1. C = A. T 2. C = {b}.

1.4.

Pares ordenados, producto cartesiano y relaciones binarias

Comenzamos directo con la definici´on. 1.4.1. Definici´ on. Sean A y B conjuntos. La pareja ordenada formada por a ∈ A y b ∈ B es el conjunto (a, b) = {{a}, {a, b}} .

9

1.4.2. Observaci´ on. La escritura de la definici´on anterior puede reducirse mucho seg´ un el caso. Por ejemplo (a, a) = {{a}}. 1.4.3. Proposici´ on. Sean A y B conjuntos. Para cualesquiera elementos a, c ∈ A y b, d ∈ B se tiene que (a, b) = (c, d) si y solo si a = c y b = d. 1.4.4. Producto cartesiano. Sean A y B conjuntos. El producto cartesiano de A y B es el conjunto A × B = {(a, b) | a ∈ A y b ∈ B} . 1.4.5. Observaci´ on. Es inmediato comprobar que el producto cartesiano (de tres conjuntos) no es asociativo; sin embargo, la identificaci´on (a, (b, c)) con ((a, b), c) es demasiado clara como para pasarla de largo. Intuitivamente identificamos los conjuntos, teniendo precauciones formales. M´ as adelante veremos un concepto m´as general, el de producto directo. 1.4.6. Proposici´ on. Sea A un conjunto arbitrario. Entonces A × ∅ = ∅ × A = ∅. 1.4.7. Observaci´ on. En general, si A y B son conjuntos, A × B 6= B × A. Proviene de la Proposici´ on 1.4.3. 1.4.8. Ejemplos. Sea A = 1, 2, 3 y B = a, b. Formar el producto cartesiano. 1.4.9. Ejercicio. Ejercicios HOJA 1 1.4.10. Definici´ on. Sean A y B conjuntos. Una correspondencia o relaci´ on binaria entre los elementos de A y los de B es un subconjunto R ⊆ A × B. Cuando (a, b) ∈ R decimos que a est´ a relacionado con b (dicho en ese orden) y escribimos aRb. 1.4.11. Observaci´ on. Algunos autores obligan a que las relaciones sean conjuntos no vac´ıos. Algunos autores reservan el t´ermino relaci´on para correspondencias en un solo conjunto. Si no causa confusi´ on, decimos relaci´on en vez de relaci´on binaria. 1.4.12. Observaci´ on. N´ otese que puede ser que un elemento a est´e relacionado con otro b, pero no rec´ıprocamente. 1.4.13. Ejemplos. 1. Si A = ∅ y B es arbitrario, entonces A × B = ∅ y por lo tanto, la u ´nica posible relaci´on entre A y B es la vac´ıa. 2. Sean A y B conjuntos cualesquiera. Siempre se tienen dos relaciones (que pueden coincidir), una es el vac´ıo y la otra es la total. 3. Sea R ⊂ R2 la relaci´ on dada por  R = (x, y) ∈ R2 | x ≤ y ; es decir, xRy ⇔ x ≤ y.

10

4. Sea R ⊆ Z2 × Z2 tal que (a, b)R(a0 , b0 ) ⇐⇒ ab0 = a0 b. 5. Sea A un conjunto. La “diagonal” de A2 ; es decir, (a, b) ∈ R ⇔ a = b, es una relaci´ on. 1.4.14. Definici´ on. Sean A y B, conjuntos, y R una relaci´ on entre A y B. 1. Al conjunto A se le llama conjunto inicial. 2. Al conjunto B se le llama conjunto final. 3. Se conoce como dominio de la relaci´ on, al conjunto DomR = {a ∈ A | ∃ b ∈ B, (a, b) ∈ R} . 4. Se conoce como imagen de la relaci´ on, al conjunto ImR = {b ∈ B | ∃ a ∈ A, (a, b) ∈ R} . 1.4.15. Ejemplo. Sea R ⊂ R2 tal que (x, y) ∈ R ⇐⇒ x = Calcular el dominio y la imagen.

11

y2 − x . y

Cap´ıtulo 2

Aplicaciones 2.1.

Relaciones y aplicaciones

Comenzamos con el concepto de aplicaci´on. 2.1.1. Definici´ on. Sean A y B conjuntos. Una aplicaci´ on entre A y B es una relaci´ on f ⊂ A × B que cumple la siguiente propiedad: Para todo a ∈ A, existe un u ´nico b ∈ B tal que (a, b) ∈ f . O bien, si (a, b) y (a, c) pertenecen a f , entonces c = d. HAREMOS DIBUJOS DE DIAGRAMAS DE GRAFOS Y SAGITALES COMO EL LIBRO DE M. A. GOBERNA P.23 Haremos dibujos de diagramas de grafos y saginatels como el libro de Goberna, p.23. Tambi´en esquemas en el plano. 2.1.2. Observaci´ on. En ocasiones, sobre todo en el c´alculo y la topolog´ıa, se suele identificar la aplicaci´on con la regla de correspondencia y a la propia aplicaci´ on con la gr´ afica (o grafo). 2.1.3. Notaci´ on. Sean A y B conjuntos y f una aplicaci´ on de A a B. Escribimos entonces f f : A → B o A −−→ B. Adem´ as, si a ∈ A y (a, b) ∈ f , como b es u ´nico podemos escribir b = f (a). 2.1.4. Observaci´ on. Como hemos dicho, una aplicaci´on es una relaci´on, que escribimos f : A → B. De este modo tenemos 1. El dominio de f , que es Domf = A. Es decir, el dominio coincide con el conjunto inicial, as´ı que ´este u ´ltimo t´ermino ya no se usa. 2. La imagen (o imagen directa) de f , que es Imf = f (A) ⊆ B.

12

Adem´ as, tenemos otras definiciones. 2.1.5. Definici´ on. Sean A y B conjuntos y f : A → B. 1. Al conjunto final B se le llama el codominio de f . 2. A la igualdad b = f (a) se le llama la regla de correspondencia de f . 3. Si (a, b) ∈ f , decimos que a es preimagen de b y que b es imagen de a. 2.1.6. Ejemplos. caci´ on.

1. Sea A un conjunto. La relaci´on “diagonal” es una apli-

2. Sea f : Z → N, tal que f (a) = a2 . Entonces f es una aplicaci´on. 3. √ La relaci´ on xRy ⇔ x2 + y 2 = 1 no es una aplicaci´on. Sin embargo, y = 2 1 − x s´ı lo es. ´ EJEMPLOS CON DIAGRAMAS y gr´aficos. SI HAY DUDAS HACER MAS

2.2.

Tipos de aplicaciones

2.2.1. Definici´ on. Sea f : A → B una aplicaci´ on. 1. Inyectiva. f (a) = f (b) ⇒ a = b o a 6= b ⇒ f (a) 6= f (b) 2. Suprayectiva (o sobreyectiva o exhaustiva). Para todo b ∈ B, existe a ∈ A tal que f (a) = b. 3. Biyectiva. Es inyectiva y suprayectiva. 2.2.2. Ejemplos. EJEMPLOS CON DIAGRAMAS SAGITALES

2.3.

Im´ agenes directas e inversas

2.3.1. Definici´ on. Sea f : A → B una aplicaci´ on. 1. Para X ⊆ A, definimos la imagen directa de X como f (X) = {f (x) | x ∈ X}. 2. Para Y ⊆ B, definimos f (Y )−1 = {a ∈ A | f (a) ∈ Y }. 2.3.2. Proposici´ on. Sea f : A → B una aplicaci´ on. La imagen directa verifica las siguientes propiedades. 1. f (∅) = ∅. 2. Si X ⊂ Y entonces f (X) ⊂ f (Y ). 13

3. Si X, Y ⊂ A entonces f (X ∪ Y ) = f (X) ∪ f (Y ). 4. Si X, Y ⊂ A entonces f (X ∩ Y ) ⊆ f (X) ∩ f (Y ). M´ as en general, si I es un conjunto y {Xα }α∈I una familia de subconjuntos de A entonces ! ! [ [ \ \ f Xα = f (Xα ) y f Xα ⊆ f (Xα ) α∈I

α∈I

α∈I

α∈I

Demostraci´ on. DEM. Hacer s´olo algunas. 2.3.3. Proposici´ on. Sea f : A → B una aplicaci´ on e Y ⊂ B. La imagen inversa verifica las siguientes propiedades. 1. f (X)−1


{

 −1 = f X{ .

2. Si I es un conjunto y {Xα }α∈I una familia de subconjuntos de A entonces !−1 f

[

Xα

α∈I

!−1 =

[

−1

f (Xα )

α∈I

y

f

\

Xα

α∈I

=

\

f (Xα )

−1

α∈I

Demostraci´ on. Se deja como ejercicio. ´ PROPIEDADES. EN LA HOJA 1 APARECEN MAS 2.3.4. Ejemplo. Sea f : R → R dada por f (x) = x2 . Sea X = [1, Calcular:

√

2] ⊂ R.

1. f (X). −1

2. f (f (X))

.
3. f f (X)−1 . Hacer lo mismo para la aplicaci´on dada por g(x) = sen x, e Y = [−2, 2].

2.4.

Composici´ on

En la HOJA 1, aparece el siguiente ejercicio. 2.4.1. Ejercicio. Sean f : A → B y g : B → C aplicaciones. Definimos la relaci´ on g ◦ f ⊂ A × C tal que (a, c) ∈ (g ◦ f ) si y s´ olo si, existe b ∈ B tal que (a, b) ∈ f y (b, c) ∈ g. Probar que g ◦ f es una aplicaci´ on. Entonces podemos introducir el siguiente concepto. 2.4.2. Definici´ on. Sean f : A → B y g : B → C aplicaciones. Se conoce como la composici´ on de f seguida de g y denotamos g ◦ f a la aplicaci´ on siguiente: 14

1. g ◦ f : A → C. Tal que 2. (g ◦ f )(a) = g(f (a)). Entonces, en la composici´on ocurre que Dom(g ◦ f ) = Domf y el codominio de la composici´ on es igual al codominio de g. 2.4.3. Ejemplos. 1. Sean f : N → N y g : N → Z, dadas por f (n) = 2n + 1 y g(n) = n2 . Entonces la composici´on de f seguida de g es (g ◦ f )(n) = g(f (n)) = g(2n + 1) = (2n + 1)2 . N´ otese que la composici´on de g seguido de f , no puede definirse, porque no coinciden la imagen de g y el dominio de f . Tambi´en notemos que a efectos pr´ acticos, eso podr´ıa corregirse con otra funci´on g 0 : N → N. 2. Sean entonces f : N → N y g 0 : N → N, dadas por f (n) = 2n + 1 y g 0 (n) = n2 . Ahora podemos hacer ambas composiciones y queda (g ◦ f )(n) = (2n + 1)2

y

(f ◦ g)(n) = 2n2 + 1.

N´ otese que (g ◦ f ) 6= (f ◦ g). 2.4.4. Teorema. Sean f : A → B, g : B → C y h : C → D aplicaciones. Entonces h ◦ (g ◦ f ) = (h ◦ g) ◦ f . Demostraci´ on. DEM 2.4.5. Proposici´ on. La composici´ on de aplicaciones inyectivas es inyectiva. Demostraci´ on. DEM 2.4.6. Proposici´ on. La composici´ on de aplicaciones suprayectivas es suprayectiva. Demostraci´ on. DEM 2.4.7. Corolario. La composici´ on de aplicaciones biyectivas es biyectiva. Demostraci´ on. DEM Por los ejercicios de la Hoja 1, tenemos que 2.4.8. Proposici´ on. Sean f : A → B y g : B → C. Entonces 1. Si g ◦ f es inyectiva entonces f es inyectiva. 2. Si g ◦ f es suprayectiva entonces g es suprayectiva.

15

2.5.

Aplicaci´ on inversa de una aplicaci´ on biyectiva

2.5.1. Notaci´ on. Sea A un conjunto arbitrario. Denotamos a la aplicaci´ on identidad en A, como IA : A → A; es decir, IA (a) = a, para todo a ∈ A. 2.5.2. Definici´ on. Sea f : A → B una aplicaci´ on. 1. Decimos que f tiene inversa (o es invertible) por la izquierda si existe g : B → A tal que g ◦ f = IA . 2. Decimos que f tiene inversa (o es invertible) por la derecha si existe g : B → A tal que f ◦ g = IB . 3. Decimos que f tiene inversa (o es invertible) si tiene inversa por ambos lados. 2.5.3. Observaci´ on. N´ otese que por los ejercicios sobre composici´on, se tiene que si f tiene inversa por la izquierda entonces f es inyectiva y si tiene inversa por la derecha entonces ser´ a suprayectiva. Los rec´ıprocos tambi´en se verifican. 2.5.4. Proposici´ on. Sea f una aplicaci´ on. 1. Si f es inyectiva entonces tiene inversa por la izquierda. 2. Si f es suprayectiva entonces tiene inversa por la derecha. Demostraci´ on. DEM Las aplicaciones con inversas a alg´ un lado verifican una ley de cancelaci´on. 2.5.5. Proposici´ on. Sean f : A → B, g1 , g2 : B → C y h1 , h2 : D → A. 1. Si f es inyectiva y f ◦ g1 = f ◦ g2 entonces g1 = g2 . 2. Si f es suprayectiva y h1 ◦ f = h2 ◦ f entonces h1 = h2 . Demostraci´ on. DEM Ahora veremos qu´e ocurre cuando se tienen inversos por los dos lados. 2.5.6. Proposici´ on. Sea f : A → B una aplicaci´ on. Si f tiene inversa por la izquierda y por la derecha entonces las inversas coinciden. En particular, la aplicaci´ on tendr´ a inversa. Demostraci´ on. DEM De la observaci´ on y las proposiciones anteriores se desprende. 2.5.7. Corolario. Una aplicaci´ on es invertible si y s´ olo si es biyectiva. En este caso, el inverso es u ´nico. 2.5.8. Proposici´ on. Sean f : A → B y g : B → C aplicaciones invertibles. Entonces (g ◦ f )−1 = f −1 ◦ g −1 . 16

Producto directo Vamos a ver una extensi´on de la idea del producto cartesiano. El producto directo. A diferencia del producto cartesiano, el producto directo no implica un orden en las coordenadas. Cuando el conjunto de ´ındices est´a ordenado, los identificamos 2.5.9. Definici´ on. Sea I un conjunto y F = {Ai }i∈I una familia de conjuntos. Se conoce como producto directo de la familia F al conjunto Y Ai = {f : I → ∪i∈I Ai | f (i) ∈ Ai } . i∈I

2.5.10. Notaci´ on. Los elementos se denotan igual que las parejas ordenadas; Q es decir, si f ∈ i∈I Ai , escribimos f = (xi )i∈I . Cuando I es finito, escribimos sus elementos como el producto cartesiano y s´ olo se diferencian por el contexto. Por ejemplo si I = {1, . . . , n}, escribimos A1 × · · · × An = {(x1 , . . . , xn ) | xi ∈ Ai } . En caso de que no se quiera escribir a una familia con ´ındices, simplemente se presupone; es decir, a la familia {A, B, C} la vemos como {A1 , A2 , A3 }. 2.5.11. Observaci´ on. Cuando el producto directo de conjuntos se define sobre un conjunto de ´ındices ordenado, puede entonces dotarse a las coordenadas de un orden, como se ver´ a en los siguientes ejemplos. 2.5.12. Ejemplos. 1. R2 = {f : {1, 2} → R | f (i) ∈ R, i = 1, 2} = {(x1 , x2 ) | xi ∈ R}, el plano habitual. 2. Rn = {f : {1, . . . , n} → R | f (i) ∈ R, i = 1, . . . , n}. Q 3. n∈N An = {f : N → ∪n∈N An | f (n) ∈ An }, es un producto infinito. Denotamos sus elementos tambi´en como f = (x1 , x2 , . . . ). 2.5.13. Observaci´ on. Ni el producto cartesiano ni el directo son asociativos, pero podemos identificarlos. Por ejemplo es claro que existe una biyecci´on entre A×(B ×C), (A×B)×C y A×B ×C, dada por (a, (b, c)) ↔ ((a, b), c) ↔ (a, b, c)

17

Cap´ıtulo 3

Orden 3.1.

Conjuntos ordenados y sus elementos distinguidos

Recordad que una relaci´ on (binaria) en un conjunto A es una correspondencia entre A y s´ı mismo. El siguiente tipo de relaciones tendr´a mucha importancia: 3.1.1. Definici´ on. Sea A un conjunto. Una relaci´ on ≤ en A se dice que es una relaci´ on de orden cuando satisface las siguientes propiedades: 1. Reflexiva: a ≤ a, para todo a ∈ A 2. Antisim´etrica: Si a, b ∈ A son elementos tales que a ≤ b y b ≤ a, entonces a=b 3. Transitiva: Si a, b, c ∈ A son elementos tales que a ≤ b y b ≤ c, entonces a≤c 3.1.2. Ejemplos. 1. En cualquiera de los conjuntos num´ericos N, Z, Q ´o R, consideramos la relaci´ on: a ≤ b si, y s´ olo si, a es menor o igual que b 2. En N∗ =: N \ {0} se considera la relaci´on: a ≤ b si, y s´olo si, a divide a b 3. Sea A el conjunto de todas las palabras posibles que se pueden formar con el alfabeto latino. (Nota importante: no se requiere que la palabra tenga sentido o significado. Por ejemplo, abbcccd ser´ıa una palabra y, por tanto, un elemento de A). Se considera la relaci´on lexicogr´ afica: Si x, y ∈ A son palabras, entonces x ≤ y cuando, empezando por la izquierda, la primera letra no com´ un de x es anterior a la de y en el alfabeto latino. As´ı, por ejemplo, abbcccd ≤ abbccdd, porque la primera letra no com´ un de

18

x = abbcccd es la tercera c mientras que en x = abbccdd es la primera d. Puesto que c est´ a antes que d en el alfabeto latino, conclu´ımos que x ≤ y. N´ otese que cuando las palabras son de longitud fija, no tenemos que considerar la palabra vac´ıa. Tambi´en n´otese que se pueden considerar otros conjuntos de s´ımbolos ordenados, por ejemplo los n´ umeros. 4. Sea X un conjunto arbitrario y consideramos en P(X) la relaci´on: Y ≤ Z si, y s´ olo si, Y ⊆ Z 3.1.3. Definici´ on. Un par (A, ≤), donde A es un conjunto y ≤ es una relaci´ on de orden en A, se dice que es un conjunto ordenado. Dicho conjunto se dir´ a totalmente ordenado cuando la relaci´ on de orden ≤ satisface adem´ as la propiedad siguiente: Para cualesquiera a, b ∈ A, ´ o bien a ≤ b ´ o bien b ≤ a 3.1.4. Ejercicio. Considerar los conjuntos ordenados (A, ≤) dados por los ejemplos 3.1.2. Decir cu´ ales de ellos son conjuntos totalmente ordenados, razonando la respuesta. Cuando un conjunto ordenado (A, ≤) es finito, una manera muy pr´actica de visualizarlo es usando el llamado diagrama de Hasse. Este consiste en dibujar los elementos de A como puntos del plano, de manera que si a < b (e.d. a ≤ b y a 6= b) entonces a aparezca debajo de b y con un segmento entre ambos. 3.1.5. Ejemplo. Si A = {a, b, c, d, e} y definimos la relaci´on ≤ en A cuyo subconjunto asociado de A × A es R = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, b), (a, c), (c, d), (c, e), (a, d), (a, e), } entonces ≤ es una relaci´ on de orden cuyo diagrama de Hasse asociado es: d @

e @ @ @c

b

@ @ @ @a Dentro de un conjunto ordenado, hay algunos elementos importantes que conviene destacar: 3.1.6. Definici´ on. Sea (A, ≤) un conjunto ordenado y a ∈ A un elemento. Diremos que: i) a es un m´ aximo de A, cuando b ≤ a para todo b ∈ A ii) a es un m´ınimo de A, cuando a ≤ b, para todo b ∈ A

19

iii) a es un elemento maximal de A cuando se verifica: si a ≤ b entonces b=a iv) a es un elemento minimal de A cuando se verifica: si b ≤ a entonces b=a 3.1.7. Ejercicios. 1. Sea (A, ≤) un conjunto ordenado. Demostrar existe un m´ aximo (resp. m´ınimo) de A si, y s´ olo si, existe un u ´nico elemento maximal (resp. minimal) de A y todo elemento de A es anterior (resp. posterior) a un elemento maximal (resp. minimal). En tal caso, m´ aximo (resp. m´ınimo) y u ´nico elemento maximal (resp. minimal) coinciden. Por tanto, de existir, el m´ aximo (resp. m´ınimo) de un conjunto ordenado es u ´nico. 2. En cada caso, dar un ejemplo de un conjunto ordenado A satisfaciendo la condici´ on requerida: a) A no tiene elementos maximales (resp. minimales) b) A tiene varios elementos maximales (resp. minimales) c) A tiene un u ´nico elemento maximal (resp. minimal), pero existe un elemento x ∈ A que no es anterior (resp. posterior) a ning´ un elemento maximal (resp. minimal). 3.1.8. Ejemplos. 1. Si A = (a, b) es un intervalo abierto de la recta real, en el que se considera el orden usual ≤, entonces A no tiene ni elementos maximales ni elementos minimales. En particular, tampoco tiene ni m´aximo ni m´ınimo 2. Si A = [a, b] es un intervalo cerrado de la recta real, entonces a el m´ınimo y b es el m´ aximo de A. 3. Sea A ⊆ N un subconjunto, en el que consideramos el orden usual ≤. Entonces (A, ≤) tiene siempre un m´ınimo, pero s´olo tiene elementos maximales en el caso en que A sea finito. En este u ´ltimo caso, A tiene m´aximo 4. Sea A = N \ {0, 1} con la relaci´on: a ≤ b si, y s´olo si, a divide a b. Un elemento a ∈ A es un elemento minimal si, y s´olo si, a es un n´ umero primo. No existen elementos maximales en A. En particular, (A, ≤) no tiene ni m´ aximo ni m´ınimo. A veces tendremos un conjunto ordenado (A, ≤) y un subconjunto B y tendremos ciertos elementos de A que son relevantes con respecto al subconjunto B. Estos son los m´ as importantes: 3.1.9. Definici´ on. Sea (A, ≤) un conjunto ordenado, B ⊆ A un subconjunto y c ∈ A. Diremos que: i) c es una cota superior de B en A cuando b ≤ c, para todo b ∈ B ii) c es una cota inferior de B en A cuando c ≤ b, para todo b ∈ B 20

iii) c es extremo superior ´ o supremo de B en A si es la menor cota superior de B en A. Dicho de otro modo, cuando c es una cota superior de B en A y, si c0 ∈ A es otra cota superior de B en A, entonces c ≤ c0 iv) c es extremo inferior ´ o ´ınfimo de B en A si es la mayor cota inferior de B en A. Dicho de otro modo, cuando c es una cota inferior de B en A y, si c0 ∈ A es otra cota inferior de B en A, entonces c0 ≤ c 3.1.10. Ejemplos. 1. No existe ninguna cota superior ni inferior de Z en R. En particular, Z no tiene ni supremo ni ´ınfimo en R. 2. Las cotas inferiores de N en R son los n´ umeros reales c ≤ 0, pero no existen cotas superiores de N en R. En particular, 0 es el extremo inferior de N en R, pero no existe el extremo superior de N en R 3. Si B es cualquiera de los intervalos [a, b], [a, b), (a, b] ´o (a, b) de la recta real, con a < b, entonces las cotas inferiores de B en R son los n´ umeros reales c ≤ a, mientras que las cotas superiores de B en R son los n´ umeros reales d ≥ b . En particular, el extremo inferior de B en R es a y el extremo superior de B en R es b 4. Sea B = {a1 , . . . , an } un subconjunto finito de N∗ = N\{0} y consideramos en N∗ la relaci´ on de orden: a ≤ b ⇐⇒ a divide a b. Entonces las cotas inferiores de B en A son los divisores comunes a a1 , . . . , an mientras que las cotas superiores son los m´ ultiplos comunes a a1 , . . . , an . En particular, el ´ınfimo de B en A es el m´aximo com´ un divisor de los ai y el supremo de B en A es el m´ınimo com´ un m´ ultiplo de los ai 3.1.11. Ejercicio. Sea (A, ≤) un conjunto ordenado y B ⊆ A un subconjunto. Cuando sea necesario, miramos a B como conjunto ordenado con la relaci´ on ≤ restringida. Demostrar que las siguientes afirmaciones son equivalentes: a) B tiene m´ aximo (resp. m´ınimo) b) B tiene extremo superior (resp. inferior) en A y dicho extremo superior (resp. inferior) pertenece a B

3.2.

Axioma de elecci´ on y algunos equivalentes. Buena ordenaci´ on

A su debido tiempo veremos que toda la teor´ıa de conjuntos, que estamos desarrollando a un nivel muy intuitivo en ´este vuestro primer contacto con el tema, se basa en unos axiomas de partida. Uno de esos axiomas es el siguiente: 3.2.1. Axioma [Axioma de elecci´ on]. Si (Ai )Q i∈I es una familia de conjuntos no-vacios indizada por un conjunto I, entonces i∈I Ai 6= ∅ 21

Q Recordad que los elementos de i∈I Ai son familias de elementos (ai )i∈I tales que ai ∈ Ai , para todo i ∈ I, y recordad tambi´enSque una tal familia (ai )i∈I se puede identificar con una aplicaci´on α : I −→ i∈I Q Ai (la que lleva i ai , para todo i ∈ I). Por tanto, dar un elemento de i∈I Ai equivale a dar, para cada i ∈ I, un elemento de Ai . Ello nos lleva a la siguiente forma m´as popular de dar el axioma anterior, que es al que debe su nombre: 3.2.2. Axioma [Axioma de elecci´ on]. Dada una familia de conjuntos novac´ıos, se puede escoger un elemento de cada conjunto El axioma es tan intuitivo que cualquiera creer´ıa que tiene que ser cierto. Sin embargo no se puede probar a partir de los restantes axiomas de la teor´ıa de conjuntos, por lo cual se a˜ nade como tal axioma. Su importancia es capital para probar resultados que tienen que ver con conjuntos infinitos, especialmente porque es equivalente a los otros dos resultados que vamos a ver en esta secci´on. Necesitamos primero introducir cierta terminolog´ıa: 3.2.3. Definici´ on. Sea A un conjunto y B ⊆ A un subconjunto. Se dice que B es una cadena en A si, con la relaci´ on de orden restringida, B es totalmente ordenado. El conjunto A se dice inductivo si toda cadena B en A tiene una cota superior en A. 3.2.4. Ejemplos. 1. Sea A un conjunto. El conjunto potencia P(A), es inductivo. 2. A´ un m´ as, todo conjunto finito ordenado es inductivo. Es f´acil verlo de forma intuitiva. Al final de esta secci´on se puede encontrar una demostraci´on formal, que depende s´ olo de la buena ordenaci´on. El siguiente postulado es fundamental y es equivalente al Axioma de Elecci´ on: 3.2.5. Lema [Lema de Zorn]. Todo conjunto inductivo no-vac´ıo tiene un elemento maximal 3.2.6. Definici´ on. Sea (A, ≤) un conjunto ordenado. Diremos que es bien ordenado si todo subconjunto no-vac´ıo de A tiene un m´ınimo 3.2.7. Ejercicio. Demostrar que todo conjunto bien ordenado es totalmente ordenado, pero el rec´ıproco no es cierto. Demostraci´ on. Supongamos que (A, ≤) es un conjunto bien ordenado y sea B = {x ∈ A | ∃ y ∈ A con x  y e y  x}; es decir, aquellos elementos de A que no est´ an relacionados con alguien. Si B 6= ∅, ya terminamos. Si no, B tiene primer elemento. Sea a ∈ B el m´ınimo. Entonces, para todo b ∈ B se tiene a ≤ b. Esto contradice que existe y ∈ B tal que a  y. 3.2.8. Ejemplo. Consid´erense N × N junto con el orden lexicogr´afico. (1, 1) < (1, 2) < . . . < (1, n) < . . . (2, 1) < (2, 2) < . . . < (2, n) < . . . .. . 22

Este conjunto est´ a bien ordenado. El siguiente postulado es tambi´en equivalente al Axioma de Elecci´on y es tambi´en frecuentemente usado: 3.2.9. Principio de la buena ordenaci´ on Si A es un conjunto no-vac´ıo, entonces existe una relaci´ on de orden ≤ en A tal que (A, ≤) es un conjunto bien ordenado Nota final: No est´ a a vuestro alcance en este momento y, desde luego, queda fuera de los objetivos del curso el probar que los tres postulados dados son equivalentes. Pero en alg´ un momento, y ya en este mismo curso, os vais a ver obligados a usar el lema de Zorn en alguna demostraci´on (p.ej. para probar que todo espacio vectorial tiene una base). Dicho lema no parece muy natural a primera vista. Sin embargo, conociendo que es equivalente a algo tan intuitivo como el Axioma de Elecci´ on, creo que os quedar´a mejor la idea de que no estamos usando herramientas artificiales o cosas raras para probar los resultados. Remito a los curiosos a la Introducci´on (Secci´on 7) del Hungerford para informaci´ on bibliogr´ afica donde pueden encontrarse las pruebas de la equivalencia de los tres postulados aqu´ı mencionados.

3.2.1.

Ap´ endice: conjuntos ordenados finitos.

Usando el principio del buen orden, vamos a probar que todo conjunto finito ordenado es inductivo y por tanto tiene al menos un m´aximo. Primero repetimos los dos auxiliares anteriores. 3.2.10. Ejercicio. Un conjunto A es infinito si tiene un subconjunto propio B ( A tal que existe una aplicaci´ on inyectiva f : A → B. Demostraci´ on. Como f : A → B es inyectiva entonces la aplicaci´on fˆ : A → Imf , es biyectiva y as´ı A es equipotente con Imf ( A. 3.2.11. Lema. Sea A un conjunto finito bien ordenado. Todo subconjunto de A, no vac´ıo, tiene m´ aximo. Demostraci´ on. Supongamos que existe X ⊂ A tal que no tiene m´aximo, y sea x1 su primer elemento. Definimos Y = X \ {x1 } y f : X → Y tal que f (x) es el primer elemento del conjunto {y ∈ X | x < y}. Es obvio que f es aplicaci´on inyectiva. Por (3.2.10) se tiene el resultado. Ahora, el resultado. 3.2.12. Proposici´ on. Sea A un conjunto finito, totalmente ordenado. Se afirma que A tiene m´ aximo. Demostraci´ on. Sea B el conjunto A dotado de un buen orden (que ya no tiene que ser el original, claro). Sea b0 el primer elemento de B, y para cada b ∈ B, definimos [b0 , b] = {x ∈ B | b0 ≤ x ≤ b}.

23

Sea F = {b ∈ B | ∃ f : [b0 , b] → A, inyectiva y tal que x < y ⇒ f (x) < f (y)} . Como al menos b0 ∈ F, se tiene que F 6= ∅, y por (3.2.11) ha de tener un m´ aximo, digamos b ∈ F, con una aplicaci´on f : [b0 , b] → A, adecuada. Caso 1. Si f es sobre, ya tenemos que f (b) es m´aximo de A. Caso 2. Supongamos entonces que f no es sobre. Entonces, al ser f inyectiva, debe ocurrir que [b0 , b] 6= B ya que A es finito y |B| = |A|. Caso 2.1. Si a´ un as´ı, f (b) es m´aximo de A, o simplemente A tiene m´aximo, ya terminamos. Caso 2.2. Si no, entonces existen x ∈ B e y ∈ A tales que: x ∈ B \ [b0 , b] el primer elemento e y > f (b). Definiendo g : [b0 , x] → A tal que ( f (m) si m ∈ [b0 , b] g(m) = y si m = x llegamos a una contradicci´ on. 3.2.13. Teorema. Todo conjunto finito ordenado es inductivo y por tanto tiene elementos maximales. Demostraci´ on. Sea (A, ≤) un conjunto finito y ordenado. Consid´erese una cadena C de A. Como A es finito, tambi´en lo es C, que adem´as es totalmente ordenado. Por (3.2.12), la cadena C tiene un m´aximo (cota superior). As´ı que toda cadena en A tiene cota superior y por tanto A es inductivo. Finalmente, por el lema de Zorn, A tiene maximales.

24

Cap´ıtulo 4

Relaciones de equivalencia 4.1.

Conceptos b´ asicos

Como hemos comentado, un m´etodo importante de las matem´aticas consiste relacionar los elementos de un conjunto. De las siguientes propiedades de las relaciones, ya hemos visto algunas. 4.1.1. Definici´ on. Sea A un conjunto y R una relaci´ on en A × B. Decimos que R es una relaci´ on de equivalencia si satisface las siguientes propiedades: 1. R es reflexiva; es decir, (a, a) ∈ R para todo a ∈ A. 2. R es sim´etrica; es decir, (a, b) ∈ R implica (b, a) ∈ R, para todo a, b ∈ A. 3. R es transitiva; es decir, (a, b) ∈ R y (b, c) ∈ R implica (a, c) ∈ R, para todo a, b, c ∈ A. 4.1.2. Ejemplos. to.

1. La diagonal; es decir, la igualdad, en cualquier conjun-

2. En Z, para m ∈ Z, la relaci´on a ∼5 b si y s´olo si 5 | (a − b). 3. En R, la relaci´ on a ∼ b si y s´olo si a − b ∈ Z. 4. En los tri´ angulos, la semejanza; es decir, tri´angulos cuyos angulos coinciden. 5. ¿Cu´ ando una relaci´ on de orden es relaci´on de equivalencia? PLANTEARLO UNA CLASE Y RESOLVERLO AL D´IA SIGUIENTE. 6. Dar un ejemplo de una relaci´on que cumpla unas propiedades y no otras, construyendo subconjuntos. M´ as ejemplos. P. 33 del Zald´ıvar. Un ejemplo que me interesa.

25

4.1.3. Ejemplo. Sea f : A → B una aplicaci´on. Definimos la relaci´on a ∼ a0 ⇔ f (a) = f (a0 ). Compru´ebese que es relaci´ on de equivalencia. 4.1.4. Notaci´ on. Si R es una relaci´ on de equivalencia en A y a, b ∈ A est´ an relacionados, entonces podemos escribir cualquiera de las tres siguientes formas 1. La tradicional: aRb, que tambi´en usamos para relaciones en general. 2. Tambi´en, a ∼R b 3. O la anterior, pero m´ as corta si no causa confusi´ on, a ∼ b.

4.2.

Clases de equivalencia

Sea A un conjunto no vac´ıo y R una relaci´on de equivalencia en A. Para cada elemento a ∈ A, podemos considerar el conjunto de todos aquellos elementos de A que est´en relacionados con a. Estas colecciones son una herramienta de trabajo importante en ´ algebra. 4.2.1. Definici´ on. Sea A 6= ∅ un conjunto y R una relaci´ on de equivalencia en A. Para cada a ∈ A, su clase de equivalencia es el conjunto [a] = {b ∈ A | a ∼ b }. Las siguientes propiedades son muy f´aciles de verificar: 4.2.2. Proposici´ on. Sea A 6= ∅ un conjunto R una relaci´ on de equivalencia en A. Las siguientes condiciones son equivalentes, para a, b ∈ A: 1. [a] ∩ [b] 6= ∅. 2. a ∼R b. 3. [a] = [b]. Si C es una clase de equivalencia cualquiera y a ∈ C entonces [a] = C, trivialmente. En este caso decimos que a es un representante de C. Como se ver´ a en los siguientes ejemplos, una correcta elecci´on de los representantes puede simplificar mucho la descripci´on de las clases de equivalencia. 4.2.3. Ejemplos. 1. Ejercicios 8c y 8e de la Hoja 2. 2. Uno que interesa es continuar el de (4.1.3) de las aplicaciones. En este caso [a] = {x ∈ A | f (a) = f (x)}.

26

4.3.

Conjunto cociente

4.3.1. Definici´ on. Sea A un conjunto y R una relaci´ on de equivalencia en A. Se conoce como conjunto cociente de A, respecto de la relaci´ on R, al conjunto de las clases de equivalencia de los elemtos de A respecto de R, o simplemente de R. Se denota A/R o A/ ∼R o simplemente A/ ∼. 4.3.2. Ejemplos. Calcular los del ejemplo anterior. Otro ejemplo, vistoso pero no importante, del Goberna. Se considera la relaci´ on de equivalencia en R, dada por x ∼ y ⇐⇒

x−y ∈ Z; 2π

es decir, los n´ umeros reales que distan en un m´ ultiplo de 2π. Podemos entonces identificar a estas clases con los ´angulos, al elegir a los representantes en el intervalo [0, 2π). Para ello, consid´erese la circunferencia en el plano real de radio 1, con centro en (0, 0), que denotamos C(0, 1) o S 1 . Entonces la aplicaci´on f : R/ ∼ −→ S 1 tal que f [x] = (cos x, sen x) est´a bien definida (no depende del representante) y es biyectiva.

4.4.

Relaciones de equivalencia y particiones

Probaremos que toda relaci´on de equivalencia induce una partici´on y viceversa. Sea A un conjunto no vac´ıo y R una relaci´on de equivalencia. Consideremos el conjunto cociente A/ ∼ y cualquier elemento C ∈ A/ ∼. Sabemos que si a, b ∈ C entonces [a] = C = [b]. Adem´as de esto se tiene el siguiente resultado. 4.4.1. Proposici´ on. Sea A un conjunto no vac´ıo y R una relaci´ on de equivalencia. Las clases de equivalencia de R verifican las siguientes propiedades: 1. [a] ∩ [b] = ∅ si y s´ olo si a 6∼ b. S 2. [a]∈A/∼ [a] = A. Demostraci´ on. Si x ∈ [a]∩[b] entonces a ∼ x y a ∼ b, de donde a ∼ b. Imposible. ´ Este es un resultado importante dentro del ´algebra. De hecho, las familias de conjuntos que verifican estas propiedades tienen nombre propio. 4.4.2. Definici´ on. Sean A e I conjuntos y P = {Bi }i∈I una familia de subconjuntos. Decimos que la familia P forma una partici´ on para A si se verifican las siguientes propiedades 1. Bi ∩ Bj = ∅ si y s´ olo si i 6= j. 27

2. La uni´ on (disjunta)

S

i∈I

Bi = A.

4.4.3. Observaci´ on. Podemos separar la propiedad (1) en dos, si escribimos Para cada i ∈ I, el conjunto Bi 6= ∅. Para i, j ∈ I, si i 6= j entonces Bi ∩ Bj = ∅. Es decir, los elementos de una partici´on son conjuntos no vac´ıos y disjuntos. As´ı que, toda relaci´ on de equivalencia induce una partici´on. El rec´ıproco se verifica. Reuniendo todo se tiene el siguiente resultado. 4.4.4. Proposici´ on. Toda relaci´ on de equivalencia induce una partici´ on. Rec´ıprocamente, toda partici´ on determina una relaci´ on de equivalencia. Demostraci´ on. Ya hemos visto en la Proposici´on 4.4.1 que toda equivalencia determina una partici´ on (en clases de equivalencia). Vamos entonces a ver el rec´ıproco. Sea {Ci }i∈I una partici´ on en A. Definimos la relaci´on a ∼ b ⇐⇒ a, b ∈ Ci para alguna i ∈ I. Se prueba entonces que es relaci´on de equivalencia y que las clases de equivalencia son justo las Ci . 4.4.5. Ejemplos. Poner tambi´en del Goberna

28

Cap´ıtulo 5

Conjuntos num´ ericos 5.1.

Cardinalidad. Conjuntos finitos e infinitos

5.1.1. Definici´ on. Decimos que dos conjuntos X e Y son equipotentes si existe una aplicaci´ on biyectiva entre ellos. 5.1.2. Observaci´ on. N´ otese que el ser equipotentes es una relaci´on reflexiva, sim´etrica y transitiva, y a´ un cuando la colecci´on de los conjuntos no sabemos bien qu´e es, podemos agrupar a los conjuntos en clases de “equipotencia”. 5.1.3. Definici´ on. El cardinal de un conjunto es su clase de equipotencia. Intuitivamente, podemos comprobar que los cardinales son colecciones disjuntas y que todo conjunto tiene cardinal. 5.1.4. Notaci´ on. Para un conjunto A, denotamos su cardinal con |A|. Conjuntos finitos e infinitos 5.1.5. Definici´ on. Decimos que un conjunto A es infinito si existe un subconjunto propio B A que es equipotente a A; es decir, que tiene una biyecci´ on f : B → A. 5.1.6. Ejemplo. Aunque todav´ıa no los definimos formalmente, de cara a un ejemplo es muy ilustrativo considerar a los n´ umeros naturales, los enteros, los racionales, etc. 5.1.7. Definici´ on. Decimos que un conjunto A es finito si no es infinito. 5.1.8. Definici´ on. Un cardinal, decimos que es finito si tiene un representante finito. En otro caso decimos que es infinito. Por ejemplo 0 = |∅|. 1 = |{∅}|.

29

2 = |{∅, {∅}}|. y as´ı, sucesivamente, donde el significado de sucesivamente es: 5.1.9. Definici´ on. Sea n un cardinal y consid´erese un representante A. Se conoce como el sucesor de n, al cardinal n∗ = |A ∪ {A}|. 5.1.10. Axioma del infinito. Todo cardinal finito tiene sucesor y la colecci´on de todos los cardinales finitos es un conjunto. 5.1.11. Ejercicio. Probar que para cualquier cardinal finito, el sucesor es u ´nico. 5.1.12. Proposici´ on. El conjunto de los cardinales finitos es infinito. Orden en los cardinales 5.1.13. Definici´ on. Sean k y r cardinales. Decimos que k ≤ r si existen representantes k = |A| y r = |B| con una aplicaci´ on inyectiva f : A → B. Sabemos que, 5.1.14. Teorema. Todo conjunto finito ordenado es inductivo y por tanto tiene maximales. Demostraci´ on. Apunte. 5.1.15. Lema. Sean A y B conjuntos finitos. Entonces existe una aplicaci´ on inyectiva f : A → B o bien f : B → A. Demostraci´ on. Como A es finito, entonces el conjunto C = {X ⊆ A | ∃ f : X → B inyectiva } ⊆ P(A) junto con el orden dado por la contenci´on es inductivo. Luego tiene maximales. Sea M un maximal de C. Entonces existe una aplicaci´on inyectiva f : M → B. Ahora separamos en casos. Caso 1. M = A. Termina la demostraci´on. Caso 2. M 6= A. Separamos en dos subcasos. Caso 2.1. Si f es sobre. Entonces la inversa por la derecha deber´a de ser inyectiva. Eso termina la demostraci´on. Caso 2.2. Si f no es sobre, consideramos a ∈ A \ M y b ∈ B \ Imf . Haci´endolos corresponder llegamos a una contradicci´on. Como consecuencia obtenemos 5.1.16. Teorema. Los cardinales finitos forman un conjunto con “≤”un orden total. Demostraci´ on. Si A y B son finitos, por lo anterior |A| ≤ |B| o viceversa.

30

5.2.

N´ umeros naturales

5.2.1. Definici´ on. El conjunto de los cardinales finitos se conoce como los n´ umeros naturales y se denota N. 5.2.2. Notaci´ on. Escribimos sus elementos 0, 1, 2, . . . y el orden n ≤ m, para n, m ∈ N. 5.2.3. Los sucesores y el principio de inducci´ on. 1. Todo n´ umero natural tiene un u ´nico sucesor y s´olo 0 no es sucesor de ning´ un n´ umero natural. 2. El conjunto de los n´ umeros naturales verifica el principio de inducci´on: si A ⊆ N es tal que a) 1 ∈ A. b) n ∈ A ⇒ n∗ ∈ A entonces A = N \ {0}. Demostraci´ on. (1) Ejercicio anterior. Para (2) yo creo que es f´acil pero siempre puede no hacerse. Mi propuesta es: Supongamos que existe m ∈ / A y sea M un representante. Hacemos S = {M 0 ⊂ M | |M 0 | ∈ A}. Como 1 ∈ A, entonces S 6= ∅., as´ı que, por los antecedentes (lema de Zorn), tiene maximales. Sea T ∈ S un maximal. Por hip´ otesis, |T |∗ ∈ A y existe x ∈ M \ T , por lo que |T ∪ {x}| = |T |∗ ∈ A. Esto contradice que T sea maximal. 5.2.4. Buen orden en los n´ umeros naturales. (N, ≤) es un conjunto bien ordenado; es decir, todo subconjunto ∅ = 6 A⊂N tiene primer elemento. Demostraci´ on. TAREA. Se puede destacar el lema de Zorn como condici´on para la inducci´on y el buen orden. Operaciones en N Las definimos de forma inductiva o recursiva. 5.2.5. La suma en N. Para n ∈ N, definimos 1. n + 1 = n∗ . 2. Si tenemos definida n + m entonces n + m∗ = (n + m)∗ .

31

Se pueden probar entonces las siguientes propiedades 5.2.6. Propiedades de la suma en N. 1. n∗ + m = n + m∗ 2. n + m = m + n (conmutatividad). 3. (n + m) + r = n + (m + r) (asociatividad). 4. Si a + c = b + c entonces a = b (cancelaci´on). Demostraci´ on. SE OMITE POR LARGA (Zald´ıvar pp. 57-59) 5.2.7. El producto en N. Para n, m ∈ N, definimos 1. n · 1 = n. 2. Si tenemos definido n · m entonces n · m∗ = n · m + n. 5.2.8. Notaci´ on. Escribimos, como siempre, indistintamente, n · m = nm. 5.2.9. Propiedades del producto. 1. n∗ m = nm + m. 2. nm = mn (conmutatividad). 3. n(m + k) = nm + nk (distributividad). 4. n(mk) = (nm)k (asociatividad).

5.3.

Conjuntos numerables y no numerables

Vamos a terminar esta parte abordando algunos aspectos m´as de la cardinalidad. Hasta ahora tenemos la definici´on de finito e infinito. 5.3.1. Definici´ on. 1. Un conjunto A, decimos que es infinito si existe B ( A, junto con una aplicaci´ on inyectiva f : A → B. 2. Un conjunto es finito si no es infinito. 3. Recordemos que la cardinalidad de un conjunto A se denota |A|. 5.3.2. Teorema [Bernstein]. Sean A y B conjuntos, tales que existen aplicaciones inyectivas f : A → B y g : B → A. Entonces, existe una biyecci´ on β : A → B. ´ Demostraci´ on. SIN DEMOSTRACION 5.3.3. Corolario. Sean A y B conjuntos, tales que existen aplicaciones sobreyectivas f : A → B y g : B → A. Entonces, existe una biyecci´ on β : A → B. 32

Demostraci´ on. Inmediata. 5.3.4. Lema. |N| = |N × N|. Demostraci´ on. Vamos a exhibir una aplicaci´on inyectiva ϕ : N × N → N. Es un poco laborioso, pero muy ilustrativo. La idea es ordenar las parejas en el orden lexicogr´ afico y luego ir contando “en diagonal”. Podemos ilustrarlo as´ı: (1, 2) 1(1, 3)        1 ...   (2, 2) (2, 1)        (3, 1)  (1, 1)

-

N´ otese que cada diagonal con pareja superior (1, n) tiene exactamente nPn−1 parejas; a saber, de (1, n) al (n, 1) y antes de llegar a ella se han contado i=1 i, parejas, todas ellas sumando sus coordenadas n + 1 y s´olo ellas tienen esa suma. Luego, al terminar la diagonal habremos contado n−1 X

i+n=

i=1

n X

i

i=1

parejas. Si llamamos S(n) a la suma de los primeros n n´ umeros naturales podemos observar que se asignar´ an (1, n) 7→ S(n − 1) + 1, (2, n − 1) 7→ S(n − 1) + 2 y as´ı (n, 1) 7→ S(n − 1) + n = S(n). De este modo, la correspondencia queda como sigue. Se considera un elemento arbitrario (i, j). Entonces vive en la diagonal de (1, i + j − 1) 7→ S(i + j − 2). Luego (i, j) 7→ S([i + j − 2] + i) = S(2i + j − 2), y aplicando la conocida f´ormula de la suma (2i + j − 1)(2i + j − 2) ϕ(i, j) = . 2 5.3.5. Teorema. |N| = |Z| = |Q| Demostraci´ on. Inmediata de la construcci´on que hemos hecho. 5.3.6. Teorema. Consid´erese el intervalo (0, 1) ⊂ R. Existe una aplicaci´ on inyectiva f : N → [0, 1], pero no existe ninguna aplicaci´ on inyectiva (0, 1) → N. Es decir, el infinito de R es “mayor” que el de N. Demostraci´ on. Vamos a dar un argumento conocido como “m´etodo de la diagonal de Cantor”. Supongamos que s´ı se tiene una aplicaci´on inyectiva. Eso finalmente significa que hay una aplicaci´on biyectiva y que hemos numerado a

33

todos los elementos del intervalo (0, 1). Entonces los escribimos x1 , x2 , . . . , en su forma decimal x1

=

0, x11 x12 x13 · · ·

x2

=

0, x21 x22 x23 · · ·

x3

=

0, x31 x32 x33 · · ·

Consid´erese el n´ umero x = 0, x11 x22 x33 · · · o sea, que sus decimales son “la diagonal” de la lista anterior (no importa que todos fuesen 9 o 0, porque lo vamos a cambiar). Ahora vamos a construir otro n´ umero, de la siguiente forma. A cada xnn asignamos otro d´ıgito ynn ∈ {0, . . . , 9} \ {xnn }, procurando que no todas las elecciones sean 0 o 9, para que y = 0, y11 y22 · · · ∈ (0, 1). Es inmediato comprobar que y no puede estar en la lista anterior.

5.4.

N´ umeros enteros

Vamos a continuar la construcci´on de los conjuntos num´ericos. 5.4.1. Proposici´ on. Consid´ese el conjunto Z = N × N. La relaci´ on (a, b) ∼ (n, m) ⇐⇒ a + m = b + n es relaci´ on de equivalencia. Demostraci´ on. DEM 5.4.2. Definici´ on. Llamamos n´ umeros enteros al conjunto cociente Z = Z/ ∼ . 5.4.3. Representantes notables. Consid´erese (n, m) ∈ Z. 1. Si n = m entonces (n, m) ∈ [(0, 0)]. Luego [(0, 0)] = {(n, m) ∈ Z | n = m} . 2. Si n 6= m se tienen dos casos. a) Si n > m, haciendo a = n − m se tiene (n, m) ∈ [(a, 0)]. Luego [(a, 0)] = {(n, m) ∈ Z | n > m, a = n − m} . b) Si n < m, haciendo a = m − n se tiene (n, m) ∈ [(0, b)]. Luego [(0, b)] = {(n, m) ∈ Z | n < m, b = m − n} .

34

5.4.4. Orden en los n´ umeros enteros. 1. [(a, 0)] ≥ [(0, b)] para todo a, b ∈ N. 2. [(a, 0)] ≥ [(b, 0)] si y s´ olo si a ≥ b. 3. [(0, a)] ≥ [(0, b)] si y s´ olo si a ≤ b. Se puede comprobar inmediatamente, pero de todas formas se ver´a en el siguiente cap´ıtulo. 5.4.5. Proposici´ on. (Z, ≤) es un conjunto totalmente ordenado. A´ un m´ as, todo entero tiene predecesor y sucesor. 5.4.6. Notaci´ on.

1. Denotamos con 0 a la clase [(0, 0)], el cero.

2. Denotamos con n a la clase [(n, 0)] y los identificamos con los n´ umeros naturales. 3. Denotamos con −n a la clase [(0, n)], que ser´ an los n´ umeros negativos. Suma y producto en los enteros. Las comprobaciones se har´an en el pr´oximo cap´ıtulo. 5.4.7. Suma. Definimos +

:

Z × Z −→ Z,

tal que,

+ ([(a, b)] , [(m, n)]) = [(a + m, b + n)] ;

es decir,

[(a, b)] + [(m, n)] = [(a + m, b + n)] 5.4.8. Propiedades de la suma. 1. Est´ a bien definida. 2. Es conmutativa. 3. Es asociativa. 4. Existe el neutro 0. 5. Para todo entero no cero, existe el opuesto o inverso bajo la suma. Demostraci´ on. La veremos en el cap´ıtulo siguiente. 5.4.9. Producto. Definimos •

: Z × Z −→ Z,

tal que,

• ([(a, b)] , [(m, n)]) = [(am + bn, an + bm)] ; [(a, b)] [(m, n)] = [(am + bn, an + bm)] 5.4.10. Propiedades del producto.

35

es decir,

1. Est´ a bien definido. 2. Es conmutativo. 3. Es asociativo. 4. Es distributivo. 5. Existe el neutro 1. Demostraci´ on. La veremos en el cap´ıtulo siguiente.

5.5.

N´ umeros racionales

5.5.1. Notaci´ on. Denotamos Z∗ = Z \ {0}. 5.5.2. Proposici´ on. Sea Q = Z × Z∗ . La relaci´ on en Q dada por [(a, b)] ∼ [(n, m)] ⇐⇒ am = bn es una relaci´ on de equivalencia. Demostraci´ on. DEM 5.5.3. Definici´ on. Llamamos n´ umeros racionales al conjunto cociente Q = Q/ ∼ . 5.5.4. Representantes notables. Consid´erese (n, m) ∈ Q. 1. Si d|mcd(n, m) entonces [(n, m)] = [(n/d, m/d)]. Luego podemos elegir representantes coprimos (y son u ´nicos). 2. [(0, 1)] = {(0, n) ∈ Q | n ∈ Z}. 3. [(1, 1)] = {(n, m) ∈ Q | n = m}. 4. [(n, 1)] = {(a, b) ∈ Q | n = a/b}. 5. [(1, m)] = {(a, b) ∈ Q | m = b/a}. 5.5.5. Orden en los n´ umeros racionales. Sean [(n, m)] y [(a, b)] n´ umeros racionales. Definimos [(n, m)] ≤ [(a, b)] ⇐⇒ nb ≤ ma. Adem´ as, 1. Decimos que un racional es positivo si es mayor que 0. 2. Decimos que es negativo si es menor que 0. 5.5.6. Proposici´ on. (Q, ≤) es un conjunto totalmente ordenado. 5.5.7. Observaci´ on. Ning´ un racional tiene sucesor (ni predecesor). 36

Suma y producto en los enteros. 5.5.8. Suma. Definimos +

: Q × Q −→ Q,

tal que,

+ ([(a, b)] , [(m, n)]) = [(an + bm, bn)] ;

es decir,

[(a, b)] + [(m, n)] = [(an + bm, bn)] 5.5.9. Propiedades de la suma. 1. Est´ a bien definida. 2. Es conmutativa. 3. Es asociativa. 4. Existe el neutro 0. 5. Para todo racional no cero, existe el opuesto o inverso bajo la suma. A´ un m´ as, si n, m ∈ Z, [(−n, m)] = [(n, −m)] = − [(n, m)]. Demostraci´ on. Ejercicio. Nosotros haremos alguno. 5.5.10. Producto. Definimos •

: Q × Q −→ Q,

tal que,

• ([(a, b)] , [(m, n)]) = [(am, bn)] ;

es decir,

[(a, b)] [(m, n)] = [(an, bm)] 5.5.11. Propiedades del producto. 1. Est´ a bien definido. 2. Es conmutativo. 3. Es asociativo. 4. Es distributivo. 5. Existe el neutro 1. 6. Para todo racional no cero, existe el inverso. Demostraci´ on. Hacer algunos. El resto, ejercicio. 5.5.12. Notaci´ on.

1. En general, escribimos m = [(m, n)] . n

2. Denotamos con 0 a la clase

0 1

3. Denotamos con m a la clase n´ umeros enteros.

= [(0, 1)], el cero. m 1

= [(m, 1)] y los identificamos con los

37

5.5.1.

Escritura decimal de n´ umeros racionales.

En este apartado nos proponemos probar, de manera rigurosa, algo que ya conoceis: que todo n´ umero racional admite una expresi´on decimal u ´nica. 5.5.13. Definici´ on. Una sucesi´ on de n´ umeros (naturales, enteros, racionales, reales o complejos), (an )n∈N se dice eventualmente peri´odica si existe un m ∈ N y un entero positivo q > 0 tal que ai = ai+q , para todo i ≥ m. Si r es el menor de los m ∈ N que satisfacen dicha propiedad, entonces el t´ermino ar es llamado el t´ermino inicial del periodo. Si p es el menor de los enteros positivos q anteriores, entonces p es llamado el periodo de la sucesi´ on. 5.5.14. Ejemplos. Los siguientes son ejemplos de sucesiones eventualmente peri´ odicas: 1. Todas las sucesiones de n´ umeros constantes o eventualmente constantes. Una sucesi´ on se dice eventualmente constante cuando existe un m ∈ N tal que ai = ai+1 , para todo i ≥ m. En tal caso el periodo de la sucesi´on es 1. 2. La sucesi´ on 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 2, 1, 3, 2, 1, 3, 2, 1, . . . es eventualmente peri´ odica, con periodo p = 3 y con a10 como t´ermino inicial del periodo. 5.5.15. Definici´ on. Una sucesi´ on de n´ umeros naturales (an )n∈N se dice decimal cuando an ∈ {0, 1, ..., 9} para todo n > 0 (n´ otese que no hay restricci´ on sobre el t´ermino a0 ). 5.5.16. Teorema. Dado un n´ umero racional α ∈ Q, α ≥ 0, existe una u ´nica sucesi´ on decimal eventualmente peri´ odica de n´ umeros naturales (an )n∈N satisfaciendo que 0 ≤ α − a0 −

a1 10

−

a2 102

− ... −

an 10n

<

1 10n ,

(∗n )

para todo n ∈ N. Adem´ as, la asignaci´ on α (an )n∈N define una biyecci´ on entre el conjunto Q+ = {α ∈ Q : α ≥ 0} y el conjunto D de las sucesiones decimales eventualmente peri´ odicas de n´ umeros naturales que no son eventualmente constantemente 9. Demostraci´ on: Expresemos el n´ umero racional dado como fracci´on reducida α = k , donde k, d ∈ N y d > 0. Constru´ ımos un par de sucesiones de n´ umeros d naturales [(an ), (rn )] como sigue. a0 y r0 ser´an el cociente y el resto de la divisi´on de k entre d. Es decir, vienen dados por la igualdad k = a0 d + r0 , siendo 0 ≤ r0 < d. Supuesto que n > 0 y ya han sido definidos los t´erminos de ambas sucesiones hasta el (n − 1)-´esimo, definimos an y rn como el cociente y resto de la divisi´ on de 10rn−1 entre d. Por propia definici´on, para n > 0 se tiene: 0 ≤ an d ≤ 10rn−1 < 10d, de lo que, multiplicando por 1/d se sigue < 10. 0 ≤ an ≤ 10 rn−1 d

38

Por tanto, la sucesi´ on (an ) es una sucesi´on decimal. Adem´as, puesto que existen a lo m´ as d restos distintos al dividir por d, existir´a un menor m ∈ N tal que rm = rm+j , para alg´ un j > 0. Denotamos por p el menor de los j > 0 que satisfacen esta propiedad. Por propia construcci´on es claro que, a partir del t´ermino m-´esimo, la sucesi´ on de restos es rm , rm+1 , ..., rm+p−1 , rm , rm+1 , ..., rm+p−1 , rm , .... Por tanto la sucesi´ on (rn ) es eventualmente peri´odica, lo que a su vez implica que la sucesi´ on (an ) es eventualmente peri´odica, pues an es el cociente de dividir 10rn−1 entre d. Veamos ahora que la sucesi´on (an ) dada satisface la propiedad (∗n ), para todo n ∈ N. Para ello probamos la siguiente igualdad por inducci´on en n α = a0 +

a1 10

+ ... +

an 10n

+

rn 10n d .

(∗∗n )

Para n = 0 se tiene k = a0 d + r0 y as´ı α = kd = a0 + rd0 = a0 + suponemos que la igualdad (∗∗n ) se verifica y observamos que rn 10n d

=

10rn 10n+1 d

=

an+1 d+rn+1 10n+1 d

=

an+1 10n+1

+

r0 100 d .

Si ahora

rn+1 10n+1 d ,

obtenemos la igualdad (∗∗n+1 ), con lo que la igualdad (∗∗n ) est´a probada para todo n ∈ N. De esta misma igualdad obtenemos entonces 0 ≤ α − a0 −

a1 10

− ... −

an 10n

=

rn 10n d

<

d 10n d

=

1 10n ,

con lo que la sucesi´ on (an ) satisface la desigualdad (∗n ), para todo n ∈ N. Veamos ahora que la sucesi´on decimal (an ) reci´en constru´ıda es la u ´nica que satisface la propiedad (∗n ), para todo n ∈ N. Supongamos que (bn )n∈N es una sucesi´ on decimal de n´ umeros naturales satisfaciendo (∗n ), para todo n ∈ N. Probamos por inducci´ on que bn = an , para todo n ∈ N. Para n = 0 tenemos 0 ≤ α − b0 < 1010 = 1, lo que implica que b0 ≤ α < b0 + 1, al igual que se tiene a0 ≤ α < a0 + 1. Pero ello implica que a0 y b0 son ambos el m´aximo del conjunto X0 = {a ∈ N : a ≤ α} y as´ı b0 = a0 . Supongamos ahora que n > 0 y que bk = ak , para todo k < n. Para simplificar la notaci´on, ponemos αr = α − a0 − − a101 −

a2 102

− ... −

ar 10r ,

para todo r ∈ N. Entonces la propiedad (∗n ) de la sucesi´on (bn ) nos da 0 ≤ αn−1 −

bn 10n

<

1 10n ,

lo que, multiplicando por 10n , nos da 0 ≤ 10n αn−1 − bn < 1, y as´ı bn ≤ 10n αn−1 < bn + 1.

39

La misma desigualdad se verifica sustituyendo bn por an , debido a que la propiedad (∗n ) se verifica para la sucesi´on (an ) tambi´en. Ello implica que bn = max(Xn ) = an , siendo Xn = {a ∈ N : a ≤ 10n αn−1 }. Nuestro siguiente paso es probar que la sucesi´on decimal (an ) asociada a α ∈ Q+ no puede ser eventualmente constantemente 9. En efecto, supongamos que no es as´ı y sea m el menor de los n´ umeros naturales n tales P que an = 9. ai Entonces se tiene que an = 9, para todo n ≥ m. Pongamos β = α− 0≤i m + 1 (¡pensad porqu´e—), se obtiene un n´ umero racional estrictamente positivo γ := 1 − 10m−1 β tal que (k − m − 1)γ < 1, para todo k > m + 1. Equivalentemente, se tiene que nγ < 1, para todo n > 1. Poniendo γ = ab , con a, b ∈ N∗ , conclu´ımos que na < b para todos los enteros n > 1. Pero eso es imposible, porque, al ser a > 0, se tiene una inclusi´on de subconjuntos {n ∈ N : na < b} ⊆ {n ∈ N : n < b}, 40

donde el subconjunto de la derecha est´a acotado superiormente por b. Por tanto, el de la izquierda tambi´en est´a acotado superiormente por b y no puede contener todos los enteros n > 1. Sea finalmente D el conjunto de las sucesiones decimales eventualmente peri´ odicas de n´ umeros naturales que no son eventualmente constantemente 9. Por los p´ arrafos anteriores, tenemos una aplicaci´on σ : Q+ −→ D, que lleva α σ(α) := (an ), la sucesi´ on decimal asociada. Dicha aplicaci´on es inyectiva. En efecto, si α, β ∈ Q+ satisfacen que σ(α) = σ(β) y denotamos por (an ) a esta sucesi´ on, entonces la propiedad (∗n ), con α y β, nos dan las desigualdades: P ai 1 0 ≤ α − 0≤i≤n 10 i < 10n P a − 101n < −β + 0≤i≤n 10ii ≤ 0. Sumando ambas desigualdades, obtenemos que − 101n < α − β < 102n , para todos los n ∈ N. Se deja como ejercicio el probar, sin el uso de l´ımites, que α − β = 0 y as´ı α = β. Finalmente, probamos la suprayectividad de σ. La prueba se divide en tres etapas: Etapa 1: Probamos que si α ∈ Q+ tiene por sucesi´on decimal asociada la sucesi´ on eventualmente nula a0 , ..., am−1 , 0, 0, ... y β ∈ Q+ tiene como sucesi´on decimal asociada 0, 0, ..., 0, am , am+1 , ..., entonces la sucesi´on decimal asociada a α + β es a0 , ..., am−1 , am , am+1 , .... Etapa 2: Probamos que si α ∈ Q+ tiene por sucesi´on decimal asociada 1 la sucesi´ on 0, a1 , a2 , ..., entonces 10m−1 α tiene como soluci´on decimal asociada 0, 0, ..., 0, a1 , a2 , ..., donde los t´erminos iniciales hasta el (m − 1)-´esimo inclusive son nulos y donde el t´ermino (i + m − 1)-´esimo es ai , para todo i > 0. Etapa 3: Si a1 , ..., ap ∈ {0, 1, ..., 9} son no todos nulos y no todos iguales a 9, entonces la sucesi´ on decimal eventualmente peri´odica 0, a1 , ..., ap , a1 , ..., ap , .... est´ a en la imagen de la aplicaci´on σ. N´ otese que, una vez cumplidas las tres etapas, la suprayectividad de σ se seguir´ a autom´ aticamente. En efecto, sea (an ) ∈ D, con periodo p y t´ermino inicial del periodo am . Por la etapa 3, sabemos que la sucesi´on decimal eventualmente peri´ odica 0, am , am+1 , . . . , am+p−1 , am , am+1 , . . . , am+p−1 , . . . es imagen de un (´ unico) γ ∈ Q+ . Entonces, por la etapa 2, sabemos que 1 σ( 10m−1 γ) es la sucesi´ on eventualmente peri´odica 0, 0, . . . , 0, am , am+1 , . . . , am+p−1 , am , am+1 , . . . , am+p−1 , . . . P ai on decimal asociada Pero se ve f´ acilmente que β := 0≤i r1 > r2 > r3 > · · · ≥ 0 debe obtenerse resto cero en un n´ umero finito de pasos: rn−2 = rn−1 qn + rn rn−1 = rn qn+1

(rn−2 , rn−1 ) = (rn−1 , rn ) (rn−1 , rn ) = rn .

Luego (a, b) = rn . Estos c´ alculos se pueden disponer en forma de tabla de la manera siguiente:

a r1

q1 b r2

q2 r1 r3

··· ··· ···

··· ··· ···

qn−1 rn−2 rn

qn rn−1 0

qn+1 rn

Por ejemplo, para los enteros a = 252 y b = 198 tenemos 1 252 198 54 36

3 1 54 36 18 0

2 18

por lo que mcd(252, 198) = 18. Si ahora nos fijamos en las divisiones efectuadas: 252

=

198 · 1 + 54

198 = 54 · 3 + 36 54 = 36 · 1 + 18 36

=

18 · 2. 53

y vamos despejando y sustituyendo, obtenemos 18 = 54(1) + 36(−1) = 54 + (198 − 54 · 3)(−1) = 198(−1) + 54(4) = 198(−1) + (252 − 198 · 1) · 4 = 198(−5) + 252(4). La igualdad 18 = 198(−5)+252(4) se conoce como una identidad de B´ezout. La generalizaci´ on del ejemplo anterior a dos n´ umeros arbitrarios nos da el siguiente teorema 6.1.12. Teorema. Sean a, b ∈ Z y d = mcd(a, b). Entonces, existen α, β ∈ Z tales que αa + βb = d. A una identidad de este tipo se le llama identidad de B´ ezout. Ahora podemos usar las identidades de B´ezout para ver una definici´on alternativa del m´ aximo com´ un divisor que nos permitir´a extender este concepto a otros anillos. 6.1.13. Proposici´ on. Sean a, b, c, d ∈ Z. Entonces d = mcd(a, b) si y solo si se cumplen las condiciones (1) d | a y d | b. (2) Si c | a y c | b, entonces c | d. (3) d ≥ 0. Demostraci´ on. Supongamos d = mcd(a, b). De la definici´on de m´aximo com´ un divisor tenemos las propiedades (1) y (3). Para probar la segunda, escribimos una identidad de B´ezout d = αa + βb. Entonces, si c | a y c | b, se tiene que c | d. Rec´ıprocamente, supongamos que a, b, d cumplen las tres condiciones del enunciado. Si a 6= 0 o b 6= 0, est´a claro que d es el mayor de los enteros que dividen a a y b. Si a = b = 0, como 0 | a y 0 | b, la condici´on (2) me dice que 0 | d por lo que d = 0. Tambi´en en este caso se tiene d = mcd(a, b). Este resultado puede generalizarse a un n´ umero finito de enteros como vamos a ver a continuaci´ on. 6.1.14. Definici´ on. Sean a1 , . . . , an ∈ Z con alg´ un ai 6= 0. El m´ aximo com´ un divisor de a1 , . . . , an , que denotaremos por mcd(a1 , . . . , an ), se define como el mayor entero d que los divide a todos. Definimos mcd(0, . . . , 0) = 0. 6.1.15. Proposici´ on. Sean a1 , . . . , an ∈ Z. Entonces mcd(a1 , . . . , an ) = mcd(mcd(a1 , a2 ), a3 , . . . , an ).

54

Demostraci´ on. Sea d = mcd(a1 , . . . , an ), e = mcd(mcd(a1 , a2 ), a3 , . . . , an ) y f = mcd(a1 , a2 ). Entonces, como d divide a a1 , . . . , an , tenemos por la proposici´ on anterior que d divide a f, a3 , . . . , an . Luego d ≤ e. Rec´ıprocamente, e divide a f, a3 , . . . , an y, por tanto, e divide a a1 , a2 , . . . , an . Luego e ≤ d. Como d, e ≥ 0 debe ser d = e. 6.1.16. Corolario. Si d = mcd(a1 , . . . , an ), entonces existen enteros α1 , . . . , αn tales que d = α1 a1 + · · · + αn an . Demostraci´ on. Ejercicio (utilizar inducci´on y la proposici´on anterior) 6.1.17. Corolario. Sean a1 , . . . , an ∈ Z. Entonces d = mcd(a1 , . . . , an ) si y solo si se cumplen las condiciones (1) d | ai para todo i = 1, . . . , n. (2) Si c | ai para todo i = 1, . . . , n, entonces c | d. (3) d ≥ 0. Demostraci´ on. Se deja como ejerfcicio. 6.1.18. Ejemplo. Para calcular el m´aximo com´ un divisor de los n´ umeros 45, 81, 12 y 51 podemos proceder de la siguiente manera: mcd(45, 81, 12, 51) = mcd(mcd(45, 81), 12, 51) = mcd(9, 12, 52) = mcd(mcd(9, 12), 51) = mcd(3, 51) = 3. 6.1.19. Definici´ on. Dos enteros a, b se llaman primos entre s´ı o coprimos si mcd(a, b) = 1. 6.1.20. Proposici´ on. Sean a, b, c ∈ Z tales que a | bc. Si a y b son coprimos, entonces a | c. Demostraci´ on. Sea 1 = αa + βb una identidad de B´ezout. Multiplicando por c tenemos c = αac + βbc. Como a | bc, tambi´en a | c. 6.1.21. Proposici´ on. Sean a y b dos enteros no nulos. Entonces a y b son coprimos si y solo si existen α, β ∈ Z tales que αa + βb = 1. Demostraci´ on. Si a y b son coprimos, existen α y β por el Teorema 9. Rec´ıprocamente, si αa + βb = 1 y d = mcd(a, b), entonces d | αa + βb por lo que d = 1. 6.1.22. Corolario. Sean a y b dos enteros no nulos y d = mcd(a, b). Si a = da0 y b = db0 , entonces mcd(a0 , b0 ) = 1. Demostraci´ on. Ejercicio.

55

6.1.2.

M´ınimo com´ un m´ ultiplo

6.1.23. Definici´ on. Dados dos n´ umeros enteros a, b distintos de cero, el m´ınimo com´ un m´ ultiplo de a y b se define como el menor entero positivo que es m´ ultiplo de a y de b a la vez. Si a o b son cero, entonces el m´ınimo com´ un m´ ultiplo de a y b es 0. Se denotar´ a por mcm(a, b). Observemos que el m´ınimo com´ un m´ ultiplo existe siempre ya que el conjunto de todos los enteros positivos que son m´ ultiplos comunes a a y b es no vac´ıo y, por tanto, debe tener un primer elemento. 6.1.24. Proposici´ on. Si a, b ∈ Z, entonces: (1) mcm(a, b) = mcm(a, |b|) = mcm(|a|, |b|). (2) mcm(a, b) = 0 si y solo si a = 0 o b = 0. (3) mcm(a, ab) = ab. Demostraci´ on. Ejercicio. 6.1.25. Teorema. Sean a, b ∈ Z. Entonces: (1) mcm(a, b) mcd(a, b) = |ab|. (2) Si c es m´ ultiplo de a y de b, entonces c es m´ ultiplo de mcm(a, b). Demostraci´ on. Si a = 0 o b = 0 el enunciado es evidente. Por tanto, por la proposici´ on anterior, podemos suponer que a, b > 0. Sea d = mcd(a, b) y supongamos que a = da0 y b = db0 para ciertos enteros a0 , b0 ∈ Z. Sea m = a0 b0 d. Observemos que m es m´ ultiplo de a y de b. Supongamos que c > 0 es m´ ultiplo de a y de b, es decir, c = αa = βb (6.1.1) para ciertos α, β ∈ Z. Entonces tenemos αda0 = βdb0 y, por tanto, αa0 = βb0 . Como, por el corolario 19, a0 y b0 son coprimos, por la proposici´on 17 a0 | β y podemos escribir β = γa0 para cierto γ ∈ Z Sustituyendo β en (1) obtenemos c = γa0 b = γa0 db0 = γm

(6.1.2)

que es mayor o igual que m y, en consecuencia, m = mcm(a, b). Adem´as ab = a0 db0 d = md = mcd(a, b) mcm(a, b). En la igualdad (2) se ha visto que que si c es m´ ultiplo de a y b, entonces tambi´en lo es de su m´ınimo com´ un m´ ultiplo. El concepto de m´ınimo com´ un m´ ultiplo de un n´ umero finito de enteros es an´ aloga al de dos y tambi´en tenemos, usando el teorema anterior, un resultado parecido al corolario 14. 56

6.1.26. Definici´ on. Sean a1 , . . . , an n´ umeros enteros no nulos. El m´ınimo com´ un m´ ultiplo de a1 , . . . , an , que denotaremos por mcm(a1 , . . . , an ), se define como el menor entero positivo que es m´ ultiplo de a1 , . . . , an a la vez. Si ai = 0 para alg´ un i, definimos mcm(a1 , . . . , an ) = 0. 6.1.27. Corolario. Sean a1 , . . . , an ∈ Z. Entonces m = mcm(a1 , . . . , an ) si y solo si se cumplen las condiciones (1) m es m´ ultiplo de a1 , . . . , an . (2) Si c es m´ ultiplo de a1 , . . . , an , entonces c es m´ ultiplo de m. (3) m ≥ 0. Demostraci´ on. Se deja como ejercicio.

6.1.3.

La ecuaci´ on diof´ antica lineal

El precio del caf´e en la m´aquina de la planta baja es de 40 cts. Ana solo tiene monedas de 50 cts y la m´aquina solo devuelve cambio en monedas de 20 cts. Ana sabe por experiencia que si la m´aquina no tiene el cambio exacto, simplemente no lo devuelve. Si Ana no quiere perder dinero ¿podr´a tomarse un caf´e? Si llamamos x al n´ umero de monedas de 50 cts. que introduce Ana e y el n´ umero de monedas de 20 cts. que le devuelve la m´aquina, se tiene que cumplir la ecuaci´ on 50x − 20y = 40 Una ecuaci´ on de este tipo, en la que se buscan soluciones que sean n´ umeros enteros, se llama una ecuaci´ on diof´antica lineal. Veamos su soluci´on. 6.1.28. Proposici´ on. Sean a, b, c ∈ Z y d = mcd(a, b). La ecuaci´ on diof´ antica ax + by = c tiene soluci´ on si y solo si d divide a c. En este caso, la soluci´ on general son todos los n´ umeros enteros de la forma  x = x0 + x0 y = y0 + y 0 donde x0 , y0 es una soluci´ on particular de la ecuaci´ on e x0 , y 0 es una soluci´ on de la ecuaci´ on ax + by = 0, llamada ecuaci´ on homog´enea asociada. Demostraci´ on. Si existen x, y ∈ Z tales que ax+by = c, entonces d | ax−by = c. Rec´ıprocamente, supongamos que d | c y pongamos a = a0 d, b = b0 d y c = c0 d. Si αa + βb = d es una identidad de B´ezout, multiplicando por c0 tenemos (c0 α)a + (c0 β)b = c0 d = c y la ecuaci´on tiene soluci´on. Veamos ahora c´omo son las soluciones. Supongamos que x0 , y0 es una soluci´on particular. Si x, y es una soluci´ on, entonces ax + by = ax0 + by0 = c, es decir, a(x − x0 ) + b(y − y0 ) = 0, luego poniendo x0 = x − x0 e y 0 = y − y0 vemos que la soluci´ on x, y tiene la forma deseada. Rec´ıprocamente, si x, y son como se indica en el enunciado, est´a claro que son soluci´on de la ecuaci´on. 57

6.1.29. Proposici´ on. Sean a, b, c ∈ Z, d = mcd(a, b) y pongamos a = a0 d, 0 b = b d. Las soluciones de la ecuaci´ on homog´enea ax + by = 0 son  x = −b0 t y = a0 t donde donde t es un entero cualquiera. Demostraci´ on. Si existen x, y ∈ Z tales que ax + by = 0, entonces ax = −by y dividiendo por d tenemos a0 x = −b0 y. (6.1.3) Dado que a0 y b0 son coprimos y a0 divide a −b0 y, a0 debe dividir a y, luego existe t ∈ Z tal que y = a0 t. Sustituyendo en (3) se tiene a0 x = −b0 a0 t y, por tanto, x = −b0 t. Por otra parte, se comprueba f´acilmente que todos los enteros de esa forma son soluci´ on de la ecuaci´on. Volviendo al ejemplo del inicio, tenemos que resolver la ecuaci´on 50x−20y = 40. Dado que mcd(50, −20) = 10 vemos que la ecuaci´on tiene soluci´on. Si calculamos una identidad de B´ezout obtenemos, por ejemplo, como soluci´on particular x0 = 4 e y0 = 8. Por otra parte, las soluciones de la ecuaci´on homog´enea son  x = 2t y = 5t. Por tanto, la soluci´ on general de la ecuaci´on es  x = 4 + 2t y = 8 + 5t Tenemos que ver ahora si hay soluciones positivas y cu´al es la m´as peque˜ na. Si exigimos que x, y ≥ 0 deber ser t ≥ −1. Tomando t = −1 vemos que Ana puede introducir 2 monedas de 50 cts y la m´aquina le devolver´a 3 monedas de 20 cts y un caf´e.

6.1.4.

M´ umeros primos. Teorema fundamental de la aritm´ etica

6.1.30. Definici´ on. Un entero p 6= 1, −1 se dice que es primo si sus u ´nicos divisores son 1, −1, p y −p. 6.1.31. Ejemplo. El primo positivo m´as peque˜ no es el 2 y es tambi´en el u ´nico primo par junto con el −2. Los primos siguientes son 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, . . . , 997, . . . , 252097800623, . . . , 243112609 − 1, . . . 1 6.1.32. Lema. Si p es un n´ umero primo y p | a1 a2 · · · an con a1 , . . . , an enteros, entonces p divide a ai para algun i. 1 El primo 243112609 − 1 es el mayor conocido a fecha de junio de 2009. Fue descubierto por el proyecto GIMPS (Great Internet Mersenne Prime Search) de inform´ atica distribuida el 23 de agosto de 2008 y tiene 12978189 cifras.

58

Demostraci´ on. Se deja como ejercicio. Proceder por inducci´on y aplicar la proposici´ on 17. 6.1.33. Teorema [Teorema fundamental de la aritm´ etica]. Sea a ∈ Z, a 6= 0, 1, −1. Entonces a = p1 p2 · · · pt para alg´ un t ≥ 1 y p1 , · · · , pt primos no necesariamente dististos. Adem´ as, estos primos son u ´nicos salvo quiz´ as el signo y el orden en el que est´ an escritos. Demostraci´ on. Veamos primero que existe una tal descomposici´on. Supongamos a > 0 y procedamos por reducci´on al absurdo. Entonces, el conjunto de los enteros mayores que 1 para los cuales no existe una tal descomposici´on tiene un minimo a0 que no puede ser primo y, por tanto, se escribe como a0 = bc con b y c distintos de 1 y −1. Como a > 0 podemos suponer que b, c > 0. Entonces a0 = bc con 1 < b < a0 y 1 < c < a0 . Ahora bien, como 1 < b, c < a0 , los enteros b y c s´ı se escriben como producto de primos: b = q1 · · · qr y c = q10 · · · qs0 pero entonces a tambi´en lo que contradice su elecci´on. Si a < −1, entonces −a = |a| = p1 · · · pt para cierto t ≥ 1 y p1 , . . . , pt primos y, por tanto, a = −|a| = (−p1 )p2 · · · pt con −p1 , p2 , . . . , pt primos. Probemos ahora la unicidad de la descomposici´on. Supongamos a = p1 · · · pt = q1 · · · qr

(6.1.4)

con p1 , . . . , pt , q1 . . . , qr primos y procedamos por inducci´on sobre t. Si t = 1, entonces a = p1 = q1 · · · qr . Dado que p1 es primo no tiene m´as divisores primos que −p1 y p1 . Por tanto, debe ser r = 1 y q1 = p1 . Supongamos ahora el resultado cierto para t = k y demostr´emoslo para t = k + 1. Si a = p1 · · · pk+1 = q1 · · · qr tenemos que pk+1 divide a q1 · · · qr . Por el lema anterior, pk+1 divide a qs para alg´ un s. Reordenando los q 0 s podemos suponer que s = r, es decir, pk+1 | qr . Como los u ´nicos divisores primos de qr son −qr y qr tenemos que qr = ±pk+1 . Sustituyendo en (4) obtenemos p1 · · · pk pk+1 = q1 · · · qr−1 (±pk ) y cancelando pk+1 , p1 · · · pk = ±q1 · · · qr−1 . Por hip´ otesis de inducci´ on k = r−1. Por tanto, k+1 = r y, despu´es de reordenar si hace falta, q1 = ±p1 , q2 = ±p2 , . . . , qk = ±pk como quer´ıamos demostrar

59

6.1.34. Corolario. Sea a ∈ Z, a 6= 0, 1, −1. Entonces, a = ±pn1 1 · · · pns s para ciertos primos positivos diferentes p1 , . . . , ps y naturales n1 , . . . , ns . Adem´ as, estos primos y sus respectivos n0i s son u ´nicos (salvo el orden). Demostraci´ on. Se deja como ejercicio. 6.1.35. Corolario. Seab a, b ∈ Z con descomposiciones en primos a = p1n1 · · · pns s

b = q1m1 · · · qrmr .

Entonces, el mcd(a, b) puede calcularse haciendo el producto de los primos comunes de a y b elevados a la m´ınima potencia, y el mcm(a, b) puede calcularse haciendo el producto de los primos comunes y no comunes de a y b elevados a la m´ axima potencia. Demostraci´ on. Se deja como ejercicio. Finalmente, vamos a demostrar que existen infinitos n´ umeros primos. 6.1.36. Teorema. Existen infinitos n´ umeros primos. Demostraci´ on. Procedemos por reducci´on al absurdo. Supongamos que p1 , . . . , pn son todos los n´ umeros primos y consideremos el n´ umero N = p1 · · · pn + 1. Dado que N es mayor que pi para todo i, no puede ser primo y, por tanto, debe ser divisible por alguno de los primos anteriores. Pero si pi | N , entonces pi | N − p1 · · · pn = 1 lo cual es contradictorio. En todo este cap´ıtulo m denotar´a siempre un entero mayor que 1. A continuaci´ on vamos a definir la relaci´on de congruencia m´odulo m que ya hab´eis visto como ejemplo al estudiar las relaciones de equivalencia.

6.2.

Congruencias.

6.2.1. Definici´ on. Dados dos n´ umeros x, y ∈ Z, decimos que son congruentes m´ odulo m y escribimos x ≡ y (mod m) si x − y es m´ ultiplo de m. 6.2.2. Proposici´ on. La relaci´ on de congruencia m´ odulo m es una relaci´ on de equivalencia. Demostraci´ on. Ejercicio. 6.2.3. Proposici´ on. Sean a, b ∈ Z y m un entero mayor que 1. (1) Si r es el resto de la divisi´ on de a entre m, entonces a ≡ r (mod m).

60

(2) Si r1 ≡ r2 (mod m) y 0 ≤ r1 , r2 < m, entonces r1 = r2 . (3) a ≡ b (mod m) si y solo si a y b dan el mismo resto al dividirlos por m Demostraci´ on. Ejercicio. Vemos que cada clase m´odulo m tiene un u ´nico representante r entre 0 y m − 1. Se le llama representante can´ onico y se obtiene como el resto de la divisi´ on entera de cualquier elemento de la clase entre m. Por este motivo, a las clases de congruencia m´ odulo m tambi´en se las llama clases de restos m´ odulo m. Dado un entero x, denotemos por x la clase de equivalencia de representante x. Entonces, por las propiedades de las clases en una relaci´on de equivalencia, sabemos que a = b o a ∩ b = ∅. a = b si y solo si a ≡ b (mod m). a ∩ b = ∅ si y solo si a 6≡ b (mod m). Denotamos por Z/(m) o Zm el conjunto cociente de Z por la relaci´on de congruiencia m´ odulo m, es decir, Zm = {a | a ∈ Z}. Por lo que hemos dicho, Zm tiene exactamente m elementos: Zm = { 0, 1, . . . m − 1 }. Los enteros 0, 1, . . . , m − 1 son los representantes can´onicos de las clases y se corresponden con los posibles restos que se obtienen al dividir un entero entre m.

6.2.1.

Propiedades aritm´ eticas de las congruencias

Veamos c´ omo se comportan las congruencias con la suma y el producto de n´ umeros enteros. 6.2.4. Proposici´ on. Sea m un entero mayor que 1 y sean a, b, a0 , b0 y c n´ umeros enteros arbitrarios. Entonces: (1) Si a ≡ a0 (mod m) y b ≡ b0 (mod m), entonces a + b ≡ a0 + b0 (mod m). (2) Si a ≡ a0 (mod m) y b ≡ b0 (mod m), entonces ab ≡ a0 b0 (mod m). (3) Si a ≡ b (mod m), entonces ac ≡ bc (mod m). El rec´ıproco es cierto si c y m son coprimos. (4) Si c 6= 0, entonces a ≡ b (mod m) si y solo si ac ≡ bc (mod mc).

61

Demostraci´ on. Si a ≡ a0 (mod m) y b ≡ b0 (mod m) tenemos que a − a0 = λm 0 y b − b = µm para ciertos λ, µ ∈ Z. Entonces, (a + b) − (a0 + b0 ) = (a − a0 ) + (b − b0 ) = (λ + µ)m, y, por tanto, a + b ≡ a0 + b0 (mod m). Por otra parte, ab − a0 b0

= (a0 + λm)(b0 + µm) − a0 b0 = a0 b0 + (a0 µ + b0 λ + λµm)m − a0 b0 = (a0 µ + b0 λ + λµm)m,

y, por tanto, ab ≡ a0 b0 (mod m). Con esto hemos probado (1) y (2). La primera parte del apartado (3) sigue del (2). Rec´ıprocamente, si c y m son coprimos y ac ≡ bc (mod m), tenemos (a − b)c = λm para cierto λ ∈ Z. Esto significa que c | λm y, como c y m son coprimos, tenemos que c divide a λ, es decir, λ = cλ0 . Por tanto, (a − b)c = cλ0 m y, entonces a ≡ b (mod m). Finalmente, para demostrar (4), observemos que para un c 6= 0 se tiene que a − b = λm si y solo si ac − bc = λmc. La proposici´ on que acabamos de ver nos permite definir en Zm una suma y un producto de forma que Zm sea un anillo conmutativo. 6.2.5. Proposici´ on. Las operaciones siguientes en Zm a+b=a+b a · b = ab est´ an bien definidas y dotan a Zm de estructura de anillo. Demostraci´ on. Las operaciones est´an definidas a partir de unos representantes concretos de las clases. Por tanto, es necesario probar que la definici´on no depende de los representantes elegidos, pero esto est´a garantizado por la proposici´on anterior. Dejamos como ejercicio comprobar que se cumplen las propiedades de anillo 6.2.6. Ejemplo. En el caso n = 6 las tablas de las operaciones en Z6 son: +

0

1

2

3

4

5

·

0

1

2

3

4

5

0

0

1

2

3

4

5

0

0

0

0

0

0

0

1

1

2

3

4

5

0

1

0

1

2

3

4

5

2

2

3

4

5

0

1

2

0

2

4

0

2

4

3

3

4

5

0

1

2

3

0

3

0

3

0

3

4

4

5

0

1

2

3

4

0

4

2

0

4

2

5

5

0

1

2

3

4

5

0

5

4

3

2

1

62

Observamos en la tabla del producto que hay elementos no nulos a, b tales que ab = 0, por ejemplo, 2 · 3 = 0. De hecho, si m = rs con r y s mayores que 1, entonces r · s = m = 0 en Zm . Tambi´en vemos que los u ´nicos elementos a para los que existe un b tal que ab = 1 son 5 y 1 (5 · 5 = 1 y 1 · 1 = 1). 6.2.7. Definici´ on. Un anillo conmutativo A es un cuerpo si cada elemento a no nulo tiene inverso, es decir, si existe un b ∈ A tal que ab = 1. 6.2.8. Ejercicio. Ver que el inverso de un elemento a es u ´nico. Se denota por a−1 . 6.2.9. Proposici´ on. En Zm , un elemento a tiene inverso si y solo si mcd(a, m) = 1. Tambi´en decimos que a tiene inverso m´ odulo m. Demostraci´ on. a tiene inverso si y solo si existe x tal que a · x = 1 para cierto x ∈ Z. Esto pasa si y solo si ax ≡ 1 (mod m), si y solo si ax−1 = my para cierto y ∈ Z; pero esta ecuaci´ on diof´antica tiene soluci´on si y solo si mcd(a, m) = 1. 6.2.10. Corolario. Zm es un cuerpo si y solo si m es primo. Demostraci´ on. Zm es un cuerpo si y solo si todo elemento a 6= 0 tiene inverso. Por la proposici´ on anterior, vemos que Zm es un cuerpo si y solo si mcd(a, m) = 1 para todo a = 1, . . . , m − 1. Eso solo es posible si m es primo. 6.2.11. Ejemplo. Para calcular el inverso de 7 en Z100 , buscamos un x tal que 7 · x = 1, es decir, debemos resolver la ecuaci´on diof´antica 7x − 100y = 1 en la que solo nos interesa una soluci´on particular (y no nos interesa la y). Usando el algoritmo de Euclides, como vimos en el tema anterior, tenemos 7 · 43 − 100 · 3 = 1 Luego (7)−1 = 43 en Z100 . 6.2.12. Definici´ on. Definimos la funci´ on Φ de Euler como la aplicaci´ on de Φ : N → N que asigna a cada n´ umero natural m el n´ umero Φ(m) = |{x ∈ N | 1 ≤ x ≤ m, mcd(x, m) = 1}|. Por tanto, Φ(m) es la cantidad de elementos que tienen inverso en Zm . Por ejemplo, Φ(1) = 1, Φ(2) = 1, Φ(3) = 2, Φ(4) = 2, Φ(12) = 4. Esta funci´on puede calcularse mediante la proposici´on siguiente: 6.2.13. Proposici´ on. Si Φ es la funci´ on de Euler, se tiene (1) Φ(p) = p − 1 si p es primo. (2) Φ(pn ) = pn−1 (p − 1) si p es primo. (3) Si mcd(n, m) = 1, entonces Φ(nm) = Φ(n)Φ(m).

63

(4) Si m = pn1 1 · · · pns s es la descomposici´ on de m en factores primos con p1 , . . . , ps primos distintos, entonces Φ(m) = m(1 −

1 1 ) · · · (1 − ) p1 ps

Demostraci´ on. La veremos en ejercicios. 6.2.14. Ejemplo. Para calcular Φ(1000) descomponemos en factores primos 1000 = 23 · 53 y, entonces Φ(1000) = Φ(23 · 53 ) = Φ(23 )Φ(53 ) = 22 · 1 · 52 · 4 = 400

6.2.2.

Algunas aplicaciones

La aritm´etica modular nos proporciona el marco adecuado para tratar cuestiones de divisibilidad con n´ umeros enteros. 6.2.15. Proposici´ on. Un n´ umero entero es divisible por 3 si y solo si la suma de sus cifras es divisible por 3. Demostraci´ on. Sea m ∈ Z, m > 0 y supongamos que sus cifras se escriben como an an−1 · · · a0 con los ai entre 0 y 9. Entonces m = an 10n + · · · + a1 10 + a0 . m es divisible por 3 si y solo si m ≡ 0 (mod 3). Pero, como 10s ≡ 1 (mod 3) para todo s, tenemos m = an 10n + · · · + a1 10 + a0 ≡ an + · · · + a1 + a0 (mod 3)

6.2.16. Ejercicio. Enunciar y demostrar un criterio de divisibilidad por 9. A continuaci´ on estudiamos las ecuaciones del tipo a x = b en Zm . Estas ecuaciones tienen una soluci´on f´acil si a tiene inverso en Zm . Por ejemplo, consideremos la ecuaci´ on 3 x = 5 en Z20 . Como mcd(3, 20) = 1, vemos, por la proposici´ on 8, que 3 tiene inverso y es 7. Luego, x = 7 · 3 x = 7 · 5 = 35 = 15 en Z20 . Lo que hemos hecho se puede expresar tambi´en en lenguaje de congruencias: la soluci´ on de la ecuaci´on 3x ≡ 5 (mod 20) est´a formada por todos los m´ ultiplos de 20 m´ as 15. 6.2.17. Proposici´ on. Dados los enteros a, b, t ∈ Z, loe enunciados siguientes son equivalentes 64

(1) t es soluci´ on de la ecuaci´ on a x = b en Zm . (2) t es soluci´ on de la congruencia ax ≡ b (mod m). (3) (t, s) es soluci´ on de la ecuaci´ on diof´ antica ax − my = b para alg´ un s ∈ Z. Demostraci´ on. Solo es un cambio de lenguaje entre aritm´etica modular, congruencias y ecuaciones diof´ anticas. 6.2.18. Proposici´ on. Sean a, b, m ∈ Z con m > 1 y d = mcd(a, m). Entonces la ecuaci´ on ax ≡ b (mod m) tiene soluci´ on si y solo si d divide a b. En este caso, la ecuaci´ on tiene d soluciones m´ odulo m que vienen dadas por los enteros x0 , x 0 +

m m m , x0 + 2 , . . . , x0 + (d − 1) d d d

donde x0 es una soluci´ on particular. Equivalentemente, las soluciones son todos los enteros x de la forma m x = x0 + λ d para λ un entero arbitrario. Demostraci´ on. La congruencia ax ≡ b (mod m) es equivalente a la ecuaci´on ax−my = b y esta tiene soluci´on si y solo si d divide a b. En este caso, pongamos b = db0 , a = da0 y m = dm0 . Entonces, la ecuaci´on diof´antica ax − my = b es equivalente a a0 x − m0 y = b0 y su soluci´on es (ver proposiciones 25 y 26 del tema 7)  x = x0 + m0 t y = y0 + a0 t donde (x0 , y0 ) es una soluci´on particular y t es un entero arbitrario, lo que prueba la segunda parte de la proposici´on. Si x0 + λm0 y x0 + µm0 son dos soluciones, tenemos x0 + λm0 ≡ x0 + 0 µm (mod m) si y solo si λm0 ≡ µm0 (mod dm0 ) si y solo si λ ≡ µ (mod d) lo que prueba la primera parte. 6.2.19. Ejemplos. 1. 4x ≡ 3 (mod 7) Como 4 y 7 son primos entre s´ı, buscamos el inverso de 4 en Z7 . R´apidamente vemos que 4 · 2 = 1, luego multiplicamos ambos miembros de la congruencia por 2 y obtenemos x ≡ 2 · 3 = 6 (mod 7). Por tanto, la soluci´ on u ´nica m´odulo 7 es x = 6. En otras palabras, los n´ umeros enteros que satisfacen la congruencia son los de la forma 7λ + 6, es decir, los m´ ultiplos de 7 m´as 6.

65

2. 77x ≡ 30 (mod 180) En este caso tenemos 77 = 7·11 y 180 = 22 ·32 ·5, luego tambi´en son primos entre s´ı y la congruencia tiene soluci´on u ´nica m´odulo 180. Para calcular el inverso de 77 en Z180 recurrimos a la Identidad de B´ezout. Despu´es de realizar los c´ alculos tenemos 180 · 3 + 77 · (−7) = 1, de donde 77(−7) ≡ 1 (mod 180). Multiplicamos, pues, la congruencia por −7 y obtenemos x ≡ −7 · 30 = −210 ≡ −30 (mod 180). Por tanto, la soluci´ on u ´nica m´odulo 180 es x = −30, es decir, los m´ ultiplos de 180 menos 30. 3. 572x ≡ 20 (mod 700) Calculamos el m´ aximo com´ un divisor de 572 y 700 mediante el algoritmo de Euclides y obtenemos mcd(572, 700) = 4. Como 4 divide a 20 la congruencia tiene 4 soluciones distintas m´odulo 700. Aprovechamos los c´ alculos hechos para expresar 4 como combinaci´on lineal entera de 572 y 700. Obtenemos 572 · 82 + 700 · (−67) = 4. Dividiendo por 4 la ecuaci´on inicial debemos resolver 143x ≡ 5 (mod. 175). Dividimos por 4 la expresi´on de arriba y tenemos 143·82+175·(−67) = 1, por lo que el inverso de 143 m´odulo 175 es 82. Multiplicando por 82 se obtiene x = 82 · 5 = 410 ≡ 60 (mod 175). Finalmente, las soluciones de la ecuaci´ on inicial son x = 60, x = 60 + 175, x = 60 + 350, x = 60 + 525 m´ odulo 700, o lo que es lo mismo, todos los n´ umeros enteros que son m´ ultiplos de 175 m´ as 60. 4. 35x + 8y = 5 Veamos que podemos usar las congruencias para resolver esta ecuaci´on diof´ antica. Si hacemos m´odulo 8 obtenemos 35x + 8y ≡ 3x ≡ 5 (mod 8). El inverso de 3 m´ odulo 8 es 3, luego x = 8λ − 1. Sustituyendo x en la ecuaci´ on tenemos 35(8λ − 1) + 8y = 5, es decir, 35λ + y = 5. Por tanto, (x, y) es soluci´ on de la ecuaci´on inicial si y solo si x = 8λ − 1 y (λ, y) es soluci´ on de 35λ + y = 5. Concluimos, pues, que la soluci´on general de la ecuaci´ on es  x = −1 + 8λ y = 5 − 35λ 66

6.3.

Congruencias de Euler y Fermat

6.3.1. Proposici´ on [Congruencia de Euler]. Sea m > 1 un entero. Si a es coprimo con m, entonces aΦ(m) ≡ 1 (mod m). Demostraci´ on. Lo que queremos demostrar es equivalente a probar que a Φ(m) = 1 en Zm . Trabajaremos, por tanto, en el anillo Zm , en el cual a tiene inverso. Sea U el conjunto de todos los elementos de Zm que tienen inverso, es decir, U = {x ∈ Zm | mcd(x, m) = 1} y consideremos la siguiente aplicaci´on f: U x

−→ 7−→

U a·x

Pod´eis ver como ejercicio que est´a bien definida (es decir, que a · x efectivamente pertenece a U y que la imagen de x no depende del representante escogido para la clase de x). Vamos a demostrar que f es biyectiva. Para ello, como U es finito, bastar´ a con demostrar que es inyectiva. Supongamos que f (x) = f (y), es decir, a · x = a · y. Como a tiene inverso en Zm , tenemos x = a −1 · a · x = a −1 · a · y = y como quer´ıamos ver. Si f es biyectiva, la imagen de f no es m´as que una permutaci´on de los elementos de U . Si ponemos U = {x1 , . . . , xΦ(m) }, entonces {x1 , . . . , xΦ(m) } = {a · x1 , . . . , a · xΦ(m) } y, por tanto, x1 · · · xΦ(m) = (a · x1 ) · · · (a · xΦ(m) ). Reordenando los factores, tenemos x1 · · · xΦ(m) = a Φ(m) · x1 · · · · xΦ(m) y, como todos los elementos de U tienen inverso, podemos cancelar x1 , . . . , xΦ(m) en cada miembro para obtener aΦ(m) ≡ 1 (mod m).

6.3.2. Corolario [Peque˜ no teorema de Fermat(primera versi´ on)]. Sea p > 1 un n´ umero primo. Entonces se cumple ap−1 ≡ 1 (mod p) para todo entero a no divisible por p. 67

Demostraci´ on. Sigue del resultado anterior dado que Φ(p) = p − 1. 6.3.3. Corolario [Peque˜ no teorema de Fermat(seguna versi´ on)]. Sea p > 1 un n´ umero primo. Entonces se cumple ap ≡ a (mod p) para todo entero a. Demostraci´ on. Si a es m´ ultiplo de p, entonces los dos miembros son congruentes con 0. En caso contrario se tiene ap−1 ≡ 1 (mod p) por el resultado anterior y, multiplicando por a, ap ≡ a (mod p). 6.3.4. Ejemplo. ¿Cu´ ales son las dos u ´ltimas cifras del n´ umero 1031243 ? Este problema es equivalente a saber cu´al es el representante can´onico de 1031243 m´ odulo 100. Para empezar 1031243 ≡ 31243 (mod 100). Ahora, dado que mcd(3, 100) = 1 podemos usar la congruencia de Euler, que dice, en este caso, 3Φ(100) ≡ 1 (mod 100) =⇒ 340 ≡ 1 (mod 100) dado que Φ(100) = Φ(22 · 52 ) = Φ(22 )Φ(52 ) = 40. Si dividimos 1243 entre 40 tenemos 1243 = 31 · 40 + 3 y, por tanto, 31243 = 331·40+3 = (340 )31 · 33 ≡ 33 = 27 (mod 100). Luego las dos u ´ltima cifras de 1031243 son 2 y 7.

6.4.

Teorema chino de los restos

En esta secci´ on nos preocupamos de la resoluci´on de sistemas de congruencias    a1 x ≡ b1 (mod. m1 ) .. .   ak x ≡ bk (mod. mk ) En primer lugar observamos que para que el sistema tenga soluci´on, cada congruencia por separado debe tenerla. Por tanto, para cada i dividimos la ecuaci´on i-´esima por mcd(ai , mi ), resultando una ecuaci´on del tipo a0i x ≡ b0i (mod. m0i ) donde ahora mcd(a0i , m0i ) = 1. Si ahora multiplicamos por el inverso de a0i m´odulo m0i tenemos una ecuaci´ on del tipo x ≡ ci (mod. m0i ). En consecuencia, el problema se reduce a estudiar sistemas de congruencias del tipo

68

   x ≡ b1 .. .   x ≡ bk

(mod m1 ) (mod mk ).

Veamos en primer lugar que, caso de tener soluci´on, esta es u ´nica m´odulo el m´ınimo com´ un m´ ultiplo de m1 , . . . , mk . 6.4.1. Proposici´ on. La soluci´ on, si existe, de un sistema de ecuaciones del tipo    x ≡ b1 (mod m1 ) .. .   x ≡ bk (mod mk ). es u ´nica m´ odulo mcm(m1 , . . . , mk ). Demostraci´ on. Sea M = mcm(m1 , . . . , mk ). Si x, y son soluciones, entonces x, y ≡ bi (mod mi ), luego x ≡ y (mod mi ). Por tanto, x − y es m´ ultiplo de todos los mi y, en consecuencia x ≡ y (mod M ). Ahora podemos ver c´ omo hallar una soluci´on en el caso en que los mi sean primos entre s´ı. 6.4.2. Teorema [Teorema Chino de los Restos, Sun Tzu s. III]. Sean b1 , . . . , bk enteros arbitrarios y m1 , . . . , mk enteros positivos tales que mcd(mi , mj ) = 1 para todo i 6= j. Entonces, el sistema de congruencias    x ≡ b1 (mod m1 ) .. .   x ≡ bk (mod mk ) tiene soluci´ on u ´nica m´ odulo M = m1 · · · mk . M Demostraci´ on. Consideremos los enteros M = m1 · · · mk y Mi = m . Veamos i que Mi y mi son primos entre s´ı: si p es un n´ umero primo que divide a Mi y mi , entonces p divide a alg´ un mj con j 6= i y llegamos a contradicci´on pues mcd(mi , mj ) = 1. Por tanto, Mi tiene un inverso m´odulo mi . Sea Ni tal que Mi Ni ≡ 1 (mod mi ) y obs´ervese que Mi Ni ≡ 0 (mod mj ) si j 6= i. Ahora no es dif´ıcil ver que el n´ umero entero

x0 = b1 M1 N1 + · · · + bk Mk Nk es una soluci´ on del sistema de congruencias que es u ´nica m´odulo M por la proposici´ on anterior. 6.4.3. Ejemplos.

69

1.

x ≡ a (mod 3) x ≡ b (mod 4) x ≡ c (mod 5) Tenemos M = 3 · 4 · 5 = 60, M1 = 20, M2 = 15 y M3 = 12, y debemos calcular N1 , N2 y N3 tales que 20N1 ≡ 1 (mod. 3)

15N2 ≡ 1 (mod. 4)

12N3 ≡ 1 (mod. 5).

Vemos f´ acilmente que podemos tomar N1 = 2, N2 = 3 y N3 = 3, de donde la soluci´ on u ´nica m´ odulo 60 del sistema es x = 40a + 45b + 36c.

2.

8x ≡ 2 (mod 10) 15x ≡ 6 (mod 21) 9x ≡ 15 (mod 24) Vemos que cada congruencia por separado tiene soluci´on y dividiendo cada una por el m´ aximo com´ un divisor apropiado el sistema es equivalente a este otro: 4x ≡ 1 (mod 5) 5x ≡ 2 (mod 7) 3x ≡ 5 (mod 8). Ahora buscamos los inversos de 4, 5 y 6 m´odulo 5, 7 y 8 respectivamente. A simple vista vemos que 4 · (−1) ≡ 1 (mod. 5)

5 · 3 ≡ 1 (mod. 7)

3 · 3 ≡ 1 (mod. 8).

Multiplicando cada ecuaci´on por el n´ umero correspondiente tenemos x ≡ −1 (mod. 5) x ≡ 6 ≡ −1 (mod 7) x ≡ 15 ≡ −1 (mod 8). Sin hacer m´ as c´ alculos vemos que x = −1 es soluci´on. En conclusi´on, la soluci´ on del sistema inicial es x = −1 m´odulo mcm(5, 7, 8) = 280.

3.

x ≡ 1 (mod 6) x ≡ 5 (mod 10) x ≡ 11 (mod 14) En este caso, los m´ odulos no son primos entre s´ı y no podemos aplicar el teorema chino de los restos. Aun as´ı podemos proceder de la siguiente manera: las soluciones de la primera ecuaci´on son los enteros de la forma x = 6t + 1. 70

Sustituyendo en la segunda, tenemos 6t + 1 ≡ 5 (mod. 10). La solucion de esta ecuaci´on son los m´ ultiplos de 5 menos 1, es decir, t = 5s − 1, que sustituyendo en la expresi´on de x hallamos x = 6t + 1 = 6(5s − 1) + 1 = 30s − 5. Por tanto, la soluci´ on del sistema formado por las dos primeras ecuaciones es x = −5 m´ odulo 30. Luego, ahora debemos resolver x ≡ −5 (mod 30) x ≡ 11 (mod 14). Siguiendo el mismo procedimiento, concluimos que la soluci´on del sistema propuesto es x = 25 m´odulo 210.

71

Cap´ıtulo 7

Polinomios En este tema vamos a estudiar los anillos de polinomios en una variable con coeficientes en un cuerpo conmutativo, haciendo especial hincapi´e en los cuerpos num´ericos.

7.1.

Polinomios con coeficientes en un cuerpo.

7.1.1. Definici´ on. Sea K un cuerpo. Un polinomio con coeficientes en K es una expresi´ on de la forma a0 + a1 X + a2 X 2 + · · · + an X n para un entero n ≥ 0 y elementos a0 , . . . , an ∈ K. La X se llama indeterminada y los elementos a0 , . . . , an se llaman los coeficientes del polinomio. Los polinomios de la forma a0 se llaman constantes y se identifican con los elementos del cuerpo K. El conjunto de todos los polinomios con coeficientes en K se denota por K[X]. Diremos que dos polionomios a0 +· · ·+an X n y b0 +· · ·+bm X m con m ≥ n son iguales si y solo si ai = bi para todo i = 1, . . . , n y bj = 0 para j = n + 1, . . . , m. 7.1.2. Ejemplos. Hemos visto que Q, R, C y Zp con p primo son cuerpos. Podemos considerar polinomios con coeficientes en cualquiera de estos cuerpos. (1) 5 + 2X 2 es un polinomio de Z7 [X]. √ (2) 1 + 2X − 5X 2 − πX 3 es un polinomio de R[X]. (3) 1 +

17 15 8 X

es un polinomio de Q[X].

(4) X − (1 + i)X 3 − X 7 es un polinomio de C[X]. (5) Q[X] ⊆ R[X] ⊆ C[X]. Veamos ahora c´ omo se definen la suma y producto de polinomios.

72

7.1.3. Definici´ on. Dados dos polimomios de K[X] A = a0 + a1 X + a2 X 2 + · · · + an X n B = b0 + b1 X + b2 X 2 + · · · + bm X m se define su suma como A + B = (a0 + b0 ) + (a1 + b1 )X + · · · + (an + bn )X n si n ≥ m (se sobreentiende que bk = 0 si k ≥ m). El producto AB se define como el polinomio C = c0 +c1 X +· · ·+cn+m X n+m cuyos coeficientes son X ck = ai bj = a0 bk + a1 bk−1 + · · · + ak b0 . i+j=k

7.1.4. Ejemplos.

(1) En Q[X], R[X] o C[X] se tiene (3 + X)(X 2 + 2X 3 ) = 3X 2 + 7X 3 + 2X 4

(2) En Z3 [X], (3 + X)(X 2 + 2X 3 ) = 3X 2 + 7X 3 + 2X 4 = X 3 + 2X 4 . 7.1.5. Proposici´ on. K[X] es un anillo conmutativo con las operaciones de suma y producto de polinomios. Demostraci´ on. Ejercicio. 7.1.6. Definici´ on. Decimos que un polinomio no nulo A tiene grado n si A = a0 + a1 X + a2 X 2 + · · · + an X n con an 6= 0. El grado de A se denotar´ a por gr(A). El grado del polinomio 0 de denotar´ a por −∞. Sea A = a0 + a1 X + a2 X 2 + · · · + an X n . Llamamos coeficiente de grado i del polimonio A al coeficiente ai . El coeficiente de grado n de un polinomio no nulo de grado n se llama coeficiente de grado m´ aximo o coeficiente principal. El coeficiente de grado cero se llama t´ ermino independiente. Si un polinomio tiene coeficiente pricipal igual a 1, se llama polinomio m´ onico La siguiente proposici´ on describe las propiedades del grado, utilizando si hace falta el convenio siguiente: −∞ + n = −∞, (−∞) + (−∞) = −∞ y −∞ < n para todo n. 7.1.7. Proposici´ on. Sean A, B ∈ K[X]. Entonces (1) gr (AB) = gr (A) + gr (B). (2) gr (A + B) ≤ m´ ax {gr (A), gr (B)}. (3) Si AB = 0, entonces A = 0 o B = 0 (decimos que K[X] es un dominio). (4) A tiene inverso si y solo si A es de grado 0. 73

Demostraci´ on. Ejercicio. Se deduce f´acilmente de la definici´on de grado. Conocemos desde la educaci´on secundaria un algoritmo para dividir polinomios, por ejemplo: X 3+

2X 2 − 3

X −1

−X 3 + 32 X 5 2X

1 2X

−1

de donde X 3 + X − 1 = (2X 2 − 3)( 12 X) + ( 52 X − 1). Vamos a utilizar este algoritmo para demostrar que, al igual que en Z, en K[X] tambi´en tenemos divisi´on entera. 7.1.8. Teorema [de la divisi´ on entera]. Sea K un cuerpo conmutativo y A, B ∈ K[X] dos polinomios con B 6= 0. Entonces, existen dos u ´nicos polinomios Q, llamado cociente, y R, llamado resto, en K[X] tales que A = BQ + R y gr (R) < gr (B). Demostraci´ on. Empecemos por ver la existencia del cociente y el resto. Si gr (A) < gr (B), podemos tomar Q = 0 y R = A. Supongamos, por tanto, gr (A) ≥ gr (B) y procedamos por inducci´on sobre el grado de A. Si gr (A) = 0, entonces A = λ ∈ K con λ 6= 0. Como el grado de B es menor o igual que el grado de A, tambi´en es B = µ ∈ K \ {0}. Entonces, podemos tomar Q = µ−1 λ y R = 0. Por hip´ otesis de inducci´on, supongamos que el resultado a demostrar es cierto para todos los polinomios A y B con gr (A) ≥ gr (B) y gr (A) ≤ k − 1 y demostr´emoslo para un polinomio de grado k. Sean A = a0 + · · · + ak X k y B = b0 + · · · + bm X m con ak , bm 6= 0 y k ≥ m ≥ 0. Recordando el algoritmo de la divisi´ on, consideremos el polinomio k−m C = A − (ak b−1 )B. m X

(7.1.1)

Esta claro que gr (C) < gr (A) = k, ya que el t´ermino de grado m´aximo de k−m )B se cancela con el de grado m´aximo de A. Luego, por hip´otesis (ak b−1 m X de inducci´ on, existen polinomios E y R tales que C = BE + R

y

gr (R) < gr (B)

Combinando (1) y (2) se obtiene k−m A − (ak b−1 )B = BE + R m X

y k−m A = (ak b−1 + E)B + R m X

con gr (R) < gr (B). La unicidad la dejamos como ejercicio. 74

(7.1.2)

7.1.9. Ejercicio. Efectuar las siguientes divisiones enteras: ◦ X 5 − X 4 + X 3 + 4X 2 − 6X + 2 entre X 3 − 2X + 1 en Q[X]. ◦ X 5 − X 4 + 2X 3 + 4X 2 − X + 1 entre 2X 2 − 3X + 2 en Z7 [X]. 7.1.10. Definici´ on. Dados dos polinomios A, B ∈ K[X], decimos que A divide a B o que B es m´ ultiplo de A si existe un polinomio C tal que B = AC, es decir, la divisi´ on entera de B entre A da resto 0. Si A divide a B y B 6= 0, decimos que A es un divisor de B. 7.1.11. Ejemplos.

(1) El polinomio X + 1 divide a X 2 − 1 en R[X].

(2) El polinomio X + 1 divide a X 2 + 1 en Z2 [X]. (3) Todo polinomio divide al polinomio 0. (4) Un polinomio de grado cero (por tanto de la forma A = λ ∈ K con λ 6= 0) divide a todos los polinomios. 7.1.12. Proposici´ on. Sean A, B, C ∈ K[X]. (1) A | B y A | C ⇒ A | B + C (2) A | B ⇒ A | B · C (3) A | B y B | C ⇒ A | C Demostraci´ on. Igual que la Proposici´on 5 del tema 7. XXXXX 7.1.13. Proposici´ on. Sean A, B ∈ K[X]. Entonces A | B y B | A ⇒ A = µB para alg´ un µ ∈ K, µ 6= 0 Demostraci´ on. Tenemos A = BC y B = AD para ciertos polinomios C y D. Entonces A = ADC, es decir, A(1 − DC) = 0, y, por tanto, A = 0 o DC = 1. En el primer caso, B tambi´en es cero y se cumple que A = µB. En el segundo caso, C y D son de grado cero y tambi´en se cumple la condici´on deseada. 7.1.14. Definici´ on. Dado un polinomio A ∈ K[X], a los polinomios de la forma λA para λ ∈ K, λ 6= 0 los llamaremos polinomios asociados de A. Observemos que cada polinomio tiene un u ´nico polinomio asociado m´ onico. 7.1.15. Definici´ on. Dados dos polinomios A, B ∈ K[X], decimos que un polinomio D es el m´ aximo com´ un divisor de A i B si cumple (1) D | A y D | B. (2) Dado S ∈ K[X], si S | A y D | B, entonces S | D. 7.1.16. Proposici´ on. Sean A, B ∈ K[X]. Si D es un m´ aximo com´ un divisor de A y B y D0 es otro m´ aximo cam´ un divisor de A y B, entonces D y D0 son asociados. 75

Demostraci´ on. De la definici´on deducimos que D | D0 y D0 | D. El m´ aximo com´ un divisor puede calcularse tambi´en mediante el algoritmo de Euclides, pues este se basa u ´nicamente en la divisi´on entera. Por tanto, no repetiremos los argumentos te´oricos que usamos con Z. Veamos un ejemplo: para calcular el m´ aximo com´ un divisor de los polinomios A = X 5 − X 4 + X 3 − X 2 3 2 y B = X − 2X + X − 2 procedemos de la siguiente forma: X2 + X + 2 X5 − X4 + X3 − X2

X 3 − 2X 2 + X − 2

2

0

4X + 4

1 1 4X − 2 2

4X + 4

Un m´ aximo com´ un divisor es 4X 2 + 4 y cualquier otro debe ser de la forma 2 µ(4X + 4) con µ 6= 0, en particular el asociado m´onico X 2 + 1 Tambi´en podemos calcular polinomios R y S tales que X 2 + 1 = A · R + B · S (Identidad de B´ ezout). Las divisiones efectuadas han sido X5 − X4 + X3 − X2 X 3 − 2X 2 + X − 2

(X 3 − 2X 2 + X − 2)(X 2 + X + 2) + (4X 2 + 4) 1 1 = (4X 2 + 4)( X − ). 4 2 =

Luego solo tenemos que despejar en la primera ecuaci´on 4X 2 + 4 = A + B(−X 2 − X − 2), es decir, 1 1 1 1 X 2 + 1 = A( ) + B(− X 2 − X − ). 4 4 4 2 7.1.17. Definici´ on. Dos polinomios A, B ∈ K[X] se llaman coprimos o primos entre s´ı si su m´ aximo com´ un divisor es µ ∈ K, µ 6= 0. Al igual que en Z tenemos los siguientes resultados: 7.1.18. Proposici´ on. Sean A, B ∈ K[X] tales que A | BC. Si A y B son coprimos, entonces A | C. Demostraci´ on. Igual que la Proposici´on 17 del tema 7. XXXXX 7.1.19. Proposici´ on. Sean A, B, C ∈ K[X]. Entonces A y B son coprimos si y solo si existen S, T ∈ K[X] tales que SA + T B = 1. Demostraci´ on. Igual que la Proposici´on 18 del tema 7. 7.1.20. Proposici´ on. Sean A, B ∈ K[X] con alguno de los dos no nulo. Si D es el m´ aximo com´ un divisor de A y B de forma que A = DC y B = DE, entonces C y E son coprimos. Demostraci´ on. Igual que la Proposici´on 19 del tema 7.

76

Vamos ahora a definir el m´ınimo com´ un m´ ultiplo 7.1.21. Definici´ on. Dados dos polinomios A, B ∈ K[X], decimos que un polinomio M es el m´ınimo com´ un m´ ultiplo de A i B si cumple (1) A | M y B | M . (2) Dado N ∈ K[X], si A | N y B | N , entonces M | N . 7.1.22. Proposici´ on. Sean A, B ∈ K[X]. Si M es un m´ınimo com´ un m´ ultiplo de A y B y M 0 es otro m´ınimo com´ un m´ ultiplo de A y B, entonces M y M 0 son asociados. Demostraci´ on. De la definici´on deducimos que M | M 0 y M 0 | M . El m´ınimo com´ un m´ ultiplo puede calcularse a partir del m´aximo comun divisor al igual que suced´ıa con los n´ umeros enteros: 7.1.23. Proposici´ on. Sean A, B ∈ K[X] dos polinomios no nulos y sea D un m´ aximo com´ un divisor de A y B. Entonces el cociente de AB entre D es un m´ınimo com´ un m´ ultiplo de A y B. Demostraci´ on. Igual que el Teorema 22 del tema 7. 7.1.24. Ejemplo. Seg´ un el ejemplo visto m´as arriba tenemos (X 5 − X 4 + X 3 − X 2 )(X 3 − 2X 2 + X − 2) = mcm (A, B), X2 + 1 de donde, mcm (A, B) = X 6 − 3X 5 + 3X 4 − 3X 3 + 2X 2 . El Teorema Fundamental de la Aritm´etica nos dice que todo n´ umero entero descompone como producto de primos. ¿Tenemos el resultado an´alogo para polinomios? El equivalente a los n´ umeros primos parece f´acil: son los polinomios irreducibles. Un polinomio P no nulo es irreducible si siempre que Q divida a P , el polinomio Q debe ser de grado cero o de la forma µP con 0 6= µ ∈ K. Pero antes estudiemos las ra´ıces de polinomios.

7.2.

Ra´ıces de polinomios.

Un polinomio P = a0 + a1 X + · · · + an X n ∈ K[X] define una funci´on P : K → K dada por P (a) = a0 + a1 a + · · · + an an . 7.2.1. Definici´ on. Dado un polinomio P ∈ K[X] y un elemento a ∈ K, decimos que a es ra´ız de P si P (a) = 0. 7.2.2. Ejemplos. (A) Seg´ un la definici´on anterior, todo elemento de K es ra´ız del polinomio cero. (B) a = 1/2 es ra´ız del polinomio 3X 3 −

77

29 2 10 X

−

1 10 X

+

2 5

∈ Q[X].

(C) a = 3 es ra´ız del polinomio X 2 + X + 1 ∈ Z13 [X]. (D) El polinomio X 2 + X + 1 no tiene ra´ıces en R. (E) a =

−1 2

√

+

3 2 i

es ra´ız del polinomio X 2 + X + 1 ∈ C[X].

(F) Un polinomio de grado 1 es de la forma aX + b con a 6= 0 y, por tanto, tiene tiene la ra´ız − ab . 7.2.3. Proposici´ on. Sea P = a0 + a1 X + · · · + an X n un polinomio de grado n a coeficientes enteros. Si un n´ umero racional pq con p y q primos entre s´ı es ra´ız de P , entonces p divide a a0 y q divide a an . Demostraci´ on. Si

p q

es ra´ız de P , entonces a0 + a1

p pn + · · · + an ( n ) = 0, q q

es decir, a0 q n + a1 pq n−1 + · · · + an−1 pn−1 q + an pn = 0. Luego vemos que p divide a0 q n y q divide a an pn . Como p y q son primos entre s´ı, obtenemos la conclusi´ on deseada. 7.2.4. Ejemplos. (A) Un polinomio m´onico a coeficientes enteros solo puede tener ra´ıces enteras. (B) Las posibles ra´ıces racionales del polinomio 18X 3 + 15X 2 − 4X − 4 son 1 1 1 1 1 2 2 4 4 ±1, ±2, ±4, ± , ± , ± , ± , ± , ± , ± , ± , ± . 2 3 6 9 18 3 9 3 9 Entre estas posibilidades comprobamos que ra´ıces.

1 2

y − 23 son efectivamente

7.2.5. Proposici´ on. Sea K un cuerpo y P un polinomio de K[X]. Un elemento a ∈ K es ra´ız de P si y solo si X − a divide a P . Demostraci´ on. Efectuamos la divisi´on entera de P entre X − a y obtenemos P = (X − a)Q + r con r ∈ K, con lo cual vemos que a es ra´ız de P si y solo si r = 0. 7.2.6. Definici´ on. Un elemento a ∈ K es una ra´ız de multiplicidad s ≥ 1 de un polinomio P ∈ K[X] si (X − a)s divide a P pero (X − a)s+1 no divide a P . Decimos que a es una raiz m´ ultiple de P si tiene multiplicidad mayor que 1. Si tiene multiplicidad 1 decimos que a es una ra´ız simple. 7.2.7. Corolario. Sea K un cuerpo y P un polinomio de K[X] de grado n ≥ 1. Entonces, P tiene a lo sumo n ra´ıces, contando cada ra´ız tantas veces como indica su multiplicidad.

78

Demostraci´ on. Procedemos por inducci´on sobre n. Para n = 1, el polinomio P es de la forma P = aX + b y tiene solo una ra´ız. Supongamos cierto el enunciado para polinomios de grado n y sea P de grado n + 1. Si P no tiene ra´ıces, el enunciado es trivialmente cierto. Si, por el contrario, a es una ra´ız de P , entonces P = (X − a)Q con Q un polinomio de grado n. Por la hip´otesis de inducci´ on, Q tiene a lo sumo n ra´ıces y, por tanto, P tiene a lo sumo n + 1 ra´ıces. 7.2.8. Corolario. Sea K un cuerpo. (i) Si P es un polinomio de grado n ≥ 0 y existen m elementos distintos a1 , . . . , am de K tales que P (ai ) = 0 con m > n, entonces P es el polinomio cero. (ii) Si P y Q son polinomios de grado a lo sumo n ≥ 0 y existen m elementos distintos a1 , . . . , am de K tales que P (ai ) = Q(ai ) con m > n, entonces P = Q. Demostraci´ on. (i) Seg´ un el corolario anterior, el polinomio P debe tener grado menor que cero, es decir, P = 0. (ii) En este caso P − Q es un polinomio de grado a lo sumo n y con m > n ra´ıces. Luego P − Q = 0. 7.2.9. Corolario. Sea P = a0 + a1 X + · · · + an X n ∈ K[X] un polinomio de grado n que tiene n ra´ıces r1 , . . . , rn (pueden estar repetidas). Entonces P = an (X − r1 ) · · · (X − rn ). Demostraci´ on. Sea Q = an (X − r1 ) · · · (X − rn ). Entonces Q = an X n + · · · y, por tanto, el polinomio P − Q tiene grado menor o igual que n − 1 y tiene n ra´ıces. Por tanto, P = Q

7.3.

Polinomios irreducibles en R[X] y C[X]. Teorema fundamental del ´ algebra.

7.3.1. Definici´ on. Un polinomio P ∈ K[X] de grado mayor o igual que uno se dice irreducible si para toda descomposici´ on P = QR con Q, R ∈ K[X], se tiene que, o bien el grado de Q es cero, o bien el grado de R es cero. Un polinomio que no sea irreducible se llama reducible. 7.3.2. Ejemplos. (A) Un polinomio de grado 1 es de la forma aX +b con a 6= 0 y es irreducible. En efecto, si aX + b = P Q entonces 1 = gr(P ) + gr(Q) y necesariamente P o Q es de grado cero. (B) Si un polinomio de grado 2 no es irreducible, entonces tiene dos ra´ıces en K (pueden ser dos ra´ıces de multiplicidad 1 o una ra´ız de multiplicidad 2). Ejercicio.

79

(C) Un polinomio P de grado 3 es irreducible si y solo si no tiene ninguna ra´ız en K. En efecto: si P descompone debe hacero como producto de un polinomio de grado 1 por un polinomio de grado 2. El polinomio de grado 1 tiene una ra´ız en K. (D) El polinomio X 2 − 2 no tiene ra´ıces en Q, luego es irreducible en Q[X]. Sin embargo, como √ de R[X] o C[X] es reducible pues se descompone √ polinomio como (X + 2)(X − 2) (E) El polinomio P = X 4 +2X 3 +3X 2 +2X +1 no tiene ra´ıces en Q (ejercicicio) pero no es irreducible en Q[X] pues P = (X 2 + X + 1)2 . 7.3.3. Teorema. Sea K un cuerpo. Todo polinomio de K[X] de grado mayor o igual que 1 factoriza como producto de polinomios irreducibles. Esta factorizaci´ on es u ´nica salvo asociados y el orden de los factores. Demostraci´ on. Ejercicio. Copiar la demostraci´on del Teorema fundamental de la Aritm´etica. Despu´es de este resultado nos gustar´ıa saber c´omo son polinomios irreducibles. La respuesta es f´ acil en el caso complejo y viene dada por el llamado ´ Teorema Fundamental del Algebra: ´ 7.3.4. Teorema [Teorema Fundamental del Algebra]. Todo polinomio de C[X] de grado mayor que cero tiene al menos una ra´ız en C. Demostraci´ on. Este resultado es debido a Gauss y su demostraci´on est´a fuera del alcance de este curso. 7.3.5. Corolario. grado 1.

(i) Un polinomio de C[X] es irreducible si y solo si es de

(ii) Todo polinomio P de grado n ≥ 1 de C[X] factoriza como P = α(X − α1 ) · · · (X − αn ) para cieros n´ umeros complejos α, α1 , . . . , αn . Demostraci´ on. Consecuencia inmediata del teorema anterior. 7.3.6. Ejemplo. Consideremos el polinomio X 8 − 1 ∈ C[X]. Sus ra´ıces son las ra´ıces octavas de la unidad. A simple vista vemos que 1, −1, i y −i son ra´ıces, por lo que el polinomio es divisible por (X − 1)(X + 1)(X − i)(X + i): X 8 − 1 = (X − 1)(X + 1)(X − i)(X + i)(X 4 + 1). Las ra´ıces de (X 4 + 1) son (ejercicio) : α = cos π4 + i sin π4 =

√

2 2

√

+

2 2 i

β = cos( π4 + π2 ) + i sin( π4 + π2 ) = − 80

√

2 2

√

+

2 2 i

β = cos( π4 + π) + i sin( π4 + π) = − α = cos( π4 +

3π 2 )

+ i sin( π4 +

3π 2 )

√

=

√ 2 2 2 − 2 i √ √ 2 2 − 2 2 i.

8

Por tanto, la factorizaci´ on de X − 1 en producto de polinomios irreducibles en C[X] es X 8 − 1 = (X − 1)(X + 1)(X − i)(X + i)(X − α)(X − α)(X − β)(X − β). ¿C´ omo ser´ıa la factorizaci´on en producto de irreducibles en R[X]? Si efectuamos el producto de las tres u ´ltimas parejas de factores en la descomposici´on anterior tenemos √ √ X 8 − 1 = (X − 1)(X + 1)(X 2 + 1)(X 2 + 2X + 1)(X 2 − 2X + 1). Finalmente, la factorizaci´on en Q[X] es (X − 1)(X − 1)(X 2 + 1)(X 4 + 1). 7.3.7. Proposici´ on. Si α = a + bi es una ra´ız compleja de un polinomio P ∈ R[X], entonces su conjugada α = a − bi tambi´en es ra´ız de P . Demostraci´ on. Sea P = a0 + a1 X + a2 X 2 + · · · + an X n . Entonces, a0 + a1 α + 2 a2 α + · · · + an αn = 0, pero por las propiedades de la conjugaci´on de n´ umeros complejos tenemos 0 = a0 + a1 α + · · · + an αn = a0 + a1 α + · · · + an αn = a0 + a1 α + · · · + an α n .

7.3.8. Corolario. Sea P ∈ R[X] un polinomio irreducible. Entonces, o bien P tiene grado 1, o bien P es un polinomio de grado 2 sin ra´ıces reales. Demostraci´ on. Es claro que los polinomios de grado 1 o de grado 2 sin ra´ıces reales son irreducibles. Supongamos que P tiene grado mayor que 2. Queremos ´ ver que no es irreducible. Por el Teorema fundamental del Algebra, P tiene alguna ra´ız α ∈ C. Si α ∈ R, P es divisible por X − α y no es irreducible. Si α 6∈ R, entonces α tambi´en es ra´ız y P es divisible por (X − α)(X − α). Pero si α = a + bi, entonces (X − α)(X − α) = X 2 − 2aX + (a2 + b2 ) ∈ R[X] y P no es irreducible.

7.4.

Factores m´ ultiples.

Vamos a ver un criterio que nos permite saber cu´ando un polinomio tiene factores irreducibles de multiplicidad mayor que 1. 7.4.1. Definici´ on. Sea K un cuerpo y P un polinomio de K[X]. Dado Q, un polinomio irredicible de K[X], decimos que Q es un factor de P de multiplicidad s ≥ 1 si Qs divide a P pero Qs+1 no divide a P . Decimos que Q es un factor m´ ultiple de P si tiene multiplicidad mayor que 1. Si tiene multiplicidad 1 decimos que G es un factor simple. 81

7.4.2. Definici´ on. Dado un cuerpo K, se define la derivada formal de un polinomio P = a0 + a1 X + · · · + an X n ∈ K[X] como el polinomio P 0 = a1 + 2a2 X + 3a3 X 2 + · · · + nan X n . Es f´ acil ver, y se deja como ejercicio, que la derivada formal cumple las propiedades que cumple la derivada de funciones de R en R respecto de la suma y producto de funciones. 7.4.3. Proposici´ on. Sea K = Q, R o C y sea P un polinomio de K[X] de grado mayor o igual que 1. El polinomio P tiene factores irredicibles m´ ultiples en K[X] si y solo si mcd(P, P 0 ) 6= 1. Demostraci´ on. Sea Q un factor irreducible de P de multiplicidad s ≥ 1. Entonces, P = Qs R para cierto polinomio R no divisible por Q. Vamos a probar que Q es un factor irreducible de P 0 de multiplicidad s − 1. En efecto, derivando P 0 = s Qs−1 Q0 R + Qs R0 = Qs−1 (s Q0 R + QR0 ). Luego Qs−1 divide a P 0 . Supongamos que Qs divide a P 0 . Entonces, Q divide a s Q0 R + QR0 , luego Q divide a s Q0 R. Como Q es irreducible y no puede dividir a Q0 pues el grado de Q0 es menor que el de Q1 , tenemos que Q divide a R, lo cual es contradictorio. Procedamos ahora a la demostraci´on del resultado. (⇒) Sea Q un factor irreducible de P de multiplicidad s > 1. Entonces, como hemos visto, Q es un factor irreducible de P 0 de multiplicidad s − 1 ≥ 1 y, por tanto, mcd(P, P 0 ) 6= 1. (⇐) Supongamos D = mcd(P, P 0 ) con gr (D) ≥ 1. Sea Q un factor irreducible de D y supongamos que la multiplicidad de Q en P es s. Vamos a demostrar que s > 1. Hemos visto al pricipio que Q es un factor irreducible de P 0 con multiplicidad s − 1. Como, por hip´otesis, Q divide a P 0 , vemos que s − 1 no puede ser cero, es decir, s > 1.

7.5.

Polinomios irreducibles en Q[X].

En Q[X] no tenemos una descripci´on de los polinomios irreducibles parecida al caso real pero vamos a dar algunos criterios u ´tiles y, para ello, necesitamos demostrar algunos resultados previos. 7.5.1. Definici´ on. Dado un polinomio P con coeficientes enteros, se llama contenido de P al m´ aximo com´ un divisor de los coeficientes de P y se denotar´ a por c(P ). Un polinomio P se llama primitivo si c(P ) = 1, es decir, si el m´ aximo com´ un divisor de sus coeficientes es 1. 7.5.2. Lema. Dado P ∈ Q[X] existe un p/q ∈ Q tal que P = pq P 0 con P 0 primitivo, es decir, todo polinomio de Q[X] es asociado a un polinomio primitivo. 1 Es en este punto en el que utilizamos que K es un cuerpo num´ erico. Si K fuese, por ejemplo, Zp , se podr´ıa dar el caso de que Q0 fuese nulo. A pesar de ello, el resultado tambi´ en es cierto en Zp .

82

Demostraci´ on. Ejercicio. 7.5.3. Ejemplo. 6 2 10 2 2 X + X+ = (9X 2 + 25X + 5) 5 3 5 15 Dado un polinomio Q = a0 + a1 X + · · · + an X n con ai ∈ Z y un n´ umero ˆ al polinomio primo p, denotaremos por Q, ˆ = a0 + a1 X + · · · + an X n ∈ Zp [X]. Q En muchas ocasiones, con el fin de simplificar la notaci´on, se omitir´a la raya que indica la clase m´ odulo p. 7.5.4. Lema. Sea p un n´ umero primo y sean P, Q dos polinomios con coeficientes enteros. ˆ = Pˆ + Q ˆ en Zp [X]. (a) Si R = P + Q, entonces R ˆ = Pˆ Q ˆ en Zp [X]. (b) Si R = P Q, entonces R Demostraci´ on. Ejercicio. 7.5.5. Proposici´ on [Lema de Gauss]. Sean P y Q dos polinomios con coeficientes enteros. Entonces c(P Q) = c(P )c(Q). Demostraci´ on. Veamos primero que el producto de polinomios primitivos es primitivo. Para ello, supongamos, por reducci´on al absurdo, que P y Q son primitivos pero P Q no es primitivo. Sea p un n´ umero primo que divida a todos ˆ = 0 en Zp [X], pero R ˆ = Pˆ Q ˆ por el lema los coeficientes de R = P Q. Entonces, R ˆ = 0. Es decir, p divide a todos los coeficientes anterior y, por tanto, Pˆ = 0 o Q de P o p divide a todos los coeficientes de Q, lo cual es contradictotio ya que P y Q son primitivos. Pongamos P = c(P )P 0 y Q = c(Q)Q0 con P 0 y Q0 primitivos. Entonces P Q = c(P )c(Q)P 0 Q0 . Dado que P 0 Q0 es primitivo, es claro que c(P Q) = c(P )c(Q). 7.5.6. Proposici´ on. Sea R un polinomio con coeficientes enteros. Si R factoriza como producto de dos polinomios de grado mayor que cero en Q[X], entonces R factoriza como producto de dos polinomios de grado mayor que cero con coeficientes enteros. Demostraci´ on. Supongamos que R = P Q con P, Q ∈ Q[X] de grado mayor que cero. Por el lema 45, R = sR0 , P = (a/b)P 0 y Q = (c/d)Q0 con a, b, c, d, s ∈ Z y P 0 , Q0 , R0 primitivos. Entonces sbd R0 = ac P 0 Q0 y por el lema de Gauss sbd = ac, es decir, (a/b)(c/d) = s. En consecuencia R = (sP 0 )Q0 y P es producto de dos polinomios de grado mayor que cero con coeficientes enteros. 83

7.5.7. Proposici´ on [Criterio de reducci´ on]. Sea R un polinomio con coeficientes enteros y sea p un n´ umero primo que no divide al coeficiente principal ˆ es irreducible en Zp [X], R es irredicuble en Q[X]. de R. Entonces, si R Demostraci´ on. Supongamos R = P Q con P , Q dos polinomios con coefiences enteros. Si a, b, c son los coeficientes principales de R ,P y Q respectivamente, se tiene a = bc y, dado que p no divide a a, tampoco divide a b o c. Por tanto ˆ gr (P ) = gr (Pˆ ) y gr (Q) = gr (Q). ˆ Como en Zp [X] tenemos gr (R) = gr (R), ˆ = Pˆ Q ˆyR ˆ es irreducible, debe ser gr (P ) = gr (Pˆ ) = 0 o gr (Q) = gr (Q) ˆ = 0. R La proposici´ on anterior concluye la demostraci´on. 7.5.8. Ejemplo. Consideremos el polinomio P =

2 3 8 2 X + 2X 2 + X + . 3 3 3

P irreducible en Q[X] si y solo si lo es el polinomio 3 P = X 3 + 3X 2 + 4X + 1. 2 Este u ´ltimo m´ odulo 2 es (no ponemos rayitas) X 3 + X 2 + 1 que es irreducible en Z2 [X] pues es de grado 3 y no tiene ra´ıces. Luego el criterio anterior nos asegura que P es irreducible en Q[X]. 7.5.9. Proposici´ on [Criterio de irreducibilidad de Eisenstein]. Sea P = a0 + a1 X + · · · + an X n un polinomio con coeficientes enteros de grado n ≥ 1. Supongamos que existe un n´ umero primo p que divide a a0 , a1 , . . . , an−1 , pero que no divide a an y p2 no divide a a0 . Entonces, P es irreducible en Q[X]. Demostraci´ on. Usando la proposici´on 49, supongamos que P = BC con B, C dos polinomios de grado mayor que cero y coeficientes enteros. En concreto, pongamos B = b0 + b1 X + · · · + bu X u y C = c0 + c1 X + · · · + cv X v . En Zp [X] ˆ = bs X s y Cˆ = ct X t tenemos Pˆ = an X n . En consecuencia, por el teorema 35, B con s, t ≥ 1. En particular, p divide a b0 y c0 y, por tanto, p2 divide a a0 = b0 c0 , lo cual es contradictorio con las hip´otesis. 7.5.10. Ejemplos. (A) El polinomio 2X 4 + 6X 3 − 15X 2 + 6 es irreducible en Q[X] por el criterio anterior con el primo p = 3. (B) Sea p un n´ umero primo. El polinomio X n + p es irreducible en Q[X] por el criterio de Eisenstein. Por tanto, en Q[X] hay polinomios irreducibles de cualquier grado. 7.5.11. Proposici´ on [Criterio de sustituci´ on]. Sea K un cuerpo conmutativo y P un polinomio de K[X]. El polinomio P es irreducible si y solo si el polinomio resultante de sustituir X por X − a con a ∈ K es irreducible. Demostraci´ on. Ejercicio.

84

7.5.12. Ejemplos. (A) Si en el polinomio X 4 − 6X 3 + 12X 2 − 10X + 5 sustituimos X por X +1 se obtiene el polinomio X 4 −2X 3 +2 que es irreducible por el criterio de Eisenstein. (B) Sea p un n´ umero primo y consideremos el polinomio X p − 1. Factorizamos por X − 1 y obtenemos X p − 1 = (X − 1)(X p−1 + X p−2 + · · · + X + 1). Φp = X p−1 + X p−2 + · · · + X + 1 se denomina el p-´ esimo polinomio ciclot´ omico y vamos a ver que es irreducible en Q[X]. Para ello, sustituyamos X por X + 1 y desarrollemos por el binomio de Newton ! ! p p p p p−1 (X + 1) − 1 = X + X + ··· + X. 1 p−1 Por tanto, (X + 1)p − 1 = X p−1 + Φp (X + 1) = (X + 1) − 1

p 1 p

! X

p−2

+ ··· +

p p−1

! .

!

con 1 ≤ k ≤ p − 1 son k divisibles por p (¿por qu´e?) podemos aplicar el criterio de Eisenstein para obtener la conclusi´ on deseada.

Dado que los n´ umeros combinatorios

85