por mar a luisa p erez seguichi.fismat.umich.mx/cursos/algebra superior 1.pdf · 2013-08-16 ·...

Algebra Superior I

por Marıa Luisa Perez Seguı

Introduccion

Se presenta aquı el material correspondiente a un curso de algebra Superior I, el cual seimparte en la Facultad de Ciencias Fısico-Matematicas de la Universidad Michoacana. Elmaterial del libro constituyo el 100 % del curso impartido el semestre de agosto de 2011 aenero de 2012 en la Facultad.

Se propone en las notas un curso basico de algebra superior. En vista que el curso vadirigido a estudiantes de primer ano de una carrera de matematicas, los temas no puedentratarse de manera muy rıgida ni abstracta. El enfoque es mediante numerosos ejemplos parailustrar los principios del razonamiento teorico en Matematicas.

En la primera seccion se da una vista panoramica al tema de Matematicas discretas. Seeligio empezar con este tema pues ofrece una buena introduccion al alumno a las matematicasformales de manera mas agil y amena que empezando con definiciones aridas de la Teorıade Conjuntos. Se empieza con algo muy natural en todos nosotros que es el contar y se danlas primeras tecnicas de conteo. En esta seccion se familiariza al alumno con los conceptosmatematicos basicos y el lenguaje de Teorıa de Conjuntos sin hablar de estos conceptos demanera formal, lo cual se deja para la tercera seccion. Este enfoque esta basado en la idea deque nosotros, como humanos, primero aprendemos a hablar y despues aprendemos gramaticade manera formal. Dentro de este capıtulo se empieza tambien a familiarizar al alumno conel significado de “demostracion matematica”; en particular se trata el tema de demostracionllamado induccion matematica.

En la segunda seccion se continua con la idea de familiarizar al alumno con las ma-tematicas elevadas a traves de un tema que de alguna manera le es familiar desde los cursosescolares de matematicas: el algebra de los numeros enteros. Tambien en esta seccion se dannumerosos ejemplos y ejercicios para que poco a poco el alumno se adentre en las matemati-cas abstractas. La segunda parte de esta seccion trata el tema de congruencias, el cual ofreceuna tecnica para estudiar la divisibilidad de enteros.

En la tercera seccion se ofrece una introduccion al lenguaje basico de las matematicasque es la Teorıa de Conjuntos. Se trata el tema tratando de hacer una liga entre la intuiciony la formalizacion. Se dan las definiciones basicas de tipo algebraico de las relaciones y lasfunciones; en particular se dan las nociones basicas de las relaciones de orden y de relacionesde equivalencia. De manera muy superficial se trata el tema de cardinalidad, mostrando alalumno que hay distintos infinitos.

Las primeras dos secciones de estas notas son una adaptacion, para un primer cursode algebra de una licenciatura en matematicas o fısica, de los temas de mis dos libros:Combinatoria [7] y Teorıa de Numeros [8] en los cuales estos temas se tratan con mayorextension y profundidad. Hice la adaptacion del contenido de ellos que me parecio apropiadopara el curso y agregue muchos ejercicios, con la intencion de que el alumno fuera haciendosuyos los conceptos de manera paulatina.

i

Indice

Introduccion I

1. Matematicas discretas 1

1.1. Conteo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2. Teorema del Binomio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3. Induccion Matematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.4. Probabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2. Teorıa de Numeros 34

2.1. Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.2. Numeros primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.3. Criterios de divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.4. Algoritmo de la division. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.5. Maximo comun divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.6. Teorema Fundamental de la Aritmetica . . . . . . . . . . . . . . . . . . . . 49

2.7. Mınimo comun multiplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.8. Ecuaciones diofantinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

2.9. Congruencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

2.10. Conjuntos de residuos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

2.11. Mas propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

2.12. Solucion de congruencias lineales . . . . . . . . . . . . . . . . . . . . . . . . 68

3. Conjuntos, relaciones y funciones 72

3.1. Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

3.2. Operaciones con conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

3.3. Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.4. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

3.5. Cardinalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

Referencias y lecturas complementarias 96

Indice Alfabetico 97

ii

1. Matematicas discretas

1.1. Conteo

Uno de los conceptos matematicos abstractos mas primitivos que conocemos es el denumero y, dentro de los numeros, el de los numeros naturales enteros positivos: 1,2, 3, 4, etc. Con ellos representamos las cantidades de objetos que se nos presentan en lavida cotidiana. En esta seccion desarrollaremos algunas tecnicas que permiten determinarcon facilidad cantidades. Comencemos por ilustrar la necesidad de aprender estas tecnicasde conteo con unos ejemplos: Si se nos ensena un punado de canicas y se nos preguntacuantas son, un vistazo nos bastara para contarlas y dar la respuesta; sin embargo si se nospregunta cuantas patas tienen 100 perros, en lugar de buscar los 100 animales y contarleslas patas, haremos una abstraccion, y la operacion: 4 × 100 = 400 nos dira la respuesta;utilizamos aquı una tecnica muy simple de multiplicacion. Desde luego hay preguntas quenecesitan tecnicas mas elaboradas. Estudiaremos estas tecnicas mediante ejemplos que iremoscomplicando gradualmente.

Analicemos primero con cuidado un ejemplo que a primera vista es trivial pero que nosensena la clave basica del conteo.

1.1 Ejemplo. ¿Cuantos numeros enteros de tres o menos cifras hay?

Solucion. La respuesta a esta pregunta es facil: Hay 1000 pues son todos los numerosenteros del 0 al 999. Esta solucion no nos ensena gran cosa. Retomemos ahora el problemabuscando una solucion constructiva; esto es, para cualquier n = 1, 2, 3, . . ., la cantidad denumeros de hasta n+ 1 cifras se puede obtener de la cantidad de numeros de hasta n cifras:simplemente se multiplica por 10. Vamos a describir con detalle este procedimiento:

Numeros de a lo mas una cifra hay 10, a saber, 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. Para contar losde hasta dos cifras (del 0 al 99) no necesitamos escribirlos todos; basta con observar que laprimera cifra puede ser cualquiera de los 10 dıgitos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, y por cada uno deestos hay 10 terminaciones distintas; por ejemplo, los numeros de dos cifras que empiezan con4 son: 40, 41, 42, 43, 44, 45, 46, 47, 48 y 49, diez en total; lo mismo para cada una de las otrasdecenas. Ası la cantidad de enteros entre 0 y 99 es 10×10 = 100. El siguiente paso es analogo:Para contar los numeros de hasta tres cifras hay que agregar un dıgito (posiblemente 0) acada uno de los 100 numeros de 2 o menos cifras; como hay diez posibilidades la respuestasera 10× 100 = 1000. ♦

Este procedimiento de “construir sobre lo ya construido” que hemos utilizado se llamaprocedimiento inductivo . Muchas demostraciones de propiedades y formulas de numerosnaturales se basan en el. Mas adelante se estudiara esto con detalle. El principio combinatorioque manejamos en el ejemplo anterior (y que manejaremos en los siguientes) es:

1

1.2. Principio Fundamental de Conteo. Si una cierta tarea puede realizarse de mmaneras diferentes y, para cada una de esas formas, una segunda tarea puede realizarse den maneras distintas, entonces las dos tareas juntas pueden realizarse (en ese orden) de mnformas diferentes.

1.3 Ejemplo. ¿Cuantas palabras de tres letras se pueden formar si se dispone de unalfabeto con dos letras: a y b. (Nota: Son permisibles palabras como bba.)

Solucion. Procederemos como en el ejemplo anterior. En este caso conviene ilustrarlohaciendo un “diagrama arbol”:

Resolvamos ahora el ejemplo utilizando nuestro Principio Fundamental de Conteo. Con-sideremos tres casillas: , la primera para la letra inicial, la segunda para la letra centraly la tercera para la letra final. En cada casilla hay dos elecciones posibles: la letra a o laletra b. La respuesta es entonces 2×2×2 = 8. El procedimiento inductivo es como sigue: Enla primera casilla hay 2 posibilidades para elegir la letra. Una vez formada una palabra deuna letra: a o b, para agrandarla a una palabra de dos letras hay dos posibilidades, ası quepalabras de dos letras hay 2 × 2 = 4. Para completar cada una de estas a una palabra detres letras hay dos posibilidades; entonces hay 4× 2 = 8 palabras de tres letras. ♦

