curso de discretas.pdf

8/15/2019 curso de discretas.pdf

1/160

Índice general

1. Aritmética Entera 11.1. intruducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2. Aritmética Modular 30

3. Técnicas de Conteo 433.1. Permutaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.1.1. Permutaciones con Repetición . . . . . . . . . . . . . . . . . . . 573.1.2. Variaciones o permutaciones . . . . . . . . . . . . . . . . . . . . 653.1.3. Variaciones o permutaciones con Repetición . . . . . . . . . . . 683.1.4. Combinaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 713.1.5. Combinaciones con Repetición . . . . . . . . . . . . . . . . . . 81

4. Relaciones en recurrencia 87

4.1. Relaciones de recurrencia lineales con coeficientes constantes . . . . . . 904.2. Relaciones de recurrencia lineal no homogéneas con coeficientes constantes 92

4.2.1. Transformada Z . . . . . . . . . . . . . . . . . . . . . . . . . . 94

5. Introducción a la teoría de grafos 985.1. INTRODUCCIÓN Y RESEÑA HISTÓRICA . . . . . . . . . . . . . . 985.2. Definiciones preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . 985.3. Problema origen de la teoría de grafos: . . . . . . . . . . . . . . . . . . 106

5.3.1. Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . 1195.4. Coloreado de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

6. Álgebra Booleana 1336.1. Látices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

6.1.1. Propiedades de las látices. . . . . . . . . . . . . . . . . . . . . . 1356.1.2. Tipos especiales de látices. . . . . . . . . . . . . . . . . . . . . 136

6.2. ÁLGEBRAS BOOLEANAS. . . . . . . . . . . . . . . . . . . . . . . . 1386.2.1. Propiedades de un álgebra booleana . . . . . . . . . . . . . . . 139

6.3. EXPRESIONES BOOLEANAS . . . . . . . . . . . . . . . . . . . . . . 1416.3.1. Forma normal disyuntiva . . . . . . . . . . . . . . . . . . . . . 1416.3.2. Forma normal conjuntiva. . . . . . . . . . . . . . . . . . . . . . 144

6.4. ALGEBRA DE CONMUTACIÓN. . . . . . . . . . . . . . . . . . . . . 1456.5. Simplificación de circuitos . . . . . . . . . . . . . . . . . . . . . . . . . 147


2/160

ÍNDICE GENERAL II

6.6. Mapas de Karnaugh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

6.6.1. Forma de introducir los valores en un mapa de Karnaugh . . . 1486.6.2. Lectura de un mapa de Karnaugh . . . . . . . . . . . . . . . . 1506.7. Diseño de circuitos usando los mapas de Karnaugh . . . . . . . . . . . 154

6.7.1. Compuertas lógicas. . . . . . . . . . . . . . . . . . . . . . . . . 154


3/160

Índice de figuras


4/160

Índice de cuadros


5/160

Capítulo 1

Aritmética Entera

1.1. intruducción

El objetivo del curso es presentar la Matemática Discreta mediante la exposición

de sus definiciones, teoremas y resultados más importantes, junto con algunas de sus

aplicaciones prácticas. Se tratarán temas como el concepto de divisibilidad y sus con-

secuencias, el algoritmo de Euclides, las ecuaciones diofánticas, los números primos, la

relación de congruencia módulo m y la aritmética en Zm y sus aplicaciones, el teore-

ma de Euler, el teorema menor de Fermat, etc. En la parte práctica se verán algunas

aplicaciones de la aritmética entera y modular, como los sistemas de numeración, laobtención de números pseudoaleatorios, las funciones "hash", la arimética modular

como modo de facilitar operaciones con números enteros muy grandes, los dígitos de

control que se emplean en nuestra vida diaria (como el ISBN de los libros o nuestros

códigos de cuentas bancarias) Dentro de la parte práctica al final se introduce uno de

los empleos más interesantes de la aritmética modular, como es su uso históricamente

en la criptografía clásica, y más recientemente, la importancia que ha alcanzado el

estudio de la factorización de enteros muy grandes en números primos gracias a algo

que ha sido vital para la expansión de los servicios en Internet y la web: la criptografía

de clave pública.

Definición 1 : El conjunto, que denotaremos por Z, de números enteros es un con-

junto de número en el que se definen dos leyes de composición (operaciones) entre sus

elementos que satisfacen la siguiente lista de leyes:

Cerradura: La suma y el producto son leyes de composición internas: ∀a, b ∈ Z =⇒a + b ∈ Z; igualmente, ab ∈ ZAsociatividad: Ambas operaciones son asociativas:∀a ∈ Z =⇒ a+(b+c) = (a+b)+c =a + b + c; igualmente a(bc) = (ab)c = abc

1


6/160


7/160

1. Aritmética Entera 3

Así que existen q y r , enteros tales que

a = bq + r, con 0 ≤ r < b

Veamos la unicidad de q y r: Por reducción al absurdo, supongamos que no son únicos,

es decir, supongamos que existen r1, r2, q 1 y q 2, enteros tales que verifican el teorema,

o sea,

a = bq 1 + r1 : con 0 ≤ r1 < ba = bq 2 + r2 : con 0 ≤ r2 < b.

Entonces,

bq 1 + r1 = bq 2 + r2 =⇒ b(q 1 − q 2) = r2 − r1 =⇒ b|q 1 − q 2| = |r2 − r1|

y al ser

0 ≤ r1, r2 < bse tiene que:

0 ≤ |r2 − r1| < bluego,

b

|q 1

−q 2

| =

|r2

−r1

| ((*))

Como

|r2 − r1| < bentonces

b|q 1 − q 2| < b lo que implica que b(1 − |q 1 − q 2|) > 0y al ser b > 0, se tendría que:

1 − |q 1 − q 2| > 0de donde sigue que:

0 ≤ |

q 1−

q 2| < 1

y como q 1 y q 2 son enteros, tendrá que ser que:

|q 1 − q 2| = 0

por tanto,q 1 = q 2 y de igual forma se sigue de (*) que: r1 = r2

Corolario 5 : Si a y b son enteros, con b = 0, entonces existen dos enteros q y r,únicos, tales que a = bq + r, donde 0 ≤ r


8/160


Demostración : Si b > 0, entonces se cumplen las hipótesis del teorema anterior,

luego se verifica el corolario.Si b 0 y aplicando el teorema anterior, existirían dos enteros q 1 yr, únicos, tales que

a = (−b)q 1 + r, con 0 ≤ r


9/160


Por el teorema anterior, existirían q 1, q 2, rl1 y r2, únicos, tales que

a = 7q 1 + r1, con 0 ≤ r1 < 7b = 7q 2 + r2, con 0 ≤ r2 < 7

Como,

a = 7q 1 + r1 =⇒ a2 = 49q 21 + 14q 1r1 + r21 = 7(7q 21 + 2q 1r1) + r21 = 7k1 + r21 con k1 = 7q 2 + 2q 1b = 7q 2 + r2 =⇒ b3 = 7(49q 32 + 21q 22r2 + 21q 2r22 + 3q 2r22) + r32 = 7k2 + r32, con k2 ∈ Z

Entonces,

a2 = b3 =⇒ 7k1 + r21 = 7k2 + r32 con 0 ≤ r1, r2 ≤ 7y de nuevo por el teorema anterior, k1 = k2 y r21 = r

32. En el siguiente cuadro se

muestran las opciones que se presentan.

r2

r22r32r1

0 1 2 3 4 5 6

0 1 4 9 16 25 36

0 1 8 27 64 125 216

0 1 2 3 4 5 6

Note que las únicas opciones en las que coinciden es cuando r1 y r2 son los dos 0 ó los

dos 1. O sea, a2 = b3 satisfacen que a2 y b3 son de la forma 7k ó 7k + 1. Por tanto,n es cuadrado y cubo si n = 7k ó n = 7k + 1.

Teorema 10 : Sean a, b y c tres números enteros, siendo a y b distintos de cero. Se

verifica:

(i) 1 divide a “ a” y “ a” divide a 0.

(ii) Si “ a” divide a “ b” y “ b” divide a “ a”, entonces a = ±b.(iii) Si “ a” divide a “ b” y “ b” divide a “ c”, entonces “ a” divide a “ c”.

(iv) Si “ a” divide a “ b” y “ a” divide a “ c”, entonces “ a” divide a pb + qc, cualesquiera

que sean p y q , enteros. (A la expresión pb + qc se le llama combinación lineal de b y

c con coeficientes enteros).

Demostración : (i) 1|a y a|0. En efecto, a = 1·a, con a ∈ Z, luego 1|a por otrolado 0 = a·0, con 0 ∈ Z , luego a|0(ii) a|b y b|a entones a = ±b, ∀a, b ∈ Z \{0}En efecto, a|b entonces ∃ p ∈ Z tal que b = ap y b|a entonces ∃q ∈ Z tal que a = bq.Por lo tanto b = bqp con lo cual b(1 − qp) = 0 y al ser b = 0 y no tener Z divisores decero, se sigue que

1 − pq = 0 de donde pq = 1


10/160


como p y q son enteron no queda más remedio que p = q = 1 ó que p = q = −1 luego,b = ap, a = bq y p = q = 1 conducen a que a = b; y el hecho de que b = ap, a = bq y p = q = −1 llevan a que a = −b, Por consiguiente se obtiene que a = ±b(iii) a|b y b|c entonces a|c.En efecto, a|b ∃ p ∈ Z tal que b = ap y el hecho de que b|c ∃q ∈ Z tal que c = bq por lotanto c = apq con pq ∈ Z, luego a|c(iv) a|b y a|c entonces a| ( pb + qc) , ∀ p, q ∈ ZEn efecto, a|b entonces ∃s ∈ Z tal que b = as luego por uniformidad pb = pas ademása|c entonces ∃t ∈ Z tal que c = at y por uniformidad qc = qat; por consiguiente

pb + qc = a( ps + qt)

Lo que implica que a| ( pb + qc), ∀ p, q ∈ Z

Ejercicio 11 : Demuestre que para a, b y c enteros, entonces:

1. Si a|b y a|c entonces a|(b + c).2. Si a|b entonces a|bc, para todo entero c.3. Para m = 0 entonces a|b si, y sólo si, ma|mb.4. Si d|a y a = 0 entonces |d| | |a|.

Definición 12 : (Divisor Común) Dados dos números enteros a y b, diremos que el

entero d = 0, es un divisor común de ambos, si divide a “ a” y divide a “ b”, es decir,d = 0, es divisor común de a y b si y solo si d|a y d|b. Observe que es lo mismo que decir que a y b son divisibles por d o que a y b son múltiplos de d.

Definición 13 : (Máximo Común Divisor) Sean a y b dos números enteros. Se dice

que d es el máximo común divisor de a y b, si d es el máximo del conjunto de los

divisores positivos comunes a ambos, ordenado por la relación de divisibilidad y se