1.4 Ejemplo. ¿Cuantas placas distintas hay con dos letras a la izquierda y tres numerosa la derecha? (Nota: Consideraremos el alfabeto de 27 letras castellanas.

Solucion. Seguimos el procedimiento de las casillas del ejemplo anterior:

27× 27︸︷︷︸lugares

para letras

× 10× 10× 10︸︷︷︸lugares

para numeros

= 729 000. ♦

2

1.5 Ejemplo. ¿Cuantas banderas bicolores se pueden formar si se dispone de 4 lienzosde tela de colores distintos y un asta? (Nota: Banderas como rojo-rojo no son permisibles;por otro lado, es importante el color que queda junto al asta, de esta manera banderas comorojo-azul y azul-rojo se consideran distintas.)

Solucion. En este caso consideramos dos casillas. La de la izquierda, digamos, representael lienzo junto al asta, el cual tiene 4 elecciones posibles. Una vez elegido este, el color parala derecha se puede escoger de 3 formas (pues no se permite la repeticion de colores). Ası hay4× 3 = 12 formas distintas de formar las banderas. ♦

1.6 Ejercicio. Escribir todas las banderas que pueden formarse segun el ejemplo anteriorsi los colores son rojo (R), azul (A), verde (V ) y blanco (B).

1.7 Ejemplo. Misma pregunta que en el ejemplo anterior pero ahora suponiendo queno hay asta. (En este caso no habra distincion entre las banderas rojo-azul y azul-rojo.)

Solucion. Para resolver este ejemplo analicemos la respuesta del ejemplo anterior. Enaquel, en la coleccion total de las 12 banderas posibles podemos aparear cada bandera consu opuesta; por ejemplo la bandera azul-verde la apareamos con la bandera verde-azul. Cadauna de las del ejemplo anterior se esta contando dos veces y, por tanto, la respuesta es122

= 6. ♦

1.8 Ejercicio. En el resultado del ejercicio refbanderas aparear cada una de las banderascon su opuesta. Dar una lista de 6 banderas que ilustre la respuesta del ejemplo 1.7.

1.9 Ejemplo. ¿De cuantas formas se pueden sentar 5 personas en 5 sillas numeradas del1 al 5?

Solucion. En el asiento #1 se puede sentar cualquiera de las 5 personas; para cada eleccionde la primera persona, la segunda puede ser cualquiera de las 4 restantes; ası en las dosprimeras sillas el numero de elecciones posibles es 5 × 4 = 20. Continuamos de maneraanaloga. Para simplificar dibujemos 5 casillas simbolizando los 5 asientos. Sobre cada casillaescribamos el numero respectivo de posibilidades y multipliquemos:

5× 4× 3× 2× 1 = 120. ♦

Si n es un numero natural, el producto de todos los numeros naturales del 1 al n aparecemuy frecuentemente en problemas de combinatoria; se llama n factorial o factorial de ny se denota por n!. (Ası la respuesta del ejemplo 1.9 es 5! = 120.)

Alejandose de la interpretacion de n! como el producto de los naturales de 1 a n, se define

0! = 1;

3

esto permite incluir el caso n = 0 en algunas formulas en las que interviene n!. Entonces

0! = 11! = 12! = 1× 2 = 23! = 1× 2× 3 = 64! = 1× 2× 3× 4 = 24.

Es facil darse cuenta que el numero 5 del ejemplo 1.9 y el que sean personas y asientosen lugar de cualquier otra cosa no es relevante; podemos generalizarlo como sigue:

El numero Pn de distintas formas en que se pueden ordenar n objetos es n!. Cada una delas listas ordenadas que se forman con los n objetos se llama permutacion (de los objetos).Tenemos entonces que el numero de permutaciones de n objetos es Pn = n!.

1.10 Ejemplo. De un grupo de 5 estudiantes quiere elegirse una comision de 3 para quecada uno visite un museo de una lista de 3 museos. ¿Cuantas comisiones distintas se puedenformar?

Solucion. Utilizando el esquema de casillas (cada una representando un museo) comoarriba, tenemos que el resultado es

5× 4× 3 = 60. ♦

1.11 Ejemplo. De un grupo de 5 estudiantes quiere elegirse una comision de 3 para quejuntos visiten un museo (el mismo todos). ¿Cuantas comisiones diferentes se pueden formar?

Solucion. Hay que observar que la diferencia entre este ejemplo y el anterior es que noimporta el orden en la eleccion. En el ejemplo anterior habıa disticion entre las casillas puescada una representaba un museo en particular distinto a los otros; en este no hay distincionentre las casillas pues, por ejemplo, una comision en que se haya elegido la sucesion dealumnos Ana-Beto-Carlos se considerara igual a la sucesion Beto-Carlos-Ana y tambienigual a la sucesion Ana-Carlos-Beto. Nuestro interes es entonces determinar en la cantidad5 × 4 × 3, en cuantas sucesiones aparece el mismo conjunto de alumnos. Para responderesto conviene plantear esta parte del ejemplo al reves: Consideremos un conjunto fijo de 3personas, por ejemplo el formado por Ana (A), Beto (B) y Carlos (C) y contemos de cuantasformas se pueden ordenar estos 3. Observemos que el numero de formas es precisamente elnumero de permutaciones de las 3 personas, o sea, P3 = 3! = 6. Entonces cada grupo de 3personas se esta contando 6 veces en el producto 5 × 4 × 3, ası que la respuesta al ejemplosera

5× 4× 3

3!= 10. ♦

1.12 Ejercicio. En los ejemplos 1.10 y 1.11 supongamos que el grupo de los 5 alumnosesta formado por Ana (A), Beto (B), Carlos (C), Daniel (D) y Elena (E). Hacer la lista de

4

los 60 arreglos de estos alumnos en los que se elige 3 para visitar museos distintos, agrupandoen esa lista las colecciones que resultan iguales si todos van a un mismo museo.

En el ejemplo anterior aprendimos el siguiente principio:

1.13. El numero de colecciones (en las que el orden no importa) con r elementos que sepueden seleccionar dentro de un conjunto de n elementos (n ≥ r ≥ 1) es

n× (n− 1)× · · · × (n− (r − 1))

r!.

Este numero recibe el nombre de combinaciones de n en r y se denota por(nr

). Dicho

de otra manera, el numero de subconjuntos de r elementos que tiene un conjunto con nelementos es

(nr

). (En el ejemplo 1.11, n = 5 y r = 3 y la respuesta es

(53

).) Notese que la

formula 1.13 no tiene sentido para n = 0; sin embargo sı tiene sentido hablar del numerode subconjuntos con 0 elementos dentro de un conjunto con n elementos; sabemos que estenumero es 1 pues solo hay un conjunto sin elementos que es el llamado conjunto vacıo.Definimos entonces (

n

0

)= 1.

1.14 Ejercicio. Sea X = {a, b, c, d, e}. Escribir todos los subconjuntos de X con(a) 0 elementos,(b) 1 elemento,(c) 2 elementos,(d) 3 elementos,(e) 4 elementos y(f) 5 elementos.Verificar que en cada caso el numero de subconjuntos obtenido sea

(5r

)y que el numero

total de subconjuntos sea 25 = 32.

1.15 Ejercicio. Basandose en la interpretacion de(nr

)como el numero de subconjuntos

de r elementos dentro de un conjunto con n elementos, explicar por que(n

r

)=

(n

n− r

).

1.16 Ejercicio. Calcular(72

),(75

),(55

)y(94

).

Con la intencion de simplificar la formula 1.13 sobre las combinaciones de n en r, ob-servemos que, para 1 ≤ r ≤ n − 1, el numerador se puede “completar” a n! multiplicandopor (n − r)!; si lo “completamos” deberemos compensar dividiendo tambien por (n − r)!.Tendremos entonces que para r = 1, 2, . . . , n− 1,

5

1.17. (n

r

)=

n!

r!(n− r)!.

Recordemos que se ha definido 0! = 1 y(n0

)= 1; notemos entonces que si sustituimos

r = 0 (y, posiblemente tambien n = 0) en el lado derecho de la formula 1.17 obtendremosn!0!n!

= 1. De la misma manera, al sustituir r = n obtendremos n!n!0!

= 1. Ası, tambien en estoscasos extremos vale la formula 1.17.

1.18 Ejercicio. Volver a hacer los ejercicios 1.15 y 1.16 utilizando la formula 1.17.

1.19 Ejemplo. De un grupo de 10 ninos y 15 ninas se quiere formar una coleccion de 5jovenes que tenga exactamente 2 ninas. ¿Cuantas colecciones distintas se pueden formar?

Solucion. La eleccion de las 2 ninas se puede hacer de(152

)= 15×14

2!= 105 formas. Como

deben ser 5 en total y debe haber 2 ninas exactamente, entonces los ninos seran 3; estos sepueden escoger de

(103

)= 10×9×8

3!= 120 formas. Por tanto el resultado es 105×120 = 12 600.♦

Como hemos visto, al determinar cantidades buscamos simplificar nuestras cuentas uti-lizando “homogeneidades” en el problema. Con este proposito, en algunas ocasiones es con-veniente dividir en casos de manera que en cada uno de ellos haya homogeneidad, y despuessumar las respuestas. Un ejemplo muy simple de esto serıa el siguiente: Si tenemos 4 paquetesde 100 hojas de papel y otros 3 paquetes de 200 hojas cada uno, entonces el numero totalde hojas que tenemos es

4× 100 + 3× 200 = 1000.

Comparemos el siguiente ejemplo con el anterior, tomando en cuenta la busqueda dehomogeneidades, como acabamos de decir.

1.20 Ejemplo. De un grupo de 10 ninos y 15 ninas se quiere formar una coleccion de 5jovenes que tenga a lo mas 2 ninas. ¿Cuantas colecciones distintas se pueden formar?

Solucion. Vamos a resolver este ejemplo como el anterior pero separando por casos ydespues sumando las respuestas de cada uno de los casos.

Caso 1: Que la coleccion tenga 2 ninas exactamente:(152

)(103

)= 12 600.

Caso 2: Que la coleccion tenga exactamente 1 nina:(151

)(104

)= 3 150.

Caso 3: Que la coleccion no tenga ninas:(150

)(105

)= 252.

La respuesta al ejemplo es 12 600 + 3 150 + 252 = 16 002. ♦

1.21 Ejemplo. Un grupo de 15 personas quiere dividirse en 3 equipos de 5 personascada uno. Cada uno tendra una labor especıfica distinta a las demas. ¿De cuantas formasdistintas es posible hacer la distribucion?

6

Solucion. Escojamos uno por uno los equipos. La eleccion del primer equipo puede hacersede(155

)= 3 003 formas; para elegir el segundo equipo ya solo habra 10 personas de donde

escoger, por tanto este se podra elegir de(105

)= 252 formas. El tercer equipo quedara formado

automaticamente con la eleccion de los otros dos. Entonces el numero de formas de hacer laeleccion sucesiva es 3 003× 252× 1 = 756 756. ♦

1.22 Ejemplo. Un grupo de 15 personas quiere dividirse en 3 equipos de 5 personascada uno. Todos los equipos tendran la misma labor. ¿De cuantas formas es posible hacer ladistribucion?

Solucion. En este caso no hay distincion entre los equipos ası que hay que dividir elresultado del ejemplo anterior entre 3!, que es el numero de permutaciones de los equipos.La respuesta es entonces 126 126. ♦

1.23 Ejemplo. En una bolsa hay 3 pelotas rojas y 2 azules. Se quiere formar una filacon todas ellas. ¿De cuantas maneras distintas puede quedar la fila?

Solucion. Primera forma. Consideremos todas las permutaciones de las 5 pelotas y con-temos cuantas de esas permutaciones son indistinguibles entre sı. Las permutaciones de las5 pelotas sabemos que son 5! = 120. En cualquiera de las permutaciones fijemonos en laubicacion de las pelotas rojas; por ejemplo − roja − roja roja. estas pueden revolverseentre sı (3! veces) formando colecciones indistinguibles, y lo mismo ocurre con las del otrocolor. Vamos a explicar lo anterior con mas detalle: Denotemos las pelotas rojas por R1, R2

y R3, y las azules por A1 y A2. Entonces las siguientes listas (en las que se han permutadolas rojas pero se han dejado fijas las azules) representan la misma coleccion:

A1 R1 A2 R2 R3

A1 R1 A2 R3 R2

A1 R2 A2 R1 R3

A1 R2 A2 R3 R1

A1 R3 A2 R1 R2

A1 R3 A2 R2 R1

.

Estas 3! listas deben considerarse como una sola. Ademas, en cada una de ellas tambien sepueden revolver las azules entre sı (2! permutaciones). Entonces al considerar las permuta-ciones de las 5 pelotas, cada arreglo se esta contando 3! × 2! = 12 veces en lugar de 1. Larespuesta al ejemplo es pues 5!

3!2!= 10.

Segunda forma. Primero podemos contar las posibilidades para colocar las pelotas rojasen los 5 lugares disponibles; esto nos dara la eleccion de 3 lugares, que puede hacerse de(53

)= 10 maneras. Para colocar las 2 azules ya solo sobran 2 lugares ası que esto se puede

hacer de(22

)= 1 forma. El resultado es 10× 1 = 10. ♦

7

1.24 Ejercicio. Escrıbanse las 10 filas distintas que se pueden formar con las pelotas enel ejemplo 1.23.

1.25 Ejemplo. En una bolsa hay 3 pelotas rojas y 2 azules. ¿Cuantas filas distintas de3 pelotas se pueden formar?

Solucion. Como son 5 pelotas en total pero solo se van a considerar filas de 3, hay que dejardos pelotas sin colocar. Consideraremos los distintos casos por separado y despues sumaremoslas respuestas parciales. Si las dos pelotas que quedan fuera son rojas, hay 3!

1!2!= 3 arreglos

con las restantes. Analogamente hay 3!3!

= 1 fila que deja las 2 pelotas azules fuera, y 3!2!1!

= 3filas que dejan una azul y una roja fuera. La respuesta al ejemplo es 3 + 1 + 3 = 7. ♦

1.26 Ejercicio. Escribir los 7 arreglos de pelotas del ejemplo 1.25 .

En algunas ocasiones, para poder hacer bien las cuentas, nuestra busqueda de homoge-neidad nos lleva a que es mas facil contar lo opuesto de lo que queremos y despues restar deun total. Ilustramos esto con el siguiente ejemplo.

1.27 Ejemplo. ¿De cuantas maneras pueden ordenarse en un estante 3 cuadernos rojos,4 azules y 2 verdes, si los verdes no deben quedar juntos?

Solucion. Conviene contar primero todas las ordenaciones posibles y despues restar aquellasen las que los verdes quedan juntos. El numero total de filas (incluyendo aquellas en que losverdes quedan juntos es 9!

3!4!2!= 1260. Para contar las que tienen juntos los cuadernos verdes

pensemos estos como pegados formando un solo cuaderno; ahora determinemos el numero dearreglos con 3 cuadernos rojos, 4 azules y 1 verde; este es 8!

3!4!= 280. La respuesta al ejemplo

es 1260− 280 = 980. ♦

1.28. Los ejemplos siguientes se refieren a la baraja usual de pokar: Cada carta tieneun sımbolo llamado numero que puede ser cualquiera de los 13 sımbolos siguientes: A, 2,3, 4, 5, 6, 7, 8, 9, 10, J , Q o K, y otro sımbolo llamado palo que puede ser cualquiera delos 4 siguientes: ♠ (espada), ♥ (corazon), ♦ (diamante) o ♣ (trebol). Todos los palosse combinan con todos los numeros para formar la baraja completa con 13× 4 = 52 cartascomo se ilustra a continuacion:

A♥ 2♥ 3♥ 4♥ 5♥ 6♥ 7♥ 8♥ 9♥ 10♥ J♥ Q♥ K♥

A♦ 2♦ 3♦ 4♦ 5♦ 6♦ 7♦ 8♦ 9♦ 10♦ J♦ Q♦ K♦

A♠ 2♠ 3♠ 4♠ 5♠ 6♠ 7♠ 8♠ 9♠ 10♠ J♠ Q♠ K♠

A♣ 2♣ 3♣ 4♣ 5♣ 6♣ 7♣ 8♣ 9♣ 10♣ J♣ Q♣ K♣

Se llama mano de pokar cualquier coleccion de 5 cartas de la baraja. La siguiente nomen-

8

clatura es usual:

par: dos cartas del mismo numero.

tercia: tres cartas del mismo numero.

pokar: cuatro cartas del mismo numero.

full: una tercia y un par.

flor: cinco cartas del mismo palo.

corrida: cinco cartas con numeracion consecutiva (segun el orden en que se escribieronarriba, pero permitiendo A tambien como numero final, en seguida de K).

Observemos que el numero total de manos de pokar es(525

)= 2 598 960.

1.29 Ejemplo. ¿Cuantas manos de pokar tienen tercia exactamente (es decir, que nosea full ni pokar).

Solucion. Primera forma. Ponemos 5 casillas: las tres primeras para la tercia y las otrasdos para las otras cartas. La primera carta se puede escoger arbitrariamente; la segunda solotiene 3 posibilidades pues debe tener el mismo numero que la primera; la tercera ya solopuede ser elegida de 2 maneras distintas; como no importa el orden de estas 3 cartas, estenumero debera dividirse entre 3!. La cuarta carta se debe escoger dentro de las 48 que son denumero distinto al de la tercia. Para la quinta carta ya solo sobran 44 cartas pues el numerodebe ser tambien distinto. La cuarta y quinta pueden haberse escogido en cualquier ordenpor lo que se debera dividir entre 2!.

52× 3× 2

3!︸︷︷︸tercia

× 48× 44

2!︸︷︷︸cartas distintas

= 54 912.

Segunda forma. Tambien formamos primero la tercia pero eligiendo antes el numero que lecorrespondera: Tenemos 13 numeros para escoger y, una vez escogido el numero, las 3 cartasque forman la tercia deben escogerse dentro de 4 posibles; entonces el numero de terciases 13

(43

). Para escoger las otras dos cartas utilizando este mismo metodo razonamos como

sigue: Hay que escoger 2 numeros (pues queremos que las otras 2 cartas sean de numerosdistintos) dentro de los 12 que sobran; esta eleccion se puede hacer entonces de

(122

)formas.

En cada uno de estos numeros que se hayan elegido hay que escoger 1 carta, cosa que puedehacerse de

(41

)formas. El resultado escrito en esta forma es

13

(4

3

)×(

12

2

)(4

1

)2

,

que, desde luego, tambien es igual a 54 912. ♦

1.30 Ejemplo. ¿Cuantas manos de pokar tienen dos pares (distintos) exactamente?

9

Solucion. Procedemos como en el ejemplo 1.29.

Primera forma.1er par︷︸︸︷52× 3

2!

2o par︷︸︸︷48× 3

2!2!

× 44 = 123 552.

(Nota: Hay que dividir entre 2! porque no importa el orden entre los dos pares.)

Segunda forma. (13

2

)(4

2

)2

× 44 = 123 552. ♦

1.31 Ejemplo. ¿Cuantas manos de pokar tienen corrida?

Solucion. El numero mas bajo de la corrida puede ser cualquiera de los siguientes: A,2, 3, 4, 5, 6, 7, 8, 9 o 10, que son 10 posibilidades. Pongamos 5 casillas; la primera casillasera para la carta de numero menor, la siguiente casilla sera para el siguiente numero, yası sucesivamente hasta la quinta casilla que sera para la carta con el numero mayor. Unavez escogido el numero menor para la corrida, todos los demas numeros quedan determinadosy lo unico que falta escoger es el palo. Entonces la cantidad de corridas es 10×4×4×4×4×4 =10 240. ♦

1.32 Ejercicio. ¿De cuantas maneras diferentes se pueden ordenar 8 personas alrededorde una mesa redonda? (Nota: Dos distribuciones se consideraran iguales si una se puedeobtener de la otra mediante un giro.)

1.33 Ejercicio. ¿De cuantas maneras distintas se pueden sentar 5 personas en una filade 8 asientos numerados del 1 al 8?

1.34 Ejercicio. ¿Cuantas diagonales tiene un polıgono regular de n lados?

1.35 Ejercicio. Probar la Formula de Pascal:(n+ 1

r + 1

)=

(n

r

)+

(n

r + 1

),

para r y n numeros enteros con 0 ≤ r < n.

1.36 Ejercicio. El Triangulo de Pascal esta definido como el triangulo de numerosen el que el renglon numero n aparecen los n+ 1 numeros(

n

0

),

(n

1

),

(n

2

), · · · ,

(n

n− 1

),

(n

n

).

10

Se muestran a continuacion los primeros 4 renglones del Triangulo de Pascal. Utilizar laformula del ejercicio anterior para construir los 10 primeros renglones.

1 11 2 1

1 3 3 11 4 6 4 1

1.37 Ejercicio. De un grupo de 24 personas se quiere elegir 5 representantes de lasiguiente forma: Pedro y Luis deben estar en el grupo elegido. Hay 8 mujeres en total pero alo mas deben figurar 2 en el grupo. ¿De cuantas maneras distintas puede hacerse la eleccion?

1.38 Ejercicio. De un grupo de 30 socios de un club se quiere elegir una mesa direc-tiva con un presidente, un secretario y 3 equipos de 2 personas cada uno. ¿Cuantas mesasdirectivas distintas se pueden formar?

1.39 Ejercicio. ¿Cuantas palabras distintas se pueden escribir revolviendo las letras dela palabra COMBINATORIA?

1.40 Ejercicio. De un conjunto de 10 botes de distintos colores se quiere escoger 5 detal manera que 3 sean para dulces y 2 sean para chocolates. ¿De cuantas formas distintas esposible hacer la eleccion?

1.41 Ejercicio. Se dispone de una coleccion de 30 pelotas divididas en 5 tamanos dis-tintos y 6 colores diferentes de tal manera que en cada tamano hay los 6 colores. ¿Cuantascolecciones de 4 pelotas tienen exactamente 2 pares de pelotas del mismo tamano (que nosean las 4 del mismo tamano)?

1.42. El siguiente problema se refiere al conjunto usual de 28 fichas de domino en quecada ficha muestra dos numeros de la coleccion 0, 1, 2, 3, 4, 5 y 6 (posiblemente repetidos),como esquematizamos a continuacion:

11

6 6 6 5 6 4 6 3 6 2 6 1 6

5 5 5 4 5 3 5 2 5 1 5

4 4 4 3 4 2 4 1 4

3 3 3 2 3 1 3

2 2 2 1 2

1 1 1

Se llaman fichas dobles aquellas en que los dos numeros mostrados son iguales. Se llamamano de domino cualquier coleccion de 7 de las 28 fichas. Notese que el numero total demanos de domino es

(287

)= 1 184 040.

1.43 Ejercicio. ¿Cuantas manos de domino tienen por lo menos 2 fichas dobles?

1.2. Teorema del Binomio

El siguiente es un resultado muy importante en aritmetica. Lo probaremos aquı utilizandoalgunas de las tecnicas de combinatoria que hemos aprendido. Mas adelante volveremos aprobarlo usando el metodo de induccion.

1.44 Teorema. Teorema del Binomio de Newton. Sean a y b numeros arbitrariosy sea n un numero natural. Entonces

(a+ b)n =

(n

0

)an +

(n

1

)an−1b+ · · ·+

(n

r

)an−rbr + · · ·+

(n

n

)bn.

Demostracion. La expresion (a+ b)n significa que tenemos que multiplicar a+ b consigomismo n veces. Entonces, al desarrollar todo el producto, los terminos que obtenemos estandados por todas las posibles elecciones de los numeros a o b en cada uno de los n factores(por ejemplo, (a+ b)3 = (a+ b)(a+ b)(a+ b) = aaa+aab+aba+abb+ baa+ bab+ bba+ bbb =

12

a3 + 3a2b+ 3ab2 + b3). Observemos entonces que los terminos obtenidos son de la forma asbr,con 0 ≤ s, r ≤ n y s + r = n, es decir, s = n − r. Ahora notemos que an−rbr aparece cadavez que se eligio b en r de los factores y a en el resto, ası que el numero de veces que apareceeste termino es

(nr

). Al agrupar terminos semejantes tenemos la formula deseada. ♦

Como hemos visto, los numeros(nr

)(para 0 ≤ r ≤ n) aparecen como coeficientes en

la expansion de un binomio elevado a la potencia n; por esta razon reciben el nombre decoeficientes binomiales. En los ejercicios 1.35 y 1.36 vimos que para una n elegida no muygrande podemos obtener facilmente los coeficientes binomiales sin recurrir en cada caso a laformula

(nr

)= n!

(n−r)!r! .

1.45 Ejemplo. Desarrollar (2x− y)5.

Solucion. Sustituimos a = 2x y b = −y en la Formula del Binomio:

(2x− y)5 =

(5

0

)(2x)5 +

(5

1

)(2x)4(−y) +

(5

2

)(2x)3(−y)2

+

(5

3

)(2x)2(−y)3 +

(5

4

)(2x)(−y)4 +

(5

5

)(−y)5

=(2x)5 + 5(2x)4(−y) + 10(2x)3(−y)2

+ 10(2x)2(−y)3 + 5(2x)(−y)4 + (−y)5

=32x5 − 80x4y + 80x3y2 − 40x2y3 + 10xy4 − y5. ♦

1.46 Ejercicio. Utilizar el Teorema del Binomio y el Triangulo de Pascal (ver ejercicios1.35 y 1.36 para desarrollar la expresion (2a− 3b2)8.

1.47 Ejercicio. Utilizar el Teorema del Binomio para desarrollar (a+ 2b− c2)4.

1.48 Ejercicio. Encontrar el coeficiente del termino a7b4ce2 en el desarrollo de (a+ b+c+ d+ e)14. (Sugerencia: Proceder como en la prueba del Teorema del Binomio.)

1.49 Ejercicio. Utilizar el Teorema del Binomio para probar la formula(n

0

)+

(n

1

)+

(n

2

)+ · · ·+

(n

n

)= 2n.

1.50 Ejercicio. Utilizar el Teorema del Binomio para probar la formula(n

0

)+

(n

2

)+

(n

4

)+ · · · =

(n

1

)+

(n

3

)+

(n

5

)· · · .

¿Que interpretacion se puede dar a esta formula en terminos de subconjuntos de un conjunto?

13

1.51 Ejercicio. Probar que para cualquier numero natural se tiene la formula(n

0

)2

+

(n

1

)2

+

(n

2

)2

+ · · ·+(n

n

)2

=

(2n

n

).

(Sugerencia: Examinar el coeficiente de xn al desarrollar ambos miembros de la igualdad(1 + x)2n = (1 + x)n(1 + x)n.)

1.52 Ejercicio. Encontrar el termino que no contiene a x en el desarrollo de(√x+

14√x

)9

.

1.3. Induccion Matematica

La induccion matematica es un metodo muy util en algunas demostraciones. Se empleageneralmente al probar formulas o propiedades de numeros naturales. En esta seccion, ademasde ilustrar ampliamente el metodo de demostracion por induccion, aprovecharemos paraprobar algunas formulas y propiedades de numeros enteros que son utiles en Matematicas.Empecemos con un ejemplo sencillo.

1.53 Ejemplo. Analicemos la sucesion (lista) de numeros n2 + n para n natural. Elprimer termino de nuestra lista es 2, pues cuando n = 1, n2 + n = 12 + 1 = 2; el segundotermino es 6 ya que 22 + 2 = 6. Ası obtenemos la sucesion:

2, 6, 12, 20, 30, 42, 56, 72, 90, . . .

Podemos notar que todos los terminos que escribimos son pares. ¿Sera cierto que todos losterminos de la sucesion son pares? La respuesta es sı. Podemos probar esto directamente (sinusar induccion matematica), observando que para cualquier natural n, el numero n2 + n sepuede escribir como n(n+ 1), o sea que todos los terminos de la sucesion son el producto dedos enteros consecutivos y, como uno de los dos enteros debe ser par, el producto tambienlo sera.

Mas abajo haremos otra demostracion del mismo resultado (es decir, de que todos losterminos de la sucesion son pares) utilizando el metodo de induccion, pero primero hablemosun poco sobre el procedimiento que seguiremos:

Notemos que con la sola proposicion: “Para cualquier natural n, el numero n2+n es par”,estamos abarcando una infinidad de proposiciones (una para cada n): 12 + 1 es par, 22 + 2 es

14

par, 32 + 3 es par, etc. Si tratamos de probar cada una individualmente no llegaremos muylejos; en cambio, si probamos

(I1) que la primera proposicion es cierta y

(I2) que, cada vez que todas las proposiciones anteriores a una fija P sean verdaderastambien lo es la misma P, entonces podemos concluir que todas las proposiciones son ciertas.En efecto, comprobemos por ejemplo que de nuestro metodo (probar (I1) e (I2)) se deduceque la 4a proposicion es cierta: La 1a proposicion es cierta por (I1); utilizando esto tenemosque, por (I2), la 2a proposicion tambien es cierta; pero entonces, al tener que la primera yla segunda afirmaciones son ciertas, por (I2) deducimos que la 3a proposicion es verdadera;ahora ya tendemos que la primera, la segunda y la tercera son ciertas ası que, otra vez usando(I2) concluimos que la 4a proposicion tambien es valida.

Ası como llegamos a la 4a proposicion, a cualquiera podemos llegar en un numero finitode pasos, ası que, con solo demostrar (I1) e (I2), podemos afirmar que todas las proposicionesson ciertas.

1a proposicion ⇒{

1a proposicion2a proposicion

⇒ ⇒

1a proposicion2a proposicion3a proposicion

⇒ · · ·

Probemos entonces (I1) e (I2) en nuestro ejemplo, esto es, para probar la afirmacion:Para todo natural n, el numero n2 + n es par.

Demostracion de (I1). Tenemos que 12 + 1 = 2, que es par.

Demostracion de (I2). Supongamos que k ≥ 2 y que todas las afirmaciones desde la pri-mera hasta la k-esima (es decir, la que se encuentra en el lugar k) son verdaderas. Queremosutilizar esta suposicion para probar que, en este caso, tambien sera verdadera la (k+ 1)-esi-ma. De hecho en nuestra demostracion utilizaremos solo la validez de la k-esima (es decir, norequeriremos utilizar toda la fuerza de nuestra suposicion). El que la k-esima afirmacion seacierta nos dice que tomamos como verdadero el que k2 +k sea par y queremos usar esto paraprobar que (k + 1)2 + (k + 1) tambien es par. Desarrollemos la expresion (k + 1)2 + (k + 1)para poder compararla con k2 + k:

(k + 1)2 + (k + 1) = k2 + 2k + 1 + k + 1 = (k2 + k) + 2k + 2 = (k2 + k) + 2(k + 1).

De esta manera hemos logrado expresar (k+ 1)2 + (k+ 1) como suma de dos numeros pares,a saber k2 + k (que estamos suponiendo es par) y 2(k + 1) (que es par por tener el numero2 como factor). Como la suma de numeros pares tambien es par, (k + 1)2 + (k + 1) es par,como querıamos probar. Esto termina la demostracion de (I2).

15

Puesto que (I1) e (I2) quedaron probadas en nuestro caso, concluimos que para todonumero natural n, el numero n2 + n es par. ♦

Notese que en el metodo de induccion se necesita un punto de partida: demostrar que unaprimera afirmacion es verdadera; en algunos casos, como veremos mas adelante. el punto departida debera abarcar mas de una afirmacion puesto que de alguna manera se utilizara den-tro de la demostracion de (I2) el que haya un numero determinado de proposiciones yademostradas. A ese punto de partida le llamaremos base de la induccion o, en formaabreviada, (BI). La suposicion de que todas las proposiciones anteriores a una dada sonverdaderas se llama hipotesis de induccion, abreviado (HI). Como vimos en el ejemplo,en algunas ocasiones, basta con que la proposicion anterior a una dada sea cierta para quela proposicion dada tambien lo sea; en estos casos la hipotesis de induccion puede simplifi-carse. La practica nos dira que tan fuerte necesitamos hacer nuestra hipotesis de inducciony cuantas afirmaciones deberan tomarse como base de induccion.

Una forma de ilustrar por que el metodo de induccion proporciona una demostracioncorrecta de algunas proposiciones es la siguiente: Supongamos que se tiene una hilera defichas de domino colocadas de manera tal que cada vez que una caiga empujara a la siguientepara que tambien caiga (esto corresponde a (I2)); si una persona empuja la primera ficha(corresponde a (I1)), podremos afirmar que cada una de las fichas debera caer en algunmomento.

En (I2), la forma en que uno hace ver como la validez de una proposicion (o variasproposiciones) “empuja(n)” la validez de la siguiente depende del problema particular deque se trate; a veces la prueba puede ser muy sencilla y otras muy complicada.

Por otro lado, el que una persona no pueda demostrar satisfactoriamente un resultadopor induccion, no quiere decir nada sobre la validez del resultado; puede ser simplemente quela sucesion de afirmaciones no tenga una liga tal que la validez de cada afirmacion “empuje”la validez de la siguiente. Siguiendo la analogıa de las fichas de domino supongamos quelas fichas de domino estuvieran alejadas entre sı pero que de todas formas se cayeran porotra razon (por ejemplo porque colocaramos un ventilador con suficiente fuerza frente aellas). Tambien la practica nos dira en que tipo de proposiciones podemos intentar haceruna demostracion por induccion y en cuales no.

Es importante tambien aclarar que la hipotesis de induccion debe abarcar la base deinduccion; es decir, la primera afirmacion que se suponga verdadera en la hipotesis de induc-cion debe haber quedado demostrada independientemente en la base. Tambien es importantehacer notar que en cualquier demostracion por induccion hay un paso comparativo en el quese establece la relacion o liga que existe entre una afirmacion y la(s) precedente(s).

16

En resumen, para hacer una demostracion por el metodo de induccion matematica sedeberan seguir los siguientes tres pasos:

Primer paso. Identificar la sucesion de proposiciones que abarca la proposicion generalque se va a demostrar.

Segundo paso. Identificar y probar la base de induccion.

Tercer paso. Hacer una hipotesis de induccion (suposicion de que todas las proposicionesque preceden a una proposicion fija son verdaderas) abarcando la base de induccion, y utilizaresa suposicion (o parte de ella), para probar que la proposicion fija tambien es cierta. (Paraello debe haberse hecho una comparacion entre la afirmacion fija que se va a demostrar yla(s) anterior(es)).

Aplicaremos estos tres pasos en los siguientes ejemplos.

1.54 Ejemplo. Probar que n = 4, 5, 6, . . . implica 2n < n!.

Solucion. La sucesion de proposiciones es:

1a proposicion: 24 < 4!.




...

La base de induccion consiste en demostrar la 1a afirmacion. Esto es sencillo ya que24 = 16, 4! = 24 y 16 < 24, ası 24 < 4!.

La hipotesis de induccion puede ser, en este caso, la siguiente: Para cierta k ≥ 4 se tiene2k < k!. (Notemos que la primera afirmacion que se toma como cierta en esta hipotesises para k = 4 y que esta quedo demostrada en la base de induccion.) Ahora usaremos lahipotesis de induccion para hacer ver que 2k+1 < (k + 1)!. En efecto, esto se deduce de lasiguiente cadena de igualdades y desigualdades en la que en la primera desigualdad se uso lahipotesis de induccion y en la segunda desigualdad se utilizo que k + 1 > 2 (esto ultimo esporque k ≥ 4):

2k+1 = 2× 2k < 2× k! < (k + 1)× k! = (k + 1)!.

(Notemos aquı que las dos igualdades en la cadena fueron de tipo comparativo: sirvieron paraestablecer la liga entre la afirmacion que estaba por probarse y la anterior, que se suponıacierta segun la hipotesis de induccion.) Hemos completado satisfactoriamente los tres pasosen el metodo de induccion, ası que el resultado queda probado. ♦

17

1.55 Ejemplo. Probar por induccion la formula de Gauss

1 + 2 + 3 + · · ·+ n =n(n+ 1)

2,

para n natural.

Solucion. Notese que el miembro izquierdo de la formula indica que dado el numeronatural n hay que sumar todos los naturales mas chicos que n, incluyendo el mismo n. Ası,la sucesion de proposiciones es:

1a proposicion: 1 = 1×22

.

2a proposicion: 1 + 2 = 2×32

.

3a proposicion: 1 + 2 + 3 = 3×42

.

4a proposicion: 1 + 2 + 3 + 4 = 4×52

.

...

En este caso la base de la induccion consiste en demostrar la 1a proposicion, la cual esobvia.

Tomaremos como hipotesis de induccion la siguiente: Para cierta k ≥ 1 (abarcando

la BI) se tiene que 1 + 2 + 3 + · · · + k = k(k+1)2

. Queremos usar esto para probar que

1 + 2 + 3 + · · ·+ (k+ 1) =(k+1)

((k+1)+1

)2

. Para ello tomamos el lado izquierdo de la igualdadque queremos probar y buscamos la forma de acomodar los terminos para usar la hipotesisde induccion y despues obtener el lado derecho de la igualdad:

1 + 2 + 3 + · · ·+ (k + 1) = 1 + 2 + 3 + · · ·+ k + (k + 1)

=k(k + 1)

2+ (k + 1)

=k(k + 1) + 2(k + 1)

2

=(k + 2)(k + 1)

2.

Notamos que la primera igualdad es el paso comparativo y en la segunda igualdad se uso laHI. Esto termina la demostracion. ♦

1.56 Nota. La formula del ejemplo anterior puede probarse tambien sin usar el metodode induccion (ni combinatoria). En efecto, llamemos Sn a la suma de los primeros n naturales,escribamos Sn de dos maneras diferentes y sumemos miembro a miembro:

Sn = 1 + 2 + · · · + (n− 1) + nSn = n + (n− 1) + · · · + 2 + 12Sn = (n+ 1) + (n+ 1) + · · · + (n+ 1) + (n+ 1)

18

De la ultima ecuacion tenemos la formula buscada.

Con induccion podemos tambien probar formulas en que hay mas de una variable. Elsiguiente es un ejemplo tıpico. El contenido de la formula es muy util en diversos problemas.

1.57 Ejemplo. Si r es cualquier numero distinto de 1 (no necesariamente natural),entonces

1 + r + r2 + · · ·+ rn =rn+1 − 1

r − 1.

para cualquier natural n.

Demostracion. La sucesion de proposiciones esta indicada por n:

1a proposicion: 1 + r = r1+1−1r−1 .

2a proposicion: 1 + r + r2 = r2+1−1r−1 .

3a proposicion: 1 + r + r2 + r3 = r3+1−1r−1 .

4a proposicion: 1 + r + r2 + r3 + r4 = r4+1−1r−1 .

...

Para probar la primera afirmacion (base de la induccion) recordemos que (r+1)(r−1) =r2 − 1 y dividamos esta ecuacion por r − 1.

La HI en este caso es: “Para cierta k ≥ 1 se cumple 1 + r + r2 + · · · + rk = rk+1−1r−1 .” A

partir de esta suposicion probemos la formula correspondiente para n = k + 1:

1 + r + · · ·+ rk+1 = 1 + r + · · ·+ rk + rk+1

=rk+1 − 1

r − 1+ rk+1 (por HI)

=rk+1 − 1 + (r − 1)rk+1

r − 1

=rk+1 − 1 + rk+2 − rk+1

r − 1

=rk+2 − 1

r − 1

=r(k+1)+1 − 1

r − 1.

De esta serie de igualdades concluimos que, si la formula se supone valida para n = k,entonces tambien lo sera para n = k + 1, y con esto completamos satisfactoriamente todoslos pasos en el metodo de induccion. La conclusion es que la formula es cierta para todo n. ♦

19

1.58 Ejercicio. Probar la afirmacion del ejemplo anterior en forma no inductiva. (Su-gerencia: Utilizar la misma idea con la que probamos la base de induccion.)

Probaremos otra vez la Formula del Binomio utilizando, en esta ocasion, la induccion.

1.59 Teorema. Teorema del Binomio de Newton. (ver ??) Sean a y b numerosarbitrarios y sea n un numero natural. Entonces

(a+ b)n =

(n

0

)an +

(n

1

)an−1b+ · · ·+

(n

r

)an−rbr + · · ·+

(n

n

)bn.

Demostracion. La sucesion de proposiciones es:

1a proposicion: (a+ b)1 =(10

)a+

(11

)b.


)a2 +

(21

)ab+

(22

)b2.


)a3(31

)a2b+

(32

)ab2 +

(33

)b3.

...

La prueba de la base de induccion (es decir de la validez de la formula para n = 1) esinmediata. Hagamos la hipotesis de induccion: “Para cierta k ≥ 1 se tiene

(a+ b)k =

(k

0

)ak +

(k

1

)ak−1b+ · · ·+

(k

r

)ak−rbr + · · ·+

(k

k

)bk.”

Utilizando esta hipotesis probemos que la formula tambien vale para n = k+1. Utilizaremosla Formula de Pascal (

n+ 1

r + 1

)=

(n

r

)+

(n

r + 1

),

para r y n numeros enteros con 0 ≤ r < n (ver 1.35). Por definicion y por HI tenemos

(a+ b)k+1 =(a+ b)k(a+ b)

=

((k

0

)ak +

(k

1

)ak−1b+ · · ·+

(k

r

)ak−rbr + · · ·+

(k

k

)ak)

(a+ b).

Ahora, desarrollando la multiplicacion indicada (primero multiplicando por a y despuespor b) obtenemos(

k

0

)ak+1 +

(k

1

)akb+ · · ·+

(k

r

)ak−r+1br + · · ·+

(k

k

)abk+1

+

(k

0

)akb+ · · ·+

(k

r − 1

)ak−r+1br + · · ·+

(k

k − 1

)bk+1 +

(k

k

)bk+1.

20

Al agrupar terminos semejantes en toda esta suma, observemos que el primero y elultimo terminos aparecen solo una vez y sus respectivos coeficientes son

(k0

)= 1 =

(k+10

)y(

kk

)= 1 =

(k+1k+1

); cada uno de los otros terminos ak+1−rbr para 0 ≥ r ≥ k, aparece dos veces,

una al multiplicar(kr

)ak−rbr por a y otra al multiplicar

(k

r−1

)ak−(r−1)br−1 por b; entonces, por

la Formula de Pascal quedara con coeficiente(k+1r

). Obtendremos entonces

(a+ b)k+1 =

(k + 1

0

)ak+1 + · · ·+

(k + 1

r

)ak+1−rbr + · · ·+

(k + 1

k + 1

)bk+1,

como querıamos. La induccion nos dice entonces que la formula vale para todo numeronatural n. ♦

Recordemos que dado un numero natural n hemos definido n! como el producto de todoslos naturales menores o iguales que n y que hemos convenido que 0! = 1. La definicion den! tambien se puede dar en forma inductiva o recursiva (es decir, se tiene una base y ladefinicion de los terminos despues de esa base se da en relacion con los terminos anterioresque ya se suponen conocidos). Dicha definicion recursiva es como sigue: Se define 0! = 1 y,para n ≥ 1 se define n! = n× (n− 1)!.

En los siguientes ejemplos compararemos algunas definiciones no recursivas con otrasrecursivas.

1.60 Ejemplo. Definamos la sucesion a1, a2, a3, . . . recursivamente por a1 = 1 y, paran ≥ 2, an = an−1 + 2. Encontrar los primeros 6 terminos de la sucesion y dar una definicionno recursiva de ella.

Solucion. Para obtener los primeros 6 terminos de la sucesion partimos de la base a1 = 1y vamos construyendo los siguientes terminos sumando 2 al termino recien construido: 1, 3,5, 7, 9, 11. Una definicion no recursiva de la misma sucesion es an = 2n− 1. ♦

El ejemplo anterior es un caso particular de las llamadas sucesiones o progresionesaritmeticas; en general una sucesion aritmetica es una sucesion de numeros a1, a2, a3, . . .en que la diferencia entre dos terminos consecutivos cualesquiera es un numero constante d,es decir an+1 = an + d, para toda n.

Otros ejemplos de sucesiones aritmeticas son:

1, 2, 3, 4, 5, . . . (aquı d = 1 y a1 = 1),

2, 4, 6, 8, 10, . . . (aquı d = 2 y a1 = 2),

10, 17, 24, 31, 38, . . . (aquı d = 7 y a1 = 10).

0,−12,−1,−3

2,−2,−5

2, . . . (aquı d = −1

2y a1 = 0).

Hemos definido sucesion aritmetica por recursion, es decir, en forma inductiva; si solocontamos con esto, es de esperar que cualquier afirmacion sobre una sucesion aritmetica

21

utilice induccion; el siguiente ejemplo (demostrado por induccion), permitira trabajarlas enforma no recursiva; en particular el resultado nos dice como conocer cualquier termino de lasucesion sin necesidad de conocer el anterior.

1.61 Ejemplo. Sea a1, a2, a3, . . . una sucesion aritmetica con diferencia d (es decir, paratoda n, an+1 = an + d. Probar que para n ≥ 2 se tiene an = a1 + (n− 1)d.

Demostracion. La sucesion de afirmaciones es:

1a afirmacion: a2 = a1 + (2− 1)d.




...

La base de induccion es, en este caso, la primera afirmacion (es decir, la afirmacionpara n = 2). Es facil darse cuenta de la validez de esta proposicion pues, por definicion,a2 = a1 + d. Hagamos ahora la hipotesis de induccion: “Para cierta k ≥ 2 es verdad queak = a1 + (k − 1)d”. Utilizando esta HI probemos que tambien es cierto el resultado paran = k + 1:

ak+1 = ak + d (por definicion)

= a1 + (k − 1)d+ d (por HI)

= a1 + kd.

Esto termina la demostracion. ♦

1.62 Ejercicio. Dada la sucesion aritmetica con primer termino a1 = 2 y d = 13

encontrara100.

1.63 Ejemplo. Probar que si a1, a2, . . . es una sucesion aritmetica con diferencia d,entonces para toda n ≥ 2, la suma Sn := a1 + a2 + · · ·+ an de los primeros n terminos de lasucesion se puede calcular segun la siguiente formula:

Sn =n(a1 + an)

2.

22

Solucion. No utilizaremos induccion sino el resultado obtenido en el ejemplo 1.61 y laFormula de Gauss 1.55.

Sn = a1 + (a1 + d) + (a1 + 2d) + · · ·(a1 + (n− 1)d

)por 1.61)

= na1 +(d+ 2d+ · · ·+ (n− 1)d

)= na1 +

(1 + 2 + · · ·+ (n− 1)

)d

= na1 +n(n− 1)

2d (por Gauss)

=n

2

(2a1 + (n− 1)d

)=n

2(a1 + an) por 1.61)

Esto termina la demostracion. ♦

En todas las pruebas por induccion que hemos hecho hasta el momento, al demostrarque la (k + 1)-esima afirmacion es verdadera solo hemos utilizado la validez de la k-esimaafirmacion; inclusive, en cada caso simplificamos la hipotesis de induccion de tal manera queabarcara solo la afirmacion anterior a la que querıamos probar y no todas las anteriores. Enlos ejemplos que trataremos a continuacion sı necesitaremos hacer la hipotesis de induccioncomo la anunciamos al principio de esta seccion. La diferencia entre los casos que siguen ylos anteriores es que cada afirmacion esta ligada no solo a la que la precede sino a una omas de las anteriores. La practica nos dira como reconocer en que caso nos encontramos;mientras tanto, podemos siempre hacer la hipotesis de induccion en su forma mas generaly, una vez que estemos en el tercer paso de la demostracion inductiva, utilizar solo lo quenecesitemos de la hipotesis.

Considerando que llegado este punto ya debe ser obvio para el lector el primer paso de lainduccion (es decir, identificar la sucesion de afirmaciones que abarca la afirmacion generalque se quiere probar), de aquı en adelante ya no incluiremos este en nuestras demostraciones.

1.64 Ejemplo. La sucesion de Fibonacci f1, f2, f3, . . . se define como sigue: f1 = 1,f2 = 1 y, para n ≥ 3, fn = fn−1 + fn−2. Construir los primeros 10 terminos de la sucesion yprobar la siguiente formula que nos proporciona una definicion no recursiva de la sucesion:

fn =

(1+√5

2

)n−(

1−√5

2

)n√

5.

Solucion. Construyamos los primeros 10 terminos de la sucesion siguiendo la definicion:Los primeros dos terminos son ambos 1 y, para construir cada uno de los terminos siguientes,

23

sumemos cada vez los ultimos dos que ya tengamos: 1,1,2,3,5,8,13,21,34, 55. Como pudimosobservar en la misma definicion, para conocer un termino es necesario conocer no solo elinmediato anterior sino los dos que le preceden. Es natural entonces pensar que una demos-tracion por induccion de una afirmacion sobre todos los terminos de la sucesion de Fibonaccideba tener una hipotesis de induccion que abarque las afirmaciones correspondientes a losdos terminos que preceden al que se considera en ese momento. Por otro lado, los primerosdos terminos estan dados de manera independiente y los demas se basan en ellos; por estarazon, la base de induccion debe constar de la prueba de las dos afirmaciones correspon-dientes a estos terminos. Tomemos el lado derecho de la formula que queremos probar paran = 1: (

1+√5

2

)1−(

1−√5

2

)1√

5=

(1 +√

5)− (1−√

5)

2√

5=

2√

5

2√

5= 1 = f1.

Hagamos ahora lo mismo para n = 2:(1+√5

2

)2−(

1−√5

2

)2√

5=

(1 + 2√

5 + 5)− (1− 2√

5 + 5)

4√

5=

4√

5

4√

5= 1,

que es igual a f2. Con esto concluimos la base de induccion. Ahora tomemos k ≥ 3 y hagamosla hipotesis de induccion: “La formula es verdadera para todos los naturales menores que k”.Tenemos entonces

fk = fk−1 + fk−2 (por definicion)

=

(1+√5

2

)k−1−(

1−√5

2

)k−1√

5+

(1+√5

2

)k−2−(

1−√5

2

)k−2√

5(por HI)

=

(1+√5

2

)k−2 (1+√5

2+ 1)−(

1−√5

2

)k−2 (1−√5

2+ 1)

√5

=

(1+√5

2

)k−2 (3+√5

2

)−(

1−√5

2

)k−2 (3−√5

2

)√

5

Por otro lado, consideremos el miembro derecho de la formula para n = k:(1+√5

2

)k−(

1−√5

2

)k√

5=

(1+√5

2

)k−2 (1+√5

2

)2−(

1−√5

2

)k−2 (1−√5

2

)2√

5

=

(1+√5

2

)k−2 (1+2√5+5

4

)−(

1−√5

2

)k−2 (1−2√5+5

4

)√

5

=

(1+√5

2

)k−2 (3+√5

2

)−(

1−√5

2

)k−2 (3−√5

2

)√

5.

24

Hemos obtenido lo mismo que tenıamos arriba, ası que la formula tambien es verdadera paran = k, y esto concluye la demostracion. ♦

1.65 Ejemplo. Definamos una sucesion a0,a1,a2,. . . como sigue: a0 = 1 y, para n ≥ 1,

an =

(n

0

)a0 +

(n

1

)a1 +

(n

2

)a2 + · · ·+

(n

n− 1

)an−1.

Probar que todos los terminos de la sucesion son impares.

Solucion. Antes de empezar la demostracion de que todos los terminos son impares no-temos primero que en la misma definicion de la sucesion se hizo una recursion que utilizano solo el termino anterior al que se esta definiendo sino todos los anteriores. Es natural en-tonces pensar que para probar que un termino an (n ≥ 1) es impar, debemos utilizar el quetodos los anteriores (a0,a1,a2,. . .,an−1) lo son; ası que en este caso, la hipotesis de inducciondebera abarcar todos estos. Conviene tambien escribir los primeros terminos de la sucesion,pues el analisis cuidadoso de varios terminos en particular muchas veces da una idea de comohacer la demostracion general.

Tenemos:

a0 = 1,

a1 =

(1

0

)× 1

= 1× 1 = 1,

a2 =

(2

0

)× 1 +

(2

1

)× 1

= 1× 1 + 2× 1 = 3,

a3 =

(3

0

)× 1 +

(3

1

)× 1 +

(3

2

)× 3

= 1× 1 + 3× 1 + 3× 3 = 13,

a4 =

(4

0

)× 1 +

(4

1

)× 1 +

(4

2

)× 3 +

(4

3

)× 13

= 1× 1 + 4× 1 + 6× 3 + 4× 13 = 75,

a5 =

(5

0

)× 1 +

(5

1

)× 1 +

(5

2

)× 3 +

(5

3

)× 13 +

(5

4

)× 75

= 1× 1 + 5× 1 + 10× 3 + 10× 13 + 5× 75 = 541.

Observamos aquı que los coeficientes que van apareciendo son los del triangulo de Pascal, elcual sabemos que es simetrico respecto a la vertical central (esto es,

(nr

)=(

nn−r

)). Tambien

sabemos que los terminos centrales en los renglones pares (es decir, los de la forma(nn2

)) son

25

todos numeros pares (pues son la suma de los dos numeros iguales arriba de el). Hechas estasobservaciones procedamos con la demostracion.

La base de induccion es la prueba de que el primer termino de la sucesion (es decir, a0)es impar, lo cual es cierto por definicion. Tomemos k ≥ 1 y supongamos que a0,a1,a2,. . .,ak−1son impares (esta es nuestra hipotesis de induccion). Probaremos que ak es impar. Dividimosla prueba en dos casos: cuando k es impar y cuando k es par. En el primer caso, factorizandolos coeficientes binomiales con sus simetricos, tenemos

ak = 1 +

(k

1

)(a1 + ak−1) +

(k

2

)(a2 + ak−2) + · · ·+

(k

k−12

)(a k−1

2+ a k+1

2

).

Ahora utilizamos la hipotesis de induccion: como cada ai (con 1 ≤ i ≤ k− 1) es impar, cadauna de las sumas a1 +ak−1, a2 +ak−2, . . ., a k−1

2+a k+1

2es un numero par; con esto ya es claro

que ak es impar, y aquı termina la prueba para el caso en que k sea impar. En el caso enque k sea par, agrupamos de la misma manera pero nos sobrara un termino sin agrupar:

ak = 1 +

(k

1

)(a1 + ak−1) +

(k

2

)(a2 + ak−2) + · · ·+

(kk2

)a k

2.

Sin embargo, el termino no agrupado tambien es par pues el coeficiente binomial en el lo es.Esto concluye la prueba en el caso en que k es par. Hemos completado satisfactoriamentelos pasos de la induccion en todos los casos. ♦

El resultado que sigue ya lo habıamos probado en la seccion 3 con las tecnicas de esaseccion. Lo probaremos ahora usando induccion.

1.66 Proposicion. Todo conjunto con n elementos tiene 2n subconjuntos

Demostracion. El resultado es obvio para cuando n = 0 pues el conjunto con 0 elementossolo tiene un subconjunto que es el mismo. Sea n ≥ 1; HI: “Todo conjunto con n−1 elementostiene 2n−1 subconjuntos.” Consideremos el conjunto X = {x1, x2, . . . , xn} con n elementos.Queremos utilizar la HI para probar que X tiene 2n subconjuntos. Consideremos el conjuntoY obtenido al quitarle a X el elemento xn. Por HI, Y tiene 2n−1 subconjuntos. Ahora bien,los subconjuntos de X podemos dividirlos en dos clases: los que no tienen al elemento xn(es decir, los que estan contenidos en Y ) y los que sı lo tienen. El numero de conjuntos delas dos clases es el mismo pues cada conjunto de la segunda clase se obtiene adjuntando elelemento xn a uno de los conjuntos de la primera. Entonces, por HI, cada una de estas clasestiene 2n−1 conjuntos; en total X tendra 2n−1 + 2n−1 = 2 × 2n−1 = 2n subconjuntos, comoquerıamos probar. Esto termina la demostracion. ♦

1.67 Ejercicio. Sea X = {x1, x2, x3, x4}. Encontrar las dos clases de subconjuntos deX de que se habla en la demostracion de 1.66 y aparear los conjuntos de una clase con losde la otra como indica esa prueba.

26

1.68 Ejercicio. Hacer una prueba inductiva y otra no inductiva de la siguiente formulapara n natural:

1

1× 2+

1

2× 3+ · · ·+ 1

n× (n+ 1)=

n

n+ 1.

(Sugerencia: Para la prueba no inductiva, observar que 1k(k+1)

= 1k− 1

k+1.)

1.69 Ejercicio. Demostrar por induccion que todo conjunto tiene la misma cantidad desubconjuntos con un numero par de elementos que con un numero impar.

1.70 Ejercicio. Probar por induccion que para n natural se tiene la formula:

12 + 22 + 32 + · · ·+ n2 =n(n+ 1)(2n+ 1)

6.

1.71 Ejercicio. Calcular directamente la suma 13 + 23 + 33 + · · · + n3 para n = 1, 2, 3y 4; usar esto para proponer una formula para calcular la suma para cualquier natural n, yprobar la formula por induccion.

1.72 Ejercicio. Calcular la suma

1× 1000 + 2× 999 + 3× 998 + · · ·+ 999× 2 + 1000× 1.

1.73 Ejercicio. Sea a0,a1,a2,. . . la sucesion de numeros definida recursivamente comosigue: a0 = −1, a1 = 1 y, para n ≥ 2, an = an−1+an−2

2. Probar por induccion que para n ≥ 1,

an ≥ 0.

1.74 Ejercicio. Probar por induccion la formula siguiente para n natural:(n

0

)+

(n

1

)+ · · ·+

(n

n

)= 2n.

(Sugerencia: Utilizar la Formula de Pascal.)

1.75 Ejercicio. La siguiente afirmacion es obviamente falsa: “En cualquier lista de nnumeros, todos son iguales entre sı.” Determinar cual es el error en la “demostracion” porinduccion que presentamos a continuacion (es decir, encontrar en que momento el proce-dimiento que se sigue en la supuesta demostracion es incompleto o incorrecto): “BI: Paran = 1 la afirmacion es verdadera pues solo hay un numero en la lista. HI: Supongamos que elresultado es cierto para cualquier lista de n numeros y tomemos una lista de n+ 1 numeros:a1, a2, . . . , an, an+1. Entonces, por HI, los primeros n numeros a1, a2 . . . , an son iguales entresı; aplicando tambien la hipotesis de induccion a los ultimos n numeros: a2, . . . , an, an+1,estos son tambien iguales entre sı. Pero entonces todos son iguales a a2, ası que todos soniguales entre sı.”

27

1.76 Ejercicio. La siguiente afirmacion es obviamente falsa: “Para construir una redcarretera en un paıs de manera que cualesquiera dos ciudades esten conectadas mediante lared, es suficiente que a cada ciudad llegue al menos una carretera (entendiendo que las carre-teras sean todas de doble sentido)”. Determinar cual es el error en la “prueba” por induccionque presentamos a continuacion: “Para dos ciudades el resultado es claramente cierto. Su-pongamos por induccion que un paıs con n ciudades cumple la propiedad y agreguemos unaciudad C; por hipotesis, de C sale una carretera, digamos a D. Entonces, a traves de D, laciudad C esta conectada con las demas, y ası, todas las ciudades estan conectadas entre sı.”

1.4. Probabilidad

Como una aplicacion de los metodos de conteo que hemos estudiado en la seccion 1, dare-mos ahora una introduccion muy breve al estudio de la probabilidad. No daremos aquı unadefinicion formal del concepto matematico de probabilidad; en lugar de ello daremos unprincipio basico (valido solo dentro de los conjuntos finitos) y trabajaremos varios ejemplosque nos aclararan la forma correcta en que dicho principio debe interpretarse.

La probabilidad de que algo ocurra es el cociente del numero de casos favorables entre elnumero total de casos posibles.

Un ejemplo muy sencillo es el siguiente: La probabilidad que al lanzar una moneda al airela cara que salga (es decir, la cara que se muestra hacia arriba cuando la moneda cae) seaaguila es 1

2, pues de 2 que es el numero total de casos posibles (aguila y sol), 1 es el favorable.

Lo que esto quiere decir es que, suponiendo condiciones ideales (por ejemplo que la monedaeste bien nivelada en cuanto a peso y forma, que se lance la moneda de tal manera que nosea posible controlar lo que va a salir, que la moneda no pueda caer de canto), si la monedase lanza al aire muchas veces, se espera que alrededor de la mitad de ellas caiga aguila. (Verel comentario despues del ejemplo 1.81, donde se explica como debe interpretarse esto.)

Otro ejemplo clasico es el del lanzamiento del dado. Aquı la probabilidad de que al lanzarun dado salga 3 es 1

6pues hay 1 caso favorable de los 6 posibles que son: que salga 1, que salga

2, etc. Desde luego, aquı tambien se supone que las condiciones del dado y del lanzamientoson ideales.

Cabe advertir que el aplicar nuestro principio descuidadamente nos puede llevar a razo-namientos erroneos como el siguiente:

28

“La probabilidad de que el numero que salga al lanzar un dado sea 3 es 12

pues son 2 loscasos posibles: que salga 3 o que no salga 3, y de estos 1 es favorable.”

El error aquı es que, aun cuando es cierto que estos son los casos posibles, estos no soncomparables al mismo nivel de frecuencia (decimos que no son “igualmente probables”), lafrecuencia con la que se espera que salga el 3 no es la mitad de las ocasiones, pues se esperaque cada numero salga con la misma frecuencia.

Mencionaremos a continuacion algunas propiedades que satisface la probabilidad. No esdifıcil convencerse de su validez. Despues de cada una haremos algun comentario al respecto.

1.77 Proposicion. (P1) La probabilidad de que algo ocurra es un numero entre 0 y 1.Es 0 cuando es imposible que ocurra, y es 1 cuando es seguro que debe ocurrir.

Esta propiedad es clara pues los casos favorables son una parte de los totales.

Los casos que nosotros tratamos aquı son todos numeros racionales, es decir, cocientes deenteros. Sin embargo al trabajar la probabilidad en un contexto mas general (con conjuntosinfinitos), dado cualquier numero entre 0 y 1 (racional o no) se pueden dar ejemplos cuyaprobabilidad sea el numero dado.

(P2) Si la probabilidad de que algo ocurra es p, entonces la probabilidad de que no ocurraes 1− p.

Esto tambien es claro pues los casos generales se componen de los favorables y los desfa-vorables. Por ejemplo, la probabilidad de que al lanzar un dado no salga el 3 es 5

6= 1− 1

6.

(P3) Si dos cosas no pueden ocurrir simultaneamente, la probabilidad de que ocurra unao la otra (es decir, cualquiera de las dos) es la suma de las probabilidades.

Por ejemplo, la probabilidad de que al lanzar un dado salga 3 o un numero par es46

= 16

+ 36. Lo que dice la propiedad es que los casos favorables se pueden contar globalmente

(en el ejemplo: 3, 2, 4 y 6 son los cuatro casos favorables de los 6 posibles), o parcialmente,y luego juntarlos (en el ejemplo, considerar por separado 3 y despues los pares). Observemosque la propiedad no serıa valida si no pidieramos que los sucesos fueran mutuamente exclu-yentes, es decir, si hubiera la posibilidad de que ocurrieran simultaneamente; por ejemplo,la probabilidad de que al lanzar un dado lo que salga sea un numero mayor que 3 o que seaun numero par es 4

6(los casos favorables son 2, 4, 5 y 6) y no 3

6+ 3

6= 1, que serıa la suma

de las probabilidades (los casos 4 y 6 son comunes a los dos y se estarıan contando dos vecesal sumar las probabilidades).

(P4) La probabilidad de que ocurran dos cosas en un orden determinado es el productode las probabilidades.

29

Por ejemplo, la probabilidad de que al lanzar dos veces una moneda primero salga aguilay luego salga sol es 1

2× 1

2= 1

4. Esto es claro si recordamos que al contar los arreglos (tanto

los favorables como los generales) tambien multiplicamos. En el ejemplo, el numero total deposibilidades es 2×2 = 4: aguila-aguila, aguila-sol, sol-aguila y sol-sol; solo hay uno favorableformado por las posibilidades favorables individuales: primero aguila y despues sol. ♦

Como ya habıamos hecho notar, el principio que propusimos de

#de casos favorables

#total de casos

debe interpretarse con cuidado. El ejemplo siguiente nos ayudara a entender un poco masesto.

1.78 Ejemplo. Dentro de cierto grupo de 4 caballos numerados del #1 al #4 se haobservado que la frecuencia con que el caballo #1 gana es el doble que con la que gana el#2; que este a su vez gana el doble de veces que el #3, y que el #3 gana el doble de vecesque el #4. Encontrar la probabilidad de que en la proxima carrera el caballo ganador sea el#1 o el #3.

Solucion. Serıa incorrecto decir que el numero total de casos es 4 y que de estos losfavorables son 2, pues se nos ha advertido que las frecuencias con las que los caballos gananno son las mismas. Tenemos que dar cierto “peso” a cada caballo de tal manera que lafrecuencia con la que dicho caballo gana este representada; esto lo hacemos como sigue:Representemos con fichas la proporcion con que ganan los caballos; por ejemplo asignemos

1 ficha al caballo #4,

2 fichas al caballo #3,

4 fichas al caballo #2 y

8 fichas al caballo #1.

El numero total de casos sera entonces el numero de fichas: 1 + 2 + 4 + 8 = 15, y elnumero de casos favorables sera 2 + 8 = 10, que es el numero de fichas correspondientes alos caballos #1 y #3. La probabilidad es 10

15= 2

3. ♦

Para eliminar complicaciones tecnicas, en los dos ejemplos siguientes consideraremosel ano con 365 dıas (sin contar en ningun caso el 29 de febrero) y supondremos que ladistribucion de los cumpleanos es pareja a lo largo del ano.

1.79 Ejemplo. Encontrar la probabilidad de que una persona determinada haya nacidoen noviembre o diciembre.

Solucion. El numero de dıas favorables es 61, ası que la probabilidad es 61365

, que esaproximadamente igual a 1

6. ♦

30

1.80 Ejemplo. Encontrar la probabilidad de que en un grupo de 61 personas al menos2 tengan el mismo cumpleanos.

Solucion. Notemos que este ejemplo difiere del anterior en que las fechas de cumpleanosno se comparan con fechas fijas sino entre sı. Veremos que los resultados son muy distin-tos. Para resolver el ejemplo resulta mas facil contar la probabilidad opuesta: que no hayaningun cumpleanos repetido, y despues usar la propiedad (P2). Utilizaremos repetidamentela propiedad (P4). Consideremos un orden fijo para las personas. La probabilidad de que elsegundo cumpleanos sea distinto del primero es 364

365. La probabilidad de que el tercero sea

distinto de los dos anteriores es 363365

, y ası sucesivamente. El resultado es

1− 364× 363× · · · × 305

36560,

que es aproximadamente igual a 0.995. Esto quiere decir que de 1000 grupos de 61 personascada uno, se espera que en solo 5 de los grupos no haya cumpleanos comunes. (Compareseeste resultado con el del ejemplo anterior. Resulta que basta con 23 personas para que laprobabilidad de que haya cumpleanos repetidos entre ellas sea mayor que 1

2.) ♦

1.81 Ejemplo. Encontrar la probabilidad de que al lanzar una moneda al aire 10 vecescaigan exactamente 5 aguilas.

Solucion. Si escribimos A por aguila y S por sol, el resultado de los diez lanzamientospuede representarse por una sucesion de longitud 10 formada por los sımbolos A y S, demanera que el numero total de posibilidades es 210 = 1024. Los casos favorables estanrepresentados por las “palabras” que tienen exactamente 5 A′s y esto es el numero de formasen que se pueden escoger 5 posiciones (donde aparezcan las A′s) dentro de un total de 10,es decir,

(105

)= 252. Entonces la probabilidad de que al lanzar una moneda al aire 10 veces

salgan exactamente 5 aguilas es 2521024

, que es aproximadamente igual a 0.25. ♦

En forma analoga a la resolucion del ejemplo anterior tenemos que la probabilidad deque de un total de 20 lanzamientos de la moneda 10 salgan aguila es 1

220

(2010

), que es aproxi-

madamente igual a 0.176. Se puede demostrar que mientras mas lanzamientos se hagan, laprobabilidad de que la mitad de las veces salga aguila es menor. Esto no contradice lo quese habıa dicho anteriormente sobre que si una moneda se lanzaba al aire un numero grandede veces se esperarıa que un numero cercano a la mitad de las ocasiones cayera aguila; laexplicacion para esto es que la idea de “cercanıa” debe manejarse en forma relativa al tamanodel numero; por ejemplo, en el caso de 10 lanzamientos podrıamos decir que los casos en quesalieran entre 3 y 7 aguilas son todos “cercanos” a la mitad, y en el caso de 20 lanzamientosdirıamos que los casos “cercanos” a la mitad son entre 5 y 15.

1.82 Ejercicio. Encontrar la probabilidad de que al lanzar una moneda al aire 10 vecessalga aguila entre 3 y 7 veces.

1.83 Ejemplo. Alejandra y Delia van a jugar un juego. Alejandra lanzara un dado y

31

le dara una moneda a Delia cada vez que lo que salga en el dado no sea 2. Si se quiere queninguna de las dos jugadoras tenga ventaja sobre la otra, ¿cuantas monedas debera pagarDelia cada vez que salga el 2?

Solucion. Como la probabilidad de que salga el 2 es 16, se espera que de cada 6 veces una

de ellas salga 2; entonces Delia debera darle 5 monedas cuando esto ocurra. En 6 juegos seespera que Alejandra pierda 5 veces una moneda y gane una vez 5 monedas, por lo que suganancia esperada es de 0. ♦

Generalicemos el ejemplo que acabamos de estudiar. Si algo puede ocurrir de un totalde r formas (mutuamente excluyentes) con probabilidades p1, p2, . . ., pr (de manera quep1 + p2 + · · ·+ pr = 1) y ganancias respectivas g1, g2, . . ., gr, entonces el valor esperado Edel suceso se define como

E = g1p1 + g2p2 + · · ·+ grpr.

Para entender mejor esta nueva definicion analicemos en el ejemplo 1.83 cual es la gananciaesperada de Alejandra si Delia le da 5 monedas cada vez que salga el 2. Llamemos p1 a laprobabilidad de que no salga el 2 y p2 a la probabilidad de que sı salga; entonces p1 = 5

6,

p2 = 16, g1 = −1 (pues Alejandra pierde una moneda cuando no sale el 2) y g2 = 5. El valor

esperado del suceso (ganancia esperada para Alejandra) es E = (−1)× 56

+ 5× 16

= 0.

1.84 Ejemplo. En el juego de ruleta hay 36 numeros (del 1 al 36) y ademas los sımbolos0 y 00, con los que el dueno de la ruleta gana automaticamente. Se ofrece pagar 36 veces loapostado cada vez que salga el numero al que uno aposto (es decir, si uno indica uno de los36 numeros y paga una ficha por jugar, en caso que al girar la ruleta la bolita se detenga enel numero escogido, el dueno de la ruleta le devolvera su ficha al jugador y le dara otras 35mas). ¿Cual es la ganancia esperada de un jugador?

Solucion. Llamemos p1 a la probabilidad de que el jugador gane, y p2 a la probabilidadde que pierda. Entonces p1 = 1

38, p2 = 37

38, g1 = 35 y g2 = −1; ası E = 35× 1

38+ (−1)× 37

38=

−238

, que es aproximadamente igual a −0.05. Esto quiere decir que el jugador espera perderalrededor de un 5 % de lo apostado; en otras palabras, el dueno de la ruleta espera ganar el5 % de lo que se apueste. ♦

En algunos de los ejercicios que se presentan a continuacion se hace referencia al juegode baraja o al de domino. Las descripciones de estos se pueden encontrar, respectivamente,en las explicaciones que aparecen antes de los ejemplos 1.28 y 1.42.

1.85 Ejercicio. Una persona quiere apostar que la suma de lo que muestren dos dadoses cierto numero. ¿A que numero le conviene apostar? Calcular la probabilidad de que salgadicho numero.

1.86 Ejercicio. Supongamos que se va a jugar un juego de pokar muy simple en el que sereparten 5 cartas y el “mejor juego” (es decir, el que tiene la menor probabilidad de ocurrir)

32

gana. Segun las probabilidades ¿como debe ser la jerarquıa entre las manos que contenganexactamente cada uno de los siguientes: full, flor, corrida, un par, dos pares, pokar y tercia?

1.87 Ejercicio. Se eligen al azar n cartas de la baraja. ¿Como debe ser n para que laprobabilidad de que entre las cartas elegidas haya (al menos) dos del mismo numero seamayor que 1

2? ¿Cual es la probabilidad si n = 14?

1.88 Ejercicio. En cierto examen de opcion multiple con 5 opciones en cada respuestase califica como sigue: por cada respuesta correcta se otorga +1 punto, por cada respuestaincorrecta se otorga −1

4de punto, y por cada pregunta sin contestar se otorgan 0 puntos.

¿Que calificacion esperarıa obtener alguien que contestara todo el examen al azar?

1.89 Ejercicio. ¿Con que frecuencia un jugador de domino espera tener una mano conal menos dos fichas dobles?

1.90 Ejercicio. Calcular la probabilidad de que al lanzar tres veces dos dados, las tresveces los numeros que salgan sean iguales entre sı (por ejemplo, la primera vez (6,6), lasegunda (1,1) y la tercera (6,6)).

1.91 Ejercicio. Se escogen al azar en sucesion tres numeros (posiblemente iguales) entreel 1 y el 100. ¿Cual es la probabilidad de que se hayan escogido en orden creciente estricto?

1.92 Ejercicio. Un grupo de 4 mujeres y 4 hombres se dividira en dos equipos con 4miembros cada uno. ¿Cual es la probabilidad de que en uno de los equipos queden todos loshombres y en el otro todas las mujeres?

1.93 Ejercicio. Un dado se lanza al aire 6 veces. ¿Cual es la probabilidad de que aparezcacada uno de los seis numeros una vez?

1.94 Ejercicio. Supongamos que de un grupo de 10 enfermedades cada una tiene pro-babilidad 1

10de atacar a un animal determinado a lo largo de su vida. ¿Que probabilidad

tiene ese animal de enfermarse de al menos una de esas enfermedades?

1.95 Ejercicio. Comparar las respuestas de las tres preguntas siguientes:

(a) Lance una moneda al aire dos veces y una de ellas salio aguila. ¿Cual es la probabilidadde que la otra tambien haya salido aguila?

(b) ¿Cual es la probabilidad de que al lanzar una moneda al aire dos veces las dos vecessalga aguila?

(c) Lance una moneda al aire y salio aguila. ¿Cual es la probabilidad de que al lanzar lamoneda otra vez vuelva a salir aguila?

33

2. Teorıa de Numeros

2.1. Divisibilidad

Esta y la siguiente seccion son una breve introduccion al estudio de una rama de lasMatematicas llamada Teorıa de Numeros, cuyo origen es el estudio del conjunto de losnumeros enteros

Z = {. . . ,−2,−1, 0, 1, 2, 3, . . .}.Ası como dentro del conjunto de los numeros naturales

N = {1, 2, 3, . . .}

no siempre se pueden considerar restas (para a y b naturales, a − b es natural si, y solo si,a > b), dentro del conjunto Z no siempre hay cocientes (por ejemplo, 6

2es entero pero 5

2

no lo es). Sin embargo la condicion de divisibilidad de enteros (es decir, la condicion paradeterminar cuando el cociente de dos enteros es otro entero) no se expresa de manera tansencilla como la de diferencia en los numeros naturales. Estudiaremos aquı algunos aspectosde este tema de divisibilidad.

En toda la seccion, las letras a, b, c, etc. representaran enteros.

Si a y b son enteros, decimos que a divide a b, en sımbolos a∣∣∣ b, si es posible encontrar

un entero x de tal manera que ax = b. Otras formas de expresar que a divide a b son:

a es divisor de b,

a es factor de b,

b es divisible entre a y

b es multiplo de a.

Si a no divide a b escribimos a - b.

2.1 Ejemplo. (a) Los numeros pares, . . . ,−4,−2, 0, 2, 4, 6, . . ., son precisamente aquellosque son divisibles por el entero 2, pues son los de la forma 2x con x entero.

(b) −12∣∣∣ 36 (aquı x = −3).

(c) 17∣∣∣ 0 (aquı x = 0; en general, para todo entero a se tiene a

∣∣∣ 0).

(d) 1∣∣∣− 11 (aquı x = −11; en general, para todo entero a se tiene 1

∣∣∣ a).

2.2 Nota. Cuando a 6= 0, son equivalentes el que a∣∣∣ b y el que b

asea un entero (en este

caso solo hay una solucion de la ecuacion ax = b, que es x = ba). Por otro lado, aun cuando

34

no podemos hablar del “entero 00”, segun la definicion que acabamos de dar podemos afirmar

que 0 divide a 0 pues la ecuacion 0 = 0x tiene solucion entera (cualquier entero sirve comosolucion).

Recordemos que si x es un numero real cualquiera, entonces el valor absoluto de x,denotado por |x|, es su distancia al 0 en la recta numerica real. Entonces, por ejemplo,|7| = 7, | − 7| = 7, |0| = 0, | − 1.43| = 1.43, |

√2| =

√2,

2.3 Proposicion. (a) Para a y b enteros, a∣∣∣ b si y solo si |a|

∣∣∣ |b|.(b) Si a

∣∣∣ b y b 6= 0, entonces |a| ≤ |b|.

(c) Para todo entero a se tiene a∣∣∣ a. (Se dice que la relacion de divisibilidad es reflexiva.)

(d) Si a, b y c son enteros tales que a∣∣∣ b y b

∣∣∣ c entonces a∣∣∣ c. (Se dice que la relacion de

divisibilidad es transitiva.)

(e) Es posible que a∣∣∣ b pero que b - a. (Se dice que la relacion de divisibilidad no es

simetrica.)

(f) Para a y b enteros, a∣∣∣ b y b

∣∣∣ a si y solo si |a| = |b| (es decir, a = ±b).

Demostracion. (a) En cada caso, basta ajustar el signo de la solucion x segun se necesite:Si b = ax, entonces |b| = |a|(±x). Recıprocamente, si |b| = |a|x, entonces b = a(±x).

(b) Tenemos que b = ax, ası que |b| = |a||x|. Como b 6= 0, entonces |a|, |b| y x son todosnaturales, ası que |b| se obtiene sumando |x| veces el numero |a| y entonces es claro que|a| ≤ |b|.

(c) Para x = 1 tenemos a = ax, por tanto a∣∣∣ a.

(d) Sean x y y enteros con ax = b y by = c; entonces axy = by = c, de donde concluimos

que a∣∣∣ c.

(e) Tomar, por ejemplo, a = 3 y b = 6.

(f) Supongamos primero que a∣∣∣ b y que b

∣∣∣ a, y vamos a probar que |a| = |b|. Si alguno de

los dos es cero, digamos a = 0, como ax = b para algun entero x, entonces tambien b = 0,ası que |a| = 0 = |b|. Si ninguno de los dos es cero entonces, por (b), |a| ≤ |b| y |b| ≤ |a|,por tanto |a| = |b|. Ahora supongamos que |a| = |b|; para ver que a

∣∣∣ b y b∣∣∣ a basta usar (c)

y (a). ♦

2.4 Nota. La propiedad (a) nos dice que la mayor parte del trabajo sobre divisibilidadcon numeros enteros se puede hacer dentro del conjunto No := {0, 1, 2, 3, . . .} (y despues

35

agregar los signos en caso necesario). La ventaja de trabajar dentro de No es que ahı tenemosuna poderosa herramienta de demostracion que es la induccion.

2.5 Proposicion. Para a, b y c enteros, tenemos que a∣∣∣ b y a

∣∣∣ c si y solo si a∣∣∣ rb + sc

para cualesquiera r y s enteros.

Demostracion. Primero supongamos que a∣∣∣ b y que a

∣∣∣ c y tomemos un numero rb + sc

con r y s enteros; queremos probar que a∣∣∣ rb + sc. Tenemos que b = ax y que c = ay para

algunos enteros x y y. Entonces rb + sc = rax + say = a(rx + sy), por lo cual rb + sc

tiene como factor a a, es decir, a∣∣∣ rb + sc, como querıamos probar. Ahora supongamos que

a∣∣∣ rb+ sc para cualquier eleccion de r y s enteros. Entonces, al tomar r = 1 y s = 0, vemos

que a∣∣∣ b pues 1b+ 0c = b; analogamente, al tomar r = 0 y s = 1 vemos que a

∣∣∣ c. ♦Si b y c son enteros, todo numero que pueda expresarse en la forma rb + sc (para r y s

enteros) se llama combinacion lineal (entera) de b y c. Como observamos en la proposicion2.5, los mismos enteros b y c son combinacion lineal de b y c. Tambien es facil convencersede que todos los multiplos de b y todos los multiplos de c son combinacion lineal de b y c(basta tomar s = 0 o r = 0, segun sea el caso). Podemos usar la proposicion anterior paraver que no cualquier numero es combinacion lineal de dos numeros escogidos b y c, como enel ejemplo que sigue.

2.6 Ejemplo. Probar que ningun numero impar es combinacion lineal de 4 y 6.

Solucion. Aplicamos la proposicion con a = 2, b = 4 y c = 6. Supongamos que un ciertonumero impar h es combinacion lineal de 4 y 6; entonces, utilizando la proposicion 2.5,

tenemos que 2∣∣∣h, lo cual es falso pues h es impar. De aquı concluimos que no es posible que

h sea combinacion lineal de 4 y 6. ♦

2.7 Nota. La proposicion 2.5 no nos da una respuesta sobre que numeros exactamenteson combinacion lineal de dos numeros fijos dados, solo nos da un criterio para saber quealgunos no lo son: si logramos encontrar un factor comun de b y c que no sea factor de h,entonces sabremos que h no es combinacion lineal de b y c, sin embargo, si no encontramostal factor, la proposicion no nos dara respuesta alguna. Para obtener una respuesta completanecesitamos avanzar bastante mas en nuestro tema; haremos esto en 2.54 e incluso propor-cionaremos un algoritmo (metodo) para escribir cualquier numero que sı sea combinacionlineal de un par de numeros dados como combinacion lineal de los mismos. Queremos hacernotar tambien que, en caso de que cierto numero h sea combinacion lineal de otros dos b y c,la pareja de enteros r y s no es unica (es decir, hay muchas formas de expresar determinadonumero como combinacion lineal de otros dos); por ejemplo, si h = 1, b = 2 y c = 3, entonces1 = 2 × (−1) + 3 × (1) (aquı r = −1 y s = 1) o tambien 1 = 2 × 2 + 3 × (−1) (aquı r = 2

36

y s = −1). Mas adelante diremos como encontrar todas las formas de escribir un numerocomo combinacion lineal de otros dos numeros enteros dados (ver 2.73).

Un caso particular de la proposicion 2.5 que se utiliza con frecuencia en problemas dedivisibilidad es el siguiente corolario.

2.8 Corolario. Si b, c y d estan relacionados por la ecuacion b + c = d, y un numero aes divisor de cualesquiera dos de ellos, entonces tambien lo es del tercero.

Demostracion. Para deducir este corolario a partir de la proposicion 2.5 basta observarque cada uno de b, c y d es combinacion lineal de los otros dos. ♦

2.2. Numeros primos

Los numeros enteros “indivisibles” juegan un papel muy importante dentro de la teorıade la divisibilidad pues a partir de productos de ellos se construyen todos los demas enteros,y muchas preguntas sobre divisibilidad tienen respuesta en el analisis de esa construccion;a esos numeros basicos les llamaremos primos. Mas concretamente, decimos que un enterop 6= ±1 es primo si sus unicos divisores son ±1 y ±p. Un entero no cero y distinto de ±1es compuesto si no es primo. Los enteros 1 y −1 no son primos ni compuestos, se llamanunidades. Al numero 0 no lo consideraremos dentro de ninguna de estas categorıas. Tene-mos entonces que son numeros primos: ±2,±3,±5,±7,±11,±13,±17, . . . Son compuestos:±4,±6,±8,±9,±10,±12,±14,±15,±16, . . . Un numero a se llamara divisor propio de

otro numero b si a∣∣∣ b pero a 6= ±1 y a 6= ±b; en este caso tambien diremos que b es multiplo

propio de a; ası, un numero primo sera aquel que sea distinto de ±1 y que no tenga divisorespropios.

A continuacion veremos el importante resultado llamado teorema fundamental de laaritmetica, que habla sobre la construccion de los enteros a partir de productos de primos; elcontenido del teorema es un resultado que hemos manejado con familiaridad desde nuestrosprimeros cursos de aritmetica: el de escribir numeros como producto de primos (por ejemplo,12 = 2 × 2 × 3). Tambien sabemos que la forma de hacerlo no es unica (por ejemplo,12 = 2× 3× 2 = (−2)× 2× (−3) = · · · ); sin embargo el orden y el signo de los primos es lounico que estorba en la unicidad de la descomposicion segun nos dira tambien el TeoremaFundamental de la Aritmetica. Por el momento no podremos probar esta parte de que ladescomposicion es esencialmente unica pues necesitamos desarrollar mas herramientas ennuestra teorıa; por esta razon por el momento enunciaremos y probaremos solo la primera

37

parte.

2.9 Teorema. Teorema Fundamental de la Aritmetica (primera parte). Todoentero distinto de 0 y de ±1 es producto de primos.

Demostracion. Sea a 6= 0,±1 y consideremos primero el caso en que a sea positivo. Si aes primo, entonces no hay nada que probar (permitimos productos de un solo factor). Si a noes primo entonces es compuesto, ası que podemos escribir a = bc, con b y c enteros positivosy distintos de 1 y de a; ademas tenemos que b y c son ambos menores que a. Otra vez, si b y cson primos, entonces ya acabamos. Si alguno de ellos (o los dos) no lo es, lo escribimos comoproducto de otros dos mas chicos, y ası sucesivamente. Este procedimiento debe terminar enalgun momento (en menos de a pasos) pues cada vez los numeros son menores y positivos;cuando termine el procedimiento habremos encontrado la descomposicion de a en productode primos como querıamos.

El caso en que a sea negativo se reduce al anterior pues podemos aplicar el resultado a−a (que es positivo) y despues agregar el signo a alguno de los primos en la descomposicionde −a. ♦

2.10 Nota. El “ası sucesivamente” que usamos en la demostracion anterior lleva implıci-ta una induccion; utilizando el lenguaje mas elegante de la induccion matematica, la demos-tracion (para el caso de numeros positivos) podrıa escribirse como sigue:

Base de induccion: El resultado es obviamente cierto para los numeros primos.

Hipotesis de induccion: Sea a ≥ 3 y supongamos que el resultado es cierto para todoslos naturales entre 2 y a − 1. Si a es primo, entonces la base de induccion nos da el re-sultado; si a no es primo entonces a = bc, con b y c enteros entre 2 y a − 1; utilizando lahipotesis de induccion escribamos b y c como producto de primos; la descomposicion de a seobtendra juntando las dos descomposiciones.

2.11 Nota. Como dijimos arriba, posteriormente completaremos el Teorema Fundamen-tal de la Aritmetica demostrando que la descomposicion es unica salvo orden y signo. Usandoeste resultado con toda su fuerza, podemos hacer la factorizacion en primos poniendo pri-mero el signo y despues escribiendo solo primos positivos en orden creciente de magnitud yagrupando los primos que son iguales en la potencia correspondiente. A esta forma la llama-remos descomposicion canonica del numero. Por ejemplo, la descomposicion canonica de−180 es −22325.

En lo que sigue estudiaremos metodos para encontrar la descomposicion canonica denumeros pequenos. Para ello necesitaremos saber tambien como decidir si cierto numero esprimo o no.

El siguiente lema esta basado en el simple hecho de que si un numero positivo a esproducto de dos divisores positivos, entonces alguno de ellos debe ser menor o igual que

38

√a (pues el producto de dos numeros positivos mayores que

√a es mayor que a). Por

ejemplo, si a = 24, en cualquiera de las siguientes descomposiciones de a como productode dos numeros observamos que uno de los factores es menor o igual que

√24 = 4.8 . . .:

24 = 3× 8 = 6× 4 = 2× 12.

2.12 Lema. Sea a un numero entero mayor que 1 con la propiedad de que ningun numeroprimo menor o igual que

√a lo divida. Entonces a es primo.

Demostracion. Supongamos que a no es primo y escribamos a = bc con 1 < b, c < a.Como estamos suponiendo que a no tiene factores primos menores o iguales que

√a, entonces

tampoco los tienen ni b ni c, ası que b y c son ellos mismos mayores que√a; pero entonces,

a = bc >√a√a = a. Esta cadena de igualdades y desigualdades nos dice que a > a, lo cual

es un absurdo, ası que nuestra suposicion no puede ser cierta y a debe ser primo. ♦

2.13 Ejemplo. Probar que 61 es un numero primo.

Solucion. Aplicando el lema, como√

61 < 8, basta que comprobemos que 61 no es divisiblepor ninguno de los primos 2, 3, 5 y 7, lo cual es claramente cierto. ♦

Si queremos dar una lista de todos los primos hasta un cierto lugar (por ejemplo, la listade todos los primos menores que 60), el lema anterior no resulta practico pues al aplicarlotendrıamos que analizar cada numero por separado y esto nos llevarıa a hacer demasiadasdivisiones. Describiremos ahora el metodo de la Criba de Eratostenes para determinartodos los primos positivos menores que un cierto numero elegido R (en la figura de abajo seilustra el metodo para cuando R = 60):

Se escriben todos los numeros enteros entre 1 y R. La idea es ir senalando los numerosprimos y tachando los no primos como sigue: Se tacha primero el 1; despues se pone entreparentesis el 2 y se tachan todos los multiplos propios de 2; a continuacion se busca el primernumero no marcado todavıa (en este caso el 3) y se pone entre parentesis; se tachan todoslos multiplos propios de el que aun no hayan sido tachados y se repite el procedimiento hastatener todos los numeros marcados, ya sea entre parentesis o tachados.

Observemos que en cualquier paso, el primer numero que se encuentra sin marca es primopues si tuviera algun factor propio a > 0, entonces el numero habrıa sido ya tachado al tachartodos los multiplos de a. Observemos tambien que, gracias al lema, todos los numeros queno han sido marcados hasta el momento en que se tachan los multiplos del ultimo primomenor o igual que

√R son primos, lo que permite terminar el procedimiento relativamente

pronto (en nuestro ejemplo, al llegar al primo 7, pues el siguiente numero sin marca serıa 11,

39

pero 11 ya es mayor que√

60).

1/ (2) (3) 4/ (5) 6/ (7) 8/ 9/ 10/(11) 12/ (13) 14/ 15/ 16/ (17) 18/ (19) 20/21/ 22/ (23) 24/ 25/ 26/ 27/ 28/ (29) 30/

(31) 32/ 33/ 34/ 35/ 36/ (37) 38/ 39/ 40/(41) 42/ (43) 44/ 45/ 46/ (47) 48/ 49/ 50/51/ 52/ (53) 54/ 55/ 56/ 57/ 58/ (59) 60/

2.14 Ejemplo. Determinar si 1517 es primo o no.

Solucion. Desde luego, en este caso no necesitamos conocer todos los primos del 1 al 1517;bastara conocer todos los primos menores que

√1517 y revisar si alguno de ellos es divisor de

1517. Como 402 = 1600, es suficiente considerar los primos menores que 40 que son: 2, 3, 5,7, 11, 13, 17, 19, 23, 29, 31 y 37. Al hacer la division de 1517 con cada uno de estos (a manoo con una calculadora) vemos que 37 es el unico que sı lo divide (y que 1517 = 37× 41), porlo que concluimos que no es primo. ♦

2.3. Criterios de divisibilidad

Enunciaremos ahora algunos criterios de divisibilidad entre numeros pequenos, algunosde los cuales son bien conocidos por nosotros desde nuestros primeros cursos de algebra.

2.15. Criterio de divisibilidad entre 2. Un entero a es divisible por 2 si, y solo si, atermina en 0, 2, 4, 6 u 8. (Por ejemplo, 38 es divisible por 2 pero 35 no lo es.)

2.16. Criterio de divisibilidad entre 3. Un entero a es divisible por 3 si, y solosi, la suma de las cifras de a es divisible por 3. (Por ejemplo, 228 es divisible por 3 pues2 + 2 + 8 = 12, que es multiplo de 3; sin embargo 343 no lo es puesto que 3 + 4 + 3 = 10,que no es multiplo de 3.)

2.17. Criterio de divisibilidad entre 4. Un entero a es divisible por 4 si, y solo si, elnumero formado por las dos ultimas cifras de a lo es. (Por ejemplo 3 128 es divisible por 4pues 28 lo es; sin embargo 411 no lo es pues 11 no es multiplo de 4).

2.18. Criterio de divisibilidad entre 5. Un entero a es divisible por 5 si, y solo si,termina en 0 o 5. (Por ejemplo 2515 es divisible por 5 pero 217 no.)

40

2.19. Criterio de divisibilidad entre 6. Un entero a es divisible por 6 si y solo a sies divisible por 2 y por 3. (Por ejemplo 43 644 sı es divisible por 6 pues es multiplo de 2 yde 3; sin embargo, 364 no lo es pues es multiplo de 2 pero no de 3.)

2.20. Criterio de divisibilidad entre 8. Un entero a es divisible por 8 si, y solo si, elnumero formado por las ultimas tres cifras de a lo es. (Por ejemplo 27 256 es divisible por 8pues 256 lo es; sin embargo 23 420 no es divisible por 8 pues tampoco lo es 420.)

2.21. Criterio de divisibilidad entre 9. Un entero a es divisible por 9 si, y solo si,la suma de las cifras de a es divisible por 9. (Por ejemplo 23 985 sı es divisible por 9 pues2 + 3 + 9 + 8 + 5 = 27, que es multiplo de 9; sin embargo 386 754 no es multiplo de 9 pues3 + 8 + 6 + 7 + 5 + 4 = 33, que no es multiplo de 9.)

2.22. Criterio de divisibilidad entre 10. Un entero a es divisible por 10 si, y solo si,a termina en 0. (Por ejemplo 29 853 780 es divisible por 10 pero 38 475 no lo es.)

2.23. Criterio de divisibilidad entre 11. Un entero a es divisible por 11 si, y solosi, la diferencia de la suma de las cifras en posicion impar de a menos la suma de las cifrasen posicion par de a es divisible por 11. (Por ejemplo 82 817 053 sı es divisible por 11 pues(2 + 1 + 0 + 3)− (8 + 8 + 7 + 5) = 6− 28 = −22, que es divisible por 11; sin embargo 2 759no lo es pues (7 + 9)− (2 + 5) = 9, que no es divisible por 11.

2.24. Criterio de divisibilidad entre 12. Un entero a es divisible por 12 si y solo aes divisible por 4 y por 3. (Por ejemplo 771 084 sı es divisible por 12 pues es multiplo de 4y de 3; sin embargo, 438 no lo es pues es multiplo de 3 pero no de 4.)

Existen diversos criterios de divisibilidad entre 7 pero ninguno de ellos es realmentepractico como los que hemos mencionado arriba en los que el analisis de divisibilidad decierto numero posiblemente grande se reduce al de otro numero bastante menor.

Las demostraciones de los criterios de divisibilidad entre 2, por 4, por 5, por 8 y por10 son muy parecidas entre sı; haremos aquı la de division por 4, dejando las otras comoejercicio. Los criterios de divisibilidad entre 3, por 9 y por 11 se dejaran para la seccion deCongruencias (ver 2.97 y 2.99), pues con las herramientas desarrolladas en esa seccion sonmuy sencillos de probar. Los criterios que mencionamos sobre la divisibilidad entre 6 y por12 se deducen facilmente del Teorema Fundamental de la Aritmetica.

2.25 Ejemplo. Demostrar el criterio de divisibilidad entre 4.

Solucion. Sea a = anan−1 · · · a1a0 la expresion decimal de a (por ejemplo, si a = 20328,entonces n = 4, a4 = 2, a3 = 0, a2 = 3, a1 = 2 y a0 = 8). Sea b = a1a0. Queremos

41

probar que 4∣∣∣ a si, y solo si, 4

∣∣∣ b. Recordemos que la expresion decimal de a significa que

a = an10n + an−110n−1 + · · · + a1101 + a0100. Sea c = an10n + an−110n−1 + · · · + a2102,

de manera que a = c + b. Podemos observar que 4∣∣∣ c pues 4

∣∣∣ 100 y 100∣∣∣ c, ası que por el

corolario 2.8 tenemos que 4∣∣∣ a es equivalente a 4

∣∣∣ b, como querıamos probar. ♦

2.26 Ejemplo. Encontrar la descomposicion canonica de los numeros a = 1320, b =−14157 y c = 600.

Solucion. En todos los casos consideramos primero |a| (al final agregamos el signo sies necesario) y le buscamos el menor divisor primo positivo; despues dividimos a entre esedivisor y al resultado se le hace lo mismo hasta obtener el numero 1; los resultados parcialesde las divisiones se van poniendo en fila por debajo de a y los divisores correspondientes seescriben a la derecha de estos; los factores primos de |a| son precisamente los que quedan enla columna de la derecha:

1320 2660 2330 2165 355 511 111

14157 34719 31573 11143 1113 131

600 2300 2150 275 325 55 51

Entonces a = 23 · 3 · 5 · 11, b = −32 · 112 · 13 y c = 23 · 3 · 52. ♦

2.4. Algoritmo de la division.

En mucho de lo que sigue necesitamos la segunda parte del Teorema Fundamental de laAritmetica (unicidad de la descomposicion de los enteros como producto de primos); paraprobar esto necesitamos desarrollar mas la teorıa, cosa que haremos a continuacion.

2.27 Teorema. Algoritmo de la division. Dados dos enteros a y b con b 6= 0 existenenteros unicos q y r de tal forma que

a = bq + r, y

0 ≤ r < |b|.

42

Demostracion. Primero probaremos la existencia de los enteros q y r. Por simplicidad,consideraremos solo el caso en que b > 0 y a ≥ 0. Los demas casos pueden deducirse de estefacilmente (ver ??). Consideremos todos los multiplos no negativos de b:

0, b, 2b, 3b, . . .

Sea qb el mayor multiplo de b tal que qb ≤ a, es decir a se encuentra entre qb y (q + 1)b enla recta numerica (permitiendose el caso en que a = qb). Definimos r := a− qb.

...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................| | | | | |

︷︸︸︷0 b 2b · · · qb (q + 1)ba

r

︸︷︷︸︸︷︷︸︸︷︷︸b b b

Entonces a = qb + r y, como la distancia entre dos multiplos consecutivos de b es |b|(que en este caso es b mismo), tenemos que 0 ≤ r < |b|, como querıamos. (Por ejemplo, sia = 20 y b = 6, entonces, 3× 6 = 18 es el multiplo de 6 mas cercano por la izquierda a 20,ası que q = 3 y r = 20 − 18 = 2. Entonces el Algoritmo de la Division en este caso nos da20 = 6× 3 + 2.)

Probaremos ahora que para cada pareja (a, b) solo hay una pareja de enteros (q, r) quecumple las dos condiciones del algoritmo. Supongamos que (q1, r1) y (q2, r2), son parejas deenteros que satisfacen las condiciones, es decir, a = bq1 + r1, 0 ≤ r1 < |b| y a = bq2 + r2,0 ≤ r2 < |b|. Tenemos que bq1 + r1 = bq2 + r2 (pues ambos miembros son iguales a a), dedonde bq1 − bq2 = r2 − r1; tomando valores absolutos y factorizando b obtenemos

(∗) |b||q1 − q2| = |r2 − r1|.

Si |r2 − r1| fuera distinto de 0, sin perdida de generalidad podrıamos suponer que r2 > r1;entonces por 2.3(b), tenemos que |b| ≤ |r2 − r1| = r2 − r1, lo cual es absurdo pues r2 − r1 ≤r2 < |b|. Concluimos entonces que |r2 − r1| no puede ser distinto de 0, o sea que r2 = r1.Ahora sustituyamos esto en la ecuacion (∗) para obtener |b||q1 − q2| = 0, y como |b| 6= 0,entonces |q1 − q2| = 0, es decir, q1 = q2. ♦

2.28 Ejemplo. Encontrar q y r del Algoritmo de la Division si a = 20 y b = −6.

Solucion. Usando 20 = 6 × 3 + 2, obtenemos 20 = (−6) × (−3) + 2, ası que q = −3 yr = 2. ♦

El numero q en la proposicion anterior es el cociente (de la division de a entre b) y elnumero r es el residuo (de la division de a entre b).

Desde luego, si no pidieramos la condicion 0 ≤ r < |b|, los enteros q y r no serıan unicos;por ejemplo, si a = 20 y b = 6, la ecuacion a = bq+ r podrıa ser cualquiera de las siguientes:

43

20 = 6× 3 + 2, 20 = 6× 4 + (−4), 20 = 6× 0 + 20, 20 = 6× (−1) + 26, etc. (De hecho, paracada valor entero de q obtenemos un valor de r.)

2.29 Observacion. Si a y b son enteros y b 6= 0, entonces b∣∣∣ a si, y solo si, el residuo r

de la division de a entre b es 0. ♦

2.5. Maximo comun divisor

Sea n ≥ 2 un natural. Dada una coleccion de numeros enteros distintos de cero a1, a2, . . . , ansu maximo comun divisor, en sımbolos mcd(a1, a2, . . . , an), es el mayor de sus divisores

comunes, es decir, d = mcd(a1, a2, . . . , an) si d∣∣∣ a1, d ∣∣∣ a2, · · · , d ∣∣∣ an, y cualquier numero

entero que cumpla estas condiciones es menor o igual que d.

2.30 Ejemplo. Hallar el maximo comun divisor d de los numeros 12, 30 y 18.

Solucion. Encontremos primero los divisores de cada uno de estos numeros. Los divisoresde 12 son:

±1,±2,±3,±4,±6 y ± 12.

Los divisores de 30 son:

±1,±2,±3,±5,±6,±10,±15 y ± 30.

Los divisores de 18 son:±1,±2,±3,±6,±9 y ± 18.

Entonces los divisores comunes son:

±1,±2,±3 y ± 6,

y el mayor de ellos es 6, ası que este ultimo es el maximo comun divisor. ♦

El metodo usado en el ejemplo anterior para encontrar el maximo comun divisor de dosnumeros no resulta muy practico. En 2.35 y 2.61 aparecen dos formas mas simples.

Estudiaremos a continuacion algunas propiedades del maximo comun divisor; considera-remos solo el caso n = 2, es decir el caso del maximo comun divisor entre dos numeros; lasgeneralizaciones para n > 2 son sencillas usando la formula recursiva

44

2.31.mcd(a1, a2, . . . , an) = mcd

(a1,mcd(a2, . . . , an)

),

y las demostraciones se dejan como ejercicio.

En ocasiones se define mcd(a, 0) = mcd(0, a) = 0 para cualquier entero a (inclusive paraa = 0). Nosotros aquı no trabajaremos mas que el caso en que ambos son distintos de cero.

2.32 Proposicion. Sean a y b enteros no cero. Entonces

(a) mcd(a, b) = mcd(|a|, |b|);(b) mcd(a, b) > 0;

(c) si a∣∣∣ b, entonces mcd(a, b) = |a|; y

(d) si d = mcd(a, b), a = da′ y b = db′ (es decir, a′ y b′ son los respectivos cocientes de ay b entre d), entonces mcd(a′, b′) = 1.

Demostracion. Las pruebas de (a) de (b) y de (c) son obvias; solo probaremos (d). Supon-gamos que el entero k > 0 es un divisor comun de a′ y b′; bastara probar que k = 1. Sean a′′

y b′′ los respectivos cocientes de a′ y b′ entre k: a′ = ka′′ y b′ = kb′′. Entonces a = da′ = dka′′

y b = db′ = dkb′′, ası que dk es divisor comun de a y b, pero d es el mayor divisor comun yk > 0, por lo que la unica posibilidad es k = 1, como querıamos probar. ♦

2.33 Nota. En la proposicion anterior, (a) nos dice que podemos restringir nuestraatencion a enteros positivos cuando se trata de estudiar el maximo comun divisor, con laventaja de que dentro de los numeros naturales disponemos del Principio de Induccion.Intuitivamente (d) nos dice que “si a a y a b les ‘quitamos’ todo lo que tienen en comun (esdecir d), entonces lo numeros que quedan (a′ y b′) no tienen ‘nada’ en comun”.

Si mcd(a, b) = 1, decimos que a y b son primos relativos o primos entre sı.

2.34 Lema. Sean a y b enteros no cero con b - a. Si q y r son enteros tales que a = bq+r,entonces mcd(a, b) = mcd(b, r).

Demostracion. Utilizando 2.5 tenemos que los divisores comunes de a y b tambien lo sonde r, y que los de b y r tambien lo son de a. En particular el mayor de los divisores comunesde a y b es el mismo que el de b y r. ♦

El siguiente resultado es muy importante. Su demostracion utiliza el Algoritmo de laDivision.

2.35 Teorema. Algoritmo de Euclides. Sean a y b enteros no cero. Entonces mcd(a, b)es combinacion lineal de a y b.

45

Demostracion. Por simplicidad supondremos que a y b son positivos (el caso general sededuce trivialmente de este ajustando signos). Si b | a entonces mcd(a, b) = b que, obviamente,es combinacion lineal de a y b. Supongamos entonces que b - a. Utilizando el Algoritmo dela Division consideremos enteros qi y ri de tal manera que

(∗)

a = bq + r1, 0 < r1 < b,b = r1q1 + r2, 0 < r2 < r1,r1 = r2q2 + r3, 0 < r3 < r2,

...rn−2 = rn−1qn−1 + rn, 0 < rn < rn−1,rn−1 = rnqn.

Por el lema anterior tenemos que

mcd(a, b) = mcd(b, r1) = mcd(r1, r2) = · · · = mcd(rn−1, rn) = rn.

Ahora probaremos por induccion que todos los residuos r1, . . . , rn son combinacion linealde a y b. La base de induccion consiste en probar que r1 y r2 son combinacion lineal de ay b (si n = 1, entonces en el primer paso podemos terminar la prueba). Despejando r1 dela primera ecuacion tenemos que r1 = a − bq, combinacion lineal de a y b. Entonces en lasegunda ecuacion, r2 = b− r1q1 = b− (a− bq)q1 = a(−q1) + b(1 + qq1); con esto termina labase de la induccion. Ahora supongamos que para cierta i ≥ 3 los dos residuos anteriores ri−1y ri−2 son combinacion lineal de a y b; como ri es combinacion lineal de ri−1 y de ri−2 es facillograr ri tambien como combinacion lineal de a y b utilizando la hipotesis de induccion. ♦

2.36 Nota. La demostracion anterior nos da tambien un metodo muy sencillo paraobtener el maximo comun divisor entre dos numeros: es el ultimo residuo no 0 de las divisionessucesivas en (∗).

En la practica, para escribir mcd(a, b) como combinacion lineal de a y b conviene seguirel procedimiento inverso del que se siguio en la demostracion anterior, es decir, ir despejandolos residuos de las ecuaciones de abajo hacia arriba. Ademas conviene marcar de algunamanera los numeros a, b y rn, por ejemplo, escribiendolos entre llaves, y tambien marcarde otra forma los residuos, por ejemplo, subrayandolos. De esta manera sabremos que losnumeros subrayados son los que se tienen que ir primero despejando, luego sustituyendo y,por ultimo, factorizando. Tambien es conveniente verificar la respuesta final pues es facilequivocarse en el camino. Ilustraremos el metodo con un ejemplo.

2.37 Ejemplo. Escribir el maximo comun divisor de 94 y 34 como combinacion linealde estos numeros.

46

Solucion. Apliquemos el Algoritmo de la Division varias veces como nos indica el Algo-ritmo de Euclides hasta encontrar el mcd(94, 34) y marquemos a, b y los residuos:

{94} = {34} × 2 + 26 (∗){34} = 26× 1 + 8 (∗∗)

26 = 8× 3 + {2} (∗ ∗ ∗)8 = {2} × 4.

Entonces mcd(94, 34) = 2. Ahora para escribir 2 como combinacion lineal de 94 y 34 primerodespejamos 2 de la ultima ecuacion y luego repetimos sucesivamente los siguientes pasos deabajo hacia arriba: sustitucion del residuo de la ecuacion precedente, factorizacion de losnumeros marcados y operaciones de los numeros no marcados:

Despeje en (∗ ∗ ∗):{2} = 26− 8× 3,

(Notese que 2 = mcd(26, 8) y hasta aquı tenemos escrito a 2 como combinacion lineal de 26y 8.)

Sustitucion del residuo de (∗∗):

{2} = 26− ({34} − 26× 1)× 3.

Factorizacion y operaciones:

{2} = 26(1 + 3) + {34}(−3)

= 26(4) + {34}(−3).

(Notese que 2 = mcd(34, 26) y hasta aquı tenemos escrito a 2 como combinacion lineal de34 y 26.) Sustitucion del residuo de (∗):

{2} = ({94} − {34} × 2) (4) + {34}(−3).

Factorizacion y operaciones:

{2} = {94}(4) + {34}(−8− 3)

= {94}(4) + {34}(−11). ♦

2.38 Ejercicio. Expresar 0 como combinacion lineal de 3 y 11 de dos maneras distintas.

2.39 Ejercicio. Expresar 20 como combinacion lineal de 7 y 4.

2.40 Ejercicio. ¿Es posible utilizar la proposicion 2.5 para decidir si 4 es combinacionlineal de 18 y 12 o no?

47

2.41 Ejercicio. ¿Es posible utilizar la proposicion 2.5 para decidir si 22 es combinacionlineal de 60 y 14 o no?

2.42 Ejercicio. Determinar si 557 es o no primo.

2.43 Ejercicio. Determinar todos los primos entre 1 y 80.

2.44 Ejercicio. Encontrar la descomposicion canonica del numero −6 511 131.

2.45 Ejercicio. Encontrar los enteros q y r del Algoritmo de la Division correspondientesa los respectivos valores de a y b:

(a) a = −19 y b = 7.

(b) a = 3 y b = −8.

(c) a = 12 y b = 3.

(d) a = −9 y b = −2.

En cada caso, hacer una ilustracion de los numeros en la recta numerica.

2.46 Ejercicio. Escribir el maximo comun divisor de 99 y 68 como combinacion linealde estos numeros.

2.47 Ejercicio. Determinar si 15, −9 y 61 son combinacion lineal de -24 y 93; en casoafirmativo, escribir una combinacion lineal para cada caso.

2.48 Ejercicio. Determinar la cantidad de divisores positivos de 600.

2.49 Ejercicio. Si a = ±pe11 p

e22 · · · pekr es la descomposicion canonica del entero a, probar

que el numero de divisores positivos de a es (e1 + 1)(e2 + 1) · · · (ek + 1).

2.50 Ejercicio. ¿Cuantas cifras tiene el numero 21996 × 52000?

2.51 Ejercicio. En una lista estan escritos los numeros del 1 al 16. ¿Es posible tachar4 de ellos de manera que al multiplicar cualesquiera 2 de los 12 que queden el resultado nosea el cuadrado de un numero entero?

2.52 Ejercicio. En una mesa hay 350 canastas vacıas numeradas del 1 al 350. Andrespuso una pelota en cada canasta con numero par, Beatriz puso una pelota en cada canastacon numero multiplo de 3, Carlos puso una pelota en cada canasta con numero multiplode 5 y Diana puso una pelota en cada canasta con numero multiplo de 11. Encontrar doscanastas con numeros consecutivos que tengan exactamente 4 pelotas entre las 2.

48

2.6. Teorema Fundamental de la Aritmetica

Utilizaremos ahora la parte teorica del Algoritmo de Euclides: “que el maximo comundivisor de dos numeros se puede escribir como combinacion lineal de los mismos” para obteneralgunos otros resultados que nos permitiran demostrar la unicidad en la descomposicion comoproducto de primos de los numeros. Mas adelante utilizaremos la parte practica del resultadopara resolver ecuaciones diofantinas (es decir, para encontrar todas las soluciones enteras deecuaciones de la forma ax+ by = c, donde a, b y c son enteros).

2.53 Corolario. Sean a y b dos enteros no cero y sea d su maximo comun divisor.Entonces cualquier divisor comun de a y b tambien es divisor de d.

Demostracion. Como c divide a a y a b, tambien divide a cualquier combinacion lineal deellos, en particular a d. ♦

El siguiente corolario nos dice exactamente que numeros pueden ser combinacion linealde dos enteros distintos de cero a y b.

2.54 Corolario. Sean a y b enteros no cero y sea d su maximo comun divisor. Un numeroc es combinacion lineal de a y b si, y solo si, es multiplo de d.

Demostracion. Por la proposicion ?? tenemos que si c es combinacion lineal de a y b,entonces d | c. Recıprocamente, supongamos que c es un multiplo de d y probemos que c sepuede expresar como combinacion lineal de a y b. Escribamos c = dc′ y d = ar+ bs (con c′, ry s enteros). Entonces, multiplicando la ultima ecuacion por c′, tenemos c = a(rc′)+b(sc′). ♦

2.55 Ejemplo. Determinar si 7 y 20 son combinacion lineal de 12 y 28; en caso afirma-tivo, escribir una combinacion lineal en cada caso.

Solucion. Como mcd(12, 28) = 4 y 4 - 7, entonces 7 no es combinacion lineal de 12 y28. Por otro lado, 4 sı es divisor de 20. Ademas, es facil expresar 4 como combinacion linealde 12 y 28 (“al tanteo”): 4 = 12(−2) + 28. Multiplicando por 5 esta ecuacion (aquı c′ delcorolario anterior es 5), obtenemos 20 = 12(−10) + 28(5). ♦

2.56 Corolario. Sean a, b y c enteros tales que a | bc. Si a y b son primos relativosentonces a | c.

49

Demostracion. Sean r y s enteros tales que ar + bs = 1 y multipliquemos esta ecuacionpor c: arc+ bsc = c. Como a | arc y a | bsc, entonces a | c. ♦

2.57 Corolario. Si b1, b2, . . . , bk son enteros y un primo p es divisor del producto b1b2 · · · bk,entonces p divide a alguna de las b′is.

Demostracion. Haremos una induccion sobre k. La base de induccion es para k = 2.Si p | b1, entonces no hay nada que probar. Si p - b1, entonces por ser p primo, p es primorelativo con b1, ası que por el corolario anterior, p | b2. Ahora supongamos que k ≥ 3 y queel resultado es cierto para k − 1 factores. Como arriba, si p | b1, entonces no hay nada queprobar, ası que supongamos que p - b1 y concluyamos que p | b2 · · · bk. Ahora aplicando lahipotesis de induccion tenemos el resultado. ♦

2.58 Nota. El resultado anterior no es cierto si no pedimos que p sea un numero primo,es decir, es posible que un numero divida a un producto sin que divida a ninguno de susfactores como lo muestra el ejemplo 6 | 4× 3.

Como corolario del resultado anterior obtenemos la unicidad en la descomposicion de losenteros como producto de primos, como probaremos a continuacion.

2.59 Teorema. Teorema Fundamental de la Aritmetica (segunda parte). Todoentero distinto de 0 y de ±1 es producto de primos en forma unica salvo orden y signo.

Demostracion. Por , ya sabemos que todo entero distinto de 0 y de ±1 es producto deprimos. Para ver la unicidad supongamos que a = ±p1p2 · · · ps = ±q1q2 · · · qt, donde s y tson naturales y los pi y los qj son primos. Queremos probar que s = t y que, salvo el signo,cada primo aparece exactamente el mismo numero de veces en la lista p1, p2, . . . , ps que en lalista q1, q2, . . . , qt. Sin perdida de generalidad, podemos suponer que los pi y los qj son todospositivos. Hagamos induccion sobre s. Para s = 1 el resultado es claro pues a serıa primo.Entonces supongamos que s ≥ 2 y que el resultado es verdadero para s − 1 factores (esdecir, la hipotesis de induccion es que si un numero acepta una descomposicion en productos − 1 primos positivos, entonces cualquier otra descomposicion de ese numero en productode primos positivos es igual a ella excepto, tal vez, por el orden de los factores). Como p1 | a,entonces p1 | q1q2 · · · qt. Por el corolario anterior, p1 debe dividir a algun qj que, sin perdidade generalidad, supongamos es q1; pero este ultimo es primo, ası que p1 = q1. Cancelandoentonces p1 y q1 en la ecuacion p1p2 · · · ps = q1q2 · · · qt, tenemos que p2 · · · ps = q2 · · · qt. Lahipotesis de induccion se aplica aquı para obtener s − 1 = t − 1 y los primos p2, . . . , ps sonlos mismos que q2, . . . , qt, de donde queda probado el teorema. ♦

Gracias al Teorema Fundamental de la Aritmetica, cada numero entero distinto de 0 y de±1 tiene una sola descomposicion canonica. Agregando potencias cero a las descomposicionescanonicas de dos o mas numeros se pueden usar los mismos primos en las factorizaciones de

50

todos ellos. Por ejemplo si a = 675 = 33 × 52 y b = 20 = 22 × 5, entonces podemos escribira = 20×33×52 y b = 22×30×5. Con esta escritura es muy facil determinar si un numero esdivisible por otro o no, como nos dice el siguiente importante corolario, cuya demostracionse deja como ejercicio.

2.60 Corolario. Sean a = ±pe11 p

e22 · · · p

ekk y b = ±pf1

1 pf2

2 · · · pfkk , donde p1 < p2 < · · · < pk

son primos positivos y las ei y las fj son enteros no negativos. Entonces a | b si, y solo si,para toda i = 1, . . . , k, se tiene que ei ≤ fi. ♦

2.61 Corolario. Sean a y b como en el corolario anterior y sea d = pm11 pm2

2 · · · pmkk donde,

para cada i, mi es el mınimo entre ei y fi (denotado por min{ei, fi}). Entonces d = mcd(a, b).

Demostracion. Por el corolario 2.60, es claro que d es divisor comun de a y b. Paraver que es el mayor, tomemos otro divisor comun c. Tambien por el mismo corolario, c =pu11 p

u22 · · · p

ukk , con cada ui ≤ ei y ui ≤ fi; pero entonces ui ≤ mi para toda i, ası que, otra

vez por 2.60, c | d, de donde c ≤ |c| ≤ d. ♦

2.62 Nota. De la demostracion anterior podemos concluir que el maximo comun divisord de dos numeros no cero a y b esta caracterizado por las siguientes propiedades:

(a) d | a, d | b, y

(b) si c | a y c | b entonces c | d.

2.63 Ejemplo. Encontrar el mcd(16 500, 1 050).

Solucion. Tenemos que 16 500 = 22 × 3× 53 × 11 y que 1 050 = 2× 3× 52 × 7, por tantomcd(16 500, 1 050) = 2× 3× 52 = 150. ♦

2.7. Mınimo comun multiplo

Sean a1, a2, . . . , ak enteros no cero. Definimos el mınimo comun multiplo de ellos, ensımbolos mcm[a1, a2, . . . , ak] como el menor de todos los multiplos comunes positivos de ellos.(Nota: En muchos textos se usa simplemente la notacion [a1, a2, . . . , ak],)

2.64 Ejemplo. (a) Si a = 10 y b = 6, entonces los multiplos positivos de a son: 10, 20,30, 40, 50, 60, 70, etc.; y los de b son: 6, 12, 18, 24, 30, 36, 42, 48, 60, 66, etc. Entonces

51

mcm[10, 6] = 30.

(b) Si a = 4, b = 6 y c = 10, entonces mcm[4, 6, 10] = 60.

Al igual que con el maximo comun divisor, estudiaremos aquı solo el mınimo comunmultiplo de dos numeros y dejaremos como ejercicio para el lector el caso de mas numeros.La formula recursiva aquı es:

2.65. mcm[a1, a2, . . . , ak] = mcm[a1,mcm[a2, . . . , ak]].

2.66 Proposicion. Sean a y b enteros no cero. Entonces

(a) mcm[a, b] es divisor de cualquier multiplo comun de a y b.

(b) Si a = ±pe11 p

e22 · · · p

ekk y b = ±pf1

1 pf2

2 · · · pfkk , con los pi primos distintos y los ei y los

fi no negativos, entonces mcm[a, b] = pM11 pM2

2 · · · pMkk , donde, para cada i, Mi = max{ei, fi}

(el maximo valor entre ei y fi).

(c) mcd(a, b) ·mcm[a, b] = |ab|.

Demostracion. La demostracion de (a) y (b) es como en la proposicion 2.61 y se dejacomo ejercicio para el lector. Para probar (c), observemos que

|ab| = pe1+f1

1 pe2+f2

2 · · · pek+fkk

y que, para cada i, min{ei, fi} es uno de los dos valores ei o fi, y max{ei, fi} es el otro, demanera que tambien

mcd(a, b) ·mcm[a, b] = pe1+f1

1 pe2+f2

2 · · · pek+fkk . ♦

El resultado del Teorema Fundamental de la Aritmetica es tan claro que ya lo hemosusado de manera intuitiva en varias ocasiones e inclusive hemos hablado ya de la descompo-sicion canonica de los numeros desde el principio de esta seccion. En los siguientes ejemplosvolveremos a usarlo, ahora ya con una mejor comprension de lo que hacemos. Utilizaremostambien sus corolarios.

2.67 Ejemplo. Probar que si p es un numero primo entonces√p no es un numero

racional (es decir, cociente de dos enteros).

Solucion. Supongamos que(ab

)2= p, con a y b primos relativos. Entonces a2 = b2p, de

donde p∣∣∣ a2 y, por ser p primo, p

∣∣∣ a. Sea a = pc. Entonces (pc)2 = b2p, por lo tanto pc2 = b2,

de donde p∣∣∣ b, lo cual es una contradiccion pues supusimos que a y b eran primos relativos. ♦

2.68 Ejemplo. Probar que el conjunto de primos es infinito.

Solucion. Supongamos que el conjunto de primosP es finito: P = {p1, p2, . . . , pk}. Sea a = p1p2 · · · pk + 1. Por el Teorema Fundamental de

52

la Aritmetica, a se descompone como producto de primos; en particular a tiene un factorprimo q. Veamos que q /∈ P, con lo cual habremos probado que de cualquier conjunto finitode primos que consideremos, forzosamente habra siempre un primo fuera de nuestra lista,concluyendo ası que el conjunto de primos no puede ser finito. Si q ∈ P, entonces q = pi

para alguna i, pero entonces q∣∣∣ a y q

∣∣∣ p1p2 · · · pk, de donde, por 2.8, q∣∣∣ 1; como esto es un

absurdo, no es posible que q ∈ P. ♦

2.69 Ejemplo. (a) Sea f(x) = anxn + an−1x

n−1 + · · · + a1x + a0 un polinomio concoeficientes enteros. Probar que si r

ses raız de f(x) con r y s enteros primos relativos,

entonces r∣∣∣ a0 y s

∣∣∣ an.

(b) Usar el inciso anterior para encontrar a, b y c tales que

f(x) = x3 − x2 − 4x+ 4 = (x− a)(x− b)(x− c).

Solucion. (a) Si rs

es raız de f(x) entonces

an

(rs

)n+ an−1

(rs

)n−1+ · · ·+ a1

(rs

)+ a0 = 0.

Multiplicando por sn obtenemos

anrn + an−1r

n−1s+ · · ·+ a1rsn−1 + a0s

n = 0.

En todos los terminos aparece s como factor (incluso en 0) excepto en anrn, por lo tanto

s∣∣∣ anrn. Pero mcd(r, s) = 1 y de aquı que s

∣∣∣ an. De manera analoga obtenemos que r∣∣∣ a0.

(b) Usando (a) tenemos que los posibles candidatos para raıces racionales del polinomio

son de la forma rs

con r∣∣∣ 4 y s

∣∣∣ 1, es decir, rs

= ±1,±2 ± 4. Sustituyendo estos valores en

f(x) vemos que las raıces son 1, 2 y −2, de donde f(x) = (x− 1)(x− 2)(x+ 2). ♦

2.8. Ecuaciones diofantinas

Dados a y b enteros no cero y c un entero cualquiera, encontraremos todas las parejasde enteros (x, y) que satisfacen la ecuacion ax + by = c. A este tipo de ecuaciones concoeficientes enteros y soluciones enteras se les llama ecuaciones diofantinas. Como vimosen 2.54, un numero entero c es combinacion lineal de otros dos a y b si, y solo si, c es multiplodel maximo comun divisor de a y b. Sin embargo hay muchas formas de escribir un numero

53

como combinacion lineal de otros dos; en ocasiones, cuando los numeros no son muy grandes,podemos proceder “al tanteo”. En casos mas complicados podemos recurrir al Algoritmo deEuclides; sin embargo, de esta manera solo podemos encontrar una o unas cuantas solucionesde la ecuacion. Para poder determinar todas las soluciones examinaremos primero el caso enque c sea 0.

2.70 Proposicion. El conjunto de soluciones de una ecuacion diofantina

ax+ by = 0

con a y b primos entre sı esta dado por:

x = −bty = at

con t entero.

Demostracion. Primero probemos que si t es entero, entonces (−bt, at) es solucion; paraello basta sustituir en la ecuacion: a(−bt)+b(at) = 0. Ahora veamos que cualquier solucion esde esa forma, es decir, que si (xo, yo) es solucion, entonces existe to entero tal que xo = −btoy yo = ato: Tenemos que axo + byo = 0, de donde (∗) axo = −byo y ası a | − byo; pero ay b son primos relativos, de donde, por 2.3, a | yo, es decir, yo = ato para algun entero to.Sustituyendo en (∗) tenemos que axo = −b(ato); ahora cancelamos a en esta ecuacion paraobtener xo = −bto, como querıamos. ♦

En la proposicion 2.70 aparece como hipotesis el que los coeficientes de las variablessean primos entre sı. En el caso en que no lo sean, hay otras soluciones aparte de las de laproposicion; por ejemplo, 6x+4y = 0 tiene como solucion a (−2, 3). El caso general (a y b nonecesariamente primos relativos) se deduce muy facilmente del de 2.70 pues toda ecuacionax + by = 0 es equivalente (es decir, tiene el mismo conjunto solucion) a una ecuaciona′x + b′y = 0 en la cual los coeficientes son primos relativos: simplemente se toma a′ = a

dy

b′ = bd, donde d = mcd(a, b); en otras palabras, se divide la ecuacion ax+ by = 0 entre d. En

resumen, tenemos el siguiente corolario.

2.71 Corolario. Sean a y b enteros distintos de 0 y sea d su maximo comun divisor.Sean a′ = a

dy b′ = b

d. Entonces las soluciones de la ecuacion ax+ by = 0 estan dadas por

x = −b′t,y = a′t,

donde t es cualquier entero. ♦

Geometricamente, sabemos que el conjunto de soluciones (no necesariamente enteras)de una ecuacion ax + by = 0 se representa en el plano por una recta por el origen. Las

54

soluciones enteras (puntos de coordenadas enteras sobre la recta) son puntos distribuidoshomogeneamente sobre la recta como se ilustra en el ejemplo siguiente.

2.72 Ejemplo. Encontrar todas las soluciones enteras de la ecuacion 4x + 6y = 0 yhacer un dibujo de ellas en el plano.

Solucion. La ecuacion es equivalente a 2x+3y = 0. Por el corolario anterior, las solucionesenteras son las parejas (−3t, 2t), con t entero. El dibujo es el siguiente:

..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.............................................................................................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................................................................................................................................

(−6, 4)

(−3, 2)

(6,−4)

(3,−2)

(0, 0)

•

•

•

•

•

Nos apoyaremos en el corolario anterior para obtener las soluciones de la ecuacion ax +by = c (con c arbitraria).

2.73 Proposicion. Sean a y b enteros distintos de 0 y sea d su maximo comun divisor.Sea c un entero multiplo de d: c = dc′. Sean a′ = a

dy b′ = b

d. Si (x1, y1) es una solucion

particular de la ecuacion ax + by = c, entonces el conjunto solucion de la misma ecuacionesta dado por

x = x1 − b′t,y = y1 + a′t,

donde t es cualquier entero.

Demostracion. Probemos primero que cualquier pareja como en el enunciado es solucionusando que (x1, y1) es solucion y el corolario anterior: a(x1− b′t) + b(y1 +a′t) = (ax1 + by1) +(a(−b′t)+b(a′t)) = c+0 = c. Ahora probemos que cualquier solucion es de la forma propuestaen el enunciado: Sea (x2, y2) solucion de la ecuacion; queremos ver que existe un entero s talque x2 = x1 − b′s y y2 = y1 + a′s, o, equivalentemente, que x2 − x1 = −b′s y y2 − y1 = a′s,;por el corolario 2.71, basta probar que (x2−x1, y2− y1) es solucion de ax+ by = 0, pero estoes facil: a(x2 − x1) + b(y2 − y1) = (ax2 + by2)− (ax1 + by1) = c− c = 0. ♦

El resultado anterior nos dice que las soluciones de la ecuacion ax + by = c se puedenobtener sumando a las soluciones de la ecuacion ax + by = 0 una solucion particular de la

55

ecuacion ax + by = c. Este resultado tiene una interpretacion geometrica interesante: Lospuntos de coordenadas enteras en la recta Rc determinada por la ecuacion ax + by = c seobtienen trasladando los de la recta Ro determinada por ax+ by = 0 mediante un punto deRc (ver la figura).

.................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

...........................................................................................................................................................................................................................................................................................................................................................

......................................................................................................................................................................................................................................................................................................................................................................

......................................................................................................................................................................................................................................................................................................................................................................

....................................................................................

................

....................................................................................

................

....................................................................................

................

....................................................................................

................

....................................................................................

................

•

•

•

•

•

•

•

•

•

• Ro

Rc

2.74 Ejemplo. Encontrar todas las soluciones enteras de la ecuacion 4x + 6y = 8 yhacer un dibujo de ellas en el plano.

Solucion. Como mcd(4, 6) = 2 y 2 | 8, la ecuacion sı tiene solucion. Dividiendo entre 2,transformemos la ecuacion en otra ecuacion equivalente pero con coeficientes primos entre sı:2x+3y = 4. Como los numeros son pequenos en este caso, encontremos al tanteo una solucionparticular, por ejemplo (2, 0). Entonces, por la proposicion 2.73 el conjunto de soluciones es(2−3t, 2t), con t entero. Esto es, variando t = . . . ,−3,−2,−1, 0, 1, 2, . . . tenemos el conjuntode soluciones:

· · · , (11,−6), (8,−4), (5,−2), (2, 0), (−1, 2), (−4, 4), · · ·El dibujo es:

...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

........................................................................................................................................................................................................................................................................................................................................................................................................................................... ........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

..

•

•

•

•

(−4, 4)

(−1, 2)

(2, 0)

(5,−2)

♦

2.75 Ejercicio. El producto de tres enteros mayores que 1 y distintos entre sı es 196.¿Cuales son los tres enteros?

56

2.76 Ejercicio. Si a y b son dos enteros positivos que cumplen que ab = 10 000 pero nia ni b son multiplos de 10, ¿a cuanto es igual a+ b?

2.77 Ejercicio. En la division de 999 entre n, donde n es un entero de dos cifras, elresiduo es 3. ¿Cual es el residuo de la division de 2001 entre n?

2.78 Ejercicio. ¿Cuantos numeros de tres dıgitos abc (con a 6= 0) son tales que a+3b+ces multiplo de 3?

2.79 Ejercicio. ¿Cual es el menor entero n tal que 15n es un cuadrado y 100n es uncubo?

2.80 Ejercicio. Si m y n son enteros positivos que satisfacen mn +mn+1 +mn+2 = 39,entonces, ¿cuanto vale nm?

2.81 Ejercicio. Se tienen n focos numerados del 1 al n. Supongase que estan todosapagados y que estan conectados cada uno con un apagador. Una sucesion de n personasva apagando y prendiendo los focos segun la siguiente regla: la primera persona cambia deposicion todos los apagadores; la segunda cambia de posicion los apagadores 2, 4, 6, 8, . . .; latercera cambia la posicion de los apagadores 3, 6, 9, 12, . . .; ası sucesivamente, hasta la ultimapersona que solo cambia la posicion del apagador n. ¿Que focos quedan prendidos al final?

2.82 Ejercicio. Las longitudes de los lados de un triangulo son los enteros 13, x, y.Encontrar el perımetro si se sabe que xy = 105.

2.83 Ejercicio. En cierta escuela 169

de los alumnos tiene ojos azules, 187

de los alumnoses pelirrojo y 1

29es zurdo. ¿Cual es el mınimo numero de alumnos que puede tener la escuela?

2.84 Ejercicio. Comparar el conjunto solucion que se da en el ejemplo 2.74 con lasolucion que hubiera dado si se hubiera considerado la solucion particular (−1, 2) en lugarde (2, 0).

2.85 Ejercicio. Encontrar todas las soluciones enteras de la ecuacion

282x− 195y = 7

y hacer un dibujo de ellas en el plano.

2.86 Ejercicio. Encontrar todas las soluciones enteras de la ecuacion

282x− 195y = 15

y hacer un dibujo de ellas en el plano.

57

2.9. Congruencias

Esta seccion debera estudiarse una vez que se hayan estudiado los conceptos basicos sobredivisibilidad de numeros enteros. Estudiaremos una relacion entre numeros enteros que secomporta en muchos sentidos como la igualdad y que tiene que ver con repeticiones cıclicasde enteros (por ejemplo, los dıas de la semana aparecen repitiendose cada 7 en forma cıclica).El nuevo lenguaje simplificara mucho la resolucion de algunos problemas sobre divisibilidad.

Empecemos por analizar algunos ejemplos.

2.87 Ejemplo. Supongamos que en este momento son las 10 de la manana; ¿que horasera dentro de 2 500 horas?

Solucion. Como cada 24 horas se repite la misma hora, podrıamos hacer una lista de2 500 numeros despues del 10, poniendo renglones de longitud 24 y viendo en que columnaquedo el ultimo (es decir, 2510). Sin embargo esto serıa muy largo y realmente lo unico quenos interesa en este problema es el residuo de 2 510 al dividirlo por 24. Al hacer la divisionencontramos que 2 510 = 24×104+14. Esto nos dice que el residuo es 14, ası que la respuestaes: Seran las 14 horas (2 de la tarde). ♦

2.88 Ejemplo. Si en este momento son las 10 de la manana, ¿que hora fue hace 2500horas?

Solucion. En este caso, como 2 490 = 24× 103 + 18, entonces, multiplicando por −1 estaecuacion, tenemos −2 490 = 24×(−103)−18; hemos encontrado en esta ecuacion un residuonegativo y, como a nosotros nos gustarıa que estuviera entre 0 y 23, sumamos y restamos24 en la ecuacion y obtenemos el nuevo residuo 24− 18 = 6. Con esto concluimos que hace2500 horas fueron las 6 de la manana. ♦

En los dos ejemplos anteriores trabajamos con repeticiones periodicas de numeros (conperiodo 24). Para estos problemas de horas del dıa, dos numeros representan la misma horasi, y solo si, tienen el mismo residuo al dividirlos por 24 o, dicho de otra manera, si, y solosi, su diferencia es un multiplo de 24. Ası, todos los numeros obtenidos al sumar (o restar)multiplos de 24 al numero 2: . . . ,−46,−22, 2, 26, 50, 74, . . . son representantes de la mismahora, a saber, las 2 de la manana. No podemos decir que “26 es igual a 2”, diremos en lugarde esto que “26 es congruente a 2 modulo 24” entendiendo que, cuando se trata de periodos

58

de longitud 24, los numeros 26 y 2 representan lo mismo.

Lo que hicimos arriba con el numero 24 lo podemos hacer con cualquier natural n,dependiendo del problema que queramos resolver; por ejemplo, si estuvieramos interesadosen dıas de la semana, las repeticiones serıan cada 7 numeros y entonces n = 7. En este casose harıa la convencion, por ejemplo, que el 1 correspondiera al lunes, el 2 al martes, el 3 almiercoles, etc.; ası el 8 corresponderıa otra vez al lunes, y ası sucesivamente, de manera quedos numeros representaran el mismo dıa de la semana si su diferencia es un multiplo de 7 o,equivalentemente, si dejan el mismo residuo al dividirlos por 7. Escribamos la definicion engeneral (para cualquier n).

Sea n un numero natural. Si a y b son enteros cualesquiera decimos que a ≡ b (mod n)

(lease a es congruente con b modulo n) si n∣∣∣ a− b.

2.89 Ejemplo. Analizar congruencias y clases modulo 6.

Solucion. Hagamos una lista de todos los enteros agrupandolos de 6 en 6 por renglones:

......

......

......

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

0 1 2 3 4 56 7 8 9 10 11

12 13 14 15 16 17...

......

......

...

Por la forma en que construimos la tabla podemos notar que todos los numeros en unamisma columna difieren por un multiplo de 6. Observamos tambien que los de una mismacolumna dejan el mismo residuo al dividirlos por 6; por ejemplo, los de la primera columnadejan residuo 0, esto es, son todos multiplos de 6 o, en otras palabras, son los enteros dela forma 6k con k entero (−12 = 6 × (−2), −6 = 6 × (−1), 0 = 6 × 0, 6 = 6 × 1, . . .);los de la segunda columna son los que dejan residuo 1, es decir los de la forma 6k + 1(−11 = 6× (−2) + 1, −5 = 6× (−1) + 1, 1 = 6× 0 + 1, 7 = 6× 1 + 1, . . .). Segun nuestradefinicion, el tipo de relacion que guardan entre sı los elementos de una misma columna sellama congruencia modulo 6. Todo el conjunto de numeros de una misma columna constituyeuna clase (modulo 6) y cualquier elemento de esa columna es un representante de la clase.Ası, por ejemplo, 0 = 12 = {. . . ,−12,−6, 0, 6, 12, 18, . . .} y −2 = 4 = {. . .−8,−2, 4, 10, . . .}.Tenemos que cada residuo en la division por 6 es representante de una clase y que en totalhay 6 clases. ♦

En nuestros ejemplos hemos observado que el que a sea congruente con b modulo n esequivalente a que a y b tengan el mismo residuo al dividirlos por n. Probemos esto en general.

59

2.90 Proposicion. Sea n un numero natural y sean a y b enteros. Supongamos quea = nq1 + r1 y que b = nq2 + r2, con q1, q2, r1 y r2 enteros que satisfagan 0 ≤ r1, r2 < n.Entonces a ≡ b (mod n) si y solo si r1 = r2.

Demostracion. Supongamos primero que a ≡ b (mod n). Si r1 ≥ r2, restemos las dosecuaciones del enunciado para obtener: a − b = n(q1 − q2) + (r1 − r2). Entonces como nes divisor de a − b y de n(q1 − q2) tambien lo es de r1 − r2; pero n > r1 ≥ r1 − r2 ≥ 0,por lo que la unica posibilidad es que r1 − r2 = 0. En el caso en que r1 ≤ r2 restamos

las ecuaciones en sentido opuesto, observando que como n∣∣∣ a − b, entonces tambien n es

divisor de −(a− b) = b− a. Ahora supongamos que r1 = r2 y probemos a partir de esto quea ≡ b (mod n). En este caso, al restar las ecuaciones nos queda a− b = n(q1− q2); por tanto

n∣∣∣ a− b y ası, a ≡ b (mod n), como querıamos probar. ♦

2.91 Ejercicio. Probar que dos numeros son congruentes modulo 2 exactamente cuandotienen la misma paridad, es decir, los dos son pares o los dos son impares. Escribir las dosclases modulo 2.

2.92 Ejercicio. Encontrar dos enteros positivos y dos enteros negativos que sean con-gruentes con 38 modulo 3.

Antes de ver mas ejemplos estudiaremos algunas propiedades de las congruencias que nospermitiran trabajarlas, en buena parte, como las ecuaciones. Estas propiedades nos ayudarana “despejar” incognitas de congruencias lineales de la misma manera que lo hacemos con lasecuaciones, con la unica excepcion de que no siempre podremos dividir.

2.93 Proposicion. Sea n ≥ 1 un entero. Para a, b, c y d enteros cualesquiera se tiene:

(C1) a ≡ a (mod n). Es decir, la relacion de congruencia es reflexiva. (En otras palabras,todo numero es congruente a sı mismo).

(C2) Si a ≡ b (mod n) entonces b ≡ a (mod n). Esto es, la relacion de congruencia essimetrica.

(C3) Si a ≡ b (mod n) y b ≡ c (mod n) entonces a ≡ c (mod n) . Es decir, la relacionde congruencia es transitiva. (En otras palabras, dos numeros congruentes a un tercero soncongruentes entre sı.)

(C4) Si a ≡ b (mod n) y c ≡ d (mod n) entonces a+ c ≡ b+ d (mod n).

(C5) Si a ≡ b (mod n) y c ≡ d (mod n) entonces ac ≡ bd (mod n).

60

Demostracion. (C1) Como a− a = 0 = n× 0, entonces n∣∣∣ a− a.

(C2) Tenemos que a− b = nk para algun entero k ası que b− a = n(−k).

(C3) Escribamos a− b = nk y b− c = nl con k y l enteros; entonces a− c = n(k + l).

(C4) Queremos probar que (a + c) − (b + d) es multiplo de n; pero (a + c) − (b + d) =(a− b) + (c− d) que es multiplo de n pues a− b y c− d lo son, por hipotesis.

(C5) Aquı queremos probar que ac − bd es multiplo de n. Para ver esto sumemos yrestemos bc: ac− bd = ac− bc + bc− bd = (a− b)c + b(c− d); este ultimo es multiplo de npues, por hipotesis, a− b y c− d lo son. ♦

Las propiedades que acabamos de probar parecen muy simples y sin gracia; sin embargoson basicas en el estudio de las congruencias. Empecemos por dar un ejemplo sencillo de suaplicacion.

2.94 Ejemplo. Encontrar el residuo modulo 5 de 374 − 49× 801 + 120.

Solucion. Para resolver el problema podrıamos hacer todas las operaciones pero serıa muylargo; en lugar de eso observemos que las propiedades (C4) y (C5) nos dicen que podemossustituir en una congruencia cualquier numero por otro al que este sea congruente, y hacerlas operaciones con el nuevo numero, a nuestra conveniencia; ademas la propiedad (C3) nosdice que despues de una cadena de congruencias el primer miembro es congruente al ultimo.Entonces modulo 5 tenemos: 37 ≡ 2, ası que, por (C1) y (C5), 372 ≡ 22 ≡ 4, 373 ≡ 4× 2 ≡ 8y 374 ≡ 8 × 2 ≡ 16 ≡ 1. Tambien tenemos que 49 ≡ 4, 801 ≡ 1 y 120 ≡ 0. Entonces, por(C4) y (C5) tenemos

374 − 49× 801 + 120 ≡ 1− 4× 1 + 0 ≡ −3 ≡ 2 (mod 5).

De todo lo anterior concluimos que el residuo es 2. ♦

En el ejemplo anterior aplicamos en varias ocasiones las propiedades de 2.93. Pudimosobservar que esas propiedades juntas nos permiten “hacer sustituciones” y operar con losnuevos numeros. Resumimos esto en el llamado Principio de Sustitucion.

2.95. Principio de Sustitucion. Para hacer operaciones (sumar y multiplicar) en unacongruencia, cualquier cantidad puede sustituirse por otra a la que esta sea congruente sinalterar la validez de la congruencia.

2.96 Nota. Hay que tomar en cuenta que los numeros que pueden sustituirse son lascantidades con las que se opera y no los sımbolos; por ejemplo, modulo 5 el residuo de 126 esel mismo que el de 26 (que es 4 porque 12 ≡ 2 (mod 5); sin embargo, el exponente 6 aquı essolo un sımbolo que representa que 12 debe multiplicarse consigo mismo 6 veces, ası que 6no puede sustituirse (se obtendrıa 4 ≡ 26 ≡ 21 ≡ 2 (mod 5), lo cual es claramente falso.

61

Aplicaremos el Principio de Sustitucion constantemente en lo sucesivo. Hagamos ahoraotro ejemplo.

2.97 Ejemplo. Probar que modulo 3 todo numero a es congruente con la suma de lascifras que lo forman. Deducir el criterio de divisibilidad entre 3: “Un entero a es divisiblepor 3 exactamente cuando la suma de las cifras de a lo es.”

Solucion. Antes de hacer la prueba ilustremos con un ejemplo lo que nos dice la primeraparte del enunciado. Si por ejemplo a = 48 104, entonces el resultado que queremos probarnos dira que a ≡ 2 (mod 3) pues 4 + 8 + 1 + 0 + 4 = 17 y, otra vez, por el mismo resultado,tendremos que 17 ≡ 1 + 7 ≡ 8 ≡ 2 (mod 3). Ahora sı, hagamos la prueba que se nospide. Consideremos la expansion decimal de a: a = amam−1 · · · a1a0; entonces a = am10m +am−110m−1 + · · ·+a110+a0. Usemos ahora que 10 ≡ 1 (mod 3) y el Principio de Sustitucion.Tenemos entonces que, modulo 3:

a ≡ am10m + am−110m−1 + · · ·+ a110 + a0 por (C1)

≡ am1m + am−11m−1 + · · ·+ a11 + a0 por (C4) y (C5)

≡ am + am−1 + · · ·+ a1 + a0 por (C1)

Ası tenemosa ≡ am + am−1 + · · ·+ a1 + a0 (mod 3).

Para probar el criterio de divisibilidad entre 3 basta observar que los numeros divisibles por3 son precisamente aquellos que son congruentes con 0 modulo 3; y que, por lo anterior, unnumero es congruente con 0 modulo 3 si, y solo si, la suma de sus cifras lo es. ♦

2.98 Ejercicio. Encontrar la ultima cifra de 2× 325 + 3× 87 × 5104 + 1235.

2.99 Ejercicio. Probar el criterio de divisibilidad por 11: “Un numero a es divisible por11 si y solo si la diferencia de la suma de las cifras en posicion par de a con la suma de lascifras en posicion impar de a es divisible por 11.”

2.100 Ejemplo. Se tienen 2003 tarjetas numeradas del 1 al 2003 y colocadas hacia abajoen orden en un monton (la tarjeta con el numero 1 aparece arriba). Sin mirar se van quitandotres tarjetas consecutivas cada vez hasta que quedan solo dos tarjetas. ¿Es posible que alfinal haya quedado la tarjeta con el numero 1002?

Solucion. Hay tres tipos de numeros considerando sus residuos al dividirlos entre 3. Del1 al 2003 hay la misma cantidad de numeros con residuo 1 y con residuo 2, pero hay unamenos con residuo 0. Al eliminar tres cartas consecutivas se elimina exactamente una decada residuo, ası que al final no puede quedar un multiplo de 3. Como 1002 sı es multiplo

62

de 3, no puede haber quedado al final. ♦

2.10. Conjuntos de residuos

Muchos problemas de numeros enteros pueden simplificarse considerablemente al trabajarcongruencias en lugar de igualdades, pues esto permite manejar conjuntos finitos en lugardel conjunto infinito de los numeros enteros.

En el siguiente ejemplo veremos como el trabajo infinito con numeros enteros se convierteen un trabajo finito al usar las congruencias.

2.101 Ejemplo. Probar que en cualquier coleccion de 7 o mas enteros siempre hay doscuya suma o diferencia es divisible entre 11.

Solucion. Supongamos que tenemos una coleccion en la que no hay dos numeros cuyasuma o diferencia sea multiplo de 11. Probaremos que la coleccion debera tener, en este caso,a lo mas 6 elementos, lo cual equivale a probar lo pedido. Analicemos los posibles residuosmodulo 11 de los numeros de la coleccion. Si hubiera dos residuos repetidos, entonces ladiferencia de los numeros correspondientes serıa multiplo de 11. De la misma manera, si unnumero de la coleccion tuviera residuo r y otro tuviera residuo 11− r, entonces la suma delos correspondientes numeros serıa divisible por 11. Entonces, dentro de la coleccion podrıahaber a lo mas un numero con residuo 0, uno con residuo 1 o 10, otro con residuo 2 o 9, otrocon residuo 3 u 8, otro con residuo 4 o 7 y otro con residuo 5 o 6. En total en la coleccionhabrıa a lo mas 6 numeros, como querıamos probar. ♦

2.11. Mas propiedades

Continuemos estudiando las propiedades basicas de las congruencias. Haremos primerounos ejercicios. Los dos primeros se utilizaran en la prueba de la proposicion 2.105.

2.102 Ejercicio. Demostrar que si d es un divisor del numero n, y a ≡ b (mod n),entonces a ≡ b (mod d), pero que el recıproco no es cierto: Para un divisor d de n es posible

63

que a ≡ b (mod d) pero que a 6≡ b (mod n).

2.103 Ejercicio. Sean n1 y n2 enteros positivos y sea m su mınimo comun multiplo.Probar que a ≡ b (mod n1) y a ≡ b (mod n2) implican que a ≡ b (mod m).

2.104 Ejercicio. Un vendedor de naranjas quiere saber cuantas naranjas tenıa ayer.Solo recuerda que eran mas de 100 pero menos de 150 y que, cada vez que hacıa montonesde 2 en 2 o de 3 en 3 o de 4 en 4 o de 5 en 5 o de 6 en 6, siempre le sobraba una naranja.Determinar cuantas naranjas tenıa el vendedor.

2.105 Proposicion. Sea n = pe11 p

e22 · · · perr la descomposicion de n en potencias de primos

distintos. Entonces la congruencia

a ≡ b (mod n)

es equivalente al sistema de congruencias

a ≡ b (mod pe11 )

a ≡ b (mod pe22 )

...

a ≡ b (mod perr ).

Demostracion. Tenemos que probar que si la congruencia se satisface para una pareja deenteros (a, b) entonces tambien esa pareja satisface el sistema, y recıprocamente, que si elsistema es valido para (a, b) entonces tambien lo es la congruencia.

Supongamos primero que a y b son enteros que satisfacen a ≡ b (mod n). Como cadauno de peii (para i = 1, 2, . . . , r) es divisor de n, entonces, por el ejercicio 2.102, tenemos quea ≡ b (mod peii ) para toda i, es decir, la pareja (a, b) satisface todas las congruencias delsistema.

Recıprocamente, supongamos ahora que a y b satisfacen todas las congruencias; entonces,por el ejercicio 2.103 y una induccion muy sencilla, como mcm[pe1

1 , pe22 , . . . , p

err ] = n, entonces

tambien es cierta la congruencia a ≡ b (mod n). ♦

2.106 Ejercicio. Probar que si en un triangulo rectangulo los lados a, b y c son numerosenteros, entonces el producto abc es multiplo de 30.

2.107 Ejemplo. Probar que la ecuacion x2− 6 = 45y no tiene solucion entera, es decir,que no es posible encontrar una pareja de enteros (x, y) que satisfagan la ecuacion.

Solucion. Notemos primero que lo que se pide es equivalente a probar que la congruenciax2 ≡ 7 (mod 45) no tiene solucion. Por la Propiedad de Sustitucion bastarıa examinar losposibles residuos modulo 45, es decir, elevar al cuadrado todos los enteros x del 0 al 44 y

64

ver que ninguno de ellos tiene residuo 7 modulo 45; sin embargo, por la proposicion anterior,se pueden simplificar considerablemente las cuentas considerando la descomposicion de 45en producto de potencias de primos distintos: 45 = 5× 9 y buscando resolver el sistema decongruencias

x2 ≡ 7 (mod 5)

x2 ≡ 7 (mod 9).

Analicemos la segunda congruencia: Los posibles residuos modulo 9 para x son 0, 1, 2, 3, 4,−4, −3, −2, −1. Los residuos modulo 9 de los cuadrados de estos son: 0, 1, 4, 0, −2, −2, 0,4, 1. Observamos que −3 (el residuo de 6 modulo 9) no esta en la lista de los cuadrados, porlo que queda probado lo que querıamos sin necesidad de examinar la otra congruencia. ♦

2.108 Ejemplo. Probar que no existe ningun entero que al elevarlo al cuadrado elresultado termine en 181 (es decir, que estas sean las tres cifras de la derecha en la notaciondecimal del numero elevado al cuadrado).

Solucion. Supongamos que x2 ≡ 181 (mod 1000). Entonces x2 ≡ 181 (mod 23) y x2 ≡181 (mod 5). Pero simplificando la primera congruencia tenemos x2 ≡ 5 (mod 8), lo cuales un absurdo pues los cuadrados de los residuos modulo 8 son: (±1)2 ≡ 1, (±2)2 ≡ 4,(±3)2 ≡ 1, (±4)2 ≡ 0 y 02 ≡ 0, ası que 5 no es residuo de ningun cuadrado modulo 8. ♦

En los ejemplos anteriores aprendimos que se pueden simplificar mucho las cuentas tra-bajando con sistemas de congruencias de modulo pequeno en lugar de una sola de modulogrande; ademas volvimos a ver como problemas aparentemente infinitos pueden reducirse aun analisis finito con la ayuda de las congruencias.

En lo que sigue estudiaremos algunas propiedades que nos ayudaran a resolver congruen-cias lineales.

2.109 Proposicion. Sea n un numero natural.

(a) Si a es un entero primo relativo con n (es decir, mcd(a, b) = 1) entonces existe unentero b tal que ab ≡ 1 (mod n). (En este caso decimos que a es invertible y que b es uninverso de a modulo n.)

(b) Recıprocamente, si a y b son enteros tales que ab ≡ 1 (mod n), entonces a y n notienen factores en comun.

Demostracion. (a) Sabemos que el maximo comun divisor de dos numeros se puede ex-presar como combinacion lineal de los mismos, ası que en este caso escribamos 1 = ar + ns.Utilizando el Principio de Sustitucion tenemos

1 ≡ ar + ns

≡ ar + 0s

≡ ar (mod n).

65

Cualquier entero b congruente con r modulo n nos servira (por (C5)).

(b) Si ab ≡ 1 (mod n) entonces n∣∣∣ ab− 1, por lo tanto existe t entero tal que nt = ab− 1.

Despejando obtenemos una combinacion lineal de a y n que da 1, ası que mcd(a, n) = 1. ♦

2.110 Ejercicio. Probar que a y n son primos entre sı, entonces ab ≡ ac (mod n) si, ysolo si, b ≡ c (mod n).

En particular, del ejercicio anterior concluimos que todas las soluciones de la congruenciaax ≡ 1 (mod n) son congruentes entre sı y podemos hablar de “el inverso” multiplicativode a modulo n (realmente estaremos hablando de la clase modulo n). Por esta razon, siab ≡ 1 (mod n), decimos que el inverso de a en Zn es b.

2.111 Ejercicio. Probar que si mcd(a, n) = d 6= 1, entonces es posible encontrar k 6≡0 (mod n) de tal manera que ak ≡ 0 (mod n). (Por ejemplo, si n = 12 y a = 9, para k = 4se cumple lo pedido.)

2.112 Ejercicio. Probar que si mcd(a, n) = d 6= 1, entonces es posible encontrar k y lenteros no congruentes entre sı tales que ak ≡ al (mod n). Ilustrar con n = 6.

2.113 Nota. En la practica, para encontrar el inverso multiplicativo de un entero a quecumpla mcd(a, n) = 1, no necesitamos escribir 1 como combinacion lineal de a y n; bastacon hacerlo “al tanteo”. Por ejemplo, si a = 5 y n = 12, para encontrar b, el inverso de amodulo n, sabemos que b tampoco tendra factores en comun con n y que lo podemos tomarentre los enteros del 0 al n− 1; ası que las posibilidades en este caso son b = 1, b = 5, b = 7,b = 11; multiplicamos estas por 5 para ver cual nos da 1 modulo 12:

1× 5 ≡ 5 (mod 12)

5× 5 ≡ 1 (mod 12)

7× 5 ≡ 11 (mod 12)

11× 5 ≡ 7 (mod 12).

Entonces b = 5.

Nuestras cuentas pueden simplificarse aun mas trabajando con residuos negativos. Porejemplo, modulo 14 un conjunto de representantes de las clases es

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,

pero tambien lo son los negativos de estos; tenemos −1 ≡ 13 (mod 14), −2 ≡ 12 (mod 14),−3 ≡ 11 (mod 14), etc. Supongamos entonces que queremos encontrar el inverso de 9 modulo14. Como 9× 3 ≡ 27 ≡ −1 (mod 14), entonces 9× (−3) ≡ 1 (mod 14); ası que el inverso de9 en Z14 es −3 = 11.

66

2.114 Ejercicio. Encontrar el inverso de 3 modulo 17.

2.115 Ejercicio. Encontrar el inverso de 14 modulo 15.

2.116 Ejercicio. Aparear cada uno de los elementos invertibles de Z20 con sus inversos.

En el conjunto de los enteros los unicos elementos que tienen inverso multiplicativo son 1y −1; sin embargo fuera del conjunto de los enteros (en el conjunto de los numeros racionaleso fraccionarios), todos los enteros no 0 tienen inverso y, por esta razon, es posible cancelarlosmultiplicativamente de las ecuaciones (por ejemplo 2x = 2y implica x = y). Sin embargo soloes posible “dividir” entre los numeros que son primos relativos con el modulo. Por el ejercicio2.111, si mcd(a, n) 6= 1, entonces podemos encontrar k y l enteros no congruentes entresı de tal manera que ak ≡ al (mod n), ası que a no podra cancelarse en esta congruencia.Sin embargo hay casos en que un entero sı puede, hasta cierto punto, cancelarse en unacongruencia aunque tenga factores en comun con n; sin embargo en estos casos el modulotambien debera modificarse, como veremos en la siguiente proposicion.

2.117 Proposicion. Sea d = mcd(a, n) y consideremos la congruencia

ax ≡ c (mod n).

(a) Si d∣∣∣ c y escribimos c = dc′, a = da′ y n = dn′, entonces la congruencia es equivalente a

a′x ≡ c′ (mod n′). En particular, la congruencia es soluble, es decir, tiene solucion.

(b) Si d - c la congruencia no tiene solucion.

Demostracion. (a) Tenemos que ax − c = d(a′x − c′), ası que n es factor de ax − c si ysolo si n′ es factor de a′x − c′, y de aquı deducimos que la congruencia ax ≡ c (mod n) esequivalente a a′x ≡ c′ (mod n′). En esta ultima el coeficiente de x (que es a′) sı es primorelativo con el modulo (que es n′), ası que la congruencia tiene solucion.

(b) Supongamos que la congruencia sı tiene solucion y sea x1 una solucion. Entonces

n∣∣∣ ax1 − c, por lo que existe un entero t tal que ax1 − c = nt, y de aquı ya es claro que d

debe ser tambien divisor de c, contradiciendo la hipotesis; por tanto la congruencia no tienesolucion. ♦

2.118 Ejemplo. Probar que 2n+ 3m es divisible entre 17 si y solo si 9n+ 5m lo es.

Solucion. Recordemos que si una congruencia se multiplica por una constante que no tengafactores en comun con el modulo, entonces la nueva congruencia es equivalente a la original.Multiplicando por 9 (que es inverso multiplicativo de 2 modulo 17) la congruencia 2n+3m ≡0 (mod 17) obtenemos n+ 27m ≡ 0 (mod 17), o sea (simplificando) n+ 10m ≡ 0 (mod 17).Multiplicando por 9 esta ultima, tenemos 9n + 90m ≡ 0 (mod 17) que, simplificando, se

67

convierte en 9n+ 5m ≡ 0 (mod 17). ♦

2.12. Solucion de congruencias lineales

Ahora ya podemos resolver congruencias lineales y sistemas de congruencias lineales.Trabajaremos algunos ejemplos.

2.119 Ejemplo. Encontrar todos los enteros x que satisfagan 4x+20 ≡ 27x−1 (mod 5).

Solucion. Empecemos por simplificar: 4x ≡ 2x − 1 (mod 5) (pues 20 ≡ 0 (mod 5) y27 ≡ 2 (mod 5)). Entonces, por (C4), 2x ≡ −1 (mod 5). Ahora encontramos el inverso de 2modulo 5: como 3 × 2 = 6 ≡ 1 (mod 5), entonces 3 es ese inverso. Por (C5), al multiplicarla congruencia 2x ≡ −1 (mod 5) por 3 obtenemos x ≡ −3 (mod 5) o x ≡ 2 (mod 5). Losenteros solucion de la congruencia son los que forman 2 = {. . . ,−8,−3, 2, 7, 12, 17, . . .} ♦

2.120 Ejemplo. Encontrar todos los enteros x que satisfagan la congruencia 3x + 1 ≡15x− 7 (mod 20).

Solucion. Tenemos −12x ≡ −8 (mod 20). Como mcd(12, 20) = 4, dividimos todo entre4 (incluso el modulo): −3x ≡ −2 (mod 5). Ahora multiplicamos por −2 para obtener x ≡4 (mod 5). Los enteros solucion de la congruencia son los que forman la clase de 4 modulo 5es decir, . . . ,−6,−1, 4, 9, 14, . . .. ♦

2.121 Ejemplo. Encontrar todos los enteros x que satisfagan la congruencia 3x + 1 ≡15x− 4 (mod 20).

Solucion. Como en el ejemplo anterior, −12x ≡ −5 (mod 20). Sin embargo 4∣∣∣ −5, ası que

no hay solucion. ♦

2.122 Ejercicio. Encontrar todos los enteros x que satisfagan la congruencia 6x+ 6 ≡1− 4x (mod 15).

Para resolver sistemas de congruencias simplemente iremos resolviendo y sustituyendo,como en el ejemplo que sigue.

68

2.123 Ejemplo. Resolver el sistema de congruencias

2x ≡ 1 (mod 7) (∗)x ≡ 1 (mod 5) (∗ ∗)

2x− 3 ≡ 29− 2x (mod 6) (∗ ∗ ∗)x+ 3 ≡ 5x− 3 (mod 2). (∗ ∗ ∗ ∗)

Solucion. Resolvemos primero cada una por separado; despues de hacer las cuentas ob-tendremos

x ≡ 4 (mod 7) (∗)x ≡ 1 (mod 5) (∗ ∗)x ≡ 2 (mod 3) (∗ ∗ ∗)0 ≡ 0 (mod 2). (∗ ∗ ∗ ∗)

Notese que la ultima congruencia se satisface siempre (no importa que valor se le de a x).Esto quiere decir que la podemos eliminar sin alterar la solucion del sistema.

De la primera congruencia tenemos que x = 4 + 7u, para cualquier valor entero deu. Trataremos de encontrar para que valores de u las otras dos congruencias tambien sesatisfacen. Sustituyendo en (∗∗) tenemos 4+7u ≡ 1 (mod 5). Ahora resolvamos con respectoa u:

2u ≡ −3 (mod 5)

u ≡ −9 (mod 5)

u ≡ 1 (mod 5),

Tenemos entonces que las soluciones comunes a las dos primeras congruencias son de la formax = 4 + 7u, donde u es de la forma 1 + 5v, esto es, x = 4 + 7(1 + 5v) = 11 + 35v. Ahoraqueremos ver para que valores de v tambien se satisface la tercera. Sustituimos en (∗ ∗ ∗) yresolvemos para v:

11 + 35v ≡ 2 (mod 3)

35v ≡ −9 (mod 3)

2v ≡ 0 (mod 3)

v ≡ 0 (mod 3).

Hemos obtenido entonces que v = 3w, w entero. Sustituimos en x: x = 11 + 35(3w) =11 + 105w para cualquier entero w. Ası que el conjunto solucion del sistema es la clase de 11modulo 105. ♦

Es claro que habra sistemas de congruencias que no tengan solucion, aun cuando cadauna de las congruencias del sistema sı sea soluble por separado. Un ejemplo muy simple de

69

esto es el sistema

x ≡ 1 (mod 2)

x ≡ 0 (mod 2).

Un ejemplo que no tiene solucion pero en el que esto no es tan obvio es:

x ≡ 1 (mod 2)

x ≡ 4 (mod 6).

2.124 Ejercicio. Probar el criterio de divisibilidad entre 4: “Un numero a es divisiblepor 4 si y solo si el numero formado por sus ultimas dos cifras es divisible entre 4.”

2.125 Ejercicio. Recordemos que la sucesion de Fibonacci f1,f2,f3,. . . se define comosigue: f1 = 1,f2 = 1 y, para n ≥ 3, fn = fn−1 + fn−2. Probar que 9 divide a una infinidad determinos de la sucesion de Fibonacci.

2.126 Ejercicio. Usar congruencias para mostrar que si k es entero, entonces a = 22k+7y b = 33k + 5 son primos relativos. (Sugerencia: Suponer que hay un primo p que divide aambos y trabajar simultaneamente las congruencias respectivas.)

2.127 Ejercicio. Probar que para todo natural n, n5 − n es divisible entre 30.

2.128 Ejercicio. Aparear cada uno de los elementos invertibles modulo 31 con sus in-versos.

2.129 Ejercicio. Probar que la ecuacion x2 + 1 = 187y no tiene solucion entera.

2.130 Ejercicio. Encontrar todos los enteros x que satisfagan la congruencia 14x− 2 ≡x+ 3 (mod 7).

2.131 Ejercicio. Encontrar todos los enteros x que satisfagan la congruencia 12x+ 7 ≡4x− 6 (mod 21).

2.132 Ejercicio. Encontrar todos los enteros x que satisfagan la congruencia 5x3−2x2+1 ≡ 0 (mod 6).

2.133 Ejercicio. Resolver el sistema de congruencias

2x ≡ 5 (mod 9)

x− 7 ≡ 9 (mod 11)

3x ≡ 0 (mod 6).

70

2.134 Ejercicio. Resolver el sistema de congruencias

2x− 1 ≡ 1 (mod 4)

4x ≡ 4− 3x (mod 11)

x ≡ 1 (mod 2)

7x ≡ −3 (mod 5).

2.135 Ejercicio. Probar que no es posible encontrar numeros enteros a y b de tal maneraque 12a+ 5b2 = 7.

2.136 Ejercicio. Probar que si a, b, c y n son enteros cualesquiera con n > 3, entonceshay un entero k tal que ninguno de los enteros k + a, k + b, k + c es divisible por n.

2.137 Ejercicio. Sea n la suma de todas las cifras del numero 55555555; sea m la sumade todas las cifras de n y sea r la suma de todas las cifras de m. Encontrar r.

2.138 Ejercicio. Encontrar todos los naturales k para los cuales 20 divide a

1 + 7 + 72 + · · ·+ 7k.

71

3. Conjuntos, relaciones y funciones

3.1. Conjuntos

En las secciones pasadas hemos tenido oportunidad de trabajar un poco con el lenguajede teorıa de conjuntos, sin hace mucho enfasis en el. En esta seccion estructuraremos unpoco mas el estudio de los conjuntos como tal.

Los conjuntos estan formados por elementos y esos elementos determinan a los con-juntos, es decir, dos conjuntos son iguales si, y solo si, tienen los mismos elementos.

Normalmente usaremos mayusculas para denotar a los conjuntos y minusculas para loselementos. Si a es un elemento del conjunto A escribimos a ∈ A; si a no pertenece a aescribimos a /∈ A.

Hay varias maneras de describir un conjunto; una de ellas es poniendo sus elementosentre llaves, por ejemplo, el conjunto A cuyos elementos son 1, 7 y 22 se representa porA = {1, 7, 22} y ası 1 ∈ A, 7 ∈ A y 22 ∈ A pero 4 /∈ A. El orden en que se escribenlos elementos dentro de las llaves no es importante ni tampoco si algun elemento aparecerepetido; por ejemplo, A = {1, 7, 22} = {7, 1, 22} = {22, 22, 1, 22, 7, 7}; en este caso elconjunto tiene 3 elementos, independientemente de cuantos se hayan enlistado. Otra formacomun de especificar un conjunto es mediante las propiedades que satisfacen sus elementos;por ejemplo, el conjunto de los numeros enteros del 1 al 5 puede escribirse tambien como

{x|x es entero y 1 ≤ x ≤ 5} = {1, 2, 3, 4, 5}.

La lınea vertical | se lee “tales que” o “con la propiedad” y puede sustituirse por : o por ;(para no confundirla con algun otro sımbolo matematico que se este usando en el texto encuestion).

El conjunto que no tiene elementos se llama conjunto vacıo y se denota por ∅. Ası ∅ ={}. Es un error decir que el conjunto vacıo es {∅} pues este ultimo tiene un elemento, asaber, el conjunto vacıo: ∅ ∈ {∅}, mientras que el conjunto vacıo tiene 0 elementos.

Algunos conjuntos importantes en matematicas son:

N = {1, 2, 3, . . .} es el conjunto de los numeros naturales.

Z = {. . . ,−2,−1, 0, 1, 2, 3, . . .} es el conjunto de los numeros enteros.

Q = {ab

: a, b ∈ Z, b 6= 0} es el conjunto de los numeros racionales. Aquı debe conside-rarse que a

b= c

dsi, y solo si, ad = bc.

R = {A.a1a2... : A ∈ Z, an ∈ {0, 1, 2, 3, . . . , 9} para n ∈ N} es el conjunto de los numerosreales. Aquı tambien debe considerarse que hay repeticiones cuando hay “colas”de 0′s o 9′s(por ejemplo 23.04999 . . . = 23.05000 . . .).

72

Si A y B son conjuntos tales que cada elemento de A tambien es elemento de B entoncesdecimos que A es subconjunto de B; escribimos A ⊂ B (algunos libros usan la notacionA ⊆ B) y leemos A “esta contenido en” B. (Esto mismo tambien puede escribirse comoB ⊃ A y leemos “B contiene a” A.) Por ejemplo

(∗) N ⊂ Z ⊂ Q ⊂ R.

Escribimos A * B si A no es subconjunto de B, es decir que algun elemento de A nopertenece a B (o, en otras palabras, que existe a ∈ A tal que a /∈ B). Si A ⊂ B pero sondistintos y queremos enfatizar la desigualdad, entonces escribimos A B y decimos que Aes subconjunto propio de B. El sımbolo ⊂ se llama contencion o inclusion. Ası tenemosque las inclusiones de ∗ son todas propias. En efecto: N Z pues −1 ∈ Z pero −1 /∈ N;Z Q ya que 1

2∈ Q pero 1

2/∈ Z; Q R ya que

√2 ∈ R pero

√2 /∈ Q.

Muchas veces es conveniente tener una visualizacion geometrica de la situacion de con-juntos respecto a otros. Para ellos utilizamos los diagramas de Venn. Por ejemplo, eldiagrama de la izquierda representa que A ⊂ B y el de la derecha que A * B:

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

A AB B

3.1 Proposicion. La relacion de inclusion entre conjuntos satisface:

(a) Para cualquier conjunto A se tiene que ∅ ⊂ A.

(b) Para cualquier conjunto A se tiene que A ⊂ A. (esta es la propiedad reflexiva dela inclusion.)

(c) Si A, B y C son conjuntos que cumplen A ⊂ B y B ⊂ C entonces A ⊂ C. (esta es lapropiedad transitiva de la inclusion.)

Si A y B son conjuntos tales que A ⊂ B y B ⊂ A entonces A = B. (esta se llamapropiedad antisimetrica de la inclusion.)

El conjunto potencia de un conjunto A es

P(A) = {B : B ⊂ A},

es decir, los elementos de P(A) son los subconjuntos de A; por ejemplo, si A = {1, 2, 3}entonces P(A) consta de 23 = 8 elementos:

P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A}.

Ası, por ejemplo {1} ∈ P(A) pero 1 /∈ P(A) y {1} * P(A).

73

3.2 Ejercicio. Decir cuales de las siguientes afirmaciones son verdaderas y cuales sonfalsas:

(a) ∅ ∈ {1, 2}.(b) {1} ⊂ {1, 2}.(c) ∅ P(∅).(d) {1, 5} ∈ N.

(e) {1, 5} ∈ P(N).

(f) {∅} ∈ P(N).

3.2. Operaciones con conjuntos

Si todos los conjuntos que se trabajan en determinado momento son subconjuntos deotro conjunto X, entonces decimos que X es conjunto universal. Por ejemplo, al estudiarel tema de divisibilidad puede considerarse al conjunto Z como el conjunto universal; engeometrıa plana el conjunto universal es el plano.

Dado un conjunto A, el conjunto de los elementos que no pertenecen a A (pero quesı pertenecen al conjunto universal) se llama complemento de A y lo denotamos por Ac .Entonces

Ac = {x ∈ X : x /∈ A}.

El diagrama de Venn correspondiente es:

....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

AAc

X

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

3.3 Proposicion. Sea X el conjunto universal. Entonces

(a) ∅ c = X y Xc = ∅.(b) Si A es un conjunto entonces (Ac)c = A. ♦

74

Si A y B son conjuntos, su union es el conjunto

A ∪B = {x : x ∈ A o x ∈ B}.

Debe entenderse que la conjuncion “o” en Matematicas significa que la proposicion en laque se encuentra es verdadera si cualquiera de las dos proposiciones que une lo es. Ası, eneste caso la union de dos conjuntos A y B se forma agregando a los elementos de A loselementos de B. Por ejemplo, si A = {1, 2, 3} y B = {3, 4, 5} entonces la union es el conjuntoA ∪B = {1, 2, 3, 4, 5}. El diagrama de Venn para la union es el siguiente:

....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

AB

Si A y B son conjuntos, su interseccion es el conjunto

A ∩B = {x : x ∈ A y x ∈ B}.

Ahora debe entenderse que la conjuncion “y” en Matematicas significa que la proposicionen la que se encuentra es verdadera si ambas proposiciones que une lo son simultaneamente.Ası, en este caso la interseccion de dos conjuntos A y B se forma tomando los elementos encomun de A y B. Por ejemplo, si A = {1, 2, 3} y B = {3, 4, 5} entonces la interseccion es elconjunto A ∩B = {3}. El diagrama de Venn para la interseccion es el siguiente:

....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

AB

Cuando A y B no tienen elementos en comun, es decir A ∩ B = ∅, decimos que A y Bson ajenos. La situacion en el diagrama de Venn es:

....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

AB

75

Si A y B son conjuntos, la diferencia A menos B es el conjunto

A \B = {x : x ∈ A y x /∈ B}.

Por ejemplo, si A = {1, 2, 3} y B = {3, 4, 5} entonces A \B = {1, 2}. El diagrama de Venncorrespondiente es:

....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

AB

3.4 Proposicion. Sean A, B y C conjuntos dentro de un conjunto universal X. Entonces

(a) A ∩B ⊂ A ⊂ A ∪B (y, similarmente, A ∩B ⊂ B ⊂ A ∪B).

(b) A ∪ A = A y A ∪ ∅ = A.

(c) A ∩ A = A y A ∩ ∅ = ∅.(d) A = A ∩B si, y solo si, A ⊂ B.

(e) (A ∪B) ∪ C = A ∪ (B ∪ C). En particular, podemos omitir los parentesis sin peligrode confusion. esta es la propiedad asociativa de la union.

(f) (A ∩B) ∩ C = A ∩ (B ∩ C). En particular, podemos omitir los parentesis sin peligrode confusion. esta es la propiedad asociativa de la interseccion.

(g) A ∪B = B ∪ A. esta es la propiedad conmutativa de la union.

(h) A ∩B = B ∩ A. esta es la propiedad conmutativa de la interseccion.

(i) A ∩ Ac = ∅ y A ∪ Ac = X.

(j) A \B = A ∩Bc.

Demostracion. Todas son inmediatas de la definicion. ♦

3.5 Proposicion. Sean A, B y C conjuntos. Entonces

(a) Distributividad de la interseccion sobre la union:

A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C).

(b) Distributividad de la union sobre la interseccion:

A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C).

76

Demostracion. (a) Se deduce de las siguientes equivalencias:

x ∈ A ∩ (B ∪ C)⇔ x ∈ A y x ∈ B ∪ C⇔ x ∈ A y (x ∈ B o x ∈ C)⇔ (x ∈ A y x ∈ B) o (x ∈ A y x ∈ C)

⇔ x ∈ A ∩B o x ∈ A ∩ C ⇔ x ∈ (A ∩B) ∪ (A ∩ C).

El diagrama de Venn correspondiente es

..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

............

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

..

..

..

..

..

.

A

B

C

(b) Se deja como ejercicio. ♦

3.6 Proposicion. Leyes de De Morgan. Sean A y B conjuntos dentro de un conjuntouniversal X. Entonces

(a) (A ∪B)c = Ac ∩Bc.

(b) (A ∩B)c = Ac ∪Bc.

Demostracion. (a) Se deduce de las siguientes equivalencias:

x ∈ (A ∪B)c ⇔ x /∈ A ∪B ⇔ x /∈ A y x /∈ B⇔ x ∈ Ac y x ∈ Bc ⇔ x ∈ Ac ∩Bc.

El diagrama de Venn en este caso es:

............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

.

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

A B

X

(b) Se deja como ejercicio. ♦

77

3.7 Corolario. Sean A, B y C conjuntos dentro de un conjunto universal X. Entonces

(a) (A \ (B ∪ C)) = (A \B) ∩ (A \ C).

(b) (A \ (B ∩ C)) = (A \B) ∪ (A \ C). ♦

3.8 Ejercicio. Decir si las siguientes propiedades son verdaderas o falsas para A, B yC conjuntos en un conjunto universal X. (Si son verdaderas, hacer una demostracion; si sonfalsas, dar un ejemplo.)

(a) Si A \B = ∅ entonces A = B.

(b) (A ∪B) ∩ C = A ∪ (B ∩ C).

(c) (A \B) \ C = A \ (B \ C).

(d) Si A tiene m elementos y B tiene n elementos entonces A∪B tiene m+n elementos.

3.9 Ejercicio. Probar la distributividad de la union sobre la interseccion y hacer eldiagrama de Venn correspondiente.

3.10 Ejercicio. Probar la ley de De Morgan no probada en las notas y hacer el diagramade Venn correspondiente.

Si A y B son dos conjuntos definimos su producto cartesiano como sigue:

A×B = {(a, b) : a ∈ A y b ∈ B}.

Si A = B, en lugar de A× B escribimos A2; ası, por ejemplo, R2 es el conjunto de parejasordenadas de numeros reales, usualmente representadas geometricamente en el plano. De lamisma manera podemos definir An para n natural. Notemos que aquı, a diferencia de enlos conjuntos, es importante si hay repeticion y el orden de los elementos, por ejemplo, enconjuntos tenemos que {1, 2} = {2, 1} = {1, 1, 2} = {2, 2, 1} pero (1, 1, 2), (1, 2, 1) y (2, 2, 1)son todos elementos distintos de R3.

3.11 Ejemplo. (a) Si A = {1, 2} y B = {2, 3, 4}, entonces

A×B = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)}.

(b) Si A = {x ∈ R : x < 3} y B = {x ∈ R : 1 ≤ x ≤ 2}, entonces A × B es el conjunto delplano que mostramos a continuacion:

...........................................................................................................................................................................................................................................................................................................................................................................................................................................

...........................................................................................................................................................................................................................................................................................................................................................................................................................................

.............................

.......

.......

.

.......

.......

.

.......

.......

.

3

1

2

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ ..............

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

...................

..............

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

78

3.12 Proposicion. Sean A, B conjuntos dentro de un conjunto universal X, y sea C unconjunto dentro de un conjunto universal Y . Entonces

(a) A× ∅ = ∅.(b) (A ∪B)× C = (A× C) ∪ (B × C).

(c) (A ∩B)× C = (A× C) ∩ (B × C).

(d) Ac × Cc 6= (A× C)c.

Demostracion. Se deducen directamente de la definicion. ♦

3.13 Ejercicio. Decir si las siguientes propiedades son verdaderas o falsas para A yB conjuntos dentro de un conjunto universal X, y C un conjunto dentro de un conjuntouniversal Y . (Si son verdaderas, hacer una demostracion; si son falsas, dar un ejemplo.)

(a) Ac × Cc = (A× Cc) ∩ (Ac × C).

(b) (A× C)c = (X × Cc) ∪ (Ac × Y ).