denotará por m.c.d. (a, b).

Teniendo en cuenta la definición de máximo de un conjunto ordenado, si llamamos D

al conjunto de todos los divisores positivos comunes a a y a b, se tendrá que:

d = m.c.d.(a, b) ⇐⇒

d|a y d|bd = máx(D)

⇐⇒

d|a y d|b∀c ∈ D, entonces c|d ⇐⇒

d|a y d|bc|a y c|b, entonces c|d

Si a = b = 0, entonces m.c.d.(a, b) = 0.

Teorema 14 : Sean a y b dos números enteros distintos de cero. Se verifica:

(i) m.c.d. (a, 0) = |a |(ii) m.c.d. (a, b) = m.c.d. ( |a |, |b|)


11/160


Demostración : (i) m.c.d. (a, 0) = |a| , ∀a ∈ Z \ {0}.

En efecto, el máximo común divisor de a y 0 es, por definición, el máximo del conjuntode los divisores comunes a a y a 0 ordenado por la relación de divisibilidad. Ahora bien,

como todos los números enteros son divisores de cero por teorema, el citado conjunto

estará formado, únicamente por los divisores de a y el mayor divisor de a es el propio a,

luego m.c.d.(a, 0) = a y al ser el máximo común divisor mayor que cero, se toma como

m.c.d.(a, 0) = a, si a > 0 y m.c.d.(a, 0) = −a, si a 0. Entonces, d|a y d

|b Luego d

| −a y d

|b por lo tanto d

||a| y d

||b|2. a > 0 y b 0. Entonces, d|a y d|b Luego d||a| y d||b|. Luego en cualquier caso, elconjunto de los divisores comunes a “a” y a “b” coincide con el de los divisores comunes

a |a| y a |b|, por lo tanto el máximo común divisor será el mismo, es decir,m.c.d.(a, b) =m.c.d.(|a|, |b|). Observe que si a y b son enteros positivos, esto es lo mismo que decirque

m.c.d.(−a, b) = m.c.d.(a, −b) = m.c.d.(−a, −b) = m.c.d.(a, b)

Nota 15 : (Máximo Común Divisor de Varios Números) Sean a1, a2,...,an números

enteros. Llamaremos máximo común divisor de a1, a2,...,an al divisor común d > 0

tal que cualquier otro divisor común de a1, a2,...,an divide también a d. Se designará

mediante m.c.d.(a1, a2,...,an).

Teorema 16 : (Existencia y Unicidad del m.c.d.) Dados dos números enteros a y b

distintos de cero, existe un único d, que es el máximo común divisorde ambos.

Demostración Supondremos que a y b son de Z+ ya que según hemos visto en

teorema, si uno de los dos o ambos fuera negativo el máximo común divisor sería el

mismo.

Existencia. Sea C el conjunto de todas las combinaciones lineales positivas con coefi-

cientes enteros que puedan formarse con a y b, es decir,

C =

ma + nb ∈ Z+ : m, n ∈ ZC es no vacío. En efecto, como a es positivo, podemos escribirlo en la forma: a =

1·a + 0·b y, al menos, a estaría en C. Así pues, C es un subconjunto no vacío de Z+.


12/160


Aplicamos el principio del buen orden y C ha de tener primer elemento o elemento

mínimo y que llamaremos d. Veamos que d es el máximo común divisor de a y b. Enefecto, d ∈ C entonces d = sa + tb, con s y t enterosPues bien:

1. d es un divisor común de a y b..Supongamos lo contrario, es decir d no es divisor de

a ó d no es divisor de b. Entonces, si d no divide a a, por el teorema de existencia y

unicidad de cociente y resto, se puede encontrar dos enteros q y r tales que a = dq + r,

con 0 < r < d de aquí que

r = a − dq =⇒ r = a − (sa + tb)q =⇒ r = (1 − sq )a + (−tq )b > 0

con 1 − sq y −tq enteros, luego r está en C . Así pues, tenemos que r ∈ C y r < d locual contradice el que d sea el míınimo de C. Consecuentemente, la suposición hecha

es falsa y d|a. Con un razonamiento idéentico, se prueba que d|b .2. Veamos ahora que d es el máximo de los divisores comunes a a y b.

En efecto, si c 2 Z es otro divisor común de a y de b, entonces c|a y c|b por teoremase concluye c|ma + nb cualesquiera que sean m y n enteros. En particular, c|sa + tbluego c|dDe 1. y 2. se sigue que d = m.c.d.(a, b).

Unicidad. En efecto, supongamos que hubiese dos máximo común divisor de a y b,

digamos d1 y d2. Entonces, d1 = m.c.d.(a, b) y como d2 es divisor común de a y b

entonces d2|d1. Por otro lado d2 = m.c.d.(a, b) y como d1 es divisor común de a y bse tiene d1|d2 por teorema se concluye que d1 = d2 ya que por definición d1 y d2 sonmayores que cero.

Corolario 17 : Si d es el máximo común divisor de a y b, entonces d es el menor

entero positivo que puede escribirse como combinación lineal de a y b con coeficientes

enteros.

Demostración : Se sigue directamente del teorema anterior.

Proposición 18 : Si d es el menor entero positivo que puede escribirse como combi-

nación lineal con coeficientes enteros de dos enteros dados a y b y es divisor común

de ambos, entonces d es el máximo común divisor de a y de b.

Demostración : En efecto, supongamos que d = pa + qb, con p, q ∈ Z y d|a y d|bEntonces:

1 d es divisor de a y de b. Directamente de la hipótesis.

2 d es el máximo. En efecto, sea c otro de los divisores comunes de a y b. Entonces,

c|a y c|b por lo que por teorema c| ( pa + qb), con p y q enteros, luego c|d. Por lo tanto,d = m.c.d.(a, b).


13/160


Corolario 19 : Si a y b son dos enteros distintos de cero, entonces m.c.d.(a, b) = 1

si, y sólo si existen dos números enteros p y q tales que pa + qb = 1.Demostración : “Sólo si.” Si m.c.d.(a, b) = 1, entonces por el corolario anterior,

pueden encontrarse dos números enteros p y q tales que pa + qb = 1,

Demostración “Si.” Sean p y q dos números enteros tales que pa + qb = 1. Como

1 es divisor de cualquier número entero, 1|a y 1|b. Se aplica la proposición anterior yllegando a que m.c.d.(a, b) = 1.

Ejemplo 20 : Demuestre que si m.c.d.(a, b) = 1 y m.c.d.(a, c) = 1, entonces m.c.d.(a,bc) =

1.

Solución 21 : Aplicando el corolario se tiene: m.c.d.(a, b) = 1 si y sólo si ∃ p, q ∈ Ztales que pa + qb = 1. Igualmente m.c.d. (a, c) = 1 ∃r, s ∈ Z tal que ra + sc = 1y multiplicando término a término, se sigue que ( pa + qb)(ra + sc) = 1 si y solo si

a( pra + psc + qrb) + (qs)bc = 1, con pra + psc + qrb y bc enteros. Aplicando de nuevo

el corolario anterior se llega a que m.c.d.(a,bc) = 1

Teorema 22 : Sean a y b dos números enteros. Entonces:

(i) Si m.c.d.(a, b) = d, entonces m.c.d.(a

d, b

d) = 1

(ii) m.c.d.(ka,kb) = k · m.c.d.(a, b), ∀k ∈ Z+

Demostración : (i) Si m.c.d.(a, b) = d, entonces m.c.d.(a

d ,

b

d) = 1. En efecto,d = m.c.d.(a, b) entonces ∃ p, q ∈ Z tales que pa + qb = d (por corolario anterior), porlo tanto ∃ p, q ∈ Z tales que pa

d +

qb

d = p

a

d + q

b

d = 1 lo que implica por corolario

anterior que m.c.d.(a

d, b

d) = 1

(ii) m.c.d.(ka, kb) = k ·m.c.d.(a, b) , ∀k ∈ Z+. En efecto, suponga que m.c.d.(a, b) = d.Luego d = m.c.d.(a, b) por corolario anterior se tiene que ∃ p, q ∈ Z tales que pa+qb = dpor lo que ∃ p, q ∈ Z tales que pka + qkb = kd. Veamos que kd es el máximo comúndivisor de ka y kb.

1. Veamos que kd es divisor de ka y kb. En efecto, d = m.c.d.(a, b) luego d|a y porconsiguiente kd|ka. Análogamente d|b y por tanto kd|kb2. Sea c cualquier otro divisor común de ka y kb. Luego c|ka y c|kb. Por teorema setiene que c| pka+qkb con p, q ∈ Z, luego c|kd. Se concluye entones que m.c.d.(ka,kb) =k · d = k · m.c.d.(a, b)

Ejercicio 23 : 1 Demostrar que si m.c.d.(a, b) = 1, entonces m.c.d.(a + b, a − b) = 1ó 2

2. Demuestre que d = m.c.d.(a, b) si, y sólo si d|a , d|b y m.c.d.( ad

, b

d) = 1.

3. Hallar dos números cuyo cociente es igual a 33

21 y su máximo común divisor sea 90


14/160


Ejemplo 24 : Los lados de un rectángulo vienen dados por números enteros positivos.

¿Cuál será la longitud de dichos lados para que el perímetro y la superficie se expresen con el mismo número?

Solución 25 : Sean x e y los lados del rectángulo, entonces el perímetro y la superficie

del mismo son respectivamente 2x + 2y y xy, luego para que se cumpla la condición del

enunciado, ha de ser 2x + 2y = xy. Observe que 2x + 2y = xy o tambien 2x−xy = −2yo mejor aún x(2 − y) = −2y, de donde x = −2y

2 − y por lo tanto x = 2y − 4 + 4

y − 2 que

escrito de otra manera se vería como x = 2 + 4

y − 2 , como x ∈ Z+, entonces

4

y − 2 ∈Z+. Consecuentemente y − 2 ha de ser divisor de 4, por tanto, y − 2 = 1 e y = 3 :x = 6, ó y − 2 = 2 e y = 4 : x = 4, ó y − 2 = 4 e y = 6 : x = 3.Definición 26 : Sean a y b dos enteros, se dice que a y b son primos entre sí o primos

relativos, si se satisface que el m.c.d.(a, b) = 1.

Ejemplo 27 : Se han plantado árboles igualmente espaciados en el contorno de un

campo triangular cuyos lados miden 144m., 180m. y 240m. respectivamente. Sabiendo

que hay un árbol en cada vértice y que la distancia entre dos árboles consecutivos está

comprendida entre 5 y 10 metros. Calcular el número de árboles plantados.

Solución 28 : Sea d la distancia entre dos árboles consecutivos. Entonces d es un divisor de 144, 180 y 240 luego ha de ser divisor de su máximo común divisor. Se

debe entonces calcular el máximo común divisor de 144, 180 y 240. Los conjuntos de

divisores positivos de los tres números son:

D144 = {1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 9, 18, 36, 72, 144}D180 = {1, 2, 4, 3, 6, 12, 9, 18, 36, 5, 10, 20, 15, 30, 60, 45, 90, 180}D240 = {1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 5, 10, 20, 40, 80, 15, 30, 60, 120, 240}

Por lo tanto, el conjunto de los divisores comunes a los tres números será:

D144 ∩ D180 ∩ D240 = {1, 2, 4, 3, 6, 12}

Note que m.c.d.(144, 180, 240) = 12. Como d ha de ser un divisor de 12 y como éstos

son 1, 2, 3, 4, 6 y 12, y d ha de estar comprendido entre 5 y 10, se sigue que d = 6.

Por lo que el número total de árboles plantados es N = 144

6 +

180

6 +

240

6 = 94

Teorema 29 : (Algoritmo de Euclides) El máximo común divisor entre dos números

a y b es igual a tomar el de la división posible entre los dos números y éste máximo

común divisor es el mismo que el máximo común divisor del divisor y el resto.


15/160


Demostración : Sean a y b dos números enteros cualesquiera con b = 0. Por el

teorema de existencia y unicidad del cociente y resto, existen dos números enterosúnicos, q y r tales que a = bq + r con 0 ≤ r < b. veamos que el máximo común divisorde a y b es el mismo que el de b y r. En efecto, sea d = m.c.d.(a, b). Entonces, d es un

divisor común de a y de b, luego por teorema d|a + (−q )b. es decir, d|r. Por lo tanto,d|b y d|r. Por otro lado se debe hallar cual es el máximo de los divisores comunes deb y r. Si c es otro divisor común a b y r, nuevamente por teorema c|bq + r, esto esc|a, luego c|a y c|b y por consiguiente ha de dividir al máximo común divisor de a yb, es decir, c|d. Como d|b, d|r y c|d se obtiene que m.c.d.(b, r) = d, y, por lo tantom.c.d.(a, b) = m.c.d.(b, r).

Nota 30 : El algoritmo de Euclides repite el proceso anterior hasta que el residuon-ésimo sea cero y por tanto m.c.d.(a, b) = m.c.d.(rn−1, 0) = rn−1.

Ejemplo 31 :Hallar el máximo común divisor de 1369 y 2597 y expresarlo como una

combinación lineal con coeficientes enteros de ellos.

Solución 32 : Haciéndolo de forma práctica relizando los cálculos en la siguiente

tabla se tiene:

2597 = 1369 + 1228

1369 = 1228 + 141

1228 = 8 (141) + 100

141 = 100 + 41

100 = 2(41) + 18

41 = 2(18) + 5

18 = 3(5) + 3

5 = 3 + 2

3 = 2 + 1

2 = 2 (1)

luego, m.c.d.(2597, 1369) = 1

Para hallar los coeficientes de la combinación lineal pedida, se hacen las mismas “cuen-

tas” pero hacia atrás.

1 = 3 − 2 · 12 = 5 − 3 · 1 de aquí 1 = 3 − (5 − 3 · 1)1 = (−1) · 5 + 2 · 3

1 = (−1) · 5 + 4 · 33 = 18 − 5 · 3 de aquí 1 = (−1)5 + 4(18 − 5 · 3) = 4 · 18 + (−5) · 5


16/160


1 = 4 · 18 + (−5) · 55 = 41 − 18 · 2

de aquí 1 = 4·

18 + (

−5)(41

−18

·2) = (

−5)

·41 + 14

·48

1 = (−5) · 41 + 14 · 1818 = 100 − 41 · 2 de aquí 1 = (−5) · 41 + 4(100 − 41 · 2) = 14 · 100 − 13 · 41

1 = 14 · 100 − 13 · 4141 = 141 − 1 · 100 de aquí 1 = 16 · 100 − 39(141 − 1 · 100) = (−39) · 141+55 · 100

1 = (−39) · 141 + 55 · 100100 = 1228 − 8 · 141 de aquí 1 = (−39)·141+55(1228−8·141) = 55·1228−479·141

1 = 55

·1228

−479

·141

141 = 1369 − 1 · 1228 de aquí 1 = 55·1228−479(1369−1·1228) = (−479)·1369+534·1228

1 = (−479) · 1369 + 534 · 12281228 = 2597 − 1 · 1369 de aquí 1 = (−479)·1369+534(2597−1·1369) = 534·2597+(−1013)

Observe que esta expresión no es única ya que para cualquier k ∈ Z, se tiene:

1 = 534 · 2597 + (−1013) · 1369= 534 · 2597 + (−1013) · 1369 + (−1369k) · 2597 + (2597k) · 1369= (534 − 1369k) · 2597 + (−1013 + 2597k) · 1369

Note también que:

m.c.d.(−1369, 2597) = 1; m.c.d.(1369, −2597) = 1; m.c.d.(−1369, −2597) = 1

y en tales casos las combinaciones lineales con coeficientes enteros estarían dados por:

1 = 1013 · (−1369) + 534 · 25971 = (−1013) · 1369 + (−534) · (−2597)1 = 1013 · (−1369) + (−534) · (−2597)

Ejemplo 33 : Calcular el máximo común divisor entre 231 y 1820. Expresar dichonúmero como una combinación lineal con coeficientes enteros.

Solución 34 :

1820 = 7 · 231 + 203231 = 1 · 203 + 28203 = 7 · 28 + 7

28 = 4 · 7


17/160


Luego m.c.d.(1820, 231) = 7

Calculando los coeficientes que construyen dicha combinación lineal se sigue el procesoinverso:

7 = 203 − 28 · 728 = 231 − 203 · 1 de aquí que 7 = 203 − (231 − 203 · 1)7 = (−7)231 + 8 · 203

7 = (−7) · 231 + 8 · 203203 = 1820 − 231 · 7 de aquí que 7 = (−7)·231+8(1820−231·7) = 8·1820+(−63)·231

Ejemplo 35 : ¿Cuál es el mayor número que al emplearlo como divisor de 68130 y

107275 origina como residúos a 27 y 49, respectivamente?

Solución 36 : Considere a n el número buscado. Luego, 68130 = nq + 27 y 107275 =

np + 49 por lo tanto:

68103 = nq, con q ∈ Z y 107226 = np, con p ∈ Z

Lo que implica que:

n|68103 y n|107226Por lo que

n = m.c.d.(68103, 107226) = 1449

Ejemplo 37 : Hallar dos números cuyo máximo común divisor es 7 y tales que los

cocientes obtenidos en su determinación por el algoritmo de Euclides son, en orden

inverso, 7, 2, 3 y 36.

Solución 38 : Si los números buscados son a y b se tiene:

a = 36 · b + r136 = 3 · r1 + r2r1

= 2·

r2

+ r3

r2 = 7 · r3

Así que m.c.d. (a, b) = r3 = 7. Por lo tanto:

r2 = r3 · 7 + 0 de donde r2 = 7 · 7 = 49r1 = r2 · 2 + r3 de donde r1 = 49 · 2 + 7 = 105

b = r1 · 3 + r2 de donde b = 3 · 105 + 49 = 364a = b · 36 + r1 de donde a = 364 · 36 + 105 = 13209


18/160


Definición 39 : Dados dos números enteros a y b, se dice que el entero m = 0 es un

múltiplo común de ambos, si es múltiplo de a y es múltiplo de b, es decir, m = 0, es múltiplo común de a y b si y sólo si a|m y b|m

Definición 40 : (Mínimo Común Múltiplo) El mínimo común múltiplo de dos números

enteros es el mínimo del conjunto de los múltiplos positivos comunes a ambos ordenado

por la relación de divisibilidad. Notaremos por m.c.m.(a, b) al mínimo común múltiplo

de los enteros a y b.

Teniendo en cuenta la definición de mínimo de un conjunto ordenado, si llamamos M

al conjunto de todos los múltiplos positivos comunes a a y b, se tiene:

m = m.c.m.(a, b) ⇐⇒ a|m y b|mm = min(M )

⇐⇒ a|m y b|m∀c con c ∈ M entonces m|c⇐⇒

a|m y b|m∀c con c ∈ M si a|c y b|c entonces m|c

Ejemplo 41 : Calcular el mínimo común múltiplo de 12 y 15.

Solución 42 : Aplicando la definición directamente. Los conjuntos de múltiplos pos-

itivos de 12 y 15 son, respectivamente:

M 12 = {12, 24, 36, 48, 60, 72, 84, 96, 108, 120,...}M 15 = {15, 30, 45, 60, 75, 90, 105, 120,...}

luego el conjunto de todos los múltiplos comunes a ambos es:

M 12 ∩ M 15 = {60, 120, 180, 240,...}

luego el mínimo de este conjunto es 60, de donde m.c.m.(12, 15) = 60

Definición 43 : (Mínimo Común Múltiplo de Varios Números) Sean a1, a2,...,annúmeros enteros. Llamaremos mínimo común múltiplo de ellos al múltiplo común

m > 0 tal que cualquier otro múltiplo común de dichos números es también múlti-plo de m. Se denotará por m.c.m.(a1, a2, ...,an) al mínimo común múltiplo de dichos

números.

Proposición 44 : Sean a y b dos números enteros positivos. Se verifica que m.c.m.(ka,kb) =

k · m.c.m.(a, b) , ∀k ∈ Z+

Demostración : i. Sea m = m.c.m. (a, b). Entonces, a|m y por consiguiente ka|km(porque?), análogamente b|m y por consiguiente kb|km, es decir, km es múltiplo común


19/160


de ka y kb.

ii. Supongamos que c es otro múltiplo común de ka y kb. Entonces, ka|c luego ∃q 1 ∈ Ztal que c = kaq 1 lo que implica que

c

k = aq 1 o mejor aún a| c

k. De forma análoga kb|c

luego ∃q 2 ∈ Z tal que c = kbq 2 lo que implica que ck

= bq 2 o mejor aún b| ck

. o sea, c

k es

un múltiplo común de a y b, luego también ha de serlo de su míınimo común múltiplo,

m, luego m| ck

equivale a decir que ∃q ∈ Z tal que ck

= mq o sea c = kmq esto es km|cy por lo tanto, c es múltiplo de km.

Por i. y ii., se concluye que m.c.m.(ka,kb) = km = k · m.c.m.(a, b)

Proposición 45 : Para cualquier par de números enteros positivos se verifica que

el producto del máximo común divisor y de su mínimo común múltiplo es igual al

producto de los dos números.

Demostración : Por teorema se demostró que si d = m.c.d.(a, b), entonces, a

d y

b

d son primos entre sí, luego m.c.m.

a

d, b

d

=

a

d · b

d.

Note que m.c.d.(a, b) · m.c.m.(a, b) = d · d · m.c.m.

a

d, b

d

= d · d · a

d · b

d = a · b

Ejemplo 46 : Sean a y b dos números enteros distintos de cero. Demostrar que las

siguientes condiciones son equivalentes:

a|b ⇐⇒ m.c.d.(a, b) = |a| ⇐⇒ m.c.m.(a, b) = |b|

Solución 47 : Veamos que a|b =⇒ m.c.d.(a, b) = |a| : En efecto, si a divide a b,entonces a es un divisor común de a y b y además cualquier otro divisor común de

a y de b divide a a, luego si a > 0, entonces m.c.d.(a, b) = a. Si a < 0, entonces

m.c.d.(a, b) = m.c.d.(−a, b) = −a lo que implica que el m.c.d.(a, b) = |a|.Ahora veamos que m.c.d.(a, b) = |a| =⇒ m.c.m.(a, b) = |b|. En efecto, suponga que m.c.d.(a, b) = |a|, entonces por la proposición anterior,

m.c.d.(a, b) · m.c.m.(a, b) = |a · b| esto es |a|·m.c.m.(a, b) = |a| · |b|de donde se concluye que m.c.m.(a, b) = |b|.Por último veamos que m.c.m.(a, b) = |b| =⇒ a|b. En efecto, si m.c.m.(a, b) = |b|,entonces, de la definición de mínimo común múltiplo se sigue que |b| es un múltiplode a, es decir a divide a |b|, luego a|b.

Ejemplo 48 : Determinar el máximo común divisor y el mínimo común múltiplo de

2689 y 4001.


20/160


Solución 49 : Mediante el algoritmo de Euclides se tiene que:

4001 = 1 · 2689 + 13122689 = 2 · 1312 + 651312 = 20 · 65 + 12

65 = 5 · 12 + 512 = 2 · 5 + 2

5 = 2 · 2 + 12 = 2 · 1

Por lo tanto m.c.d.(4001, 2689) = 1 y por lo tanto m.c.m.(4001, 2689) = 4001·2689 =10758689

Ejercicio 50 : del algoritmo de la división llegue a que el máximo común divisor como

una combinación lineal con coeficientes enteros de 4001 y 2689 es

1 = −1117 · 4001 + 1662 · 2689

Ejemplo 51 :El mínimo común múltiplo de los términos de una fracción es 340.

Determinar la fracción sabiendo que no altera su valor si se suma 20 al numerador y

25 al denominador.

Solución 52 : Por hipótesis se tiene que a

b =

a + 20

b + 25 luego a (b + 25) = b (a + 20) o

mejor aún 25a = 20b esto es

a

db

d

=

20

525

5

(esto al dividir por su m.c.d). Por lo tanto a

d = 4

y b

d = 5. Como m.c.d.(a, b) · m.c.m.(a, b) = a · b, se obtiene entonces que d · 340 = a · b.

Note que: 340

a =

b

d = 5 de donde a = 68 ó también

340

b =

a

d = 4 de donde b = 85 se

consigue entonces que dicha fracción es 68

85

.

Ejemplo 53 : Hallar dos números, sabiendo que su suma es 240 y su mínimo común

múltiplo es 1768.

Solución 54 :Sean a y b tales números y sea d su máximo común divisor. Si llamamos

a′ = a

d y b′ =

b

d entonces m.c.d.(a′, b′) = 1 y m = m.c.m.(a′, b′) = a′ · b′. Sea m =

m.c.m.(a, b), entonces a′·b′ = ad

· bd

= m

d por lo tanto d ·a′ ·b′ = 1768 y d ·a′+d·b′ = 240,

luego d · a′ · b′d · a′ + d · b′ =

1768

240 =

221

30 =

a′ · b′a′ + b′

. Note que a′ · b′ y que a′ + b′ son primos


21/160


relativos, ya que si c es el máximo común divisor de a′ · b′ y a′ + b′, entonces c|a′b′ y c|a

′

+ b′

y también c| (a′

)2

+ a′

·b′

por lo que c| (a′

)2

. y como m.c.d.(a′

, b′

) = 1, existirán dos números enteros p y q tales que pa′ + qb′ = 1. Luego, p (a′)2 + qa′b′ = a′ y como

consecuencia c|a′ y de igual forma como c|a′+b′ entonces c|b′ de donde m.c.d.(a′, b′) =c = 1. Por lo tanto m.c.d.(a′ · b′, a′ + b′) = 1. Con lo cual se concluye que a′ · b′ = 221y que a′ + b′ = 30 de aquí que:

a′2 − 30a′ + 221 = 0

de donde a′ = 17 y b′ = 13 ó a′ = 13 y b′ = 17. Como d · a′ + d · b′ = 240 entonces d = 8 y por consiguiente a = 136 y b = 104 que son los números buscados.

Definición 55 : (Ecuación Diofántica) Una ecuación diofántica es una ecuación lin-

eal con coeficientes enteros y que exige soluciones enteras.

Teorema 56 : Sean a, b y c tres números enteros. La ecuación lineal ax + by = c

tiene solución entera si, y sólo si el máximo común divisor de a y b divide ac.

Demostración : “Sólo si”. En efecto, suponga que los enteros x0 e y0 son solución

de la ecuación ax + by = c, es decir, ax0 + by0 = c. Ahora, si d = m.c.d.(a, b), entonces

d = m.c.d.(a, b) y por lo tanto d|a y d|b, luego d|ax0 + by0 con lo cual se concluye qued|c

“Si”. Recíprocamente, suponga que d = m.c.d.(a, b) es divisor de c. Entonces, el

m.c.d.(a, b) = d, por lo tanto m.c.d.

a

d, b

d

= 1, Luego ∃ p, q ∈ Z tales que a

d p+

b

dq = 1.

Note que a

dcp +

b

dcq = c siendo

c

d entero ya que, por hipótesis, d es divisor de c. Si se

toma x0 = cp

d y y0 =

cq

d se tendría que ax0 + by0 = c por lo que los enteros x0 e y0

son solución de la ecuación ax + by = c. A la solución encontrada se llamará solución

particular del sistema.

Ejemplo 57 : Encontrar una solución para la ecuación diofántica 525x + 100y = 50

Solución 58 : Calculamos el m.c.d. (525, 100) que mediante el algoritmo de Euclides

dá como resultado:

525 = 5 (100) + 25

100 = 4( 25)

luego m.c.d.(525, 100) = 25 y como 25 divide a 50, el teorema anterior asegura la

existencia de solución entera para la ecuación. Siguiendo el método inverso en la

demostración del algoritmo de Euclides, se hallan los coeficientes de la combinación


22/160


lineal del m.c.d. (525, 100) obteniendo que 25 = 1 · 525+(−5) · 100. Por tanto, los coe-

ficientes son p = 1 y q = −5 y según el citado teorema una solución para la ecuación sería x0 =

cp

d y y0 =

cq

d donde c es el término independiente de la ecuación y d el

máximo común divisor de los coeficientes de x e y. Como consecuencia x0 = 50 · 1

25 = 2

y y0 = 50 · (−5)

25 = −10

Teorema 59 : (Solución general de las ecuaciones Diofánticas) Sean a, b y c tres

números enteros no nulos tales que el máximo común divisor de a y b divide ac.

Entonces la solución general de la ecuación ax + by = c es x = x0 + kb

d y y =

y0

−k

a

d ·donde x0 e y0 es una solución particular de la misma y k es cualquier número

entero.

Demostración : Sea d el máximo común divisor de a y b. Por hipótesis d divide a

c y por el teorema anterior se asegura la existencia de una solución particular x = x0 e

y = y0 para el sistema. Entonces, ax0 + by0 = c. Dividiendo ahora ambos miembros de

esta ecuación por el máximo común divisor de a y b, se tiene, a

dx0 +

b

dy0 =

c

d siendo

c

d

entero y a

d, b

d primos relativos entre sí, luego el máximo común divisor de ambos es 1 y

como 1 divide a c

d , el teorema anterior asegura la existencia de una solución particular

x1, y1 para esta ecuación, por lo tanto

a

d x1 +

b

dy1 =

c

d. Obserbe que ya se tiene quea

dx0 +

b

dy0 =

c

d y que

a

dx1 +

b

dy1 =

c

d por consiguiente

a

d (x1 − x0) + b

d (y1 − y0) = 0

o mejor aún a

d (x1 − x0) = bd (y0 − y1) lo que implica que

b

d|ad

(x1 − x0) y como ady

b

d son primos relativos entre sí, entonces

b

d| (x1 − x0) por l tanto ∃k ∈ Z tal que

x1 − x0 = k · bd

por lo que x1 = x0 + k · bd

. Sustituyndo el valor de x1 − x0 ena

d (x1 − x0) + b

d (y1 − y0) = 0 se consigue que a

d · k · b

d +

b

d (y1 − y0) = 0 se llega a que

a

d · k + y1 − y0 = 0 de donde y1 = y0 − k · a

d.

Por último observe quexl e y1 es solución de la ecuación ax + by = c, puesto que,

ax1 + by1 = a

x0 + k · b

d

+ b

y0 − k · a

d

= ax0 + ak · b

d + by0 − bk · a

d

= ax0 + by0 = c (por hoipótesis)

luego, x = x0 +k · bd

y y = y0−k · ad

es solución de la ecuación ax + by = c cualquiera

que sea k ∈ Z . La solución anterior se llama solución general de dicha ecuación.

Ejemplo 60 : En el ejemplo para la ecuación diofántica 525x + 100y = 50 se obtuvo

que x0 = 2 y y0 = −10 por lo tanto luego una solución general está dada por:


23/160


x = 2 + k100

25 = 2 + 4k y y = −10 − k · 525

25 = −10 − 21k, siendo k cualquier

número entero.

Ejemplo 61 : Calcular las soluciones enteras de la ecuación diofántica 66x +550y =

88

Solución 62 : Se debe demostrar primero que la ecuación admite solución entera.

Primero se debe calcular el máximo común divisor entre 66 y 550 por el algoritmo de

Euclides se tiene que:

550 = 8 (66) + 22

66 = 3 (22)

por lo que m.c.d.(66, 550) = 22 y como 22 divide a 88, término independiente de la

ecuación, por teorema anterior se sigue que la ecuación propuesta admite una solución

particular x = x0, y = y0. Veamos cual es la ecuació particular. Desde el algoritmo

de Euclides se llega a que 22 = (−8) · 66 + 1 · 550 luego, x0 = 88 · (−8)22

= 32 y

y0 = 88 · 1

22 = 4 es una solución particular de la ecuación. Por último al calcular

ahora la solución general se consigue que si una solución particular de la misma es

x0 = −32 y y0 = 4, entonces la solución general es x = −32 + k · 55022

= −32+25 · ky y = 4

−k

· 66

22

= 4

−3

·k siendo k cualquier número entero.

Ejemplo 63 : Una persona va a un supermercado y compra 12 litros de leche, unos

de leche entera y otros de deslactosada, por 1200 pesos. Si la leche entera vale 30

pesos. más por litro que la deslactosada y ha comprado el mínimo posible de leche