3.14 Ejercicio. Para a = (a1, a2) ∈ R2 y r > 0, r real definamos

Br(a) = {(x, y) ∈ R2 :√

(x− a1)2 + (x− a2)2 < r}.

Probar que si s < r y a ∈ R2 entonces Bs(a) Br(a) y hacer un dibujo de esto.

3.3. Relaciones

Hemos tenido ya oportunidad de trabajar ya innumerables ejemplos de relaciones, porejemplo, dentro del conjunto de las personas podemos hablar de la relacion ”ser hermanode”, o la de que una ciudad pertenezca a determinado paıs, o la relacion de divisibilidad entrelos enteros, o la relacion de que un numero sea menor que otro, etc. Para efectos de podertrabajar correctamente en matematicas, se formaliza la definicion de relacion como sigue:Una relacion de un conjunto A a un conjunto B es un subconjunto R del productocartesiano. Si (a, b) ∈ R decimos que a esta relacionado con b y escribimos aRb.

La definicion que acabamos de dar resulta poco natural; sin embargo, para tener bienestructuradas las Matematicas deben ponerse todos los conceptos en un lenguaje axiomatico,basado en la Teorıa de Conjuntos. Desde luego, una vez que ya queda bien establecido el

79

concepto, uno lo usa tranquilamente de manera mas ligera (no hacerlo le impedirıa avanzary harıa la teorıa muy tediosa). En los ejemplos que daremos a continuacion empezaremosestableciendo como algunas relaciones que nos son familiares se pueden ver como subconjun-tos de un producto cartesiano; posteriormente definiremos algunas relaciones importantes enMatematicas de manera mas informal.