deslactosada ¿Cuántos litros habrá comprado de cada una?

Solución 64 : Si x el número de litros de leche entera, entonces 12 − x es el númerode litros de leche delactosada y si y es el precio de la leche delactosada, entonces el

precio de la leche entera será y + 30. Como el precio total de la leche comprada es

1200, se tiene que:

x(y + 30) + y(12 − x) = 1200Luego

xy + 30x + 126 − xy = 1200esto es 30x + 12y = 1200. Primero se debe ver si dicha ecuación admite soluciones

enteras. Por tanto se debe hallar el máximo común divisor entre 30 y 12. Usando el

algoritmo de Euclides se llega a que:

30 = 2 · (12) + 612 = 2 · (6)


24/160


25/160


algoritmo de Euclides.

990 = 11 · (84) + 6684 = 1 · (66) + 1866 = 3 · (18) + 1218 = 1 · (12) + 612 = 2 · (6)

Así que el m.c.d. (990, 84) = 6. Luego 84x +990y = c tiene solución entera si y sólo si

6|c y esto sucede si y sólo si ∃q ∈ Z tal que c = 6 · q. Y como 10 < c


26/160


y y0 = 5 · 1

1 = 5 y la solución general está dada por x = −5 + 9k y y = 5 − 8k

siendo k cualquier número entero.

Ejemplo 70 : Un granjero tiene un cesto de naranjas. Haciendo grupos de 3 sobran

2 y haciendo grupos de 4 sobran 3. Hallar el número de naranjas que contiene el cesto

sabiendo que el número de naranjas está entre 100 y 110.

Solución 71 : Sean x e y los números de grupos de tres y cuatro naranjas, respectiva-

mente. Si N es el número total de naranjas que contiene el cesto, tendremos 3x+2 = N

y 4y + 3 = N luego restando miembro a miembro, se obtiene 3x − 4y = 1. Note que esta ecuación tiene soluciones enteras ya que como m.c.d.(3, 4) = 1 y 1 divide a 1, que

es el término independiente de la ecuación, resulta que la misma admite soluciones enteras. Por lo tanto una solución particular estaría dada por 1 = (−1)·3 + (−1)(−4)luego,x0 =

1 · (−1)1

= −1 y y0 = 1(−1)1

= −1 la cual es una solución partic-ular de la ecuación. Ahora la solución general x = −1 + −4 · 1 · k = −1 − 4k y y = 1 − 3 · 1 · k = −1 − 3k, siendo k cualquier número entero. Calculando, finalmente,cuantas naranjas hay en el cesto se consigue que 3x + 2 = N y como x = −1 − 4kentonces 3(−1 − 4k) + 2 = N de donde N = −12k − 1 y como 100 ≤ N ≤ 110 se consigue que 100 ≤ −12k − 1 ≤ 110 con lo que se obtiene que 101

12 ≤ −k ≤ 111

12 o

mejor aún −

111

12 ≤ k

≤ −101

12 lo que implica que

−9, 25

≤ k

≤ −8, 42, y como k es un

número entero se concluye que k = −9, de donde N = −12(−9) − 1 = 108 − 1 = 107naranjas

Ejemplo 72 : Hallar el menor número de cuatro cifras que dividido por 4, 7 y 11 da

resto 3, y que dividido por 13 da resto 1.

Solución 73 : Sea n dicho número, entonces por el algoritmo de la división existen

q 1, q 2 y q 3 tales que n = 4 ·q 1 + 3 luego n −3 = 4 ·q 1 igualmente n = 7 ·q 2 + 3 de donde n−3 = 7 ·q 2 y n = 11·q 3+3 de donde n−3 = 11·q 3, luego 4|n−3 , 7|n−3 y 11|n−3,

es decir, n − 3 es un múltiplo común a 4, 7 y 11, por tanto ha de ser múltiplo de su mínimo común múltiplo y al ser m.c.m.(4, 7, 11) = 4·7·11 = 308 entonces 308|n − 3luego debe existir un entero x tal que n − 3 = 308x, esto es n = 308x + 3. Por otrolado y también por el algoritmo de la división, existe un entero y tal que n = 13y + 1,

por tanto, n = 308x + 3 y n = 13y + 1 de donde 308x − 13y = −2. Se debe ver si esta ecuación admite soluciones enteras. Calculando el máximo común divisor de 308


27/160


y 13 por el algoritmo de Euclides se obtiene que:

308 = 23 · (13) + 913 = 1 · (9) + 4

9 = 2 · (4) + 14 = 4 · (1)

luego m.c.d.(308, 13) = 1 y 1 divide a −2, que es el término independiente de la ecuación, luego tiene soluciones enteras. Ahora buscando los coeficientes enteros de

1 expresado como combinación lineal de 308 y −13, se tiene que 1 = 9 − 2 · 4 y 4 = 13 − 1 · 9 de donde 1 = 9 − 2 · (13 − 1 · 9) = 2 · (−13) + 3 · 9, por otro ladocomo 1 = 2 · (−13) + 3 · 9 y 9 = 308 − 23 · 13 entonces 1 = 2(−13) + 3 · [308 +23 · (−13)] = 3 · 308 + 71 · (−13) así que 3 · 308 + 71 · (−13) = 1, cuya solución particular es x0 =

(−2) · 31

− 6 y y0 = (−2) · 711

− 142. Ahora la solución general

es x = −6 + k · (−13)1

= −6 − 13k y y = −142 − k · 3081

= −142 − 308k, donde k es cualquier número entero. Por último calculando finalmente el número pedido.

n = 308x + 3 y x = −6 − 13k de donde n = 308(−6 − 13k) + 3 = −1845 − 4004k. y al ser n > 0, se tiene que −1845 − 4004k > 0 de donde k


28/160


Así que m.c.d.(19, 99) = 1 y como 1 divide a 1990, que es el término independiente

de la ecuación, se concluye que ésta tiene soluciones enteras. Ahora calculando una solución particular, expresando 1 como combinación lineal de 19 y 99 usando hacia

atrás los cálculos hechos en el algoritmo de Euclides, se tiene que 1 = 4 − 1 · 3 y como3 = 19 − 4 · 4 se consigue que 1 = 4 − 1 · (19 − 4 · 4) = −1 · 99 + 5 · 4, ahora como1 = −1 ·99+5 ·4 y 4 = 99 −5 ·19, entonces 1 = −1 ·19+5 ·(99−5 ·19) = 5 ·99−26 ·19esto es 5 · 99 − 26 · 19 = 1. Por otro lado y0 = 1900 · (−26)

1 = −49400 y z0 =

1900·51

= 9500. Note que la solución general es: y = −49400 + k · 991

= −49400 + 99ky z = 9500 − k · 19

1 = 9500 − 19k, siendo k cualquier número entero. Finalmente,

cuantos animales de cada clase compró? Teniendo en cuenta que adquirió animales

de las tres clases, se tiene que y > 0 luego −49400 + 99k > 0 de donde 99k > 49400esto es k > 498,9 y z > 0 por lo que 9500 − 19k > 0 luego 19k < 9500 esto es k < 500, con lo cual se concluye que k = 499. Así pues y = −49400 + 99 · 499 = 1;z = 9500−19·499 = 19, y al ser x +y +z = 100 se consigue que x = 100−1−19 = 80,por tanto compró 80 pollos, 1 conejo y 19 terneros

Observación 76 : Note que si a es cualquier número entero mayor que 1, entonces

a = a · 1, con 1 ∈ Z, es decir, a es un divisor de a. a = 1 · a, con a ∈Z, es decir, 1 es un divisor de a, luego todo número entero a > 1 tiene al menos dos divisores, el 1 y

el propio a.

Definición 77 : (Número primo) Se dice que el número entero p > 1 es un número

primo si los únicos divisores positivos que posee son 1 y p. Si un número entero no es

primo se dirá entonces que es compuesto.

Nota 78 : De la definición de número primo se sigue que p es primo si, y sólo si es

imposible escribir p = ab con a, b ∈ Z y 1 < a, b < p.

Observación 79 : Que dos números enteros a y b, se dicen que son primos entre

sí o que son primos relativs, cuando el máximo común divisor entre ambos es 1. La

definición anterior admite generalización a una familia de números enteros a1, a2, ...,

an. Dichos números serán primos relativos, cuando m.c.d.(a1, a2, ......, an) = 1

Ejemplo 80 : Demuestre que cualquiera que sea n ∈ Z, los números 3n + 11 y 2n + 7son primos relativos

Solución 81 : Observe que 2(3n+11)+(−3)(2n+7) = 6n+22−6n−21 = 1. Luego por el corolario antes visto (¿Que dice ese corolario?), se sigue que m.c.d.(3n+11, 2n+7) =

1. Por lo tanto, ambos números son primos relativos.


29/160


Proposición 82 : Todo número compuesto posee, al menos, un divisor primo.

Demostración : Se debe probar que si un número entero a es compuesto, entonces

tiene, al menos, un divisor primo. Usando reducción al absurdo, se supone que la

proposición anterior es falsa o lo que es igual que su negación es verdadera, o sea, el

número entero a es compuesto y, sin embargo, no tiene divisores primos. Entonces, el

conjunto

C =

n ∈ Z+ : n > 2, compuesto y sin divisores primoses no vacío ya que, al menos, a ∈ C . Pues bien, como C es un subconjunto no vacío deZ+, por el principio del buen orden tendrá un primer elemento m. Entonces, m ∈ C

implica que m es compuesto y m no tiene divisores primos, por lo tanto ∃m1 con m1 =1, m1 = m y m1|m. y m1 no es primo, esto es ∃m1, compuesto m1|m y 1 < m1 < m.Note que, si m1 no tuviera divisores primos, entonces m1 ∈ C siendo m1 < m, lo cuales imposible ya que m es el mínimo de C , por lo tanto m1 ha de tener al menos un

divisor primo p. Pero p|m1 y m1|m luego p|m, es decir m tiene un divisor primolo cual es una contradicción ya que m ∈ C , es decir no tiene divisores primos. Comoconsecuencia, la suposición hecha es falsa y por lo tanto si un número es compuesto

entonces ha de tener al menos un divisor primo.

Teorema 83 : Existen infinitos números primos.

Demostración : Usando el método de reducción al absurdo, se supone lo contrario,

es decir que la cantidad de números primos existente es finita, suponga que sólo hay k

números primos, p1, p2, ......, pk. Pues bien, sea m el producto de todos ellos más 1, es

decir, m = ( p1 · p2 · ... · pk) + 1. Entonces, m = pi, i = 1, 2,...,k. es decir es distinto detodos los primos que existen, luego no puede ser primo, de aquí que sea compuesto y

por el teorema anterior tendrá al menos un divisor primo que es uno de los existentes,

o sea que existe p j con j ∈ {1, 2, ......, k} tal que p j |m y como p j | p1 · p2 · ... · pk, entoncesha de dividir a la diferencia de ambos, p j |m − p1 · p2 · ... · pk. Luego, p j|1. De aquí que p j = 1 ó p j =