3.15 Ejemplo. (a) En la relacion “ser hermano de”, los conjuntos A y B son conjuntosde personas y (a, b) ∈ R⇔ a es hermano de b.

(b) Otra relacion puede definirse entre A, el conjunto de los paıses y B, el conjunto delas ciudades, diciendo que (a, b) ∈ R si, y solo si, b es la capital de a.

(c) Si A = B = N la relacion “ser multiplo de” tiene por elementos (a, b) con a = xb paraalguna x ∈ N.

(d) En el conjunto potencia de N, A = P(N), tenemos la relacion de contencion o inclusion,es decir, decimos que X esta relacionado con Y si, y solo si, X ⊂ Y .

(e) En cualquier conjunto A se considera la relacion de igualdad.

(f) Para A el conjunto de los triangulos en el plano, una relacion importante es la relacionde semejanza.

(g) Dado un natural n, la congruencia modulo n es una relacion en A = Z.

(h) En R es importante la relacion “≤”.

En lo que sigue tomaremos los conjuntos A y B como uno mismo.

Una relacion R en un conjunto A es:

Reflexiva si aRa para todo a ∈ A. En 3.15 son reflexivas las relaciones definidas en (c),(d), (e), (f), (g) y (h).

Simetrica si aRb implica bRa. En 3.15 son simetricas las relaciones definidas en (a), (e),(f) y (g).