−1 y esto es imposible ya que p j es primo. De la contradicción a la que

se llega se sigue que la suposición hecha es falsa y por tanto existen infinitos números

primos.

Ejemplo 84 : Demuestre que si p = 5 es un número primo impar, entonces p2 − 1 ó p2 + 1 es divisible por 10.

Solución 85 : Por el teorema de existencia y unicidad del resisuo, existen q y r

enteros únicos tales que p = 5q + r, con 0 ≤ r


30/160


Entonces p es impar y p +1 es par, por lo tanto 2| p+1. Note que r es impar ya que q es

par puesto que: Si r es impar entonces r + 1 es par si y sólo si 2|r +1, luego 2| p−5q +1y como 2| p + 1 entonces 2|5q, así que 2|q, o sea que q es par. Ahora como r es impar,entonces q es par. Tome q = 2q 1 con q 1 ∈ Z+, se tiene que p2 = 25q 2 + 10qr + r2,como q = 2q 1, entonces p2 = 100q 21 +20q 1r + r

2, de donde p2 − r2 = 10(10q 21 + 2q 1r),por consiguieente 10| p2 − r2, luego hay dos opciones para ,r = 1 ó r = 3. Note que si r = 1 y 10| p2 − r2, entonces 10 | p2 − 1, o si r = 3 y 10| p2 − r2, entonces 10| p2 − 9 y como 10 |p2 - 9 + 10 entonces 10| p2 + 1. Por otro lado si r es par, entonces q ha de ser impar, luego q = 2q 1 + 1 con q 1 entero no negativo. Luego p2 = 25q 2 + 10qr + r2,

y q = 2q 1 + 1, por lo tanto p2 = 100q 21 + 100q 1 + 25 + 20q 1r + 10r + r2 de donde

p2

−r2

−25 = 10(10q 2

1 + 10q 1 + 2q 1r + r), lo que implica que 10

| p2

−r2

−25. y hay

dos opciones, r = 2 ó r = 4. Entonces, para el caso r = 2 se tiene que 10| p2 − r2 − 25luego 10| p2 − 29,note que 10| p2 − 29+30 por lo que 10| p2 + 1. Ahora si r = 4 entonces 10| p2 − r2 − 25, esto es 10| p2 − 41 y como 10| p2 − 41+40 se tiene que 10| p2 − 1, luegoen cualquier caso p2 − 1 ó p2 + 1 es divisible por 10.

Teorema 86 : (La criba de Eratóstenes) Si un número entero mayor que 1 no tiene

divisores primos menores o iguales que su raíz, entonces es primo.

Demostración : Sea p entero estrictamente mayor que 1. Utilizamos el mótodo

de demostración por el contrarrecíproco, es decir que si p no es primo, entonces existe,al menos, un divisor primo de p menor o igual que su raíz. En efecto, si p no es primo,

entonces es compuesto y por la proposición anterior se tiene que al menos un divisor

primo a. Note que a es menor o igual que la raíz de p, ya que como a| p entonces p = aq ,con 1 < a < p, y q ∈ Z y es tal que 1 < q < p. Si se considera que a ≤ q , entoncesa2 ≤ aq lo qu implica que a2 ≤ p por lo que a ≤ √ p.con lo que se exhibe un divisorprimo de p menor o igual que la raíz de p.

Ejemplo 87 : Suponga que se quiere saber si el 9 es primo. Entonces, como √

9 = 3,

los números primos menores o iguales que 3 son el 2 y el propio 3. Como 2 no es

divisor de 9, pero 3 si lo es, luego 9 no es primo. Observe que al ser las raíces de 10, 11, 12, 13, 14 y 15 menores que 4, los números primos menores o iguales que ellas

son, también, 2 y 3, luego el criterio anterior puede emplearse para ver si estos números

son o no primos. En efecto, el 10 no es primo ya que 2 es divisor de 10. 2 y 3 no son

divisores de 11, luego el 11 es primo. El 12 no es primo ya que es múltiplo de 2. 13 no

es múltiplo de 2 ni de 3 por lo tanto es primo. El 14 no es primo ya que 2 es divisor de

14. El 15 no es primo ya que es múltiplo de 3. Por tanto, los números primos entre 2 y

24 son aquellos que no sean múltiplos de 2, ni de 3. Los números primos entre 2 y 48.

Aquellos que no sean múltiplos de 2, ni de 3, ni de 5. Los números primos entre 2 y


31/160


120. Aquellos que no sean múltiplos de 2, ni de 3, ni de 5, ni de 7. Así sucesivamente,

se podría encontrar todos los números primos.

Ejercicio 88 : Encontrar todos los números primos que hay entre el 1 y el 100.

Ejemplo 89 : Determine si el 811 es primo utilizando la Criba de Eratóstenes.

Solución 90 : √

811 = 28,5 y los números primos menores o iguales que 28,5 son

2, 3, 5, 7, 11, 13, 17, 19 ó 23 y dado que ninguno de estos números divide a 811, se con-

cluye que dicho número es primo.

Lema 91 : (Lema de Euclides) Si un número entero divide al producto de otros dos

y es primo con uno de ellos, entonces divide al segundo de los dos.

Demostración : Sean a, b y c tres números enteros, tales que a divida a b · c ysupponga que es primo relativo con b. Como m.c.d.(a, b) = 1, por corolario existen dos

números enteros p y q tales que pa + qb = 1. Por otra parte, si a divide a bc, como a

divide a a, entonces divide a cualquier combinación lineal con coeficientes enteros de

a y bc. En particular, a| ( pac + qbc) es decir, a|( pa + qb)c luego a|c.

Corolario 92 : Sea p un número entero mayor que 1. Las siguientes afirmaciones

son equivalentes:

(a) p es un número primo.(b) Si p divide al producto de dos números enteros, entonces divide a uno de los dos.

Demostración : ”(a) =⇒ (b)”. Se debe probar que para cualquier par de enteros,a y b, p es primo entonces ( p|ab solo si p|a ó p|b) o lo que es igual, p es primo y p|abentonces p|a ó p|b. Usando el método de reducción al absurdo se supone p es primoy p|ab y p ∤ a y p ∤ b, note que, si p no es divisor de a, como p es primo, el únicodivisor común de a y de p es 1, luego a y p son primos relativos, es decir, p|ab ym.c.d.(a, p) = 1. Aplicando el lema de Euclides se obtiene que p|b lo cual contradicela suposición hecha. si p no es divisor de b se hace igual al anterior.

”(b) =⇒ (a)”. Se debe demostrar que para cualquier par de enteros, a y b, ( p|abentonces p|a ó p|b) por tanto p es primo. Utilizaremos el método de demostración porel contrarecíproco, se debe demostrar que pueden encontrarse dos enteros a y b tales

que si p no es primo entonces p|ab y p ∤ a y p ∤ b. En efecto, si p no es primo, entonceses compuesto luego tendrá además del 1 y p, otro divisor a, es decir, existe a tal que

a| p. Pues bien, a| p si ∃b ∈ Z tal que p = ab siendo 1 < a < p y 1 < b < p. Además, p ∤ a ya que si p|a, entonces p|a y a| p por lo cual a = p lo cual es imposible. p ∤ b porla misma razón que p ∤ a. Luego se han encontrado dos enteros a y b tales que p|ab y p ∤ a y p ∤ b.


32/160


Corolario 93 : Si un número primo divide al producto de varios números enteros,

entonces ha de dividir a uno de ellos.

Demostración : En efecto, sea p un número primo y suponga que p|a1 · a2 · a3 ·... · an, entonces, p|a1 · (a2 · a3 · ... · an) , aplicando el corolario anterior p|a1 ó p|a2 ·a3 · ... · an. Si p|a1 , el corolario está demostrado, de lo contrario p|a2 · a3 · ... · anluego, p|a2·(a3 · a4 · ... · an) y, nuevamente por el corolario anterior, p|a2 ó p|a3·a4·...·an,Repitiendo el proceso un número finito de veces, se encuentra al menos un ai con

1 ≤ i ≤ n, tal que p|ai.

Ejemplo 94 : Demostrar que el número √

2 es irracional.

Ejemplo 95 Si √

2 fuese racional, entonces podría expresarse como un cociente de dos

enteros a y b primos entre sí (fracción irreducible), es decir, √

2 = a

b con m.c.d.(a, b) =

1. Note que al elevar al cuadrado ambos miembros de esta igualdad, resulta: 2 = a2

b2,

luego a2 = 2b2 lo que implica que 2|a · a, luego por corolario 2|a y consecuentemente,existe un entero q tal que a = 2q, luego a2 = 4q 2, pero a2 = 2b2 lo que implica que

2b2 = 4q 2 o lo que es lo mismo b2 = 2q 2, así que 2|b · b que por corolario se llega que 2|b. Por lo tanto 2 es un divisor común de a y b, lo cual es una contradicción ya que estos dos números son primos relativos, luego la suposición hecha es falsa y

√ 2 es

irracional.

Teorema 96 (Fundamental de la aritmética) Cualquier número entero n mayor que

1 puede escribirse de manera única como un producto de números primos.

Demostración :Sea a un número entero mayor que 1. Se debe probar inicialmente

que a puede escribirse como un producto de números primos y, posteriormente, se debe

probar que esa descomposición es única.

i) Descomposición: .Si a es primo, se considera el número como un producto de un

sólo factor y el teorema está demostrado. Si a no es primo, entonces es compuesto, y

por proposición se puede asegurar que tendrá, al menos un divisor primo. Sea p1 elmenor divisor primo de a. Entonces existirá un entero a1 tal que a = p1a1. Si a1 es

primo, entonces el teorema está demostrado. Si a1 no es primo entonces es compuesto

y aplicando de nuevo la proposición anterior tendrá al menos un divisor primo. Sea

p2 el menor divisor primo de a1, entonces existe un entero a2 tal que a1 = p2a2, con

a1 > a2 y por lo tanto a = p1 p2a2. Se repite el proceso un número finito de veces, y

se obtiene a1 > a2 > a3 >···> ak−1 con a = p1 · p2 · p3 · ... · pk−1 · ak−1, donde ak−1es primo o es la unidad, entonces tomando ak−1 = pk, si es primo o ak−1 = 1, se sigue

que a = p1 · p2 · p3 · ... · pk−1 ó a = p1 · p2 · p3 · ... · pk−1 · pk y a está escrito como un


33/160


producto de factores primos.