Transitiva si aRb y bRc implica aRc. En 3.15 son transitivas las relaciones definidas en(a), (c), (d), (e), (f), (g) y (h).

Antisimetrica si aRb y bRa implica a = b. En 3.15 son antisimetricas las relacionesdefinidas en (c), (d), (e) y (h).

Orden parcial si es reflexiva, transitiva y antisimetrica. En 3.15 son orden parcial (c),(d), (e) y (h).

Relacion de equivalencia si es reflexiva, transitiva y simetrica. En 3.15 son relacionde equivalencia (e), (f) y (g).

La definicion de antisimetrıa es un poco mas difıcil de entender. Notemos, por ejemplo,que la relacion definida en (c) no es antisimetrica si se define en Z en lugar de N pues

80

5R(−5) y (−5)R5 pero 5 6= −5. Tambien notemos que la relacion “ser padre de” definidaen el conjunto de las personas es antisimetrica por vacuidad, puesto que el conjunto deelementos que satisfacen la hipotesis (aRb y bRa) es vacıo.

Las relaciones de equivalencia y los ordenes parciales son muy importantes en Matemati-cas. A continuacion profundizamos un poco sobre estos conceptos.

De costumbre, cuando se tiene una relacion de equivalencia R, en lugar de escribir aRbse pone a ∼ b y se dice que a es equivalente a b.

Si ∼ es una relacion de equivalencia en un conjunto A, para a ∈ A definamos el subcon-junto de A, llamado clase de a, por

a = {x ∈ A : x ∼ a},

es decir a consta de todos los elementos equivalentes a a. Notemos que a ∈ a, que si b ∈ aentonces tambien a ∈ b, y que si a ∈ b y b ∈ c entonces a ∈ c. Esto nos da una particiondel conjunto A en sus clases, esto es, A es la union de las clases y dos clases distintas nose intersectan (es decir, su interseccion es el conjunto vacıo). Por ejemplo, en la relacion decongruencia modulo 6 dentro de A = Z, el conjunto Z queda partido en las 6 clases ajenas: 0,1, 2, 3, 4 y 5 y, por ejemplo, 2 = {. . . ,−10,−4, 2, 8, 14, . . .}. Recıprocamente, si un conjuntoA esta partido como la union de subconjuntos (ajenos dos a dos), entonces esta particiondetermina una relacion de equivalencia en A definiendo que dos elementos son equivalentessi, y solo si, pertenecen al mismo subconjunto de la particion.

De las observaciones hechas aquı arriba tenemos que es esencialmente lo mismo el hablarde relaciones de equivalencia que de particiones.

3.16 Ejercicio. En cada una de las relaciones de equivalencia definidas en 3.15 deter-minar cuales son las clases.

Estudiemos ahora las caracterısticas de los ordenes parciales. El ejemplo clasico de ordenparcial es el de ≤ en R o en algun subconjunto de R. Es costumbre denotar cualquier ordenparcial por este mismo sımbolo. Como muchos de nuestros ejemplos son con numeros y nocoincide la nocion de≤ con la del orden parcial que definimos, para no confundir denotaremospor � un orden parcial generico.

Muchas veces conviene hacer un esquema (llamado esquema de Hasse) para representarun orden parcial dentro de un conjunto uniendo los elementos que son comparables de maneraque los mas grandes queden arriba. Por ejemplo, en el siguiente esquema representamos unorden parcial en el conjunto A = {a, b, c, d, e, f, g, h, i, j}.

81

3.17.

...............................................................................................................................................................................................................................................................................................................................................................................

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

..........................................................................................................................................................

............................

............................

............................

....................................................................................................................................................

..................

..................

..................

..................

..................

..................

..................

..................

.................................................................................................................................................

...................................................................................................................................................................................................................................................................................................................................

a

b c

d

e

f g

h

i

j

•

•

•

•

•

•

•

•

•

•

Aquı, por ejemplo, se entiende que a � c porque estan unidos por una lınea y c quedaarriba de a; tambien, sin necesidad de poner mas lıneas en el dibujo, se sobreentiende latransitividad y la reflexividad; por ejemplo, como c � d entonces a � d y c � c.

Sea � un orden parcial en un conjunto A. Decimos que: � es orden total (o cadena)si dados a, b ∈ A se tiene forzosamente que a � b o b � a. Observemos que (c), (d) y (e) en3.15 no son ordenes totales.

Un elemento a0 ∈ A es minimal si (a � a0 ⇒ a = a0).

Un elemento es a0 ∈ A es menor si para todo a ∈ A se tiene que a0 � a.

Analogamente, dado un orden parcial se define elemento maximal y elemento mayor.

Las definiciones de minimal y de menor se parecen pero no son la misma. Veremos algunosejemplos para que esto quede claro.

3.18 Ejemplo. (a) En 3.17 resulta que a es elemento menor y minimal, y que i, j y gson todos maximales (y no hay elemento mayor).

Estudiemos que pasa en los ejemplos de 3.15.

En (c) 1 es elemento menor y minimal, pero si en lugar de N tomamos como conjuntobase a N\{1}, entonces ya no hay ningun elemento menor y todos los primos son minimales.En ninguno de los dos casos hay maximal ni mayor, pero si la misma relacion la tomamosen N ∪ {0} entonces 0 es elemento mayor y maximal.

En (d) ∅ es elemento menor y minimal y N es mayor y maximal. La misma relaciondefinida en P \ {∅} no tiene elemento menor y cada subconjunto de N que conste de un solo

82

elemento es elemento minimal de la relacion.

En (e) todos los elementos son minimales y maximales (y no hay menor ni mayor cuandoel conjunto tiene mas de un elemento).

En (h) no hay elementos minimales, ni menor, ni maximales, ni mayor. Si se cambia elconjunto base por A = (0, 1] entonces no hay elementos minimales ni menor pero 1 es mayory maximal.

3.19 Observacion. (a) En caso de existir un elemento menor este es unico, tambien esel unico minimal (y lo mismo para elemento mayor).

(b) Los elementos minimales pueden no existir y, en caso de que existan, puede habermas de uno (y lo analogo para mayor y maximal).

(c) Si el orden es total, entonces los conceptos de minimal y menor son iguales (y loanalogo para mayor y maximal).

Enunciamos a continuacion una propiedad muy importante que tiene N como conjuntoordenado y que no la comparte con Z (ni con Q o R).

3.20. Principio del Buen Orden. Todo conjunto no vacıo de N tiene un elementomenor (tambien llamado primer elemento).

A continuacion vamos a profundizar un poco sobre este principio. Para ello empecemospor observar que ya hemos hecho demostraciones por induccion cuando trabajamos connumeros naturales (o con subconjuntos de N o, incluso, con conjuntos que se parecen a Nen el sentido del orden). Enunciaremos aquı el principio bajo el cual las demostraciones porinduccion son correctas (segun la Logica Matematica).

3.21. Principio de Induccion. Si un subconjunto S de N contiene al 1 y cada vez quecontiene a un natural n tambien contiene a su sucesor n+ 1, entonces S = N.

Veremos que los dos principios son equivalentes, es decir, si se supone uno de ellos comocierto, el otro resulta ser una proposicion. Como habıamos dicho anteriormente, en Logica sefundamentan las Matematicas y se dan definiciones o axiomas de los conceptos; los axiomasdeben ser independientes unos de otros (ninguno debe poder probarse suponiendo otro ytampoco debe haber contradicciones entre ellos). En el caso que estamos tratando ahora,cualquiera de los dos principios puede tomarse como axioma dentro de la definicion de N (yel otro es una proposicion).

3.22 Proposicion. El Principio de Induccion y el Principio del Buen Orden son equi-valentes.

Demostracion. Empecemos probando que el Principio de Induccion implica el del BuenOrden. Sea ∅ 6= A ⊂ N y supongamos que A no tiene primer elemento; apliquemos el

83

Principio de Induccion a S = N \ A; como 1 no puede estar en A (pues serıa su primerelemento) entonces 1 ∈ S; y si n ∈ S, entonces, como A no tiene primer elemento, entonceslos numeros 1, 2, . . . , n no pertenecen a A (pues el mas chico de los que sı perteneciera serıael primer elemento de A); entonces tampoco n+ 1 ∈ A (por la misma razon), ası que hemosprobado que n ∈ S ⇒ n + 1 ∈ S, de donde, por el Principio de Induccion, S = N, peroentonces A = ∅, lo cual es una contradiccion.

Ahora veamos que el Principio del Buen Orden implica el de Induccion: Sea S ⊂ N talque 1 ∈ S y en el cual se verifica que n ∈ S ⇒ n + 1 ∈ S. Queremos probar que S = N.Supongamos que no y sea A = N \ S; por nuestra suposicion, este conjunto es no vacıo y,como estamos suponiendo tambien que el Principio del Buen Orden vale, entonces A tieneprimer elemento n0; observemos que n0 6= 1 (pues 1 ∈ S), ası que n0 − 1 es un natural queno pertenece a A y entonces n0 − 1 ∈ S; esto es a una contradiccion porque S cumple lapropiedad de que al sumar 1 a cualquier elemento de S se obtiene otro elemento de S. ♦

Otro concepto importante en conjuntos parcialmente ordenados es el siguiente. Una cotasuperior para un subconjunto A de un conjunto parcialmente ordenado X es un elementox0 tal que a ≤ x0 para todo a ∈ A. La existencia de una cota superior nos dice que Aesta acotado superiormente. Una cota inferior mınima para el conjunto A se llama su-premo de A y, en vista de que, en caso de existir el supremo es unico, lo denotamos porsupA. Analogamente se define cota inferior, conjunto acotado inferiormente, ınfimoe inf A. Cuando un conjunto A esta acotado superior e inferiormente decimos simplementeque esta acotado.

3.23 Ejemplo. Dentro de R analicemos las posibles cotas para varios conjuntos:

(a) N no tiene cota superior; −π, 0, 37, 1 son cotas inferiores y 1 es ınfimo.

(b) El conjunto de cotas inferiores de A = { 1n

: n ∈ N} es R \ P ; 0 es ınfimo y 1 essupremo.

(c) Si A = [−∞,−17), entonces A no tiene ınfimo y supA = −1

7. Todo numero mayor o

igual que −17

es cota superior para A.

(d) Si A = {x ∈ R : x2 ≤ 2} entonces supA = 2 e inf A = −2. (Para ver esto, observemosque la desigualdad es equivalente a |x| ≤

√2, ası que A = {x : −2 ≤ x ≤ 2}.)

3.24 Observacion. Hemos visto que un conjunto puede tener muchas cotas inferiores(o superiores) o no tener ninguna; sin embargo supremos e ınfimos, en caso de existir, sonunicos. Tambien observamos que el supremo y el ınfimo de A pueden o no estar en A.

3.25 Ejercicio. En el orden parcial definido en 3.17 sean B = {b, c, e} y C = {i, h}.Determinar si estos conjuntos tienen cotas superiores o inferiores y, en dado caso, sus ınfimosy supremos.

El conjunto de los numeros reales tiene una propiedad muy importante que no tiene Q y

84

es la siguiente.

3.26. Principio del Supremo. Todo subconjunto no vacıo de R y acotado superior-mente en R tiene supremo en R.

3.27 Ejercicio. Dar un ejemplo de un subconjunto de Q que este acotado superiormentepero que no tenga supremo.

3.4. Funciones

Un ejemplo importante de relacion es el de las funciones. Nosotros estamos ya acostum-brados a trabajar funciones; por ejemplo, hablamos del numero que le toca a un alumnoinscrito a una universidad, o al color de pelo de cada persona, o a la temperatura de unobjeto en cada instante, o la funcion “elevar al cuadrado” un numero real, etc. Daremos con-tinuacion una definicion que engloba todas estas y formalizaremos la definicion en terminosde relaciones.

Dados dos conjuntos A y B, un tipo de relacion f en A × B que cumple que para cadaelemento de A existe exactamente un elemento b ∈ B con (a, b) ∈ f se llama funcion de Aen B; escribimos f : A → B; al unico elemento b ∈ B tal que (a, b) ∈ f se le denota porb = f(a) y se dice que b es la imagen de a bajo f o que b es el resultado de aplicar f aa; tambien es costumbre escribir a 7→ f(a). El conjunto A es el dominio de la funcion y Bes el codominio de la funcion. Otra forma de pensar en las funciones es decir que constande dos conjuntos A (dominio), B (codominio) y una regla que asocia a cada elemento a deA exactamente un elemento f(a) ∈ B; en este caso, al subconjunto de A × B que define larelacion se le llama grafica de f y se le denota por Graf(f); ası

Graf(f) = {(a, f(a)) ∈ A×B : a ∈ A}.

Analicemos los ejemplos de 3.15

3.28 Ejemplo. (a) La relacion “ser hermano de” no es funcion por dos razones: Haypersonas que no tienen hermanos y hay personas que tienen mas de un hermano.

(b) Sin meternos en complicaciones polıticas, podemos pensar que cada paıs tiene exacta-mente una capital y entonces la relacion en que A es el conjunto de paıses y B es el conjuntode ciudades sı es funcion.

(c) La relacion en Z “ser multiplo de” no es funcion pues, por ejemplo, (6, 2) y (6, 3) son

85

ambos elementos de la relacion.

(d) La relacion de contencion en A = P(N) tampoco es funcion pues, por ejemplo {1} ⊂{1, 2} y tambien {1} ⊂ {1, 3}.

(e) La relacion de igualdad sı es funcion en cualquier conjunto A; se le llama funcionidentica y se le denota por idA. Entonces idA(a) = a para toda a ∈ A. En este caso, lagrafica de la funcion es {(a, a) : a ∈ A}. En el caso en que A = {1, 2, 3}, se tiene queidA(1) = 1, idA(2) = 2 y idA(3) = 3.

(f), (g) y (h) de 3.15 no son funciones.