ii) Unicidad. Suponga lo contrario, es decir a puede descomponerse en producto defactores primos de dos formas distintas: a = p1 · p2 · p3 · ... · pk−1 · pk, siendo los pi primos para 1 ≤ i ≤ k y a = q 1 · q 2 · q 3 · ... · q r−1 · q r, siendo los q j primospara 1 ≤ j ≤ r. Suponga que el número de factores es distinto, o sea, k = r. Tomesin perder generalidad por ello,k < r. Entonces a = p1 · ( p2 · p3 · ... · pk−1 · pk) dedonde p1|a, luego p1|q 1 · q 2 · q 3 · ... · q r−1 · q r de donde p1|q j para algún j entre 1 y r(esto por corolario) luego p1 = q j , ya que q j es primo y p1 = 1. Se puede suponerque j = 1. Si no lo fuese bastaría con cambiar el orden de los factores. Se tiene

entonces que p1 = q 1 y p1 · p2 · p3 · ... · pk−1 · pk = p1 · q 2 · q 3 · ... · q r−1 · q r, dedonde, al ser p1

= 0, se sigue que p2

· p3

· ...

· pk−1

· pk = q 2

· q 3

· ...

· q r−1

· q r. Sea

ahora a1 = p2 · p3 · ... · pk−1 · pk y a1 = q 2 · q 3 · ... · q r−1 · q r. Entonces a1 < a, ya1 = p2 · ( p3 · ... · pk−1 · pk) luego p2|a1 esto es p2|q 2 · q 3 · ... · q r−1 · q r, o sea que p2|q jpara algún j entre 2 y r (por corolario). Entonces p2 = q j , ya que q j es primo y p2 = 1.Y ahora suponer que j = 2. Bastaría cambiar el orden de los factores si no fuese así. Se

sigue entonces que p2 · p3 · ... · pk−1 · pk = p2 ·q 3 · ... ·q r−1 ·q r y, al ser p2 = 0, se tiene que p3 · ... · pk−1 · pk = q 3 · ... ·r−1 ·q r, y llamando a2 = p3 · ... · pk−1 · pk y a2 = q 3 · ...q ·r−1 ·q r,se tiene que a2 < a1 < a. Como k < r, se repite el proceso k − 1 veces, y se tiene queak−1 = pk y ak−1 = q k · q k+1 · ... · q r, siendo ak−1 < ak−2 < ... < a2 < a1 < a. Entoncescomo ak−1 = pk se tiene que pk

|ak−1 de donde pk

|q k

·q k+1

·...

·q r, lo que implica que

pk|q j para algún j entre k y r (por el corolario). Luego pk = q j , ya que q j es primoy pk = 1 y razonando igual que en los pasos anteriores, se puede suponer que j = k,o sea, pk = q k y pk = q k · q k+1 · ... · q r, al ser pk = 0, se tiene 1 = q k+1 · q k+2 · ... · q r,de donde se sigue que q k+1 = q k+2 = ... = q r = 1 lo cual es imposible ya que estos

números son primos, por tanto, k = r y a = p1 · p2 · p3 · ... · pk−1 · pk, siendo así ladescomposición única.

Corolario 97 : Sea a un número entero tal que |a| > 1, entonces a tiene una factor-ización única de la forma: a = ± pα11 · pα22 · pα33 ... · pαkk , siendo k > 1, los pk primos

distintos con p1 < p2 < ... < pk y i > 1 para 1 ≤ i ≤ k.Demostración : Si a > 1, por el Teorema fundamental de la aritmética, a puede

descomponerse en factores primos. Agrupamos todos los primos iguales a p1 en el

factor pα11 , se hace igual con p2, p3 y así sucesivamente hasta pk, obteniendo así la

descomposición pedida. Si a es negativo, entonces −a es positivo con lo cual bastaráaplicar el razonamiento anterior a −a.


34/160

Capítulo 2

Aritmética Modular

Definición 98 : Sea m un entero positivo y a, b dos números enteros. Se dice que a y

b son congruentes módulo m, si m divide a a − b. Utilizaremos la notación a ≡ b(módm), es decir, a ≡ b(mód m) si y sólo si m|a − b

Ejemplo 99 : 80 ≡ 20(mód 15), ya que 15|60; −8 ≡ 16(mód 4), ya que 4| − 24;−5 ≡ −25(mód 10), ya que 10|20; 12 ≡ −3(mód 5), ya que 5|15

Ejemplo 100 : Encontrar cinco número enteros distintos, cada uno los cuales sea

congruente con 13 módulo 11.

Solución 101 : Sea a cualquiera de los n+umeros buscados. Entonces, a ≡ 13(mód11)si y sólo si a = 13+11q , con q ∈ Z. Si ahora se toma, por ejemplo, q = −2, −1, 0, 1 ó 2,se obtienen los cinco números buscados: a = 13+11·(−2) = −9; a = 13+11·(−1) = 2;a = 13 + 11 · 0 = 13; a = 13 + 11 · 1 = 24; a = 13 + 11 · 2 = 35.

Teorema 102 : Sea m cualquier número entero positivo. Entonces,

(a) Cualquier número entero es congruente módulo m exactamente con uno de los

enteros 0, 1, ......, m − 1.(b) Dos números enteros son congruentes entre sí módulo m si, y sólo si ambos dan el

mismo resto al dividirlos por m.

Demostración : (a) Se debe probar que si a es un número entero cualquiera,

entonces es congruente módulo m exactamente con uno de los enteros 0, 1, ......, m − 1.De hecho, a ∈ Z y m ∈ Z+ entonces existen q y r enteros únicos tales que a = mq + r,con 0 ≤ r < m (Porque?). Esto si y sólo si a − r = mq , con 0 ≤ r < m, por lo que

30


35/160


m|a − r, con 0 ≤ r < m, luego a ≡ r(mód m), con 0 ≤ r < m, lo que implica que:

a ≡ 0(mód m)a ≡ 1(mód m)a ≡ 2(mód m)

...

a ≡ m − 1(mód m)

A este número r, único, se le llama menor residuo de a, módulo m.

(b) Sean a y b dos enteros cualesquiera.

“Sólo si.” Si a ≡ b(mód m), entonces a − b = mq , con q ∈ Z. Por otra parte, por elteorema de existencia y unicidad de cociente y el residuo (porque?), pueden encontrarseq 1, q 2, r1 y r2 enteros, tales que a = mq 1 + r1 y a = mq 2 + r2 de aquí que a − b =m(q 1 − q 2) + r1 − r2. Se tiene que a − b = mq y a − b = m(q 1 − q 2) + r1 − r2 y comoel residuo de dividir a − b entre m es único, r1 − r2 = 0, luego, r1 = r2 es decir, a y bdan ambos el mismo residuo al dividirlos por m.

“Si.” Recíprocamente, suponga que ambos a y b, dan el mismo residuo al dividirlos

por m, es decir, existen q 1, q 2 y r, enteros, tales que a = mq 1 + r y b = mq 2 + r. Note

que restando miembro a miembro, se obtiene que a − b = m(q 1 − q 2) esto si y sólo sim

|a

−b si y sólo si a

≡ b(mód m)

Ejemplo 103 : Demuéstrese que todo número primo mayor o igual que 5 es congru-

ente con 1 ó con 5 módulo 6.

Solución 104 : Se debe probar que si p es primo y p > 5, entonces p ≡ 1(mód (6)) ó p ≡ 5(mód (6)). En efecto, suponga que la proposición es falsa es decir, p es primo y p > 5, sin embargo, p ≡ 1(mód (6)) y p ≡ 5(mód (6)). Entonces, por la parte (a) del teorema anterior, p ≡ 0(mód (6)) ó p ≡ 2(mód (6)) ó p ≡ 3(mód (6)) ó p ≡ 4(mód (6)).Pues bien, Si p ≡ 0(mód (6)), entonces 6| p lo cual es imposible ya que p es primo. Si p

≡ 2(mód (6)), entonces 6

| p

−2 y 2

|6 entonces 2

| p

−2 y como 2

|2 entonces 2

| p

−2 + 2

osea que 2| p lo que contradice que contradice el que p sea primo con p > 5. Si p ≡3(mód (6)) entonces 6| p−3 y como 3|6 entonces 3| p−3 y a su vez como 3|3 se tiene que 3| p−3 + 3 esto es 3| p y esto contradice el que p sea primo. Si p ≡ 4(mód (6)), entonces 6| p−4 lo que implica que y 2|6 entonces 2| p−4 , y como 2|4 entonces 2| p−4+4 lo que implica que 2| p y esto contradice el que p sea primo. Lo cual contradice lo supuesto y la proposición propuesta es cierta, es decir, p ha de ser congruente módulo 6 con 1 ó

con 5.

Ejemplo 105 : Demuéstrese que si d|m y a ≡ b(mód (m)), entonces a ≡ b(mód (d)).


36/160


Solución 106 : Trabajando directamente de la transitividad de la relación de divisi-

bilidad de d|m y como a ≡ b(mód (m)), se tiene que m|a − b luego d|a − b si y sólo si a ≡ b(mód (d))

Teorema 107 : Sean a,b,c y m tres enteros con m > 0. Se verifica que:

(a) a ≡ a(mód (m)).(b) Si a ≡ b(mód (m)), entonces b ≡ a(mód (m))(c) Si a ≡ b(mód (m)) y b ≡ c(mód (m)), entonces a ≡ c(mód (m))

Demostración : (a) a ≡ a(mód (m)). Teniendo en cuenta que m = 0, m|0 luegom|a − a por lo tanto a ≡ a(mód (m))(b) Si a ≡ b(mód (m)), entonces b ≡ a(mód (m)). En efecto, Si a ≡ b(mód (m)),entonces m|a−b luego m|(−1)(a−b) lo que implica que m|b−a o sea que b ≡ a(mód (m))(c) Si a ≡ b(mód (m)) y b ≡ c(mód (m)), entonces a ≡ c(mód (m)). En efecto, Sia ≡ b(mód (m)), entoncs m|a − b y como b ≡ c(mód (m)) se tiene que m|b − c Por lotanto m|(a−b)+(b−c), con lo cual se puede concluir que m|a−c esto es a ≡ c(mód (m))

Teorema 108 : Sean a, b, c, d, p y m, enteros con p = 0 y m > 0. Se verifica que :(a) si a ≡ b(mód (m)) y c ≡ d(mód (m)), entonces a + c ≡ b + d(mód (m)) y ac ≡bd(mód (m)).

(b) Si a ≡ b(mód (m)), entonces pa ≡ pb(mód (m)).(c) Si p|a, p|b, m.c.d.( p, m) = 1 y a ≡ b(mód (m)), entonces a

p ≡ b

p(mód (m))

Demostración : Utilizando, al igual que en el teorema anterior, las propiedades

de la divisibilidad se tiene que:

(a) Si a ≡ b(mód (m)) y c ≡ d(mód (m)), entonces a + c ≡ b + d(mód (m)) y ac ≡bd(mód (m)). En efecto, Si a ≡ b(mód (m)) y c ≡ d(mód (m)),entonces m|a − b ym|c − d por lo tanto m|(a − b) + (c − d) lo que implica que m|(a + c) − (b + d), estoes a + c ≡ b + d(mód (m)). Por otro lado como m|a − b luego m|ac − bc, igualmentem|c − d por lo tanto m|bc − bd luego m|(ac − bc) + (bc − bd) esto es m|ac − bd con locual se concluye que ac ≡ bd(mód (m))(b) Si a ≡ b(mód (m)), entonces pa ≡ pb(mód (m)). En efecto, a ≡ b(mód (m)) entoncesm|a − b luego m| p(a − b) por lo tanto m| pa − pb esto si y sólo si pa ≡ pb(mód (m))(c) Si p|a, p|b, m.c.d.( p, m) = 1 y a ≡ b(mód (m)), entonces a

p ≡ b

p(mód (m)). En

efecto, p|a y p|b por lo tanto p|a − b y como a ≡ b(mód (m)) lo que conduce a quem|a−b por lo tanto ∃q 1 ∈ Z tal que a−b = mq 1. De aquí se sigue que p|mq 1. Note que,si p|mq 1 y como m.c.d.( p, m) = 1, se teiene que p|q 1, es decir, q 1 = pq con q entero.


37/160


Entonces, a − b = mq 1 y q 1 = pq lo que conduce a que a − b = mpq, por lo tantoa

p − b

p = mq esto es m|a

p − b

p , con lo cual se concluye que a

p ≡ b

p(mód (m))

Ejemplo 109 : Demostrar que el cuadrado de cualquier número entero es divisible

por 3 o es congruente con 1 módulo 3.

Solución 110 : Sea a un número entero arbitrario. Por teorema a es congruente

módulo 3 con 0, 1 ó 2. Pues bien, Si a ≡ 0(mód 3) entonces a2 ≡ 0(mód 3), (por teorema) luego 3|a2, es decir es divisible por 3. Ahora si a ≡ 1(mód 3) entonces a2 ≡1(mód 3) (por teorema) y se concluye lo solicitado. Igualmente si a ≡ 2(mód 3),entonces a2 ≡ 4(mód 3), (por teorema) 3|a2 − 4 esto es a2 − 4 = 3q, luego a2 = 3q + 4,

así que a2 = 3(q + 1) + 1, con lo que se sigue que 3|a2−1, de aquí que a2 ≡ 1 (mód 3) ,luego a2 es divisible por 3 o es congruente con 1 módulo 3.

Corolario 111 : Si ai ≡ bi (mód m) para 1 ≤ i ≤ n, entonces (i)

ni=1

ai ≡n

i=1

bi (mód m)

(ii)n

i=1

ai ≡n

i=1

bi (mód m)

Demostración : En ambos casos usando el método de inducción matemática se

tiene que:

(i)n

i=1

ai ≡n

i=1

bi (mód m) . Veamos que es cierto para n = 2. En efecto, por el teorema

anterior, Si a1 ≡ b1 (mód m) y a2 ≡ b2 (mód m) entonces a1 + a2 ≡ b1 + b2 (mód m),(Paso inductivo). Suponga que la proposición es cierta para n = p, es decir, si ai ≡bi (mód m) para i = 1, 2, ...,p, entonces

pi=1

ai ≡ p

i=1

bi (mód m) . Demuestre ahora que

también se cumple para n = p+1. En efecto, si ai ≡ bi (mód m) para i = 1, 2,...,p,p+1entonces

pi=1

ai ≡ p

i=1

bi (mód m) y ai ≡ bi (mód m) , entonces p

i=1

ai + a p+1 ≡ bi ≡ p

i=1

bi + b p+1 (mód m) , por lo tanto

p+1i=1

ai ≡ p+1i=1

bi (mód m) , y, consecuentemente, la

proposición será cierta para todo n.

(ii)n

i=1

ai ≡n

i=1

bi (mód m) . Basta aplicar el apartado (a) del teorema anterior y la

igualdad p+1i=1

ai ≡ p

i=1

ai · a p+1 (mód m) , para llegar al resultado.

Ejemplo 112 : Demostrar que si el último dígito de un número n es t, entonces

n2 ≡ t2 (mód 10)


38/160


Solución 113 : En efecto, si n = ak10k + ak−110k−1 + ... + a110 + a0, es la de-

scomposición polinómica de n, entonces a0 = t, luego n =n

i=1

ai10ι + t, de aquí

que n − t =n

i=1

ai10ι. Ahora bien, 10 ≡ 0 (mód 10) luego 10i ≡ 0 (mód 10) , igual-

mente ai10i ≡ 0 (mód 10) para 1 ≤ i ≤ k, de aquí que por el corolario anterior,k

i=1

ai10ι ≡ 0 (mód 10), de donde n − t ≡ 0 (mód 10) , o sea que n ≡ t (mód 10) con lo

cual se concluye que n2 ≡ t2 (mód 10)

Ejemplo 114 : Demostrar que el residuo de dividir 204572 entre 7 es 1

Solución 115 : 21 ≡ 0 (mód 7) y −1 ≡ −1 (mód 7) , luego 20 ≡ −1 (mód 7) , o sea que 204572 ≡ (−1)4572 (mód 7) , esto es 204572 ≡ 1 (mód 7) , es decir que el residúo es 1.

Ejercicio 116 : Demuestre:

(a) Si a ≡ b (mód m), entonces m.c.d.(a, m) = m.c.d.(b, m).(b) Si a ≡ b (mód m), entonces an ≡ bn (mód m) para cualquier entero positivo n.(c) Si a + b ≡ c (mód m), entonces a ≡ c − b (mód m).(d) Si a

≡ b (mód m) y d

|a y d

|m, entonces d

|b.

Ejemplo 117 : Demuestre que para cualquier entero positivo n, el número 3 · 52n+1 +23n+1 es divisible por 17.

Solución 118 : Note que 3 · 52n+1 = 3 · 52n · 5 = 3 · 52n · 5 = 15 · 25n luego23n+1 = 23n · 2 = 23n · 2 = 2 · 8n. Por otro lado 15 ≡ −2 (mód 17) y 25 ≡ 8 (mód 17)luego 25n ≡ 8n (mód 17) , por teorema se concluye que 15 · 25n ≡ (−2) · 8n (mód 17) ,por lo tanto 15 · 25n + 2 · 8n ≡ 0 (mód 17) , esto es 3 · 52n+1 + 23n+1 ≡ 0 (mód 17) .Luego el número dado es divisible por 17.

Ejemplo 119 : Demuestre por inducción que el número 72n −48n − 1 es divisible por 2304 para cualquier entero positivo n.

Solución 120 : Se debe probar que: 72n −48n−1 ≡ 0 (mód 2304) , ó también 72n −48n − 1 ≡ 0 (mód 2304) , esto es (49)n ≡ 48n + 1 (mód 2304) , o lo que es lo mismo(48 + 1)n ≡ 48n + 1 (mód 2304) . Analizando por inducción: Para n = 1 es ciertoclaramente. Veamos si es cierto para n = 2. En efecto, (48 + 1)2 = 482 + 2 · 48 + 1,esto si y sólo si (48 + 1)2 = 48 · 2 + 1 + 2304, luego (48 + 1)2 − (48 · 2 + 1) = 2304,de donde (48 + 1)2 ≡ 48 · 2 + 1 (mód 2304) . Supongamos que es cierto para n = p,


39/160


es decir, (48 + 1) p ≡ 48 · p + 1 (mód 2304) . Se debe demostrar que es cierto para n = p + 1. En efecto, como (48 + 1) ≡ 48 · 1 + 1 (mód 2304) y (48 + 1)

p

≡ 48 · p + 1 (mód 2304) , luego al aplicar un teorema anterior, se tiene (48 + 1) p (48 + 1) ≡(48 · p + 1) (48 + 1) (mód 2304) , pero (48 · p + 1) (48 + 1) = 2352 p + 49 = 2304 p +48 p +48+1, de aquí que (48 p +1)(48+1)− [48( p +1) +1] = 2304 p. Lo que implica que (48 · p + 1) (48 + 1) ≡ 48( p + 1) + 1(mód 2304) , por transitividad de la congruencia se tiene que (48+1) p+1 ≡ 48( p + 1 ) + 1 (mód 2304) . Como consecuencia, la congruencia es cierta para cada entero positivo n, o sea (48 + 1)n ≡ 48 · n + 1 (mód 2304) . Luego72n − 48n − 1 es divisible por 2304.

Ejercicio 121 : (1) Calcular el resto de dividir 96n+1 + 32n+1

·4872n

−10 por 730. (2)

Demostrar que para cualquier entero positivo n, el número 10n(9n − 1) + 1 es divisible por 9.

Definición 122 : (Relación de equivalencia) se dice que una leción R es de equiva-

lencia si dicha relación es:

1. Reflexiva: Todo elemento del conjunto K está relacionado consigo mismo. Es decir,

∀x ∈ K, xRx.2. Simétrica: Si x ∈ K e y ∈K, se tiene que si xRy, entonces yRx.3. Transitiva: Si x, y,z ∈K y xRy e yRz, entonces xRz

Teorema 123 : Dado un entero m > 0, la relación de congruencia módulo m es una relación de equivalencia en el conjunto de los números enteros.

Demostración : Ejercicio.

Teorema 124 : Dado un número entero cualquiera a, su clase de equivalencia es el

conjunto formado por todos los enteros que dan el mismo residuo que a al dividirlos

entre m.

Demostración : Recuerde que la clase de equivalencia de un elemento es el con-

junto formado por todos los elementos relacionados con él. Por lo tanto, si a es un

número entero cualquiera, y [a] = {x ∈ Z tales que x ≡ a (mód m)} es el conjuntode los elementos congruentes con a módulo m, entonces por el teorema de existencia

y unicidad de cociente y reiduo se puede asegurar que existen q 0 y r, enteros y únicos

tales que a = mq 0+r, con 0 ≤ r < m y por teorema se tiene que [a] estará formada portodos los enteros que dejen como residuo r al dividirlos entre m, es decir, [a] = {x ∈ Ztales que x = mq + r, con q ∈ Z}

Definición 125 : (Suma) Dados dos enteros cualesquiera a y b, Se define la suma en

Zm en la forma siguiente: [a] + [b] = [a + b].


40/160


Ejemplo 126 : Sumar en el conjunto de las clases de restos módulo 5, Z5, las clases

[31] y [58].

Solución 127 : Según la definición anterior, [31]+[58] = [89] = {x ∈ Z tales que x = 5q + 4, con q {..., −16, −11, −6, −1, 4, 9, 14, 19, 24...} = [4].

Ejemplo 128 : Note que en Z5, las clases [16] y [63] son iguales, respectivamente, a

las clases [31] y [58], por lo tanto su suma ha de ser igual a la calculada en el ejemplo

anterior. En efecto, [16] + [63] = [79] = {x ∈ Z tales que x = 5q + 4, con q ∈ Z} ={..., −16, −11, −6, −1, 4, 9, 14, 19, 24...} = [4]

Teorema 129 : La s

Documents

curso de discretas.pdf