(i) Para A el conjunto de alumnos de una universidad determinada y B = N, tenemos lafuncion definida por f(a) = numero de registro de a en la universidad.

(j) Si A es el conjunto de las personas y B es el conjunto de los colores rojo, cafe, blanco,gris, amarillo, negro y verde, definimos una funcion por a 7→ color de pelo de a, para cadaa ∈ A.

(k) La funcion “elevar al cuadrado un numero real” se describe por f : R→ R, f(x) = x2.Aquı, por ejemplo, f(10) = 100, f(0) = 0 y f(−

√2) = 2.

La definicion que dimos de funcion como relacion esta basada en la formalizacion ma-tematica dentro de la teorıa de conjuntos. Mas bien la costumbre es considerarlas comoasignaciones y llamar grafica de la funcion a su definicion como relacion (subconjunto delproducto cartesiano). Sin embargo, es importante hacer notar que una funcion depende detres cosas: el dominio, el codominio y la regla de asignacion; ası, por ejemplo, las funcionesf : N→ Z, g : N→ N y h : Z→ Z que tienen la misma regla de asignacion x 7→ 2x+ 1 sontodas distintas; inclusive, es posible que una determinada asignacion no defina funcion paraciertos dominios y codominios pero sı la defina para otros, como es el caso de la asignacionx 7→ x

2de N en N que no es funcion, pues hay elementos del dominio que no tienen imagen

en el codominio (1, por ejemplo, pues 12

no es natural), y, sin embargo, esa misma asignacionsı es funcion de N en Z.

Sabemos que la grafica de una funcion de A en B es un subconjunto de A × B; esto esde especial importancia cuando A y B son subconjuntos de R porque entonces la grafica sepuede dibujar como una “curva” en el plano. Esta “curva” no necesariamente es una lıneacontinua (tal vez ni siquiera consta de pedazos de lıneas) pero sı satisface una condicionimportante: cada recta vertical que pasa por cualquier punto del dominio (que se ubica en eleje x) intersecta a la “curva” en exactamente un punto. Otras condiciones sobre esa curva,dependiendo de la funcion de que se trate, se estudian, mayormente, en los cursos de CalculoDiferencial e Integral.

Decimos que una funcion f : A → B es inyectiva si no hay dos elementos distintos deA que tengan la misma imagen, es decir,

Si a1, a2 ∈ A son tales que f(a1) = f(a2) entonces a1 = a2,

86

o, equivalentemente,

Si a1, a2 ∈ A son distintos entonces f(a1) 6= f(a2).

Un esquema que nos ilustra que una funcion no es inyectiva es el siguiente.

........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ .............................................................................................................................................................

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

...............................................................................................................................................................................................................................................................................................................

A B

......................................................................................................................................................................................

..................................................................................................................................

......................

........................................................................................................................................................................................................................................................................................................................ ......................

••

•

En 3.28 el ejemplo (b) es una funcion inyectiva porque no hay dos paıses que tengan lamisma capital; tambien (e) y (a) son inyectivas, pero (j) no lo es porque hay mas de unapersona que tiene el pelo negro; tampoco (k) es inyectiva porque, por ejemplo, f(−1) =(−1)2 = 12 = f(1).

Decimos que una funcion f : A → B es suprayectiva si todos los elementos de B sonimagen de elementos de A, es decir, si

B = {f(a) : a ∈ A},

o, de otra manera, si para todo b ∈ B existe a ∈ A tal que f(a) = b.

En los ejemplos de 3.28 tenemos que (b) no es suprayectiva ya que hay ciudades que noson capital de ningun paıs; (e) es obviamente suprayectiva; (a) no lo es porque hay naturalesque no son numero de registro de ningun alumno, ni tampoco (j) porque no hay ningunapersona que tenga color de pelo verde, ni (k) porque los numeros negativos no son imagende ningun real.

Es importante notar que la inyectividad o suprayectividad dependen del dominio y codo-minio de las funciones; por ejemplo, vimos que la funcion x 7→ x2 no es inyectiva si el dominioy el codominio son R, pero se vuelve inyectiva y suprayectiva si se restringen el dominio y elcodominio a R+, el conjunto de reales positivos. Ası mismo la funcion de f : R→ R definidapor f(x) = 2x+1 sı es suprayectiva porque dado y ∈ R, se tiene que y es imagen de y−1

2, pero

la funcion g : Z→ Z con la misma regla de correspondencia que f (es decir g(x) = 2x + 1)no es suprayectiva en vista de que los numeros pares no son imagen de ningun entero.

Una funcion f : A→ B es biyectiva si es inyectiva y suprayectiva. De los ejemplos quehemos visto arriba, solo son biyectivas 3.28(e), la funcion elevar al cuadrado cuando ambosel dominio y el codominio son R+ y la funcion x 7→ 2x + 1 cuando el dominio y codominioson R.

3.29 Observacion. Sea f : A→ B con A,B ⊂ R. Entonces

(a) f es inyectiva si, y solo si, cualquier recta horizontal intersecta Graf(f) en a lo mas

87

un punto.

(b) f es suprayectiva si, y solo si, cualquier recta horizontal que pasa por puntos delcodominio (que se ubica en el eje y) intersecta Graf(f) en por lo menos un punto.

(c) f es biyectiva si, y solo si, cualquier recta horizontal que pasa por puntos del codominiointersecta Graf(f) en exactamente un punto. ♦

Si f : A→ B y g : B → C son funciones, su composicion g◦f (lease “f seguida de g) esla funcion de A en C definida por (g◦f)(a) = g(f(a)). Notese que, por comodidad, escribimosf a la derecha de g a pesar de que f se aplica primero que g. esta es una especie de “operacion”entre funciones que resulta no ser conmutativa aun cuando los dominios y codominios seanel mismo (en otro caso, es posible que ni siquiera este definida la composicion); por ejemplo,si f : R→ R y g : R→ R son las funciones definidas por f(x) = x2 y g(x) = 2x+1, entonces(g ◦ f)(x) = g(x2) = 2x2 + 1, mientras que (f ◦ g)(x) = f(2x + 1) = 4x2 + 4x + 1; hastaaquı hemos visto que f ◦ g y g ◦ f estan definidas por un polinomio distinto, sin embargotodavıa no hemos probado que son funciones distintas; para ello debemos ver que algunade las tres condiciones que las determinan (dominio, codominio y regla de aplicacion) esdistinta; como f ◦g y g◦f tienen mismo dominio y codominio hay que probar que la regla deaplicacion da distinto resultado en algun elemento; veamos que el numero 1 nos sirve comoejemplo: (g ◦ f)(1) = 3 pero (f ◦ g)(1) = 9; con esto ya podemos concluir que g ◦ f 6= f ◦ g.

Como dijimos arriba, la composicion de funciones es una especie de operacion. No esoperacion pues no siempre se pueden operar funciones porque dependen de que el codominiode la primera que se aplica sea el dominio de la segunda (o que al menos sea subconjuntode ese dominio). Sin embargo, de la misma manera que hablamos de la no conmutatividad,podemos hacernos mas preguntas que sabemos que otras operaciones satisfacen. Empecemospor ver que se da la asociatividad, es decir, si f : A → B, g : B → C y h : C → D sonfunciones, entonces (h ◦ g) ◦ f = h ◦ (g ◦ f) pues ambas son funciones de A en C y si a ∈ Aentonces

((h ◦ g) ◦ f)(a) = h(g(f(a))) = (h ◦ (g ◦ f))(a).

De costumbre omitimos los parentesis y escribimos h ◦ g ◦ f .

Ahora veamos que idA funciona como neutro por la derecha para todas las funciones condominio A: Si f : A → B, entonces es claro que f ◦ idA = f (pues ambas funciones tienenpor dominio A, por codominio B y, al aplicarlas a los elementos a ∈ A la imagen es f(a).De la misma manera, la funcion que trabaja como neutro por la izquierda de las funcionescon codominio B es idB (aquı se tiene idB ◦ f = f para f : A→ B).

Una cuestion mas difıcil es la existencia de inversas, ya sea por la izquierda o por laderecha, y tenemos el siguiente resultado.

3.30 Proposicion. Sea f : A→ B una funcion.

(a) Existe g : B → A tal que g ◦ f = idA si, y solo si f es inyectiva. En este caso, g es

88

una inversa izquierda de f .

(b) Existe g : B → A tal que f ◦ g = idA si, y solo si f es suprayectiva. En este caso, ges una inversa derecha de f .

Demostracion. (a) Supongamos primero que f : A → B es inyectiva y construyamosg : B → A. Tomemos a0 elemento fijo en A. Para b ∈ B tenemos dos casos: que exista unelemento a ∈ A tal que f(a) = b; en ese caso, la inyectividad nos dice que a es unico ydefinimos g(x) = a; si no existe tal a entonces definimos g(b) = a0. Es claro que g ◦ f = idA.

Ahora supongamos que g es una inversa izquierda de f y probemos que f es inyectiva.Sean a1 y a2 elementos de A tales que f(a1) = f(a2). Aplicando g a esta igualdad tenemos

g(f(a1)) = g(f(a2))

(g ◦ f)(a1) = (g ◦ f)(a2)

idA(a1) = idA(a2)

a1 = a2,

de donde concluimos que f es inyectiva.

(b) Supongamos ahora que f : A → B es suprayectiva y construyamos una inversaderecha g : B → A de f . Como f es suprayectiva, dado a ∈ A sabemos que existe b ∈ Btal que f(b) = a; entonces, para cada elemento a ∈ A escojamos un elemento b ∈ Btal que f(b) = a (la posible eleccion global de estos elementos, es decir, uno para cadaa, esta garantizada por el llamado Axioma de Eleccion de la Teorıa de Conjuntos) ydefinamos g(a) como ese elemento b escogido para a. Es claro que f ◦ g = idA.

Ahora supongamos que f tiene inversa derecha g y probemos que f es suprayectiva; paraesto debemos dar un elemento arbitrario b ∈ B y exhibir un elemento a ∈ A tal que f(a) = b;ası, dado b ∈ B tomemos a = g(b) ∈ A y veamos que este a funciona:

f(a) = f(g(b)) = (f ◦ g)(b) = idB(b) = b. ♦

3.31 Corolario. Una funcion es biyectiva si, y solo si, f tiene inversa izquierda y derecha.En este caso, solo hay una inversa izquierda, una inversa derecha y estas coinciden.

Demostracion. Ya sabemos que existen g, h : B → A con g inversa izquierda de f yh inversa derecha de f . Probemos que g = h y esto nos dara la unicidad de ambas y sucoincidencia:

g = g ◦ idB = g ◦ (f ◦ h) = (g ◦ f) ◦ h = idA ◦ h = h. ♦

La inversa de una funcion biyectiva f se denota por f−1.

3.32 Ejemplo. (a) Sea f : N → Z definida por f(x) = x − 5. Es claro que f esinyectiva pues a1 − 5 = a2 − 5⇒ a1 = a2 ası que, segun la proposicion anterior, debe tenerinversa izquierda. Construyamos una inversa izquierda g : Z → N tomando a0 = 83 en la

89

demostracion de la proposicion anterior:

g(x) =

{x+ 5, si x ≥ −4,

83, si x < −4.

Observemos aquı que la eleccion de 83 es claramente arbitraria y que cualquier otra definicion,incluso aunque no hubiera sido una constante, habrıa servido.

(b) Sea f : R→ Z la funcion parte entera, es decir, f(x) = [x], el mayor entero menoro igual que x (por ejemplo, f(10.32) = 10, f(1) = 1, f(−2.5) = −3, f(π) = 3, f(−1

4) = −1).

Una inversa derecha puede ser g : Z→ R definida por g(x) = x. Notemos que otra forma dedefinir g podrıa ser g(x) = x+ 1

2.

(c) Sea f : R → R definida por f(x) = 2x3 − 1. Entonces f es biyectiva y su inversa

esta definida por g(x) = 3√

x+12

.

3.33 Observacion. Si f : R→ R es biyectiva, entonces la grafica de la funcion inversaf−1 se obtiene reflejando la grafica de f a traves de la recta a 45o (como si esta recta fueraun espejo) pues (a, b) ∈ Graf(f)⇔ (b, a) ∈ Graf(f−1).

3.34 Ejercicio. Dibujar las graficas de las siguientes funciones de R en R.

(a) La funcion identica.

(b) La funcion f definida por f(x) = 2x+ 1.

(c) La funcion f definida por f(x) = [x].

(d) La funcion f definida por

f(x) =

{1, si x ∈ Q,0, si x /∈ Q.

3.35 Ejercicio. Determinar si las siguientes funciones son inyectivas, suprayectivas obiyectivas y, en los respectivos casos, construir una funcion inversa por la izquierda, o porderecha o por ambos lados:

(a) f : R→ R, f(x) = sen(x).

(b) f : R→ R, f(x) = |x|.(c) f : R2 → R, f(x, y) = x.

(d) f : R→ R, f(x) = 5x− π.

(e) f : Q→ R, f(x) = 2x

Si f : A→ B es funcion y A1 ⊂ A, definimos la imagen de A1 bajo f como el conjunto

f(A1) = {f(a) : a ∈ A1} = {b ∈ B : existe a1 ∈ A1 con f(a) = b}.

90

Si B1 ⊂ B definimos la imagen inversa o preimagen de B1 bajo f como el conjunto

f−1(B1) = {a ∈ A : f(a) ∈ B1}.

Por ejemplo, si f : R → R esta definida por f(x) = x2, entonces f(R) = [0,∞), f(Z) ={0, 1, 4, 9, 16, . . .}, f−1({−1}) = ∅ y f−1({1}) = {−1, 1}.

3.36 Observacion. Sea f : A→ B una funcion. Entonces

(a) f es suprayectiva si, y solo si, f(A) = B.

(b) f es inyectiva si, y solo si, para todo b ∈ B se tiene que f−1(b) consta a lo mas de unelemento.

(c) f es biyectiva si, y solo si, para todo b ∈ B se tiene que f−1(b) consta de un elementode A exactamente.

3.37 Nota. Se usa la misma notacion f−1 para dos cosas distintas: la funcion inversa, encaso de que la funcion f sea biyectiva, y la imagen inversa de un subconjunto del dominio.Realmente, cuando f : A→ B es biyectiva y b ∈ B entonces, al aplicar la funcion inversa f−1

a b obtenemos el unico elemento a de A tal que f(a) = b (ası f−1(b) = a) y, si consideramosla imagen del conjunto {b}, su imagen inversa es el conjunto cuyo unico elemento es esemismo a (es decir, f−1{b} = {a}).

Tenemos algunas propiedades basicas.


(a) Si A1 ⊂ A2 ⊂ A entonces f(A1) ⊂ f(A2).

(b) Si A1, A2 ⊂ A entonces f(A1 ∪ A2) = f(A1) ∪ f(A2).

(c) Si A1, A2 ⊂ A entonces f(A1∩A2) ⊂ f(A1)∩f(A2). Si la funcion es inyectiva, entoncesse da la igualdad.

(d) Si A1, A2 ⊂ A entonces f(A1 \ A2) ⊃ f(A1) \ f(A2). Si f es inyectiva entonces se dala igualdad.

Demostracion. Demostraremos solo (c) y dejaremos las demas como ejercicio. Sea b ∈f(A1 ∩ A2). Entonces b = f(a) para algun a ∈ A1 ∩ A2, ası que a ∈ A1 y a ∈ A2 y entoncesb = f(a) ∈ f(A1) y b = f(a) ∈ f(A2), de donde entonces b = f(a) ∈ f(A1) ∩ f(A2).Ahora supongamos que f es inyectiva y sean A1, A2 subconjuntos de A. Queremos probarque f(A1 ∩A2) ⊃ f(A1) ∩ f(A2). Sea b ∈ f(A1) ∩ f(A2) y sean a1 ∈ A1 y a2 ∈ A2 tales quef(a1) = b y f(a2) = b. Por ser f inyectiva, a1 = a2 ∈ A1 ∩A2 de donde b ∈ f(A1)∩ f(A2). ♦

3.39 Ejercicio. Probar los incisos (a), (b) y (d) de la proposicion anterior.

91


(a) Si B1 ⊂ B2 ⊂ B entonces f−1(B1) ⊂ f−1(B2).

(b) Si B1, B2 ⊂ B entonces f−1(B1 ∪B2) = f−1(B1) ∪ f−1(B2).

(c) Si B1, B2 ⊂ B entonces f−1(B1 ∩B2) = f−1(B1) ∩ f−1(B2).

(d) Si B1, B2 ⊂ B entonces f−1(B1 \B2) = f−1(B1) \ f(B2).

Demostracion. Demostraremos solo (d) y dejaremos las demas como ejercicio.

Tenemos que a ∈ f−1(B1 \ B2) ⇔ f(x) ∈ B1 \ B2 ⇔ f(a) ∈ B1 y f(a) 6∈ B2 ⇔ x ∈f−1(B1) \ f(B2). ♦

3.41 Ejercicio. Probar los incisos (a), (b) y (c) de la proposicion anterior.

3.42 Ejercicio. Sea f : R→ R la funcion definida por f(x) = 3x+2. Determinar f [0, 2)y f−1[0, 2).

3.43 Ejercicio. Sea f : R→ R la funcion definida por f(x) = x2−1. Determinar f [1, 3)y f−1[1, 3).


(a) Si A1 ⊂ A entonces f−1(f(A1)) ⊃ A1. Si f es inyectiva entonces se da la igualdad.

(b) Si B1 ⊂ B entonces f(f−1(B1)) ⊂ B1. Si f es suprayectiva entonces se da la igualdad.

Demostracion. (a) Sea a1 ∈ A1. Para ver que a1 ∈ f−1(f(A1)), por definicion de imageninversa, debemos aplicarle f a a1 y ver si su imagen cae en f(A1), pero eso es claro porquea1 ∈ A1.

Ahora supongamos que f es inyectiva y tomemos un elemento a en f−1(f(A1)); entonces,por definicion de imagen inversa, f(a) ∈ f(A1) ası que existe a1 ∈ A1 tal que f(a) = f(a1);la inyectividad nos dice entonces que a = a1 y ası tenemos que a ∈ A1.

(b) Sea b ∈ f(f−1(B1)); esto quiere decir que b = f(a) para algun a ∈ f−1(B1), perola definicion de imagen inversa nos dice que f(a) ∈ B1 y esto termina esta parte de lademostracion.

Ahora supongamos que f es suprayectiva. y sea b1 ∈ B1; usando que f suprayectivatomemos a ∈ A tal que f(a) = b1; pero como b1 ∈ B1 entonces a ∈ f−1(B1), de dondeb1 = f(a) ∈ f(f−1(B1)). ♦

3.45 Ejercicio. Sea f : R → R la funcion definida por f(x) = [x]. Encontrar dosconjuntos de reales A1 y B1 tales que f−1(f(A1)) 6= A1 y f(f−1(B1)) ⊂ B1.

3.46 Ejercicio. Probar que si f : A→ B es una funcion, entonces la relacion ∼ definida

92

en A por x ∼ y ⇔ f(x) = f(y) es relacion de equivalencia. ¿Cuales son las clases deequivalencia?

3.5. Cardinalidad

Veremos aquı que N,Z y Q tienen el mismo “tamano” pero que el “tamano” de R esmayor. Debemos precisar que significa esto del tamano o cardinalidad de manera media-namente formal. Notemos que cuando decimos que un cierto conjunto tiene 3 elementos esporque al contar se establece una funcion biyectiva entre ese conjunto y el conjunto {1, 2, 3}.Por ejemplo, el conjunto {2, 8, 21} tiene tres elementos pues los contamos al mismo tiem-po que {1, 2, 3}: 1 ↔ 2, 2 ↔ 8, 3 ↔ 21. Ası, para n ∈ N consideramos a los conjuntos{1, 2, . . . , n} como basicos, y decimos que un conjunto A tiene cardinal n, en sımbolos#A = n, si existe una biyeccion entre A y {1, 2, . . . , n}. Tambien decimos que el cardinal delconjunto vacıo es 0. En conjuntos infinitos la situacion es bastante mas complicada. Toma-mos N como conjunto basico y a su cardinal le llamamos ℵ0 (lease alef 0). Tambien decimosque un conjunto con cardinal ℵ0 es numerable.

3.47 Observacion. Un conjunto A es numerable si, y solo si, es infinito y podemosenlistar los elementos de A de manera que no haya repeticion y que se abarquen todos loselementos: a1, a2, a3, . . . (pues, una vez establecida la biyeccion N→ A, a la imagen de i ∈ Nle llamamos ai).

Veremos a continuacion que Z y Q son numerables pero que R no lo es.

3.48 Proposicion. Z es numerable.

Demostracion. Enlistamos los elementos de Z:

0, 1,−1, 2,−2, 3,−3, . . . . ♦

3.49 Ejercicio. Probar que si A y B son numerables, entonces A ∪B tambien lo es.

3.50 Proposicion. Q+ es numerable.

Demostracion. Escribamos los elementos de Q+ en una tabla y numeremoslos en zigzagsiguiendo las flechas como indica el esquema, saltandonos los elementos que ya fueron conta-dos (por ejemplo, al pasar por 2

2nos lo saltamos pues ya lo habıamos contado en su expresion

11):

93

3.51 Corolario. Q es numerable.

Demostracion. Usamos la proposicion anterior y el ejercicio 3.49. ♦

3.52 Proposicion. R no es numerable.

Demostracion. Supongamos que sı lo es y demos una numeracion para los elementospositivos de R:

A1 = B1.b1,1b1,2b1,3 · · ·A2 = B2.b2,1b2,2b2,3 · · ·A3 = B3.b3,1b3,2b3,3 · · ·

...

Construyamos un elemento c = 0.c1c2c3 ∈ R que no este en esta numeracion tomando: cncualquier dıgito distinto de 0, 9 y de bn,n. ♦

Dentro de la Teorıa de Conjuntos se prueba que hay conjuntos con cardinal mayor queel de R. Otra idea importante en este sentido es la pregunta de si hay conjuntos que tienencardinalidad intermedia entre la de N y la de R. Se prueba que la existencia o no es inde-pendiente de la axiomatica mas estandar de la Teorıa de Conjuntos. En ciertos contextosse toma la no existencia como axioma y se le llama Hipotesis del Continuo. Todo estocorresponde a un estudio muy complicado dentro de la Logica.

3.53 Ejercicio. Probar que el conjunto de los numeros irracionales no es numerable.

94

3.54 Ejercicio. Probar que si A y B son conjuntos numerables entonces tambien lo esA×B.

3.55 Ejercicio. La siguiente afirmacion es obviamente falsa: “El conjunto N de losnumeros naturales es finito.” Determinar cual es el error en la “prueba” por induccion quepresentamos a continuacion: “Para cada natural n sea An = {n}. Sabemos que la union detodos los conjuntos An nos da el conjunto N, y que la union de dos conjuntos finitos es finito.Entonces BI: A1 ∪ A2 es finito. HI: Supongamos que A1 ∪ A2 ∪ · · · ∪ An−1 es finito paracierta n ≥ 3. Entonces, A1 ∪ A2 ∪ · · · ∪ An = (A1 ∪ A2 ∪ · · · ∪ An−1) ∪ An, que es la unionde dos conjuntos finitos (usando la HI), ası que A1 ∪ A2 ∪ · · · ∪ An tambien es finito. Enconclusion, N es finito.”

95

Referencias y lecturas complementarias

[1] Albert, Algebra Superior, UTEHA.

[2] Cardenas, H., Lluis, E., Raggi, F., Tomas, F., Algebra Superior, ed. Trillas, 1992.

[3] Gentile, E., Aritmetica Elemental, Monografıa no. 25 de la Serie de Matematicas delPrograma Regional de Desarrollo Cientıfico y Tecnologico de la OEA, Ediciones de la OEA,1988

[4] Kurosh, Algebra Superior, MIR.

[5] Lipschutz, Matematicas Finitas, Schaum, McGraw-Hill.

[6] Niven, Zuckerman, Introduccion a la Teorıa de Numeros, Editorial Limusa-Wiley,Mexico 1972.

[7] Perez M.L. Combinatoria, Cuadernos de Olimpiadas de Matematicas, Instituto deMatematicas, UNAM, 3a edicion, 2005.

[8] Perez M.L. Teorıa de Numeros, Cuadernos de Olimpiadas de Matematicas, Institutode Matematicas, UNAM, 2a edicion, 2009.

[9] Spitznagel, E. L., Selected Topics in Mathematics, Holt, Rinehart and Winston, Inc.,1971.

96

Indice alfabetico

(a, b), 43A ⊂ B, 73A ∩B, 75A ∪B, 75A * B, 73A \B, 76A ⊆ B, 73A×B, 78A B, 73Ac, 74B ⊃ A, 73Graf(f), 85N, 95P(A), 73Q, 72R, 72Z, 72ℵ0, 93♣, 8∅, 72♥, 8a, 81♠, 8a - b, 34a ≡ b (mod n), 59a ∈ A, 72a 7→ b, 85a /∈ A, 72a � b, 81a ∼ b, 81diamondsuit, 8f(A), 90f(a), 85f : A→ B, 85f−1, 89f−1(B), 91g ◦ f , 88idA, 86inf(A), 84

mcd(a, b), 44mcm[a, b], 51n!, 3sup(A), 84(nr

), 5

acotado, 84inferiormente, 84superiormente, 84

alef 0, 93algoritmo de Euclides, 45algoritmo de la division, 42antisimetrica, 73, 80aplicacion (de funcion), 85axioma de eleccion, 89

baraja, 8base de induccion, 16BI, 16

cadena, 82cardinal, 93cardinalidad, 93clase (en una relacion de equivalencia), 81cociente (de una division), 43codominio, 85coeficientes binomiales, 13combinacion lineal entera, 36combinaciones, 5complemento, 74composicion (de funciones), 88congruente, 58congruente modulo n, 59conjunto, 72conjunto potencia, 73conjunto universal, 74conjunto vacıo, 72conjuntos ajenos, 75contencion, 73corazon (en baraja de pokar), 8

97

corrida (en baraja de pokar), 9cota inferior, 84cota superior, 84criba de Eratostenes, 39criterio de divisibilidad

entre 10, 41entre 11, 41entre 12, 41entre 2, 40entre 3, 40entre 4, 40entre 5, 40entre 6, 41entre 8, 41entre 9, 41

descomposicion canonica, 38diagrama de Venn, 73diamante (en baraja de pokar), 8diferencia (de conjuntos), 76distributividad de interseccion sobre union,

76distributividad de union sobre iterseccion, 76divide, 34divisibilidad, 34divisible, 34divisor, 34divisor propio, 37dominio, 85

ecuacion diofantina, 53ecuaciones equivalentes, 54elemento, 72elemento maximal (en orden parcial), 82elemento mayor (en orden parcial), 82elemento menor (en orden parcial), 82elemento minimal (en orden parcial), 82elementos equivalentes (bajo relacion de equi-

valencia), 81espada (en baraja de pokar), 8

factor, 34factorial, 3ficha (de domino), 11

ficha doble (de domino), 12flor (en baraja de pokar), 9full (en baraja de pokar), 9funcion, 85

biyectiva, 87inyectiva, 86suprayectiva, 87

funcion identica, 86funcion parte entera, 90

grafica (de funcion), 85

Hasse (esquema de), 81HI, 16hipotesis de induccion, 16hipotesis del continuo, 94

imagen (de funcion), 90imagen de elemento bajo funcion, 85imagen inversa, 91inclusion, 73induccion matematica, 14ınfimo, 84interseccion, 75inversa derecha (de funcion), 89inversa izquierda (de funcion), 89inverso (modulo n), 65invertible, 65

leyes de De Morgan, 77

mınimo comun multiplo, 51maximo comun divisor, 44multiplo, 34multiplo propio, 37mano (de domino), 12mano (en baraja de pokar), 8

numeroracional, 72compuesto, 37entero, 34, 72entero positivo, 1natural, 1, 72primo, 37

98

racional, 52real, 72unidad, 37

numero (en baraja de pokar), 8numeros primos entre sı, 45numeros primos relativos, 45numerable, 93

orden parcial, 80orden total, 82

pokar, 8, 9palo (en baraja de pokar), 8par (en baraja de pokar), 9particion (de conjunto), 81Pascal (formula), 10Pascal (triangulo), 10permutacion, 4preimagen, 91principıo del buen orden, 83principio de induccion, 83principio de sustitucion (en congruencias), 61principio del supremo, 85principio fundamental de conteo, 2probabilidad, 28procedimiento inductivo, 1producto cartesiano, 78progresion aritmetica, 21propiedad asociativa de la interseccion, 76propiedad asociativa de la union, 76propiedad conmutativa de la union, 76propiedad conmutativa de lainterseccion, 76

recursiva, 21reflexiva, 35, 60, 73, 80relacion, 79relacion de equivalencia, 80residuo (de una division), 43

simetrica, 35, 60, 80soluble (congruencia), 67subconjunto, 73subconjunto propio, 73sucesion aritmetica, 21

sucesion de Fibonacci, 23, 70supremo, 84

teorema del binomio de Newton, 12teorema fundamental de la aritmetica, 37, 38,

50tercia (en baraja de pokar), 9trebol (en baraja de pokar), 8transitiva, 35, 60, 73, 80

union, 75

vacuidad, 81valor absoluto, 35valor esperado, 32

99

por mar a luisa p erez seguichi.fismat.umich.mx/cursos/algebra superior 1.pdf · 2013-08-16 ·...

Documents