Teoría de Números e Inducción

Capítulo 3
Teoría de Números e Inducción

3.1 Introducción
La aritmética forma parte de la vida cotidiana y es capaz de proveer buenos problemas a
los estudiantes que tengan un poco de curiosidad. Las ciencias de la computación constitu-
yen un aliado valiosísimo a la hora de experimentar con los números y sus soluciones. La
criptografía de clave pública, el comercio electrónico, la transmisión y almacenamiento de
datos, son algunos de los hechos del mundo moderno cuyo desarrollo está basado en la
teoría elemental de números y la aritmética. Gentile (1985, p.1) decía, en el Prólogo de su
libro, “la evolución de la computación ha hecho que la aritmética deje de ser una ciencia
contemplativa y de especialistas para transformarse en una verdadera rama aplicada. La
necesidad de nuevos algoritmos de computación requiere vastos y profundos conocimientos
aritméticos”.
La capacidad de enviar un mensaje que no pueda ser comprendido por quien intenta in-
terceptarlo, pero que pueda ser descifrado por su destinatario, así como la certeza que de-
berá tener éste sobre la procedencia o validación de la firma de dicho mensaje, son razones
de peso que justifican el creciente avance de la Criptografía. Como conjunto de técnicas que
permiten proteger el secreto de la comunicación, la Criptografía usa, entre otros elementos,
la aritmética modular, la teoría de números enteros no negativos y más particularmente la de
los números primos y coprimos. Ya se trate de graves y rápidas decisiones en situaciones
beligerantes o de procesos de grandes transacciones comerciales que requieran demorar la
información pública, lo cierto es que, los gobiernos o firmas responsables subvencionan
equipos de criptólogos para incidir sobre el cifrado y descifrado de mensajes. Y estos equi-
pos cuentan con matemáticos especialistas en teoría de números y sus aplicaciones.
En este capítulo, trabajaremos conceptos básicos de la teoría elemental de números ente-
ros. Éstos serán identificados con su expresión matemática habitual, Z (zeta). Nos referire-
mos a las operaciones que caracterizan a Z como un anillo conmutativo con identidad que
no tiene divisores propios del cero; luego haremos mención al principio de la buena ordena-
ción y a la relación entre divisores, números primos, máximo común divisor y mínimo común
múltiplo; también nos introduciremos en cuestiones básicas de aritmética modular. Poste-
riormente trabajaremos con otro principio, el de inducción matemática y finalizaremos el
capítulo con una buena aplicación de la inducción a las ciencias informáticas.
El propósito es lograr un adecuado manejo algebraico de los enteros positivos que sean
primos. Entre las operaciones y propiedades que identifican a los enteros, aparecen, el algo-
ritmo de la división y las congruencias.

173
Matemática Discreta

Este algoritmo de la división permite desarrollar toda la teoría de la divisibilidad hasta lle-
gar al Teorema Fundamental de la Aritmética, que muestra la representación y unicidad de
los enteros positivos distintos de 1 como un producto de potencias de números primos.

3.2 El anillo de los enteros

En el conjunto de los números enteros se definen dos operaciones habitualmente conoci-
das como adición y multiplicación. Se denominan leyes de composición interna u operadores
binarios definidos en Z y se simbolizan habitualmente con “+” y “·”, respectivamente y se
leen “mas” y “por”. ¿Por qué decimos que estas operaciones son leyes de composición
interna u operadores binarios definidos en Z? Porque tanto la adición como la multiplicación
son funciones que tienen el dominio en ZxZ y el conjunto de llegada en Z; es decir, dado un
par ordenado de números enteros, la suma y el producto entre dichos enteros también es un
número entero. Simbólicamente, podemos expresar esta idea anotando:
 a, b  Z: a + b  Z y a · b  Z.
Cuando no se preste a confusión, escribiremos “a b” en lugar de “a · b”.
En ambos casos, sumando o multiplicando dos números enteros, obtenemos como suma
o producto, respectivamente, otro número entero. Esto también nos permite referirnos a Z
diciendo que es cerrado respecto de la suma y del producto. La operación “+” satisface los
siguientes axiomas:
a1) Asociatividad:  a, b, c  Z, (a + b) + c = a + (b + c).
a2) Conmutatividad:  a, b  Z, a + b = b + a.
a3) Existencia de neutro:  0  Z tal que  a  Z, a + 0 = a.
a4) Existencia de opuesto: Para cada a  Z,  (a)  Z tal que a + (a) = 0.
Estos axiomas de asociatividad, conmutatividad, existencia de elemento nulo o neutro y
de elemento inverso aditivo u opuesto para cada entero, caracterizan a (Z, +) como un gru-
po abeliano.
Si a  Z, b  Z; para simplificar la notación de b + (a) escribiremos b  a.
La operación “·” satisface los siguientes axiomas:
a5) Asociatividad:  a, b, c  Z, (a b) c = a (b c).
a6) Conmutatividad:  a, b  Z, a b = b a.
a7) Existencia de neutro:  1  Z tal que  a  Z, a 1 = a.
Es decir, también se satisfacen la asociatividad, la conmutatividad y la existencia del ele-
mento identidad o neutro para el producto.
Ambas operaciones “+” y “·” están relacionadas por el axioma de la distributividad de la
multiplicación respecto de la adición:
a8)  a , b, c  Z, a (b + c) = a b + a c; (b + c) a = b a + c a.
Los axiomas mencionados caracterizan a (Z, +, · ) como anillo conmutativo con identidad.
Decimos además que el anillo de los enteros Z, no tiene divisores propios del cero porque si
el producto de dos enteros cualesquiera es nulo entonces alguno de ellos es nulo.

174
 Teoría de Números e Inducción

Es decir, en Z se satisface:
a9)  a , b  Z, si a b = 0 entonces a = 0 o b = 0.
Más adelante, enfatizaremos esta última propiedad de los enteros.

Actividad 1
Problema Nº1: ¿Cuáles de las siguientes proposiciones son verdaderas? Justifica. En ca-
so de que sean falsas proporciona contraejemplos.
1.1)  a, b  Z, si a2 = b2 entonces a = b.
1.2)  a, b  Z, si a2 = b2 entonces a = b.
1.3)  a, b  Z, si a2 = b2 entonces a = b o a = b.
1.4)  a, b  Z, si a2 = b2 entonces a = b y a = b.
1.5)  a, b  Z, si a2 = b2 entonces o a = b o a = b.
1.6)  a, b  Z, si a2 = b2 entonces a3 = b3.
1.7)  a, b  Z, si a2 = b2 entonces |a|=|b|.
1.8)  a, b  Z, si a < b entonces a2 < b2. (Recordemos que a < b si y sólo si a  b < 0).

Problema Nº2: Analiza la validez de la siguiente demostración en Z.

TEOREMA:  a  Z, a = 0.
Demostración:
Se verifica que a2 = a2. Luego a2  a2 = a2  a2.
Es decir: (a  a) (a + a) = a (a  a) y cancelando a + a = a. Sumando a ambos lados de
la igualdad, el opuesto de a, (a), obtenemos a = 0.

Problema Nº3: Analiza la validez de la siguiente demostración en Z.

TEOREMA:  a  Z, 0 < a.
Demostración:
Se verifica que 0 < 1.
Luego 0 a < 1 a, multiplicando a ambos lados por a, y operando 0 < a.

Problema Nº4: Analiza la validez de las siguientes afirmaciones en Z.

4.1)  a, b  Z, tales que a2 = 2 b2.
4.2)  a, b  Z, tales que a2 = 15 b2.
4.3)  a, b, c  Z{0}, tales que a2 = b2 + c2.
4.4)  a, b, c  Z{0}, tales que a3 = b3 + c3.
4.5)  a, b, c  Z{0}, tales que a4 = b4 + c4.
Observación: Los últimos dos ítems del ejercicio son casos particulares del Último Teo-
rema de Fermat.

175
Matemática Discreta

Problema Nº5: En el próximo párrafo estudiaremos propiedades de los divisores y de la

divisibilidad. En estos ejercicios queremos que nuestro lector determine la validez de las
siguientes afirmaciones utilizando sus conocimientos previos sobre la aritmética y sus sabe-
res sobre lógica proposicional:
5.1) Si un número entero es divisible por 12 entonces es divisible por 4.
5.2) Si un número entero es divisible por 12 entonces no es divisible por 4.
5.3) Si un número entero no es divisible por 12 entonces no es divisible por 4.
5.4) Si un número entero no es divisible por 12 entonces es divisible por 4.
5.5) Si un número entero no es divisible por 4 entonces no es divisible por 12.
5.6) Si un número entero no es divisible por 4 entonces es divisible por 12.
5.7) Si un número entero es divisible por 4 entonces es divisible por 12.
5.8) Si un número entero es divisible por 4 entonces no es divisible por 12.

Problema Nº6: Demuestra que en Z, a3  1 = 0 si y sólo si a = 1.

Problema Nº7: Utilizando conocimientos de aritmética y de lógica, asigna un valor de ver-

dad (falso o verdadero) a cada proposición:
7.1) Un número es divisible por 3 si y sólo si es divisible por 9.
7.2) Si un número entero positivo es par entonces, es divisible por 2 o por 3.
7.3) Si un número entero positivo es par entonces, es divisible por 2 y por 3.
7.4)  n  Z, la expresión n3 + 13 n + 7 es impar.
7.5) La expresión n3 + 13 n + 7 = 0 no posee soluciones enteras.

3.3 Divisibilidad y divisores

El conjunto de los enteros positivos, que designamos con Z+ es un subconjunto de los
números enteros Z, que tiene una propiedad que lo caracteriza y lo distingue de Q+ o R+.
Ésta se refiere a que todo subconjunto no vacío Y de Z+ contiene un entero positivo a  Y, tal
que a  y para todo y  Y, es decir, Y contiene un elemento mínimo. Por ejemplo, si
Y = {x  Z+ : x < 100}, entonces Y tiene un elemento mínimo que es x = 1. Sin embargo,
existen subconjuntos de Q+ o R+, como V = {x  Q+: 0 < x < 100} o el intervalo abierto
W = (0, 1) que no tienen elementos mínimos.
Esta propiedad de Z+ se llama principio de la buena ordenación y para enunciarla necesi-
tamos entender el concepto de conjunto bien ordenado.

Definición 3.1
Sea R el conjunto de los números reales. Decimos que un subconjunto Y de R es bien or-
denado si todo subconjunto no vacío de Y posee un primer elemento o elemento minimal. El
conjunto vacío es un conjunto bien ordenado.

176
 Teoría de Números e Inducción

Ejemplo 1
El conjunto Y = {2, 0, 3} es un conjunto bien ordenado. En efecto, los subconjuntos no
vacíos de Y son: {2}, {0}, {3}, {2, 0}, {2, 3}, {0, 3}, {2, 0, 3} y cada uno de ellos tiene
a 2, 0, 3, 2, 2, 0, 2 respectivamente, como primer elemento. Más aún, podemos afirmar
que todo subconjunto finito de R es bien ordenado.

Ejemplo 2
Sea V = {x  Q: x = 1/n, n  N}. V no es bien ordenado. Para demostrar la verdad de es-
ta proposición es suficiente mostrar que V tiene subconjuntos que no tienen un primer ele-
mento. Vamos a probar, por el absurdo, que el propio V no tiene primer elemento. Supon-
gamos que sí, es decir, que V tiene a x0 como primer elemento. En este caso, existirá un
n0  N, tal que x0 = 1/n0. Pero la fracción 1/(n0 +1)  V y verifica que 1/(n0 +1) < 1/n0 y esto
es absurdo porque x0 = 1/n0 era el elemento mínimo. El absurdo provino de suponer que V
tenía primer elemento.

Principio de la buena ordenación

Todo subconjunto no vacío de enteros positivos tiene un elemento mínimo, es decir, Z+ es
un conjunto bien ordenado.

Este principio es utilizado para justificar el método de inducción matemática al cual nos
referiremos más adelante; también, para justificar el algoritmo de la división y para demostrar
otras propiedades referidas a los enteros, tal como veremos en este libro.

Aunque el conjunto Z no es cerrado respecto de la división de enteros no nulos, existen

muchos casos en los que un entero divide exactamente a otro. Por ejemplo 3 divide a 6. Lo
que implica la existencia de un cociente igual a 2 y un resto igual a 0. Es decir, la división es
exacta y hay resto nulo. Formalizaremos esta idea acerca de la divisibilidad, estudiando la
relación “ … divide a …” en el conjunto de los enteros.

Definición 3.2
Si a, b  Z y b  0 decimos que b divide al entero a y lo simbolizamos b|a, si existe un en-
tero n tal que a = b n. También podemos decir que b es un divisor de a, que a es un múltiplo
de b, que b es un factor de a, o que a es divisible por b.
Si a = 0 y b  0 decimos que b divide al entero 0 y lo simbolizamos b|0, porque existe un
entero n = 0 tal que 0 = b 0. Luego, en Z, todo entero no nulo es un divisor del 0.
Con la notación b | a, que leemos b no divide al entero a, denotamos la negación de b|a.

Definición 3.3
Decimos que un entero b  0 es un divisor propio de 0 si existe un entero n  0 tal que
0 = b n. Es decir, existen divisores propios de 0 si 0 se puede expresar como producto de

177
Matemática Discreta

elementos no nulos.

Podemos afirmar que en Z, el elemento 0 no tiene divisores propios pues 0 = b n si y sólo

si b=0 o n=0. Sin embargo, existen anillos conmutativos, a los que nos referiremos más
adelante, que tienen divisores propios de cero.

Propiedad 3.1
Z no tiene divisores propios de cero. Z se denomina un dominio entero porque no tiene di-
visores propios del 0.

De la propiedad anterior se deduce que, dados a, b enteros, si a b = 0 entonces a = 0 o

b = 0. Esta propiedad permite cancelar sin necesidad de multiplicar ambos miembros de
una ecuación por el inverso de un entero que, excepto para 1 y (−1), no es entero.

Ejemplo 3
Si estamos en presencia de una ecuación de la forma 3p = 3q con p, q enteros, la pode-
mos plantear como 3(p  q) = 0. Como Z no tiene divisores propios del cero, debe ser que 3
es 0 o que (p  q) es cero. Como 3 un entero no nulo, la única solución es p  q = 0 o sea
p = q.

Enunciaremos ahora algunas propiedades de la divisibilidad en los enteros. Recordemos

que siempre que hablemos de un entero b que divida a otro entero a, el divisor b debe ser
no nulo.

TEOREMA 3.1
Para a, b, c  Z se verifican:
i) 1|a; a|0 y a|a, si a  0.
ii) Si a|b  b|a entonces a =  b, donde a  0 y b  0.
iii) Si a|b  b|c entonces a|c, si a  0 y b  0.
iv) Si a|b entonces a|b c, si a  0.
v) Sean x, y, z enteros y a  0. Si z = x + y y a divide a dos de los enteros x, y, z, entonces
divide al restante. Esto significa que si a divide a dos enteros, entonces divide tanto a la
suma como a la diferencia de dichos enteros.
vi)  x, y  Z si a  0 , a|b  a|c entonces a|(x b + y c), es decir a divide a toda combi-
nación lineal entera (con coeficientes enteros) de b y c.

Demostración del ítem i):

Como a = 1 a, 0 = a 0 y a = a 1 siendo a, 0  Z y a  0, deducimos que se verifican 1|a,
a|0 y a|a.

178
 Teoría de Números e Inducción

Demostración del ítem ii):

Si a|b y b|a existen enteros m, n tales que b = a m, a = b n. Reemplazando el valor de b
en la segunda ecuación obtenemos a = (a m) n = a (m n), lo que implica que m n = 1.
Como m, n son enteros, la única posibilidad es que se verifiquen m = n = 1 o
m = n = 1. Luego a =  b.

Demostración del ítem iii):

Si a|b existe un entero m tal que b = a m; si b|c existe un entero n tal que c = b n. Re-
emplazando el valor de b en la segunda ecuación obtenemos que c = (a m) n =a (m n),
siendo el producto m n un entero. Entonces a|c.

Demostración del ítem iv):

Si a|b existe un entero n tal que b = a n. Multiplicando a ambos lados de la igualdad por
un entero c, obtenemos b c = (a n) c = a (n c), donde el producto n c es un entero. Luego
a|(b c).

Demostración del ítem v):

Sean x, y, z enteros tales que z = x + y.
Analizaremos los distintos casos donde a divide a dos de los enteros x, y, z. Suponemos
primero que a divide a los enteros x, y, esto es, a|x, a|y. Luego se verifica que x = a k,
y = a m siendo k, m enteros. Sumando miembro a miembro estas igualdades obtenemos
x + y = a (k + m) siendo k + m un número entero.
Entonces a|(x + y), es decir, a|z. Luego, si a divide a dos enteros, entonces divide a la
suma de éstos.
Suponemos ahora que a divide a los enteros x, z, esto es, a|x, a|z. Luego se verifica que
x = a k, z = x + y = a m siendo k, m enteros. Restando miembro a miembro estas igualda-
des obtenemos x  z =  y = a (k  m) siendo k  m un número entero.
De donde y = a (m  k) siendo m  k un entero. Entonces a|y. Luego, si a divide a dos
enteros, divide a la diferencia de éstos.
Dejamos a cargo de nuestro lector completar la prueba.

Demostración del ítem vi):

Si a|b entonces b = a m y si a|c entonces c = a n para m, n  Z. Luego, la combinación
lineal x b + y c = x (a m) + y (a n) = (x a) m + (y a) n = (a x) m + (a y) n = a (x m) + a (y n) =
=a (x m + y n), por las propiedades asociativa, conmutativa y distributiva en Z. Como
(x m + y n) es un número entero se sigue que a es divisor de (x b + y c).

Observación:
La parte vi) puede generalizarse de la siguiente forma. Para 1  i  n, sea ci  Z.
Si a|ci i, entonces a|(x1 c1 + x2 c2 +... +xn cn), con xi  Z.

179
Matemática Discreta

Es decir, si un entero a es divisor de un número finito de enteros, también es divisor de

toda combinación lineal entera de ellos.

Ejemplo 4
¿Es cierto que si a|b y c|b entonces a c|b? Por ejemplo, 2|36 y 3|36, luego 6|36. Sin
embargo, 12|36 y 18|36 pero 216 no divide a 36. Luego, la pregunta no es cierta para todos
a, b, c enteros.

Ejemplo 5
Pensemos en la sucesión de las potencias enteras no negativas de 4. Esto es 1, 4, 16, 64,
256, 1.024, ..., 4n, ... Sumando (1) a cada elemento, obtenemos la sucesión 0, 3, 63, 255,
1.023, …, 4n  1, ... Observamos que los primeros elementos de esta sucesión admiten a 3
como divisor. ¿Será cierto que 3 es divisor de 4n  1 para todo entero n no negativo? Más
adelante, la inducción matemática nos proveerá la prueba que necesitamos para demostrar
la validez de esta propiedad.

Ejemplo 6
Supongamos que queremos determinar para qué valores de n  Z+ el número entero
5 n2 + n tiene a 2 como divisor.
Para ello podemos considerar dos casos, si n es par y si n es impar. En el caso en que n
sea un número par entonces tenemos que existe k  Z+ tal que n = 2 k.
Luego 5 n2 + n = 5 (2 k)2 + (2 k) = 5 (4 k2) + (2 k) = 20 k2+ 2 k = 2 (10 k2 + k); y como
(10 k2 + k) es un número entero entonces 2 divide a 5 n2 + n si n es par.
En el caso en que n sea impar, tenemos que existe k  Z0+ tal que n = 2 k+1. Entonces:
5 n2 + n = 5 (2 k+1)2 + (2 k+1)
= 5 (4 k2 + 4k +1) + (2 k +1)
= (20 k2 + 20 k + 5)+ (2 k +1)
= 20 k2 + 22 k + 6
= 2 (10 k2 + 11 k + 3);
y como (10 k2 + 11 k + 3) es un número entero entonces 2 divide a (5 n2 + n) cuando n es
impar. Luego, 2 es un divisor de (5 n2 + n) para todo n  Z+.

Ejemplo 7
¿Existen enteros x, y, z tales que 12x + 8y + 20z = 105? Es decir, de las infinitas solucio-
nes de esta ecuación de primer grado, ¿existen soluciones enteras?
Supongamos que existen x, y, z enteros tales que cumplen la ecuación anterior. Como se
verifica que 4|12, 4|8, 4|20, por la generalización del Teorema 3.1 vi), 4 divide a toda com-
binación entera de ellos, por lo tanto, 4|105. Sin embargo, esto es falso, y esta contradicción
se obtuvo del hecho de suponer que existían tales enteros x, y, z.

180
 Teoría de Números e Inducción

Ejemplo 8
¿Existen enteros x, y tales que 32x + 10y = 41? Supongamos que existen x, y enteros ta-
les que cumplen la ecuación anterior. Dado que 2|32, 2|10, por el Teorema 3.1 vi), 2 divide
a toda combinación entera de 32 y 10, luego 2 divide a 41. Sin embargo, esto es falso, por lo
que no existen tales enteros.

Ejemplo 9
¿Existen enteros x, y tales que 14 = 42x + 70y? Si dividimos la ecuación por 14 obtene-
mos 1 = 3x + 5y, de donde resulta que x = 2, y = 1 es una solución. Otra solución es
x = 3, y = 2. Estas soluciones para x e y son sencillas de encontrar; sin embargo no tene-
mos un criterio general para determinarlas.

Más adelante veremos bajo qué condiciones esta ecuación tiene soluciones enteras. De-
mostraremos además que si existen soluciones enteras, éstas no son únicas, y mostraremos
cómo encontrarlas.

Analizando el conjunto de los números enteros positivos, por el Teorema 3.1 i) observa-
mos que todo entero a mayor que uno, tiene al menos dos divisores positivos distintos: 1 y el
mismo a. Algunos como 2, 3, 5, 7, 11, 13, 17, ... que tienen solamente dos divisores positivos
distintos reciben el nombre de números primos, mientras que todos los demás enteros posi-
tivos mayores que 1 que no son primos, se llaman números compuestos. Por ejemplo, 39 es
compuesto porque además de los divisores 1 y 39 tiene a 3 como factor. Un número com-
puesto tiene entonces, al menos, algún otro divisor positivo que será distinto de 1 y de sí
mismo. Es decir, si m es un número compuesto existirá un divisor m1 de m tal que m = m1m2
donde m1  1 y m1  m.

Observación:
El 1 no es primo ni compuesto. No es primo porque no tiene dos divisores positivos distin-
tos. No es compuesto pues no tiene otros divisores distintos de la unidad y de sí mismo. El
mínimo entero positivo que es compuesto es 4 y sus divisores positivos son 1, 2, 4.

Definición 3.4
Un entero positivo p  1 es un número primo si sus únicos divisores positivos son 1 y p.

Observaciones:
1. La definición de número primo se puede extender a los enteros de esta manera: un en-
tero p es un número primo si tiene exactamente cuatro divisores distintos: 1, 1, p y p.
2. El 0 no es primo porque todo entero no nulo divide a 0, es decir, posee más de 4 divi-
sores. Nosotros trabajaremos sólo con los primos mayores que 1.

181
Matemática Discreta

Ejemplo 10
Probaremos que 2 es un número primo. En efecto, sean a y b enteros positivos tales que
2 = a b. Si a=1 entonces b=2 y 2 es primo. Si a 1, entonces a  1 y como b  0, a b  1 b
= b, de donde 2  b. Luego b = 1 y como consecuencia a = 2, de donde resulta que los
únicos divisores de 2 son 1 y 2.

Existe una relación fácil de verificar entre números primos y compuestos expresada a
través de la siguiente propiedad.

Propiedad 3.2
Si n  Z+ y n es un número compuesto, entonces existe un número primo p tal que p|n.
Es decir, todo número compuesto admite al menos un divisor que es un número primo.

Demostración:
Suponemos lo contrario. Es decir, suponemos que el conjunto S = {n  Z+: n es número
compuesto y no tiene divisores primos} es no vacío.
Si S  , como es un subconjunto de los enteros positivos, por el principio de la buena
ordenación, S tiene un elemento mínimo m.
Como m  S, el elemento m es compuesto y no tiene divisores primos. Es posible escribir
a m como m = m1 m2 donde 1  m1  m y 1  m2  m.
Como m1  S porque m es el elemento mínimo de S, entonces m1 es primo o tiene diviso-
res primos. Cualquiera sea el caso, existe un primo p tal que p divide a m, y esto contradice
nuestra suposición. Luego S = .

TEOREMA 3.2: Un legado de Euclides.

Existen infinitos números primos.

Demostración:
Supongamos por el contrario que este resultado es falso. Es decir que sólo existe un
número finito de números primos p1, p2 ... pk, que son mayores que 1. Entonces cualquier
primo de Z es alguno de los pi, 1  i  k.
Formemos el número entero p1 p2 ... pk, producto de todos los primos de Z. El número
q = (p1 p2 ... pk) + 1 no es 1 pues p1 p2 ... pk >1 y además q es mayor que cada uno de los pi,
1  i  k, y por lo tanto no es primo. Luego q es un número compuesto. Por la propiedad
anterior, existe un primo, que será alguno de los pi, 1  i  k, tal que pi|q. Como pi|q y
pi|p1 p2... pk resulta por Teorema 3.1, que pi|1, de donde pi = 1 lo cual es un absurdo pues
pi > 1, 1  i  k. Esta contradicción surge al suponer que sólo existe un número finito de
primos.

182
 Teoría de Números e Inducción

Propiedad 3.3
Para verificar que un entero dado n > 1 es primo, basta con comprobar que ningún primo
p tal que p  n lo divide.

Demostración:
Probaremos que un número entero n  1 es un compuesto si y sólo si es divisible por un
primo p  0 tal que p  n . Sea n un entero mayor que 1, luego, n es divisible por un primo q
que es positivo. Es decir, el conjunto de los primos positivos que dividen a n es no vacío y
luego tiene un primer elemento o elemento minimal que denotamos por p. Luego n = p c,
siendo c un entero. Si n no es primo entonces 1  c y como p es el mínimo, debe ser que
p  c. Luego, multiplicando ambos miembros por p, tenemos que p2  p c = n, y por lo tanto
p n.

Ejemplo 11
Usamos la propiedad anterior para responder las siguientes preguntas:
a) ¿Es 247 un número primo? Bastará con estudiar si el número dado es divisible por
algún primo p  247  15,72. Todos los primos positivos a estudiar son p = 2, 3, 5, 7, 11,
13. El número 247 no es divisible por 2, ni por 3, ni por 5, 7 u 11. Pero es divisible por 13.
Luego 247 no es un número primo, es un número compuesto y más aún, 247=13 · 17.
b) ¿Es 101 un número primo? Calculamos 101  10,05 . Los primos menores o iguales
que 101 son 2, 3, 5, 7. Pero como ninguno de ellos divide a 101, concluimos que 101 es
primo.

Ejemplo 12
Construimos la sucesión de números enteros positivos:
q1 = 2 + 1
q2 = 2 · 3 +1
q3 = 2 · 3 · 5 +1

qn = 2 · 3 · 5 · … · pn +1
donde cada qi, 1 ≤ i ≤ n es el producto de los n primeros primos más uno. Nos pregunta-
mos ¿qn es un número primo para cada n?
Probando vemos que: 2 + 1 = 3 es primo; 2 · 3 + 1 = 7 es primo; 2 · 3 · 5 + 1 = 31 es
primo. Estas pruebas nos llevan a pensar que tal vez la afirmación sea cierta, sin embargo
2 · 3 · 5 · 7 · 11 · 13 +1 = 30.031 = 59 · 509 no es primo y por lo tanto la afirmación es falsa.
¿Puedes encontrar otro ejemplo en el que el producto 2 · 3 · 5 · … · p n +1 no arroje un
número primo?

Dado un entero n, los enteros pueden clasificarse en aquellos que son múltiplos de n y los
que no son múltiplos de n. Muchos de los resultados de la teoría de números se obtienen

183
Matemática Discreta

clasificando los enteros que no son múltiplos de n de acuerdo a sus restos en la división por
n. El siguiente teorema llamado teorema de la división o algoritmo de la división es la base de
esta idea.

TEOREMA 3.3: El algoritmo de la división.

Si a, b  Z con b > 0 entonces existen q, r  Z, únicos, tales que a = b q + r con
0  r  b. Decimos que a es el dividendo, b es el divisor, q es el cociente y r es el resto de la
división de a por b.

Ejemplo 13
a) Para a = 220 y b = 13, se obtiene 220 = 13 · 16 + 12 por el algoritmo de la división. Es
decir, el cociente es q = 16 y el resto es r = 12.
b) Para a = 1.331 y b = 11 se obtiene 1.331 = 11 · 121. En este caso, como r = 0, enton-
ces 11 divide a 1.331.
El teorema anterior dice que dados un dividendo a y un divisor b ambos enteros, con
b > 0, existen y son únicos un cociente q y un resto r que verifican a = b q + r, donde r es
no negativo y menor que b.
Veamos como proceder cuando el dividendo es negativo y el divisor positivo, para obte-
ner el resto no negativo y menor que el divisor.

Ejemplo 14
Sean a, b  Z+:
a) Si a = b q para algún q  Z+ entonces podemos escribir (a) = b (q).
Para el dividendo (a)  0 y el divisor b  0, el cociente es (q)  0 y el resto es 0.
b) Si a = b q + r para algún q  Z+ y 0  r  b entonces:
(a) = b (q)  r = b (q)  b + b  r = b (q 1) + (b  r).
Para el dividendo (a)  0 y el divisor b  0, el cociente es (q 1)  0 y el resto, b  r, ve-
rifica las desigualdades 0  b  r  b.
Este ejemplo conduce al siguiente resultado general.

TEOREMA 3.4: El algoritmo de la división generalizado en Z.

Sean a, b  Z, b  0. Existen y son únicos, los enteros q, r tales que a = b q + r, con
0  r |b|.

Ejemplo 15
a) Para a = 630 y b = 90 se obtiene 630 = 90 (7).
b) Para a = 450 y b = 80 se obtiene que 450 = 80 (6) + 30 pues 450 = 80 · 5 + 50,
luego 450 = 80 (5)  80 + 80  50 = 80 (51) + (80  50) = 80 (6) + 30, siendo los
enteros q 1 = (5) 1 = 6 y b  r = 80  50 = 30.

184
 Teoría de Números e Inducción

c) Para a = 735 y b =  31, como 735 = 31 · 23 + 22, entonces:

735 = (31) 23  22
= (31) 23  31 + 31  22 =
= (31) (23 + 1) + (31  22) = (31) 24 + 9.
Entonces q = 24 y r = 9 verifica 0  9 |31|.
d) Sean a = 735 y b =  31. Obtenemos 735 = 31 · 23 + 22; reescribiendo en términos
de b, 735 = (31) (23) + 22; luego q = 23 y r = 22 verifica 0  22 |31|.

Observación:
Notemos que en todos los casos el resto en el algoritmo de la división es siempre un
número no negativo.

Actividad 2
Problema Nº1: Examina si cada uno de los subconjuntos de Q, es bien ordenado:
1.1) Y1 = {x  Q : x = 1 / 2n, n  N}
1.2) Y2 = {x  Q : x = 1 / 3n, n  N}
1.3) Y3 = {x  Q : x = 1 / n, n  Z, n  0}
1.4) Y4 = {x  Q : x = 1 / n, n  N}  {0}
1.5) Y5 = N

Problema Nº2: Prueba los siguientes resultados:

2.1) Si a  N y a|1, entonces a = 1.
2.2) Sean a, b, c enteros positivos. Entonces, a = b c implica b  a y c  a.

Problema Nº3: Sean a, x, y enteros, donde a  0. Prueba que si a x = a y entonces x = y,

utilizando operaciones definidas en Z.

Problema Nº4: Si n  Z+, ¿cuáles de los siguientes números enteros tienen a 2 como divi-
sor?
4.1) 3n2 + 1 4.5) 3(1)n−1 + 3(1)n
4.2) n (n + 1) 4.6) n (3n +1)
4.3) n (n + 2) 4.7) (n + 1) (5n + 2)
4.4) n  n
3
4.8) (n  1) (n + 1)

Problema Nº5: Prueba que:

5.1) a|a2; a|a3; ...; a|an si n es natural y a  0.
5.2) Sean x, y, z enteros. Si z = x + y y a divide a los enteros y, z, entonces a divide al en-
tero x.
5.3) Si a  Z y a|1 entonces a = 1 o a = 1.

185
Matemática Discreta

5.4) Son proposiciones equivalentes:

a) a|b b) a||b| c)|a||b d)|a|||b|

Problema Nº6: Sean a, b, c  Z+:

6.1) Si se verifica que a|b c, ¿es cierto que a|b o que a|c?
6.2) Dar otro ejemplo, distinto al del ejemplo 4, donde se verifique que a|b y c|b, pero
que a c | b.
6.3) ¿Es cierto que si a|b2 entonces a|b?

Problema Nº7: Sean a, b, c  Z. Demuestra que si a | (bc), entonces a | b y a | c.

Problema Nº8: Resuelve:

8.1) La ecuación 24x + 72y + 48z = 35, ¿tiene soluciones enteras?
8.2) Encuentra tres enteros positivos x, y, z tales que 31|5x + 7y + 11z.

Problema Nº9: Demuestra que:

9.1) 3 es un número primo.
9.2) 5 es un número primo.

Problema Nº10: Verifica si los siguientes números son primos: 211, 1.001, 473.

Problema Nº11: Encuentra el cociente q y el resto r en cada uno de los siguientes casos,
siendo a el dividendo y b el divisor:
11.1) a = 31 y b = 11
11.2) a = 45 y b = 8
11.3) a = 0 y b = 36
11.4) a = 137 y b = 22

Problema Nº12: Demuestra que no existen enteros entre 0 y 1.

(Sugerencia: Niega la tesis y utiliza el principio de buena ordenación con el conjunto
S = {c  Z+ : 0 < c < 1}. ¿Qué pasa con el cuadrado del elemento mínimo de S?)

3.4 El máximo común divisor y el mínimo común múltiplo

Dado el concepto de divisor de un entero, deseamos introducir la noción de máximo
común divisor de dos o más enteros y posteriormente el de mínimo común múltiplo. Sin
embargo, por razones que veremos más adelante, evitaremos hacer uso del tamaño del
entero en la definición.

186
 Teoría de Números e Inducción

Definición 3.5
Sean a, b  Z. Un entero positivo c es un divisor común de a y de b si c divide a ambos,
es decir, si c|a y c|b.

Ejemplo 16
Los divisores comunes de 30 y 12 son 1, 2, 3, y 6, de los cuales 6 es el mayor. Los núme-
ros 13 y 15 tienen un único divisor común que es 1.

Definición 3.6
Sean a, b  Z no ambos nulos; d  Z+ es el máximo común divisor de a y b si:
i) d|a y d|b.
ii) Para todo entero c tal que c|a y c|b entonces c|d.
Indicamos al máximo común divisor d de a y b como d = mcd(a, b).
Definimos el mcd(0, 0) = 0.

Ejemplo 17
mcd(12, 30) = 6, mcd(42, 70) = 14, mcd(5, 7) = 1, mcd(0, 5) = 5.
mcd(12, 30) = 6, mcd(42, 70) = 14, mcd(5, 7) = 1, mcd(0, 5) = 5.

Propiedad 3.4
Sean a y b números enteros. Si c|a y c|b entonces c|mcd(a, b).

Demostración:
Se verifica en forma inmediata ya que si d = mcd(a, b) y si c es un entero tal que c|a y
c|b entonces c|d por su definición, es decir c|mcd(a, b).

Propiedad 3.5
Sean a, b  Z no ambos nulos. Se verifican:
i) mcd(a, b) = mcd(b, a)
ii) mcd(a, b) = mcd(a, b)
iii) mcd(a, b) = mcd(a, b)
iv) mcd(a, 0) = a
v)  k  Z mcd(a, ka) = a
vi) mcd(a, b) = mcd(b, r) siendo r el resto de dividir a por b, es decir, a = q b +r con
0 ≤ r <b.

Demostración del ítem i):

Sea d = mcd(a, b), entonces d verifica que d|a y d|b y si c|a y c|b entonces c|d. Te-
niendo en cuenta que la conjunción es conmutativa, esto se puede escribir como d|b y d|a
y si c|b y c|a entonces c|d. De donde d = mcd(b, a).

187
Matemática Discreta

Demostración del ítem ii):

Sea d = mcd(a, b), entonces d verifica que d|a y d|b.
Veamos que d cumple con las condiciones de ser el mcd(a, b).
Como d|a entonces d|(a) porque a se puede escribir como a = d k, para algún k  Z,
luego a = d (k), para algún entero (k). Entonces d|(a) y d|b. Además, todo entero c tal
que c|(a) y c|b, verifica también que c|a y c|b luego c|d porque d = mcd (a, b). Luego
d = mcd (a, b)

Demostración del ítem iii):

Si a  0 y b  0 entonces |a|= a y |b|= b luego se verifica la tesis.
Si a  0 y b  0 entonces |a|= a y |b|= b luego se verifica la tesis (por ii). Análogamen-
te si a  0 y b  0.
Si a  0 y b 0 entonces |a|= a y |b|= b.
Entonces mcd (a, b) = mcd(a, b) = mcd(a, b) = mcd(a, b) (por ii).

Demostración del ítem iv):

Si a  0 entonces |a|= a y por consiguiente |a||a y |a||0. Sea c un entero positivo tal
que c||a| y c|0, luego c||a|, entonces |a|= mcd(a, 0).
Si a  0 entonces |a|= a y también se verifica porque (a)|a y (a)|0 y si c es tal que
c|(a) y c|0, luego c|(a), o lo que es lo mismo, c||a|. Con lo que completamos la prueba
de que |a|= mcd(a, 0).

Dejamos como ejercicio al lector la prueba del ítem v)

Demostración del ítem vi):

Sea d = mcd(a, b). Vamos a mostrar que d = mcd(b, r), es decir vamos a probar que
d|b, d|r y que si c|b y c|r entonces c|d.
Como a = q b + r y d|a y d|b por ser el máximo común divisor de ellos, entonces tene-
mos que d|(a − q b) y por lo tanto d|r.
Además, si c|b y c|r entonces c|(q b + r) y por lo tanto c|a. Pero como d es el máximo
común divisor de a y b tenemos que c|d.
Luego d = mcd(b, r).

TEOREMA 3.5
Si a, b son enteros no ambos nulos, entonces su máximo común divisor d existe, es único
y además existen enteros m0, n0 tales que d = m0 a + n0 b.

Demostración:
Dados a, b, enteros no ambos nulos, formemos todas las combinaciones lineales enteras
y llamamos A = {m a + n b : m, n  Z}.

188
 Teoría de Números e Inducción

Como a, b no son simultáneamente nulos, A = {m a + n b : m, n  Z} tiene elementos

que no son cero.
Más aún, si x  A y x < 0 entonces (x)  A y (x) > 0, ya que si x = m1 a + n1 b enton-
ces (x) = (m1) a + (n1) b. Luego A tiene elementos positivos.
Consideremos el conjunto A+ = {a  A : a > 0}  A.
Por el principio de la buena ordenación, existe un elemento mínimo d en A+.
Como d  A+  A existen m0, n0  Z que verifican d = m0 a + n0 b.
Veamos que d es el máximo común divisor buscado. Sea c  Z+ tal que c|a y c|b enton-
ces, c|(m0 a + n0 b), es decir c|d.
Falta demostrar que d|a y d|b. Como a y d son enteros y d > 0, por el algoritmo de la di-
visión tenemos que a = d q + r, donde 0  r  d.
Reemplazando d por su valor se obtiene a = (m0 a + n0 b) q + r de donde resulta que r =
(q n0) b + (1  q m0) a, pertenece a A. Pero r < d, y como d es el mínimo de los elementos
positivos de A, r no puede ser positivo, por consiguiente r = 0 y a = d q, lo que implica que
el entero d|a. De manera similar podemos demostrar que d|b.
Hemos probado que d es máximo común divisor de a y b. Para probar la unicidad de d,
supongamos que existe t  0 tal que t|a, t|b y tal que para cualquier c que verifique c|a y
c|b entonces c|t. Como d = mcd(a, b), t|a y t|b entonces t|d. De la misma forma, como
d|a y d|b, por las propiedades de t tenemos que d|t. Luego, t = d.

Observaciones:
1. El recíproco de este Teorema no es cierto. Sin embargo, si dados dos enteros a y b no
nulos, existen m0 y n0 tales que 1 = a m0 + b n0 entonces, 1 = mcd(a,b).
2. Del Teorema anterior se deduce que, para dos enteros a, b no ambos nulos, si el
máximo común divisor existe, entonces éste es único y es el menor entero positivo que se
puede escribir como combinación lineal entera de a y b.

Ejemplo 18
La representación de d = mcd(a, b) como d = m0 a + n0 b, donde m0, n0 son enteros, no
es única. En efecto, 2 = mcd(4, 6) y se puede escribir como:
2 = 2 · 4 + (1) 6
= (2 + 3) 4 + (1  2) 6
= (2 + 6) 4 + (1  4) 6
= 8 · 4 + (5) 6.
Si mcd(a, b) = d = m0 a + n0 b y t es un múltiplo de a y de b, entonces t = a k = b h, cal-
culando:
d = m0 a + n0 b = m0 a + n0 b +t – t = m0 a + k a + n0 b  h b = (m0 + k) a + (n0  h) b,
con lo que la combinación lineal entera para d = mcd(a, b) no es única.
Veamos otro ejemplo: mcd(36, 28) = mcd(36, 28) = 4
4 = (3) 36 + (4) (28)

189
Matemática Discreta

= (3) 36 + (4) (28) + 36 · 28  36 · 28

= 25 · 36 + 32 (28), asociando convenientemente.

Corolario 3.6
Para a y b  Z y para n  Z+ U {0}, se verifica que: mcd(a n, b n) = n mcd(a, b).

Demostración:
Si n = 0 se verifica trivialmente. Si n es positivo, mcd(a n, b n) es el menor entero positivo
del conjunto {x a n + y b n : x, y  Z} = {(x a + y b) n : x, y  Z} que es n veces, el menor
entero positivo del conjunto {x a + y b : x, y  Z}.

Corolario 3.7
Para todo a, b, n enteros positivos, si n|a b y mcd(a, n) = 1, entonces n|b.

Demostración:
Si n|a b entonces a b = n k, para algún entero k. Como 1 = m 0 a + n0 n, entonces el en-
tero b = m0 a b + n0 n b = m0 n k + n0 n b = n (m0 k + n0 b), siendo este último factor
(m0 k + n0 b) un entero, por lo que n|b.

Propiedad 3.8
Para a, b enteros no nulos y d = mcd(a, b), se verifica que mcd(a/d, b/d) = 1.

Demostración:
Sea d = mcd(a, b). Luego existen enteros x, y tales que d = x a + y b. Dado que d|a y
d|b, existen enteros m, n tales que a = m d y b = n d. Notemos además que a/d y b/d son
enteros. Sustituyendo a y b obtenemos d = x (m d) + y (n d) donde x, y, m, n son enteros.
Operando algebraicamente tenemos que d = (x m + y n) d de donde deducimos que
(x m + y n) = 1 por ser Z un dominio entero. Como 1 es el menor entero positivo y vimos
que se puede escribir como combinación lineal entera de m y n entonces 1 = mcd(m, n) =
mcd(a/d, b/d).

Ejemplo 19
Dados dos enteros positivos, 12 y 30, mcd(12, 30) = 6 entonces existen x, y  Z tales que
6 = x 12 + y 30 o , dividiendo por 6, 1 = x 2 + y 5, de donde se sigue que x = 2 e y = 1 es
solución. Pero para k  Z, 1 = 2((2) 5k) + 5 (1 + 2k), luego, las soluciones para x, y no
son únicas.

En este ejemplo fue posible hallar fácilmente el máximo común divisor, además de los va-
lores para x e y porque trabajamos con números pequeños. Sin embargo, cuando los ente-

190
 Teoría de Números e Inducción

ros no son pequeños, encontrar el mcd no es una tarea fácil. Veamos como se puede en-
contrar el máximo común divisor para a, b enteros positivos arbitrarios.
Supongamos que queremos encontrar mcd(315, 113). La respuesta la da el siguiente
Teorema debido a Euclides que permite encontrar el máximo común divisor de dos enteros
positivos por divisiones sucesivas. La restricción en este Teorema a dos enteros positivos se
justifica por Propiedad 3.5.

TEOREMA 3.6: Algoritmo de Euclides

Sean a, b  Z+.
Si a = b, entonces mcd(a, b) = a = b.
Si a > b y b es divisor de a, entonces mcd(a, b) = b.
Si a > b y b no es divisor de a, por el algoritmo de la división se tiene:
a = b q1 + r 1 0  r1  b
Si r1 es divisor de b, entonces mcd(a, b) = mcd(b, r1) = r1.
Si r1 no es divisor de b, por el algoritmo de la división se tiene:
b = r1 q 2 + r 2 0  r2  r1
Si r2 es divisor de r1, entonces mcd(a, b) = mcd(b, r1) = mcd(r1, r2) = r2.
Si r2 no es divisor de r1, por el algoritmo de la división se tiene:
r1 = r2 q3 + r3 0  r3  r2
Y reiterando el procedimiento anterior hasta obtener el resto nulo:

ri = ri+1 qi+2 + ri+2 0  ri+2  ri+1

rk3 = rk2 qk1 + rk1 0  rk1  rk2
rk2 = rk1 qk + rk 0  rk  rk1
rk1 = rk qk+1
Entonces el último resto no nulo es igual al mcd(a, b).

El uso de la palabra algoritmo en el enunciado no es casual. En efecto, siguiendo los pa-

sos indicados en el enunciado del teorema se construye un algoritmo que recibe dos enteros
positivos como entrada y genera su máximo común divisor como salida. El lector puede
ampliar estos conceptos en nuestra lectura complementaria.

Ejemplo 20
a) Determinaremos el mcd(315, 113). Luego expresaremos el resultado como una combi-
nación lineal de los enteros dados:
315 = 2 · 113 + 89 0  89  113
113 = 1 · 89 + 24 0  24  89
89 = 3 · 24 + 17 0  17  24
24 = 1 · 17 + 7 0  7  17

191
Matemática Discreta

17 = 2 · 7 + 3 0 3  7
7=2·3+1 0 1  3
3=3·1
Como 1 es el último resto no nulo, entonces 1 = mcd(315, 113).
Escribamos ahora a 1 como una combinación lineal de 315 y 113. Si despejamos todos
los restos no nulos en las igualdades anteriores tenemos que:
315 − 2 · 113 = 89
113 − 1 · 89 = 24
89 − 3 · 24 = 17
24 − 1 · 17 = 7
17 − 2 · 7 = 3
7−2·3=1
Trabajando en reversa, desde atrás hacia delante, a partir del último renglón resulta:
1=72·3
= 7  2 (17  2 · 7)
= (2) 17 + 5 · 7
= (2) 17 + 5 (24  1 · 17)
= 5 · 24 + (7) 17
= 5 · 24 + (7) (89  3 · 24)
= (7) 89 + 26 · 24
= (7) 89 + 26 (113  1 · 89)
= 26 · 113 + (33) 89
= 26 · 113 + (33) (315  2 · 113)
= (33) 315 + 92 · 113.
Luego, hemos escrito a 1 = mcd(315,113) como combinación lineal de ellos.
Los enteros 315 y 113 se denominan coprimos, primos relativos o primos entre sí porque
el mcd(315, 113) = 1.

b) Encontraremos el mcd(1.341, 743) y luego lo expresaremos como combinación lineal

entera de los números dados.
1.341 = 743 · 1 + 598
743 = 598 · 1 + 145
598 = 145 · 4 + 18
145 = 18 · 8 + 1
18 = 18 · 1
Como 1 es el último resto no nulo, luego mcd(1.341, 743) = mcd (1.341, 743) = 1. Tra-
bajando de la misma forma que en el ejemplo anterior tenemos:
1 = 145 – 18 · 8
= 145 – (598 – 145 · 4) 8
= (8) 598 + 145 + 32 · 145

192
 Teoría de Números e Inducción

= (8) 598 + 33 · 145

= (8) 598 + 33 (743 – 598 · 1)
= (8) 598 + 33 · 743 – 33 · 598
= (41) 598 + 33 · 743
= (41) (1.341  743) + 33 · 743
= (41) 1.341 + 41 · 743 + 33 · 743
= (41) 1.341 + 74 · 743
Hemos escrito ahora el 1 como combinación lineal de 1.341 y 743. Como queremos ex-
presarlo como combinación lineal de 1.341 y 743 escribimos:
1 = (41) 1.341 + 74 · 743 = 41 (1.341) + 74 · 743
c) Dejamos a cargo del lector verificar que
6 = mcd(450, 372) y que 6 = 19 (450) + (23) (372)

Ejemplo 21
Se desea embaldosar un salón de 4.410 cm de ancho por 8.085 cm de largo con baldo-
sas cuadradas que sean lo más grande posible y tal que no sea necesario cortar ninguna de
ellas. ¿Cuál debe ser la longitud del lado de cada baldosa? ¿Cuántas baldosas se necesitan
para cubrir el suelo de la habitación?
Supongamos que la longitud de los lados de cada baldosa es “a” cm. Luego, “a” debe
dividir tanto al ancho de la habitación como así también al largo de la misma, es decir,
a|4.410 y a|8.085, porque las baldosas son cuadradas y no se cortan. Además, como que-
remos que cada baldosa sea lo más grande posible, a debe ser el más grande de todos los
números que dividen a 4.410 y a 8.085. En conclusión, a debe ser el máximo común divisor
entre 4.410 y 8.085.
Luego,
8.085 = 4.410 · 1 + 3.675
4.410 = 3.675 · 1 + 735
3675 = 735 · 5
Por lo tanto, la longitud del lado de cada baldosa deberá ser de a = mcd(8.085, 4.410) =
735 cm.
Finalmente 8085 = 11 · 735 y 4.410 = 6 · 735, por lo tanto, se necesitarán 11 · 6 = 66
baldosas.

Ejemplo 22
Encontremos, si existe, una solución entera para la ecuación 6 x + 10 y = 104.
Como mcd(6,10) = 2, dividimos ambos miembros de la ecuación por 2. Obtenemos
3 x + 5 y = 52.
Por el algoritmo de la división, mcd(3, 5) = 1 = 3 · 2 + 5 (1). Luego:
52 = 3 · 104 + 5 (52) y multiplicando por 2 obtenemos que

193
Matemática Discreta

104 = 6 · 104 + 10 (−52). Por lo tanto x = 104 y = −52 es solución. Pero ésta no es la
única solución, ya que 104 = 6 (104  5k) + 10 (52 + 3 k), donde k  Z.

Definición 3.7
Una ecuación, en una o más variables, con la restricción de que sus soluciones sean
números enteros se denomina ecuación diofántica.
La ecuación diofántica más simple es la ecuación diofántica lineal en dos variables
a x + b y = c, donde a, b y c son enteros dados, con a y b no ambos nulos. Veamos bajo
qué hipótesis, estas ecuaciones tienen soluciones enteras.

TEOREMA 3.7
Sean a, b, c enteros. La ecuación diofántica a x + b y = c tiene una solución entera
x = x0, y = y0 si y sólo si el mcd(a, b) divide a c.

Demostración:
Supongamos que la ecuación diofántica a x + b y = c tiene una solución entera x = x0,
y = y0, luego a x0 + b y0 = c. Si d = mcd(a, b) entonces d|a y d|b; y por el Teorema 3.1,
d|a x0 + b y0 es decir d|c.
Recíprocamente, sea d = mcd(a, b), que por hipótesis es divisor de c. Existen entonces
dos enteros x1 e y1 tales que d = a x1 + b y1. Como d es un divisor de c entonces existe un
entero k tal que c = d k, y reemplazando el valor de d tenemos que c = (a x1 + b y1) k =
=a (x1 k) + b (y1 k) por lo que la ecuación diofántica tiene una solución entera tomando
x0 = x1 k, y0 = y1 k.

Ejemplo 23
Encontremos, si existen, las soluciones enteras de la ecuación 243 x +198 y = 9.
Calculemos primero el mcd(243, 198) con el algoritmo de Euclides. Tenemos que
243 = 198 · 1 +45
198 = 45 · 4 + 18
45 = 18 · 2 + 9
18 = 2 · 9
Como el último resto no nulo es 9, entonces mcd(243, 198) = 9. Ahora por el Teorema an-
terior tenemos que como 9|9, la ecuación diofántica 243 x +198 y = 9 tiene solución.
Trabajemos ahora en reversa para escribir a 9 como una combinación lineal de 243 y 198.
9 = 45 − 18 · 2
= 45 − (198 − 4 · 45) 2
= 45 · 9 − 198 · 2
= (243 − 1 · 198) 9 − 198 · 2
= 243 · 9 − 198 · 11
= 243 · 9 + 198 (−11).

194
 Teoría de Números e Inducción

Entonces una solución de la ecuación diofántica es x0 = 9, y0 = −11.

Si queremos encontrar más soluciones de esta ecuación podemos hacerlo de la siguiente
manera:
9 = 243 · 9 + 198 (−11)
= 243 · 9 + 243 · 198 k − 243 · 198 k +198 (−11)
= 243 (9 + 198 k) + 198 (−243 k −11)
Y por lo tanto obtenemos infinitas soluciones de la ecuación diofántica que son de la for-
ma x = 9 + 198 k, y = −11 − 243 k, con k  Z. Si elegimos k = 0, obtenemos la solución
particular x0, y0.
En el ejemplo anterior encontramos infinitas soluciones de una ecuación a x + b y = c,
utilizando una solución particular x0, y0 y sumando y restando un múltiplo entero del producto
a b. Sin embargo este método no nos proporcionará en general todas las soluciones. Para
obtener todas las soluciones hay que sumar y restar un múltiplo entero del mínimo común
múltiplo de a y b, cuya definición vemos a continuación.

Definición 3.8
Sean a, b  Z no ambos nulos; c  Z+ es el mínimo común múltiplo de a y b si:
i) a|c y b|c,
ii) Para todo entero d tal que a|d y b|d entonces c|d.
Se indica c = mcm(a, b). Definimos el mcm(0, 0) = 0.

De la definición se deduce que si c = mcm(a, b) y si d es un múltiplo común de a y b en-

tonces c|d. Es decir, c es el mínimo común múltiplo de a y b si es el menor entero positivo
que es múltiplo de a y b.

Ejemplo 24
Para calcular el mcm(3, 5) pensamos en los múltiplos comunes a ambos: 15, 30, 45, 60,
75, ... y de ellos tomamos aquel que es divisor de todos los múltiplos comunes. Concluimos
que mcm(3, 5) = 15.

Ya sabemos que si tenemos tres enteros a, b, c tales que a|c y b|c, no es siempre cierto
que (a b)|c. Sin embargo, sí es cierto si dividimos por mcm(a,b), como vemos en la siguien-
te propiedad:

Propiedad 3.9
Sean a, b, c  Z. Si a|c y b|c entonces mcm(a,b)|c.

Demostración:
Se verifica en forma inmediata ya que si t = mcm(a, b) y si c es un entero tal que a|c y
b|c entonces por definición t|c, es decir mcm(a,b)|c.

195
Matemática Discreta

Ejemplo 25
Queremos encontrar todos los enteros positivos menores que 1.000 divisibles por 2 y por
3. Para ello podemos utilizar la propiedad anterior.

Como los múltiplos comunes a 2 y 3 son 6, 12, 18, 24, … y el menor es 6, entonces el
mcm(2, 3) = 6. Si c es un entero divisible por 2 y por 3 entonces también será divisible por 6,
por la propiedad anterior. Por lo tanto, todos los enteros que sean divisibles por 2 y 3 si-
multáneamente serán de la forma c = 6 k con k  Z. Como buscamos aquellos tales que
0 < c <1.000, entonces 0 < 6 k < 1.000 o lo que es lo mismo 0 < k < 1.000/6 ≈ 166,6.
En consecuencia, todos los enteros positivos menores que 1.000 son de la forma c = 6 k,
con 1 ≤ k ≤ 166.

El siguiente teorema proporciona una forma de calcular el mínimo común múltiplo de dos
números utilizando el máximo común divisor de ellos.

TEOREMA 3.8
Para a, b  Z+ se verifica que mcm(a, b) mcd(a, b) = a b.

Demostración:
Sean h, k enteros tales que a = k mcd(a, b) y b = h mcd(a, b). Observar que tales enteros
existen pues mcd(a, b) es un divisor de a y de b.
Luego k = a / mcd(a, b) y h = b / mcd(a, b). Por la Propiedad 3.9 podemos asegurar que
mcd(k, h) = 1.
Sea t = h a. Luego t = h a = h k mcd(a, b) es múltiplo de a, pero también es múltiplo de
b. En efecto, t = h a = h k mcd(a, b) = k (h mcd(a, b)) = k b.
Sea c un entero que es múltiplo de a y de b.
Luego c = m a y c = n b donde se sigue que m y n son enteros. Por sustitución obtene-
mos: c = m k mcd(a, b) ; c = n h mcd(a, b) de donde m k = n h. Luego h|m k, y como
mcd(k, h)=1 entonces h divide a m, y por lo tanto existe un entero s tal que m = s h. Final-
mente, c = m a = s h a = s t, es decir, t|c. Por lo tanto, t es el mcm(a, b) y se verifica que
mcm(a, b) = t = h k mcd(a, b) = [a / mcd(a, b)] b, o equivalentemente:
a b = mcm(a, b) mcd(a, b).

Observaciones:
1. Para a, b  Z, se verifica que: mcm(a, b) = mcm (|a|,|b|), de donde podemos escribir
que mcm(a, b) mcd(a, b) =|a||b|.
2. Para a, b  Z, si a y b son coprimos o relativamente primos, es decir mcd(a, b) =1, en-
tonces mcm(a, b) = |a b|.

196
 Teoría de Números e Inducción

Ejemplo 26
a) Hemos calculado que mcd(315, 113) = 1. Luego por el teorema anterior, el
mcm (315, 113) = 315 · 113 = 35.595.
b) El mcm(117, 1.326) = mcm(117, 1.326) = 117 · 1.326/ mcd(117, 1.326) =
=155.142 / 39 = 3.978.
c) Tres aviones de línea regular salen del aeropuerto, uno cada 3 días, otro cada 12 días y
el tercero cada 18 días. ¿Cada cuántos días saldrán los tres aviones a la vez?
Supongamos que los tres aviones salieron a la vez después de “a” días. Luego, a debe
ser múltiplo de 3, 12 y 18, pero además debe ser el menor múltiplo de los tres, por lo tanto, a
= 36.

Ejemplo 27
Continuando con el ejemplo 23, si queremos encontrar ahora todas las soluciones enteras
de la ecuación diofántica 243 x +198 y = 9, tenemos que calcular el mcm(243, 198).
Sabemos que el mcd(243, 198) = 9, así que por el teorema anterior tenemos que
mcm(243, 198) = 243 · 198 / 9 = 5.346.
Por otro lado, observemos que como 5.346 = mcm(243, 198) tenemos que
5.346 = 22 · 243 y 5.346 = 27 · 198.
Ahora podemos expresar la forma general de las soluciones de la ecuación diofántica.
9 = 243 · 9 + 198 (−11)
= 243 · 9 + 5.346 k − 5.346 k +198 (−11)
= (243 · 9 + 5.346 k) + (− 5.346 k +198 (−11))
= 243 (9 + 22 k) + 198 (−27 k −11)
Entonces todas las soluciones de la ecuación diofántica son de la forma:
x = 9 + 22 k ; y = −27 k −11 , donde k  Z.

Actividad 3
Problema Nº1: Sea a  Z, a ≠ 0. Prueba que: mcd(a, ka) = a,  k  Z.

Problema Nº2: Para cada uno de los siguientes pares de enteros determina el máximo
común divisor y exprésalo como una combinación lineal de ambos.
2.1) 250, 111
2.2) 1.820, 231
2.3) 456, 624
2.4) 1.769, 2.378

Problema Nº3: Si a = 630, b  Z+, mcd(a, b) = 105 y mcm(a, b) = 242.550 ¿Cuál es el

valor de b?

197
Matemática Discreta

Problema Nº4: Encuentra un par de soluciones enteras, si existen, para cada ecuación:
4.1) 105 x + 198 y = 27
4.2) 104 x + 91 y = 13
4.3) 31 x + 19 y = 7
4.4) 42 x + 26 y = 16
4.5) 288 x + 51y = 3
4.6) 52 x + 13 y = 1
4.7) 145 x + 58 y = 87
4.8) 243 x + 198 y = 9

Problema Nº5: ¿Para que valores enteros de c, 10  c  20, la ecuación diofántica

84x + 990y = c no tiene solución? Determina las soluciones para los otros casos.

Problema Nº6: 1.800 tornillos pesan tanto como 6.930 tuercas. ¿Cuál es el menor número
de tuercas y de tornillos para los cuales las tuercas pesan igual que los tornillos?

Problema Nº7: Sea la ecuación lineal a x +b y = c, con a, b, c  Z. Prueba que si x0, y0 es

una solución de esta ecuación entonces todas las soluciones resultan de las fórmulas:
x = x0 + b k / mcd(a,b) ; y = y0  a k / mcd(a,b), donde k  Z.
Sugerencia: primero prueba que para k entero,
x = x0 + b k / mcd(a,b), y = y0  a k / mcd(a,b)
satisfacen la ecuación diofántica, sabiendo que x0, y0 es una solución. Luego prueba que si
x, y es otra solución cualquiera entonces tiene la forma dada.

Problema Nº8: En un parque de diversiones cobran 180 pesos a los mayores y 75 pesos a
los menores. En un cierto día se recaudaron 9.000 pesos y asistieron más adultos que me-
nores. ¿Cuáles fueron los posibles números de asistentes?

Problema Nº9: Para cada uno de los siguientes pares de enteros determina el mínimo
común múltiplo entre ellos.
9.1) 250, 111
9.2) 1.820, 231
9.3) 456, 624
9.4) 1.769, 2.378
Observa que el mcd(a, b) para estos pares de enteros fue calculado en el problema Nº2.

Problema Nº10: Para cada uno de los siguientes pares de enteros a, b determina el
mcm(a, b).
10.1) 816, 7.209
10.2) 810, 570

198
 Teoría de Números e Inducción

10.3) 4.563, 624

10.4) 884, 1.292

Problema Nº11: Si c > 0, c|a, c|b, mcd(a/c, b/c) = 1 entonces c = mcd(a, b).

Problema Nº12: Resuelve:

12.1) Un comerciante desea poner en cajas 12.028 manzanas y 12.772 naranjas, de mo-
do que cada caja contenga el mismo número de manzanas y de naranjas y, además, el
mayor número posible. Hallar el número de naranjas de cada caja y el número de cajas ne-
cesarias.
12.2) Un coche necesita que le cambien el aceite cada 9.000 km, el filtro del aire cada
15.000 km y las bujías cada 30.000 km. ¿A qué número mínimo de kilómetros habrá que
hacerle todos los cambios a la vez?
12.3) En un sector rectangular de 40 m de largo por 52 m de ancho de una playa se de-
sea instalar carpas cuadradas que sean lo más grande posibles. ¿Cuántas carpas se podrán
instalar? ¿Cuál será el área de cada carpa?
12.4) Rosa tiene cubos azules de 5,5 cm de arista y cubos rojos de 4,5 cm de arista. Api-
lando los cubos en dos columnas, una de cubos azules y otra de cubos rojos, quiere conse-
guir que las dos columnas tengan igual altura. ¿Cuántos cubos, como mínimo, necesita de
cada color?

3.5 Primos relativos. Teorema fundamental de la aritmética

El primer resultado claro sobre la factorización única en productos de primos, el llamado
Teorema Fundamental de la Aritmética, fue enunciado por Gauss, en sus Disquisitiones
Arithmeticae de 1.801 (Gentile, 1.985).
En las secciones anteriores hemos estudiado varias propiedades y hemos resuelto ejerci-
cios donde el máximo común divisor de dos enteros era 1. Estos enteros se llaman copri-
mos, relativamente primos o primos entre sí y a continuación nos referiremos a propiedades
relacionadas con ellos.

Ejemplo 28
Los enteros 8 y 15 son coprimos ya que los divisores positivos de 8 son 1, 2, 4, 8 y los de
15 son 1, 3, 5, 15, luego mcd(8, 15) = 1.

Propiedad 3.10
Si b y c son coprimos con a, entonces b c es coprimo con a.

Demostración:
Como mcd(a, b) = 1, entonces 1 = ma + nb para m, n  Z. Luego, c = mac + nbc. Si

199
Matemática Discreta

d = mcd(a, b c) entonces d|a y d|bc, por consiguiente d|(mac + nbc) , de donde d|c.
Puesto que d|a y d|c y mcd(a, c) = 1, resulta d = 1. Por lo tanto, 1 = mcd(a, bc), por lo que
bc y a, son coprimos.

Propiedad 3.11
Sean a y b coprimos y c un entero tal que c|a y c|b, entonces c = 1 o c = 1.

Demostración:
Si c|a y c|b entonces c|mcd (a, b), es decir c|1. Luego c = 1 o c = 1.

Esta propiedad nos dice que si dos enteros son coprimos, los únicos divisores comunes
que tienen son 1 y –1. Si trabajamos en los enteros positivos, podemos asegurar que 1 es el
menor y único entero positivo que divide a ambos.

Propiedad 3.12
Sea p  Z+. Si a, b  Z, p es primo y p divide al producto ab entonces divide a uno de
ellos. En símbolos, si p es primo y p|a b, entonces p|a o p|b.

Demostración:
Sea p un primo tal que p|a b. Si p|a ya está probado. Si p no divide a a, entonces
mcd(p, a) = 1; luego 1 = m a + n p con m, n enteros. Multiplicando por b, obtenemos
b = m a b + n p b. Como p|a b, existe algún entero k tal que a b = k p y reemplazando
tenemos que b = m (k p) + n p b = (m k + n b) p para algún entero k. Luego, p|b.

TEOREMA 3.9
Si p es primo y p|( a1a2 ... an) entonces p|ai para algún i con 1  i  n.

Demostración:
Si p|ai para algún i, 1  i  n, no hay nada que probar. Si no es así, supongamos que p no
divide a a1, entonces p y a1 son primos relativos. Pero por hipótesis p|a1(a2 ... an) luego
p|a2 ... an. Se repite la demostración anterior reemplazando a1 por a2 y así sucesivamente
hasta obtener que p|ai para algún i con 1  i  n.

Los números primos desempeñan un papel muy importante en el conjunto de los núme-
ros enteros ya que todo entero mayor que 1 o bien es primo o bien es un producto de pri-
mos.

TEOREMA 3.10: Teorema fundamental de la aritmética.

Si n es un entero mayor que 1, entonces n es primo o puede escribirse de manera única
en la forma n = p1a1 p2a2 ... pkak donde p1  p2  ...  pk son números primos y los exponentes

200
 Teoría de Números e Inducción

a1, a2, ..., ak son enteros positivos.

Observaciones:
1. Al enunciar el Teorema 3.10 en la forma anterior aseguramos la unicidad de la des-
composición, ya que evitamos pensar que un entero positivo, por ejemplo, el número 6, se
pueda factorizar como 2 · 3 o 3 · 2 dando lugar a dos factorizaciones diferentes.
2. Otra forma análoga de enunciar este teorema, es expresar que cada entero mayor que
1, puede escribirse de manera única como un producto de primos, salvo el orden de los
factores.
3. La notación empleada permite usar los mismos factores primos para dos enteros cua-
lesquiera a condición de ponerle exponente cero a aquellos primos que no figuren en la
descomposición del número que se trate.

Ejemplo 29
Consideremos el número 35.700. Para determinar su factorización como producto de po-
tencias de primos, procedemos en la forma siguiente:
35.700 = 2 · 17.850 = 22 · 8.925 = 22 · 3 · 2.975 = 22 · 3 · 5 · 595 = 22 · 3 · 52 · 119 =
= 22 · 3 · 52 · 7 · 17.
Esta forma de expresar el número 35.700 como producto de potencias de primos se co-
noce como la “expresión normal de un número”.
La expresión normalizada de 25.200 es 25.200 = 24 · 32 · 52 · 7.

TEOREMA 3.11
Los únicos divisores del entero positivo n = p1a1 p2a2 ... pkak son los números de la forma
b = p1b1 p2b2 ... pkbk donde 0  b1  a1, ..., 0  bk  ak.

Corolario 3.13
Sean m, n  Z+ con n = p1a1 p2a2 ... pkak y m = p1b1 p2b2 ... pkbk donde pi es primo, ai  0 y
bi  0, para todo i. Entonces si ei = min{ai, bi} y fi = max{ai, bi},  i, se tiene que mcd (m, n)
= p1e1 p2e2 ... pkek y mcm(m, n) = p1f1 p2f2 ... pkfk.

Ejemplo 30
Usaremos las expresiones normales de 35.700 y de 6.000 para calcular el mcd y el mcm
entre esos números. Dado que, 35.700 = 22 · 3 · 52 · 7 · 17 y 6.000 = 24 · 3 · 53, resulta:
mcd(35.700, 6.000) = 22 · 3 · 52 · 70 · 170 = 300
mcm(35.700, 6.000) = 24 · 3 · 53 · 7 · 17 = 714.000

Actividad 4
Problema Nº1: Si a y b son coprimos, demuestra que mcm(a, b) =|a b|.

201
Matemática Discreta

Problema Nº2: Halla la descomposición en factores primos de:

2.1) 120
2.2) 720
2.3) 5.040
2.4) 3.675

Problema Nº3: Halla todos los números enteros positivos de tres cifras que sean divisibles
por 9 y por 11.

Problema Nº4: Sean a, p enteros, con p un número primo. Entonces a y p son coprimos,
si y sólo si p no divide al número a.

Problema Nº5: Sean m, n  Z+ tales que m n = 24 · 34 · 53 · 7 · 113 · 13.

Si el mcm(m, n) = 22 · 33 · 52 · 7 · 112 · 13. ¿Cuál es el mcd(m, n)?

Problema Nº6: Encuentra el número de divisores positivos de:

6.1) 148.500
6.2) 7.114.800
6.3) 7.882.875
6.4) 198.450

Problema Nº7: Dados a, b, c, d  N, decide si son verdaderas o falsas las siguientes afir-
maciones:
7.1) a|b y c|d  a c|b d
7.2) a|b y c|d  a + c|b + d

Problema Nº8: Demuestra las siguientes propiedades:

8.1) Si b|c y mcd(a, c) = 1, entonces mcd(a, b) = 1.
8.2) Si b|c entonces mcd(a, b) = mcd(a+c, b), para todo a  Z+.
8.3) Si mcd(a, c) = 1, entonces mcd(a, b) = mcd(a, b c).

Problema Nº9: Demuestra las siguientes propiedades:

9.1) mcm(ka, kb) =|k|mcm(a, b) cuando k no es nulo.
9.2) a|b si y sólo si mcm(a, b) =|b|
9.3) Si a = c e y b = c f, donde c = mcd(a, b) entonces mcm(a, b) = c|e||f|

3.6 Relaciones binarias en los enteros. La congruencia entera.

Recordemos los operadores binarios, div y mod; div: calcula el cociente entero de dos
números enteros; mod: calcula el resto no negativo de la división de dos números enteros.

202
 Teoría de Números e Inducción

Si a  Z y n  Z+, por el algoritmo de la división, existen únicos enteros q y r con 0  r  n

tal que a = n q + r.
Si utilizamos los operadores mod y div, resulta que q = a div n y r = a mod n. Luego, n es
factor de a si y sólo si a mod n = 0.
Si volvemos sobre el estudio del algoritmo de la división, podemos observar que al dividir
un entero por un número natural n se obtienen restos 0, 1, …, n  1, más aún, se observa
que dos números enteros tienen el mismo resto al dividirlos por n si y sólo si difieren en un
múltiplo de n. Con esta idea, y ya que tenemos una buena definición de resto o residuo en la
división de un entero por otro entero positivo n, es conveniente ahora proporcionar una nota-
ción especial para indicar la igualdad de los restos.
Observemos que 5 y 8 tienen el mismo resto al ser divididos por 3. En efecto, 5 = 3 · 1+ 2
mientras que 8 = 3 · 2 + 2. Entonces 5 mod 3 = 2 y 8 mod 3 = 2, es decir que podemos
escribir esto como (5 mod 3) = (8 mod 3). Análogamente (2 mod 3) = (4 mod 3) porque 2
= 3 · 0 + 2 y 4 = 3 (2) + 2.

Definición 3.9
Decimos que “x es congruente con y módulo n” y lo denotamos x  y (mod n) si el resto
de dividir a x por n coincide con el resto de dividir a y por n, es decir si (x mod n) =
=(y mod n).
Entonces, 5  8 (mod 3); 5  2 (mod 3), 4  2 (mod 3), 8  4 (mod 3).

Propiedad 3.14
Sean x, y enteros y n un entero positivo. Entonces, x  y (mod n) si y sólo si n es divisor
de (x  y).

Demostración:
x  y (mod n) si y sólo si (x mod n) = (y mod n) si y sólo si el resto de la división de x por n
es el mismo que el resto de la división de y por n, si y sólo si x = n q 1 + r, y = n q2 + r, para
enteros únicos q1 y q2, donde 0  r  n, si y sólo si restando miembro a miembro estas dos
igualdades, resulta x  y = n (q2  q1) siendo (q2  q1) un entero, si y sólo si, n es divisor de
(x  y).

Observaciones:
1. Por la proposición anterior tenemos que si x  y (mod n) entonces existe un entero k tal
que x = k n + y. Por lo tanto se tiene que todo entero x es congruente, módulo n, con el
resto de la división entera de x por n.
2. Dos números enteros distintos r y s tales que 0 ≤ r ≤ n  1 y 0 ≤ s ≤ n  1 no son
congruentes módulo n, porque no pueden diferir en un múltiplo de n. Por lo tanto, todo
número es congruente módulo n, con un único elemento del conjunto {0, 1, 2, …, n  1}.

203
Matemática Discreta

Ejemplo 31
49  38 (mod 11) ya que 49 = 11 · 4 + 5 y 38 = 11 · 3 + 5. Equivalentemente decimos
que 11 es divisor de (49  38), o sea 11|11.
También 13  52 (mod 5) porque 13 = 5 (3) + 2 y 52 = 5 · 10 + 2. Equivalentemente
decimos que 5 es divisor de (13  52), es decir 5|(65).

Definición 3.10
Una relación binaria  en los enteros es un subconjunto del producto cartesiano
Z x Z = {(a,b) : a, b  Z} de manera que un par de elementos a, b  Z x Z están relaciona-
dos por  si (a, b)  . En este caso decimos que “a se relaciona con b” y escribimos
a  b.

Una relación binaria en los enteros se dice que es una relación de equivalencia si satisfa-
ce las siguientes tres propiedades:
Reflexiva: para todo a  Z, a  a.
Simétrica: para todo a, b  Z, si a  b entonces b  a.
Transitiva: para todo a, b, c  Z, si a  b y b  c entonces a  c.

Las tres propiedades anteriores son muy importantes, ya que una relación de equivalen-
cia permite hacer una identificación o igualación entre los elementos que son equivalentes
entre sí, como veremos más adelante. La validez de las tres propiedades anteriores asegura
la consistencia de esa identificación.

Ejemplo 32
Un ejemplo que conocemos de una relación binaria en los enteros, que es una relación de
equivalencia, es la igualdad “=” entre números enteros. En efecto, si a es un número entero
entonces a = a y por lo tanto la relación es reflexiva. Si dos números enteros a, b satisfacen
que a = b entonces también se cumple que b = a, y por lo tanto la relación es simétrica. Y si
tenemos que tres números enteros a, b, c satisfacen que a = b y que b = c entonces tam-
bién a = c, confirmando la validez de la transitividad de esta relación.

Ejemplo 33
Sean x, y enteros y 3 un entero positivo. Sea  la relación binaria definida en Z que indica
que x  y si y sólo si “x es congruente con y módulo 3”, que es una relación de equivalencia
en Z. Esta relación se puede enunciar también diciendo: x  y (mod 3) si y sólo si x  y = 3 k,
para algún k  Z.
Para asegurar que x  y (mod 3) si y sólo si x  y = 3 k, para algún k  Z, es una relación
de equivalencia debemos verificar que se cumplen las propiedades reflexiva, simétrica y
transitiva.
Esta relación es reflexiva porque como x – x = 0 = 3 · 0, entonces 3|0.

204
 Teoría de Números e Inducción

Veamos que es simétrica. Si x  y (mod 3) entonces x – y = 3 k, k  Z.

Como y – x = 3(– k), con (– k)  Z, entonces 3|y – x, es decir y  x (mod 3).
Para demostrar la transitividad, consideremos x, y, z  Z, donde x  y (mod 3) y además
y  z (mod 3), es decir x – y = 3 k, k  Z, y – z = 3 h, h  Z. Sumando miembro a miembro
estas dos igualdades resulta x – z = 3 (k + h), donde la expresión (k + h)  Z.
Luego 3|x – z, es decir x  z (mod 3).

Generalizando, si a y b son enteros y n un entero positivo, la relación de congruencia

módulo n, es una relación de equivalencia, es decir, posee las siguientes propiedades:
Reflexiva:  a  Z , a  a (mod n).
Simétrica:  a, b  Z si a  b (mod n) entonces b  a (mod n).
Transitiva:  a, b, c  Z si a  b (mod n) y b  c (mod n) entonces a  c (mod n).

Si consideramos una relación de equivalencia  en los enteros, éstos pueden separarse

en clases de equivalencia de acuerdo a sus relaciones. En cada clase de equivalencia es-
tarán los enteros que estén relacionados entre sí de la siguiente manera.

Definición 3.11
Sea a un número entero y sea  una relación de equivalencia en los enteros. La clase de
equivalencia de un entero a es el conjunto [a] = {b  Z : a  b}.

Dado que la relación de equivalencia  es reflexiva, tenemos que todo entero a pertenece
a su propia clase de congruencia. Por otra parte, de la simetría y transitividad de la relación
de congruencia, tenemos que dos clases son o bien iguales o bien no tienen ningún elemen-
to en común. En consecuencia, las clases de equivalencia determinan una partición del
conjunto de los enteros como unión disjunta de las clases de equivalencia.
Si pensamos en la división por un entero n positivo, los enteros pueden separarse en n
clases de equivalencia de acuerdo a sus restos módulo n. En cada clase de equivalencia
estarán los enteros que tienen el mismo resto al ser divididos por un entero n. La clase de
equivalencia módulo n que contiene a un entero a es:
[a]n = {b  Z : a  b (mod n)} o equivalentemente [a]n = {a + k n : k  Z}.
En decir, la clase [a]n es el conjunto de todos los enteros que al dividirlos por n tienen un
resto r que es congruente con a módulo n.
Cada clase de equivalencia queda determinada por un resto, por lo tanto, hay n clases
distintas, ya que en la división por n tenemos n restos posibles {0, 1, …, n-1}. El entero a,
que es el elemento que describe a la clase, se llama “líder” o “representante” de la clase de
a módulo n.

Ejemplo 34
La clase [3]7 significa el conjunto de enteros que tienen resto 3 al ser divididos por 7:

205
Matemática Discreta

[3]7 = {..., 11, 4, 3, 10, 17, ...}

La clase [0]7 significa el conjunto de enteros que tienen resto 0 al ser divididos por 7:
[0]7 = {..., 7, 0, 7, 14, 21, 28, ...}
Y continuando con los otros restos, que deben ser siempre menores que 7, obtenemos
las clases:
[1]7 = {..., 6, 1, 8, 15, 22, 29, ...}
[2]7 = {..., 5, 2, 9, 16, 23, 30, ...}
[4]7 = {..., 3, 4, 11, 18, 25, 32, ...}
[5]7 = {..., 2, 5, 12, 19, 26, 33, ...}
[6]7 = {..., 1, 6, 13, 20, 27, 34, ...}
Podríamos haber simbolizado a [3]7 como [11]7, o bien [4]7, o [10]7.

Si bien el entero que representa a la clase no es único, ya que cualquier elemento de la

clase puede ser un representante, en general se elige como representante a aquel que satis-
faga 0 ≤ r < n.
En toda relación de equivalencia se puede definir el conjunto cociente, que es el conjunto
formado por todas las clases de equivalencias. En este caso, el conjunto
Zn = {[a]n / 0  a  n  1},
formado por todas las clases de equivalencia módulo n, es el conjunto cociente.
Para simplificar la notación indicamos Zn = {0, 1, ..., n  1} entendiendo que representa-
mos con 0 = [0]n , 1 = [1]n , ..., n  1 = [n  1]n, para el caso de módulo n.

En el Ejemplo 34, Z7 = {[0]7, [1]7, [2]7, [3]7, [4]7, [5]7, [6]7} = {0, 1, 2, 3, 4, 5, 6}.
Análogamente, para n = 3, tenemos tres clases de equivalencia y el conjunto cociente es
Z3 = {[0]3, [1]3, [2]3}, siendo:
[0]3 = {..., 3, 0, 3, 6, 9, 12, ...}
[1]3 = {..., 2, 1, 4, 7, 10, 13, ...}
[2]3 = {..., 1, 2, 5, 8, 11, 14, ...}
En forma simplificada podemos escribir Z3 = {0, 1, 2}.

En la siguiente propiedad veremos el comportamiento de la relación de congruencia

módulo n con respecto a las operaciones de suma y multiplicación en el conjunto de los
números enteros.

Propiedad 3.15
Sea n un entero positivo. Entonces, dados a1, a2, b1, b2 enteros:
i) Si a1  b1 (mod n) y a2  b2 (mod n), entonces a1 + a2  b1 + b2 (mod n).
ii) Si a1  b1 (mod n) y a2  b2 (mod n) entonces a1 a2  b1 b2 (mod n).
iii) Si a1  b1 (mod n) y m es un entero positivo, entonces a1m  b1m (mod n).

206
 Teoría de Números e Inducción

Demostración del ítem i):

Si a1  b1 (mod n) y a2  b2 (mod n) entonces tenemos que a1=k1 n + b1 y a2 = k2 n + b2
para algunos enteros k1 y k2. Sumando estas igualdades miembro a miembro tenemos que
a1 + a2 = (k1 + k2) n + (b1 + b2) y por lo tanto a1 + a2  b1 + b2 (mod n).

Demostración del ítem ii):

Si a1  b1 (mod n) y a2  b2 (mod n) entonces tenemos que a1=k1 n + b1 y a2 = k2 n + b2
para algunos enteros k1 y k2. Multiplicando estas igualdades miembro a miembro tenemos
que:
a1 a2 = (k1 n + b1) (k2 n + b2)
= k1 n k2 n + k1 n b2 + b1 k2 n + b1 b2
= (k1 k2 n + k1 b2 + b1 k2) n + b1 b2.
Y, por lo tanto, a1 a2  b1 b2 (mod n).

Observación:
Más adelante, la inducción nos permitirá generalizar el resultado anterior y demostrar el
item iii).

Actividad 5
Problema Nº1: Recuerda que si x, y son enteros y n es un entero positivo, x  y (mod n) si
y sólo si n|(x  y) o equivalentemente, x  y = n k, para algún entero k.
1.1) Demuestra que a  a (mod n). Esto asegura que la relación de congruencia es reflexi-
va.
1.2) Demuestra que si a  b (mod n) entonces b  a (mod n). Esto asegura que la relación
de congruencia es simétrica.
1.3) Demuestra que si a  b (mod n) y b  c (mod n) entonces a  c (mod n). Esto asegura
que la relación de congruencia es transitiva.

Problema Nº2: En el anillo de los enteros, expresa al menos, 5 elementos para cada clase
de equivalencia:
2.1) [4]5 2.2) [1]3 2.3) [5]8 2.4) [0]11

Problema Nº3: Sea A = {4, 2, 1, 3, 5, 7, 8, 10}. Sean x, y  A y 3 un entero positivo.
Encuentra las clases de equivalencia de la relación x  y (mod 3) si y sólo si 3|(x  y) y es-
cribe el conjunto cociente.

Problema Nº4: Prueba que si a y b son representantes de una misma clase módulo n, en-
tonces mcd(a, m) = mcd(b, m).

207
Matemática Discreta

Problema Nº5: Sea n un número natural. Prueba que:

5.1) si a1  b1 (mod n) entonces −a1  −b1 (mod n).
5.2) si a1  b1 (mod n) y a2  b2 (mod n) entonces a1−a2  b1−b2 (mod n).

Problema Nº6: El resto de la división de un número por 4, es 3 y el resto de la división del

mismo número por 9 es 5. Encuentra el resto de la división del número por 36.

Problema Nº7: Sea  la relación: “a  b si y sólo si mcd(a, b) = 1” definida en Z+. ¿Es 

reflexiva, simétrica, transitiva o antisimétrica?
Una relación  se dice que es antisimétrica si se cumple la siguiente propiedad: Si a  b
y b  a entonces a = b. Observemos que la propiedad de antisimetría no es opuesta a la
propiedad de simetría.

3.7 Ecuaciones lineales en congruencia

En la sección anterior, vimos que la congruencia módulo un entero n tiene un buen com-
portamiento respecto de las operaciones de adición y multiplicación en Z. Este buen com-
portamiento permite definir operaciones de adición y multiplicación en el conjunto cociente
Zn. En los próximos capítulos veremos que estas operaciones hacen que el conjunto cocien-
te, Zn sea un anillo conmutativo con unidad. Podemos definir la suma y el producto de ele-
mentos de Zn de la siguiente manera.

Definición 3.12
Sean a y b enteros, y n un entero positivo. Entonces la suma y el producto de clases en el
conjunto cociente Zn están definidas por: [a]n + [b]n = [a + b]n y [a]n [b]n = [a b]n.

Aceptaremos que las operaciones están bien definidas. La definición anterior nos permite
operar con las clases de equivalencia y en particular, resolver ejercicios como el que vere-
mos a continuación.

Ejemplo 35
Supongamos que un entero a tiene resto 3 cuando lo dividimos por 11 y queremos en-
contrar el resto de la división por 11 del entero a + 4.
Sabemos que [a]11 = [3]11. Entonces trabajando en el conjunto cociente Z11 tenemos que
[a + 4] 11 = [a]11 + [4]11 = [3]11 + [4]11 = [3 + 4]11 = [7]11 y por lo tanto el entero a +4 tiene
resto 7 si lo dividimos por 11.
Ahora si queremos ver el resto de dividir a (5 a2 + 2 a + 17) por 11, entonces podemos
proceder de la misma manera y obtener
[5 a2 + 2 a + 17]11 =
=[5]11 [a]11 [a]11 + [2]11 [a]11 + [17]11

208
 Teoría de Números e Inducción

= [5]11 [3]11 [3]11 + [2]11 [3]11 + [6]11

= [5 · 3 · 3 + 2 · 3 + 6]11
= [141] 11
= [9]11
Y por lo tanto, el resto de dividir a (5 a2 + 2 a + 17) por 11 es 9.

A continuación mostramos otras propiedades interesantes de la relación de congruencia.

Propiedad 3.16
i) Si a  b (mod n) y m es un divisor de n entonces a  b (mod m).
ii) Si a  b (mod n) y d es un divisor común de a, b y n, entonces a/d, b/d y n/d son ente-
ros y a/d  b/d (mod n/d).

Demostración del ítem i):

Si a  b (mod n), entonces existe un entero k1 tal que a = k1 n + b. Además como m es
un divisor de n, existe otro entero k2, tal que n = k2 m.
Reemplazando tenemos que a = k1 n + b = a = k1 (k2 m) + b = (k1 k2) m + b con k1 k2
entero y por lo tanto a  b (mod m).

Demostración del ítem ii):

Si a  b (mod n), entonces existe un entero k1 tal que a = k1 n + b. Como d es un divisor
común de a, b y n entonces podemos dividir toda la igualdad anterior por d para obtener a/d
= k1 n/d + b/d con a/d, b/d y n/d enteros y por lo tanto a/d  b/d (mod n/d).

Definición 3.13
Una congruencia de la forma a x  b (mod n) donde n es un entero positivo, a y b son
números enteros y x es una variable entera se llama, congruencia lineal o ecuación lineal de
congruencia en la variable x.

Observemos que, a x  b (mod n) si y sólo si n|(a x − b), si y sólo si existe un entero k tal
que a x – b = k n. Por lo tanto, encontrar una solución de la ecuación a x  b (mod n) es
equivalente a encontrar enteros x y k tales que a x = k n + b, o lo que es lo mismo, resolver
la ecuación diofántica a x − k n = b en las variables x y k. Puesto que conocemos la condi-
ción necesaria y suficiente para que esta ecuación diofántica tenga solución, tenemos el
siguiente teorema.

Teorema 3.12
La ecuación a x  b (mod n) tiene solución si y sólo si el mcd(a, n) divide a b.

El Teorema anterior nos permite entonces resolver ecuaciones lineales en el conjunto co-

209
Matemática Discreta

ciente de las clases de equivalencia, ya que resolver la ecuación lineal a x = b en Zn es lo

mismo que resolver la congruencia lineal a x ≡ b (mod n).

Recordemos que si existe alguna solución de la ecuación diofántica asociada a la con-

gruencia lineal, el algoritmo de Euclides nos permite hallarla, y más aún, si existe una solu-
ción entonces hay infinitas soluciones.

Se puede probar que si d = mcd(a, n) y x0 es una solución de la congruencia lineal, en-

tonces la ecuación tiene exactamente d soluciones en Zn que son:
[x0]n, [x0 + n/d]n, [x0 + 2 n/d]n, … , [x0+ (d − 1) n/d]n

En el caso particular en que a y n sean coprimos tenemos que:

i) la ecuación a x ≡ b (mod n) tiene solución para cualquier b entero,
ii) todas las soluciones pertenecen a la misma clase de equivalencia módulo n.

Ejemplo 36
Resolvamos la ecuación 3 x = 4 en Z11. Estamos buscando soluciones de la congruencia
lineal 3 x ≡ 4 (mod 11). Esto es equivalente a decir que 3 x − 4 es múltiplo de 11, o lo que es
lo mismo, que existe un entero k tal que 3 x + 11k = 4.
Como mcd(3, 11) = 1 entonces la ecuación tiene solución, más aún, sabemos que la so-
lución será única módulo 11, es decir, todas las soluciones estarán en la misma clase de
equivalencia módulo 11. Para encontrar las soluciones de la ecuación diofántica escribimos
11 = 3 · 3 + 2; 3 = 2 · 1 + 1. Y por lo tanto, 1 = 3 − 2 · 1 = 3 − (11 − 3 · 3) 1 =
=4 · 3 + (−1) 11.
Multiplicando miembro a miembro por 4 tenemos que 4 = 16 · 3 + (−4) 11. Luego, una
solución de la congruencia lineal es x =16.
Para buscar todas las soluciones de la ecuación diofántica, tenemos que sumar y restar
un múltiplo entero de mcm(3, 11) que es 33. Entonces para m entero tenemos
4 = 16 · 3 + (−4) 11
= 16 · 3 + m 33 − m 33 + (−4) 11
= (16 · 3 + m 33) + ((−33) m + (−4) 11)
= (16 + m 11) 3 + ((−3) m − 4 ) 11.
Tenemos que todas las soluciones, son de la forma 16 + m 11 para cualquier m entero.
Esto significa que todas las soluciones de la ecuación diofántica están en la clase [16]11,
pero como [16]11 = [5]11 entonces todas las soluciones de la congruencia lineal están en la
clase de 5 módulo 11 y todos los representantes de la clase de 5 módulo 11 son soluciones
de la congruencia lineal. Luego, en Z11 la única solución es x =5.

Ejemplo 37
Resolvamos la ecuación 2 x = 4 en Z10.
En este caso, la ecuación diofántica asociada a la congruencia lineal 2 x ≡ 4 (mod 10) es

210
 Teoría de Números e Inducción

2 x + 10 k = 4. Como mcd(2, 10) = 2 y 2|4, entonces la ecuación tiene solución, pero las
soluciones no serán únicas módulo 10.
Para encontrar las soluciones de la ecuación diofántica escribimos a 2 como combinación
lineal de 2 y 10 y por lo tanto tenemos que 2 = 2 · 1 + 10 · 0 y multiplicando la igualdad
anterior por 2 tenemos que 4 = 2 · 2 + 10 · 0, de donde obtenemos que una solución de la
congruencia lineal es x = 2.
Para buscar todas las soluciones tenemos que sumar y restar un múltiplo entero del
mcm(2, 10) = 10 y por lo tanto, para m entero, tenemos que
4 = 2 · 2 + 10 · 0
= 2 · 2 + m 10 − m 10 + 10 · 0
= (2 + m 5) 2 + ((−2) m + 0) 10.
Y por lo tanto todas las soluciones son del tipo 2 + m 5, para m entero. Esto nos conduce
al hecho de que toda solución es congruente con 2 o con 7 módulo 10 y por lo tanto toda
solución está o en la clase [2]10 o en la clase [7]10, y todo representante de cualquiera de
estas clases es solución de la congruencia lineal. Luego, en Z10 las soluciones de la ecua-
ción 2 x = 4 son dos, x1 = 2 y x2 = 7.

Actividad 6
Problema Nº1: Sabiendo que el resto de la división de un entero a por 7 es 5, calcula los
restos de la división por 7 de cada uno de los siguientes enteros:
1.1) a
1.2) 2a
1.3) 3a + 7
1.4) 10a + 1
1.5) a2 + a +1
1.6) 7a + 1

Problema Nº2: Prueba que la adición y la multiplicación de clases en el conjunto cociente

satisfacen las siguientes propiedades:
De la adición:
2.1) Asociativa: ([a]n + [b]n) + [c]n = [a]n + ([b]n + [c]n).
2.2) Conmutativa: [a]n + [b]n = [b]n + [a]n.
2.3) Existencia de neutro:  [0]n  Zn tal que  [a]n  Zn, [a]n + [0]n = [a]n.
2.4) Existencia de opuestos: Para cada [a]n  Zn,  ([a]n) = [a]n  Zn tal que se verifica
[a]n + ([a]n) = [0]n.
Estas propiedades caracterizan a (Zn, +) como un grupo abeliano.
De la multiplicación:
2.5) Asociativa: ([a]n [b]n) [c]n = [a]n ([b]n [c]n).
2.6) Conmutativa: [a]n [b]n = [b]n [a]n.

211
Matemática Discreta

2.7) Existencia de identidad:  [1]n  Zn tal que  [a]n  Zn, [a]n [1]n = [a]n.
2.8) Distributiva: [a]n ([b]n + [c]n) = [a]n [b]n + [a]n [c]n.
Todas las propiedades mencionadas caracterizan a (Zn, +, ·) como anillo conmutativo con
identidad.

Problema Nº 3: Resuelve las siguientes ecuaciones:

3.1) 2 x = 3 en Z10.
3.2) 9 x = 4 en Z12.
3.3) 9 x = 6 en Z12.
3.4) 5 x = 2 en Z7.

Problema Nº4: Prueba que si a b ≡ a c (mod n) y mcd(a, n) = 1, entonces b ≡ c (mod n).

Sugerencia: Prueba primero que como mcd(a, n)= 1 entonces existe un entero x tal que a
x ≡ 1 (mod n) y luego utilizar este elemento x para “cancelar” el valor de a en la congruencia
a b ≡ a c (mod n).

Problema Nº5: Encuentra un ejemplo para el que se satisfaga que a b ≡ a c (mod n) pero
que no se verifique ≡ c (mod n).

Problema Nº6: Sea p un número primo.

Demuestra que si a b ≡ 0 (mod p) entonces a ≡ 0 (mod p) o b ≡ 0 (mod p).

Problema Nº 7: Resuelve la congruencia lineal 221 x ≡ 85 (mod 340). Halla todas las solu-
ciones x, tales que 0 ≤ x ≤ 340.

3.8 Inducción
A lo largo del capítulo hemos hecho referencia a propiedades que son verdaderas para
todos los números naturales. Más aún, en algunas de ellas, extendimos sus dominios a los
enteros no negativos. Hemos visto, por ejemplo, que:
i) 2 es divisor de n (n+1),  n  N.
ii) 1 + 2 + 3 +... + (n 1) + n = n (n+1) /2,  n  N.
iii) Si un conjunto X tiene n elementos, entonces P(X) = {A: A  X} tiene 2n elementos,  n  N0.
n
iv) Si n  N0, se verifica que 2
k
C(n,k)  3 .
n

k 0

Existen además, otras propiedades que se verifican para todos los números naturales,
excepto para un número finito de ellos. Por ejemplo:

212
 Teoría de Números e Inducción

v) Si un conjunto X tiene n elementos, el número de subconjuntos que tienen tres elemen-

n(n  1)(n  2)
tos es ,  n  N  n  3.
6
vi) Si n  N  n  6, entonces 2n > (n + 1)2.

Para demostrarlas, utilizamos principalmente argumentos que provienen de la combinato-

ria y de la teoría de números. Si bien éstos son muy útiles y potentes para probar algunas
propiedades referidas a los números naturales, no son suficientes.
Existe una importante técnica de demostración, la inducción matemática, que agregare-
mos a las herramientas que ya poseemos para hacer frente a demostraciones de propieda-
des referidas a los números naturales.
Supondremos que tenemos una función proposicional referida a los números naturales,
por ejemplo, alguna de las ya dadas o alguna de las siguientes. Supongamos además que
deseamos demostrar que es verdadera para todo su dominio de definición:
vii) La expresión n2  n es entero par,  n  N.
viii)  x,  y , x, y  N0, tales que n = 3 x + 5 y,  n  N  n  8.
n (n+1) (2 n  1)
ix) 1 + 4 + 9 + 16 + ... +n2 = ,  n  N.
6
Para ello, aplicaremos la técnica de inducción:
El primer paso para aplicar una prueba por inducción es verificar que la proposición es
cierta para n = 1. Esto se denomina el caso base.
El segundo paso, llamado hipótesis inductiva, es asumir que la proposición es verdadera
para n = k, siendo k algún natural fijo, pero elegido al azar.
El tercer paso, llamado paso inductivo, es demostrar que la proposición es cierta para
n = k +1, bajo la suposición de que es cierta para n = k.
Un enunciado formal del Principio de Inducción Matemática es el siguiente.

Principio de Inducción Matemática

Sea P(n) una función proposicional referida a los números naturales que cumple las si-
guientes condiciones:
i) P(1) es verdadera.
ii) Si P(k) es verdadera, también lo es P(k + 1).
Entonces, P(n) es una proposición verdadera para todos los números naturales.

Ejemplo 38
Siendo a, b números reales, probaremos que P(n): (a b) n = an bn, es verdadera para todo
n  N, utilizando el principio de inducción matemática.

Demostración:
El caso base, n= 1, se verifica trivialmente: (a b)1 = a b = a1 b1.

213
Matemática Discreta

Por la hipótesis inductiva, suponemos que P(k): (a b)k = ak bk es verdadera para algún k
natural. La prueba del paso inductivo completa la demostración. Para n = k + 1, demostra-
remos que P(k + 1) es verdadera.
En efecto, (a b)k+1 = (a b)k (a b) = ak bk (a b) por la hipótesis inductiva. Entonces, aplican-
do las propiedades conmutativa y asociativa del producto de números reales, tenemos que
ak bk (a b) = ak bk a b = (ak a) (bk b) = ak+1 bk+1.
Por lo tanto (a b)k+1 = ak+1 bk+1, con lo cual resulta que P(k + 1) es verdadera. Luego P(n)
es verdadera  n  N.

Ejemplo 39
n (n+1)
Probaremos que 1 + 2 + 3 + … + n = ,  n  N, utilizando el principio de in-
2
ducción matemática.

Demostración:
Para el caso base.
1(1+1)
El lado izquierdo es 1 y el lado derecho es = 1. Luego P(1) es verdadera.
2
Asumimos que P(k) es verdadera cuando n = k. Es decir, por la hipótesis inductiva se ve-
k (k +1)
rifica que 1 + 2 + 3 + ... + k = .
2
Para probar el paso inductivo, es decir, para demostrar que P(k + 1) es verdadero, note-
mos que debemos poder expresar a:
(k +1) (k + 2)
1 + 2 + 3 + ... +k + (k + 1) como , hecho que resulta de reemplazar a n
2
por (k + 1). En efecto, utilizando la hipótesis inductiva, tenemos que:
k (k +1)
1 + 2 + 3 + ... + k + (k + 1) = + (k + 1). Pero sumando fracciones y extrayen-
2
do el factor común (k + 1) obtenemos:
k (k +1) + 2 (k +1) (k +1) (k + 2)
1 + 2 + 3 + … + k + (k + 1) = = con lo cual resulta
2 2
P(k + 1) verdadera. Luego P(n) es verdadera  n  N.

Ejemplo 40
Demostraremos que para todo n  N, 4n – 1 es divisible por 3.
Razonando “inductivamente”, si n = 1, tenemos que ver si 41 – 1 es divisible por 3. Esto
es cierto porque 3 = 3. 1.
Supongamos cierto que 4k – 1 es divisible por 3, es decir, que existe un entero c tal que
4 – 1 = 3 c. Veamos ahora que 4k+1 –1 es divisible por 3. Para ello escribimos: 4k+1 –1 =
k

= 4 · 4k – 4 + 4 –1 = 4 (4k – 1) + 3 = 4 · 3 c + 3 = 3 (4 c + 1) donde 4c +1 es un entero.

Por lo tanto 4k+1 – 1 es divisible por 3.

214
 Teoría de Números e Inducción

Esto prueba la validez del paso inductivo. Luego nuestra afirmación es, en virtud del Prin-
cipio de Inducción, válida para todo n  N.

Ejemplo 41
Utilizaremos la inducción para demostrar que la proposición P(n): n2  n es un entero par,
 n  N, es verdadera.

Demostración:
Veamos el caso base. Como 12  1 = 0 que es un entero par, afirmamos que P(1) es ver-
dadera.
Por la hipótesis inductiva, asumimos que P(k) es verdadera, esto es, la expresión k2  k es
un entero par.
La prueba del paso inductivo completa la demostración. Para n = k + 1, demostraremos
que P(k + 1) es verdadera.
En efecto, (k + 1)2  (k + 1) = k2 + 2 k + 1  k 1 = (k2  k) + 2 k que es la suma de dos
enteros pares y por lo tanto un entero par. (La expresión (k2  k) es un entero par por la hipó-
tesis inductiva).
Luego es verdadero que, n2  n sea un entero par  n  N.

En aplicaciones del álgebra matricial, muchas veces interesa conocer la potencia n-ésima
de una matriz. Veamos el siguiente ejemplo, donde el uso de la inducción es fundamental
para justificar la validez de una expresión.

Ejemplo 42
 1 1 0
 
Sea A =  0 1 1 una matriz de tamaño 3 x 3. Utilizaremos la inducción para probar
 0 0 1
 
1 n n(n  1) / 2 
n
 
que, para cada n natural, se tiene que A =  0 1 n .
0 0 1 
 

Demostración:
 1 1 1(1  1) / 2   1 1 0 
   
   0 1 1 .
1
El caso base, n =1, se verifica pues A =  0 1 1
0 0 1   0 0 1
   
 1 k k(k  1) / 2 
 
Por la hipótesis inductiva, suponemos que P(k): Ak =  0 1 k  es verdadera pa-
0 0 1 
 
ra algún k natural.

215
Matemática Discreta

La prueba del paso inductivo completa la demostración. Para n = k + 1, demostraremos

que P(k + 1) es verdadera. En efecto,
 1 k k(k  1) / 2   1 1 0 
  
Ak+1 = Ak A =  0 1 k   0 1 1
0 0 1   0 0 1
  
 1 k  1 k  k(k  1) / 2 
 
= 0 1 k 1 
0 0 1 
 
 1 k  1 (k  1)k / 2 
 
= 0 1 k  1  . Luego, para todo n  N, P(n) es verdadera.
0 0 1 
 

Ejemplo 43
Probemos que P(n): (1+x)n  1 + xn es verdadera para todo n  N, si x ≥ 0.

Demostración:
Veamos el caso base para n = 1. Como (1 + x)1 = 1 + x  1 + x =1 + x1, afirmamos
que P(1) es verdadera.
Asumimos que P(k): (1 + x)k ≥ 1 + xk es verdadera para algún k  1.
Probemos ahora que P(k+1) es verdadera, es decir que (1 + x)k+1 ≥ 1 + xk+1, para probar
el paso inductivo y completar la demostración.
En efecto:
(1 + x)k+1 = (1 + x)k (1 + x) ≥ (1 + xk) (1 + x) = 1 + x + xk + xk+1 ≥ 1 + xk+1
donde la primera desigualdad se debe a la utilización de la hipótesis inductiva y la segunda
al hecho de que, como x ≥ 0, entonces x + xk ≥ 0.
Por lo tanto vale que (1+x)n ≥1 + xn para todo n entero y todo valor de x ≥ 0.

Ejemplo 44
En el Capítulo 1 hemos utilizado el Teorema de la Deducción repetidas veces sin haberlo
demostrado. Ahora demostraremos dicho Teorema que es muy importante para la Lógica
Proposicional. Es decir, demostraremos que:
P(n) = ((p1  p2  …  pn  q)  r)  ((p1  p2  …  pn)  (q  r )) es verdadera para
todo n ≥ 1.

Demostración:
Veamos el caso base para n = 1.
((p1  q)  r )  ((p1  q)  r )  (p1  q)  r )  (p1  (q  r))  (p1  (q  r) ).
Lo cual afirma que P(1) es verdadera.
Por la hipótesis inductiva, suponemos que P(k) es verdadera, esto es,

216
 Teoría de Números e Inducción

((p1  p2  …  pk  q)  r)  ((p1  p2  …  pk)  (q  r )),

o equivalentemente,
((p1  p2  …  pk  q)  r)  ((p1  p2  …  pk)  (q  r )),
es verdadera para algún k  1.
Para completar la demostración, probaremos que P(k+1) es verdadera, es decir que
((p1  p2  …  pk  pk+1  q)  r)  ((p1  p2  …  pk  pk+1)  (q  r )),
En efecto:
((p1  p2  …  pk  pk+1  q)  r)  ((p1  p2  …  pk  pk+1  q)  r)
 (((p1  p2  …  pk  q)  pk+1)  r)
 (((p1  p2  …  pk  q)  pk+1)  r)
 (((p1  p2  …  pk  q)  r)  pk+1))
 ((p1  p2  …  pk)  (q  r ))  pk+1))
 ((p1  p2  …  pk  pk+1)  (q  r ))
 ((p1  p2  …  pk  pk+1)  (q  r )).
Que era lo que queríamos demostrar.

La elección de n = 1 para el caso base, no es obligatoria. Ocasionalmente se puede ex-

tender para n = 0 o comenzar por algún n = n0. Lo que se necesita es un primer elemento
n0  N0 para que el proceso de inducción tenga un lugar de inicio, una base en donde co-
menzar. Cuando esto sucede, podemos expresar el principio de inducción matemática de
esta manera.

Principio de Inducción Matemática

Sea P(n) una función proposicional referida a los números naturales. Si
i) P(n0) es verdadera.
ii) Si P(k) es verdadera para k  n0, también lo es P(k + 1).
Entonces, P(n) es una proposición verdadera  n  N0  n  n0.

Ejemplo 45
Sea a un número natural, a ≠ 1. Utilicemos inducción para demostrar que
a0 + a1 + … + an = (an+1  a0) / (a  1)  n  N0.

Demostración:
Veamos el caso base para n = 0.
Como a0 = 1 y (a0+1  a0) / (a  1) = (a1  a0) / (a  1) = (a  1) / (a  1) = 1, afirmamos
que P(0) es verdadera.
Por hipótesis inductiva asumimos que P(k) es verdadera para algún k  0, elegido al azar.
Probemos ahora que P(k+1) es verdadera, es decir que
a0 + a1 + … + ak + ak+1 = (ak+2  a0) / (a  1),
para probar el paso inductivo y completar la demostración. En efecto:

217
Matemática Discreta

a0 + a1 + … + ak + ak+1 = (ak+1  a0) / (a  1) + ak+1

= (ak+1  a0 +(a  1) ak+1) / (a  1)
= (ak+1  a0 +ak+2  ak+1) / (a  1)
= (ak+2  a0) / (a  1).
Luego tenemos que a0 + a1 + … + an = (an+1  a0) / (a  1)  n  N0.

En el capítulo anterior nos interesamos por averiguar el número de cadenas de bits de

longitud finita “n” que se pueden formar. Veamos cómo utilizar la inducción para justificar los
resultados obtenidos.

Ejemplo 46
¿Cuántas cadenas de bits de longitud menor o igual a “n” se pueden formar?
Si comenzamos con n = 0, tenemos 1 = 20 cadenas de longitud cero (la vacía).
Para n = 1, hay 2 = 21 cadenas posibles: 0, 1.
Para n = 2, hay 4 = 22 cadenas posibles: 00, 01, 10, 11.
Para n = 3, hay 8 = 23 cadenas posibles: 000, 001, 010, 011, 100, 101, 110, 111.
Para n = k, hay 2k cadenas posibles.
Observemos que la siguiente disposición resulta útil para intuir la respuesta:
Cadenas de longitud 0: 20 = 1.
Cadenas de longitud  1: 20 + 21 = 3.
Cadenas de longitud  2: 20 + 21 + 22 = 3 + 4.
Cadenas de longitud  3: 20 + 21 + 22 + 23 = 7 + 8.
Cadenas de longitud  4: 20 + 21 + 22 + 23 + 24 = 15 + 16.

Por lo tanto, el número de cadenas de longitud menor o igual a “n” es 2 n + 2n – 1, o de
manera equivalente 2n+1 – 1.

Utilizando el principio de inducción matemática probaremos que:

20 + 21 + 22 + … + 2n = 1 + 2 + 4 + … + 2n = 2n+1 – 1,  n  N0.

Demostración:
El caso base, para n = 0, se . El lado izquierdo es 1 y el lado derecho es 2 0+1 – 1 = 21 – 1
= 1. Luego P(0) es verdadera.
Supongamos que P(k) es verdadera cuando n = k. Es decir, por la hipótesis inductiva se
verifica que 1 + 2 + 4 + … + 2k = 2k+1 – 1.
Para probar el paso inductivo, es decir, para demostrar que P(k + 1) es verdadero, no-
temos que debemos poder expresar a:
1 + 2 + 4 +.......+ 2k + 2k + 1 como 2k+2 – 1, hecho que resulta de reemplazar a n por
(k + 1). En efecto:

218
 Teoría de Números e Inducción

1 + 2 + 4 +.......+ 2k + 2k + 1 = 2k+1 – 1 + 2k+1 utilizando la hipótesis inductiva. Pero

agrupando potencias obtenemos:
1 + 2 + 4 +.......+ 2k + 2k + 1 = 2k+1 + 2k+1 – 1 = 2.2k+1 – 1 = 2k+2 – 1, con lo cual resulta
P(k + 1) verdadera. Luego P(n) es verdadera  n  N0.

En el ejemplo siguiente, el caso base es para n = 4.

Ejemplo 47
Si n  N  n  4, demostraremos que P(n): 2n  n! es verdadera.

Demostración:
Observemos que, para n = 1, tenemos que 2  1!, para n = 2, se verifica que 4  2!, para
n = 3, es 8  3!. Sin embargo, para n = 4 podemos verificar el caso base.
Para n = 4, se verifica que 16  4! = 24.
Suponemos que P(k) es verdadera para n = k y k  4. Es decir, supongamos que 2k  k!,
para algún k  4, elegido al azar.
Para probar el paso inductivo, es decir, la verdad de P(k + 1) observemos que, dado que
k  2 resulta 2 < k + 1, luego, podemos expresar a: 2k+1 = 2k · 2  k! · 2  k! (k + 1) donde
en la última desigualdad hemos usado la hipótesis inductiva.
Luego 2k+1  k! (k + 1) = (k + 1)! y por lo tanto 2n  n! , es cierta  n  N  n  4, como
queríamos demostrar.

Existe una forma alternativa de la inducción, conocida como principio de inducción com-
pleta. La base de la inducción requiere que la proposición sea verdadera para un número
finito de naturales consecutivos a partir de n = n0 y hasta n = n1 con la condición n0  n1. Por
la hipótesis inductiva supondremos que todas las proposiciones son verdaderas desde
n = n0, n0 + 1, n0 + 2, ..., k  1, k donde k  n1, es un natural particular, pero elegido al azar,
para poder establecer la verdad de la proposición cuando n = k + 1. Formalmente pode-
mos presentar esta forma alternativa de la manera siguiente.

Principio de Inducción Completa

Sea P(n) una función proposicional referida a los números naturales.
i) P(n0), P(n0 + 1), P(n0 + 2), ..., P(n1  2), P(n1  1), P(n1) son verdaderas, donde n0  n1,
n0  N0, n1  N.
ii) Si P(n0), P(n0 + 1), …, P(n1  1), P(n1), ..., P(k  1), P(k) donde k  n1, son verdaderas,
también lo es P(k + 1).
Entonces, P(n) es una proposición verdadera  n  N  n  n0.

Ejemplo 48
Demostraremos que x y, x, y  N0, tales que n = 3 x + 5 y,  n  N  n  8.

219
Matemática Discreta

Demostración:
Probamos el caso base. Para n = 8, existen x = y = 1 tales que 8 = 3 · 1 + 5 · 1.
Para n = 9 tenemos que 9 = 3 · 3 + 5 · 0.
Para n = 10, podemos escribir 10 = 3 · 0 + 5 · 2.
Supongamos que P(8), P(9), ..., P(k2), P(k1), P(k) son verdaderas para k 10. Es decir,
por la hipótesis inductiva se verifica que k = 3 x + 5 y para algún x, para algún y, con x, y
enteros positivos o nulos.
Para probar el paso inductivo, es decir, que P(k + 1) es cierto, notemos que podemos
expresar a:
k + 1 = (k – 2 ) + 3 , pero k – 2  k, y k – 2  10 – 2 = 8, por lo tanto vale la hipótesis in-
ductiva para k – 2. Existen x’, y’ tales que k – 2 = 3 x’ + 5 y’. Luego
k + 1 = (k – 2 ) + 3 = 3 x’ + 5 y’ + 3 = 3 (x’ + 1) + 5 y’, por lo que existen valores
x’’= x’ + 1 y y’’= y’ tales que k + 1 = 3 x’’ + 5 y’’. Entonces P(k + 1) es verdadera.
Luego,  x  y, x, y  N0, tales que n = 3 x + 5 y es verdadera  n  N  n  8.

Ejemplo 49
Vamos a dar un último ejemplo de inducción completa. Si a0 = 3; a1 = 9; a2 = 29 y
an = 9 an–1 – 26 an–2 + 24 an–3,  n  N  n  3 queremos demostrar que  n  N0 se tiene
que an = 2n + 3n + 4n. En este caso, la función proposicional puede expresarse como
an = 2n + 3n + 4n,  n  N0.

Demostración:
Como esta secuencia de números está definida usando tres casos bases, probemos que
los tres son verdaderos.
Para n = 0, a0 = 3 = 20 + 30 + 40.
Para n = 1, a1 = 9 = 21 + 31 + 41.
Para n = 2, a2 = 29 = 22 + 32 + 42.
Sea un natural arbitrario k  2. Asumimos que P(0), P(1), P(2), ..., P(k2), P(k1), P(k) son
todas verdaderas. Probemos que se verifica el paso inductivo.
Como k  2, entonces k + 1  3, luego podemos usar la definición de ak+1 para escribir:
ak+1 = 9 ak – 26 ak–1 + 24 ak–2
= 9 (2k + 3k + 4k) – 26 (2k1 + 3k1 + 4k1) + 24 (2k2 + 3k2 + 4k2)
= 2k1(18 – 26 + 12) + 3k1(27 – 26 + 8) + 4k1 (36 – 26 + 6)
= 2k1(4) + 3k1(9) + 4k1 (16)
= 2k+1 + 3k+1 + 4k+1.
Luego, an = 2n + 3n + 4n,  n  N0.

Frecuentemente comprobamos la verdad de una proposición para algunos valores de n,

usualmente pequeños. Por ejemplo:

220
 Teoría de Números e Inducción

Si P(n) es la proposición n2 = (n  1)2 + 2 n  1, entonces, para n = 1, el lado izquierdo es

1 = 1, y el lado derecho es (1  1)2 + 2 · 1  1 = 1, de donde P(1) es verdadera. Análoga-
2

mente, para n = 2 tendremos que 22 = 4 y (2  1)2 + 2 · 2  1 = 4, de donde P(2) es verda-

dera y así podemos continuar. Un razonamiento inductivo nos proporcionará la verdad de n2
= (n  1)2 + 2 n 1,  n  N.

Pero la verdad de algunos casos particulares no garantiza la verdad de la proposición pa-

ra todos los casos. Por ejemplo, si consideramos la función proposicional:
“f(n) = n2 – n + 41 es un número primo”, la expresión da un número primo cuando n toma
valores enteros desde 0 hasta 40. En efecto,
si n = 0, 0 – 0 + 41 = 41 es un número primo;
si n = 1, 1 – 1 + 41 = 41 es un número primo;
si n = 2, 4 – 2 + 41 = 43 es un número primo;
si n = 3, 9 – 3 + 41 = 47 es un número primo;
si n = 4, 16 – 4 + 41 = 53 es un número primo y así sucesivamente. Sin embargo, para n =
41, el número n2 – n + 41 no es primo. En efecto, 412 – 41 + 41 = 412.

Es decir, de la verdad de algunos casos particulares, no podemos inferir la verdad para

todos los naturales. Sin embargo, en algunos problemas, la verificación de casos particula-
res puede ayudar a encontrar una función proposicional que sea verdadera para todos los
números naturales. Si se encuentra tal expresión, posteriormente se requerirá una prueba
por inducción matemática, que permita asegurar o refutar la verdad para todos los naturales.

Ejemplo 50
Observemos que
1 = 1,
1 – 4 = – (1 + 2),
1 – 4 + 9 = 1 + 2 + 3,
1 – 4 + 9 – 16 = – (1 + 2 + 3 + 4),
1 – 4 + 9 – 16 + 25 = 1 + 2 + 3 + 4 + 5.
Estos casos particulares sugieren la existencia de una proposición que puede ser expre-
sada, en términos de los números naturales como:
1 – 4 + 9 – 16 + ... + (– 1)n+1 n2 = (– 1)n+1 (1 + 2 + 3 + 4 + ... + n),  n  N.
O bien, 1 – 4 + 9 – 16 + ... + (– 1)n+1 n2 = (– 1)n+1 n (n + 1) / 2,  n  N.
Una prueba por inducción matemática de esta proposición permitirá asegurar o refutar la
verdad para todos los naturales.

Ejemplo 51
Observemos que
1 + 2 = 3,

221
Matemática Discreta

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.
Estos casos particulares sugieren la existencia de una proposición referida a los números
naturales. ¿De qué manera podríamos escribir esta proposición, suponiendo que sea posible
generalizarla para todos los naturales?
Se trata de números naturales consecutivos, donde cada fila comienza con el cuadrado
de un número natural y que la cantidad de sumandos está relacionada con ese natural.
Veamos las distintas formas de escribir la proposición:
n2 + (n2 + 1) + (n2 + 2) + (n2 + 3) + ... +(n2 + n) =
= (n2 + n + 1) + (n2 + n + 2) + ... +(n2 + n + n)
Operando sólo en el lado derecho de la igualdad obtenemos
n2 + (n2 + 1) + (n2 + 2) + (n2 + 3) + ... +(n2 + n) =
= n n2 + n n + n (n + 1) / 2
= (2 n n2 + 2 n n + n (n + 1))/2
= (2 n3 + 3 n2 + n ) / 2
= n (n + 1)(n + 1/2).
Una prueba por inducción matemática de esta proposición permitirá asegurar o refutar la
verdad para todos los naturales.

3.9 La inducción en los algoritmos

En las ciencias de la computación, cuando escribimos un segmento o trozo de un algo-
ritmo, quisiéramos tener la seguridad de que es correcto, es decir que produce la salida
correcta para una razonable (correcta) entrada de datos. Por supuesto que esto depende de
muchos factores que escapan a nuestro control, como por ejemplo, el compilador, las ope-
raciones del sistema, el hardware usado para correr el programa, etc. Pero asumiendo que
todo esto funciona de acuerdo a lo esperado, ¿cómo podemos estar seguros que el pro-
grama trabajará bien?
Una dirección es observar las entradassalidas dadas por el algoritmo haciendo correr el
programa para un número finito de entradas arbitrariamente elegidas. Esto permitirá detectar
o no, posibles errores. Por ejemplo, un algoritmo que muestra números primos a partir de la
fórmula n2 – n + 41, funcionará bien para algunas sustituciones de n, por ejemplo n = 5; n =
12; etc., en realidad funciona bien cuando n tome valores comprendidos entre 0 y 40.
¿Cómo estar seguros que el programa es correcto? ¿Cómo estar seguros que siempre
produce la salida deseada? En los casos que estamos tratando, existe una estrecha relación
entre la salida correcta de un algoritmo y las demostraciones por inducción matemática o
inducción completa. Veamos algunos ejemplos.

222
 Teoría de Números e Inducción

Ejemplo 52
Lee el siguiente algoritmo, donde N representa un número natural.

BEGIN
Read(N);
Ans := 0;
FOR J: = 1 TO N DO
T := 2 * J  1;
Ans := Ans + T
ENDFOR
Write (‘El cuadrado de ’,N,‘ es ’, Ans);
END

Reflexiona: ¿cómo calcula este algoritmo el cuadrado de un número n? Si seguimos los

pasos del algoritmo completando un cuadro similar al siguiente para N = 5

J T Ans

Valores iniciales

Iteración 1

Iteración 2...

J T Ans

Iteración 1 1 2 * 1 1 = 1 0 + (2 * 1 1) = 0 + 1 = 1

Iteración 2 2 2 * 2 1 = 3 1 + (2 * 2 1) = 1 + 3 = 4

Iteración 3 3 2 * 3 1 = 5 (1 + 3) + (2 * 3 1) = (1 + 3) + 5 = 4 + 5 = 9

Iteración 4 4 2 * 4 1 = 7 (1 + 3 + 5) + (2 * 4 1) = (1 + 3 + 5) + 7 = 9 + 7 = 16

Iteración 5 5 2 * 5 1 = 9 (1 + 3 + 5 + 7) + (2 * 5 1) = (1 + 3 + 5 + 7) + 9 = 25

Podemos observar que el algoritmo calcula el cuadrado de un número n sumando el cua-

drado del natural precedente con el enésimo número impar.
Vamos a demostrar, usando inducción matemática que la salida de este algoritmo es n2,
calculándolo como (n  1)2 + (2 n 1),  n  N.
Caso base para n = 1
12 = 1 y (11)2 + 2 · 1 1 = 1, por lo que P(1) es verdadera.
Asumimos que P(k) es verdadera cuando n = k. Es decir, por la hipótesis inductiva se ve-
rifica que k2 = (k  1)2 + 2 k 1.
Para probar el paso inductivo, es decir, para demostrar que P(k + 1) es verdadero, note-
mos que debemos poder expresar a:
(k + 1)2 = k 2 + 2 (k +1) 1, hecho que resulta de reemplazar a n por (k + 1).

223
Matemática Discreta

En efecto:
(k + 1)2 = k2 + 2 k + 1 (desarrollo del cuadrado del binomio)
= [(k  1)2 + 2 k 1] + 2 k + 1 (aplicando la hipótesis inductiva)
= k2  2 k + 1 + 2 k 1 + 2 k + 1 (desarrollo del cuadrado del binomio)
= k2 + 2 (k + 1) 1. (por cancelar y reagrupar convenientemente)
Luego n2 = (n  1)2 + 2 n 1,  n  N. Y como conclusión, el algoritmo resuelve correcta-
mente la tarea  n  N.

Ejemplo 53
Lee el siguiente algoritmo, donde N representa un número natural.

BEGIN
Read(N);
Ans := 0;
J := 1;
WHILE (J  N) DO
T := J * (J + 1);
Ans := Ans + T;
J := J + 1
ENDWHILE
Write( ,N,‘ * ’, N + 1,‘ * ’, N + 2,‘/ 3 = ’, Ans);
END

Reflexiona: ¿cómo calcula este algoritmo el producto n (n + 1) (n + 2) /3?

Seguimos los pasos del algoritmo completando el cuadro siguiente para N = 5.

J T Ans

Valores iniciales 1 0

Iteración 1 2 1*2 0+1*2

Iteración 2 3 2*3 (0 + 1 * 2) + 2 * 3

Iteración 3 4 3*4 (0 + 1 * 2 + 2 * 3) + 3 * 4

Iteración 4 5 4*5 (0 + 1 * 2 + 2 * 3 + 3 * 4) + 4 * 5

Iteración 5 6 5*6 (0 + 1 * 2 + 2 * 3 + 3 * 4 + 4 * 5) + 5 * 6

Si generalizamos, podemos decir que el algoritmo calcula n (n + 1) (n + 2) / 3 como la

suma de los productos de dos naturales consecutivos, es decir
1 · 2 + 2 · 3 + 3 · 4 + 4 · 5 + … + n ( n + 1) = n ( n + 1) (n + 2) / 3.
El algoritmo dado, ¿resuelve correctamente esta tarea para todos los naturales? Nueva-
mente, el principio de inducción matemática garantizará que el programa funciona bien

224
 Teoría de Números e Inducción

cuando se demuestre que:

1 · 2 + 2 · 3 + 3 · 4 + 4 · 5 + … + n ( n + 1) = n ( n + 1) (n + 2) / 3,  n  N.

Ejemplo 54
Lee el siguiente algoritmo, donde N representa un número natural.

BEGIN
Read(N);
Ans := 0;
K := 1;
WHILE (K  N) DO
T := K * (K + 1);
L : = 1 / T;
Ans := Ans + L;
K := K + 1
ENDWHILE
Write (‘La división ’,N,‘ / ’,N + 1,’ = ’,Ans);
END

Reflexiona: ¿cómo calcula este algoritmo la división n / (n + 1)?

Si seguimos los pasos del algoritmo para N = 4, obtenemos:

K T L Ans

Valores iniciales 1 0

Iteración 1 2 1 * 2 1 / 1*2 1/ 1 * 2 = 1 / 2

Iteración 2 3 2 * 3 1 / 2 * 3 1/ 1 * 2 + 1/ 2 * 3 = 2 / 3

Iteración 3 4 3 * 4 1 / 3* 4 1/ 1 * 2 + 1/ 2 * 3 + 1 / 3 * 4 = 3 / 4

Iteración 4 5 4 * 5 1 / 4 * 5 1/ 1 * 2 + 1/ 2 * 3 + 1 / 3 * 4 + 1 / 4 * 5 = 4 / 5

Podemos generalizar y decir que el algoritmo muestra N / (N + 1) y que lo calcula como

N
1
 k(k  1) . Probaremos, por inducción que es cierto para todo natural.
k 1

Ejemplo 55
n
1 n
Demostraremos que P(n) :  k(k  1)  n  1,  n  N es verdadera.
k 1

Demostración:
1 1
Para k = 1 se verifica que  , luego P(1) es verdadera.
1 2 1  1

225
Matemática Discreta

Suponemos la existencia de un k  N tales que P(k) es verdadera. Es decir para algún

1 1 1 k
k  N se verifica que   ...  .
1 2 2  3 k (k  1) k  1
Demostraremos que P(k+1) es verdadera.
En efecto,
1 1 1 1 k 1
  ...    .
1 2 2  3 k (k  1) (k  1)(k  2) k  1 (k  1)(k  2)
asociando los primeros k sumandos y aplicando la hipótesis inductiva.
Luego:
k 1 k(k  2)  1 k 2  2k  1 (k  1)2 k 1
     .
k  1 (k  1)(k  2) (k  1)(k  2) (k  1)(k  2) (k  1)(k  2) k  2
Lo que muestra que P(n) es válida  n  N.

Actividad 7
Problema Nº1: Da una prueba no inductiva para la proposición:
2 + 4 + 6 + ... +2 n = n (n + 1), n  N.

Problema Nº2: Muestra que 1 + 3 + 5 + ... +(2 n  1) = n2,  n  N.

Problema Nº3: Utilizando la inducción matemática, prueba que

3.1) 1 + 4 + 7 + ... + (3 n  2) = (3 n2  n) / 2,  n  N.
n (n +1) (2 n  1)
3.2) 1 + 4 + 9 + 16 + ... + n2 = ,  n  N.
6
3.3) 1 + 2 + 4 + 8 + ... + 2n = 2n+1 – 1,  n  N0.
3.4) 1 + 5 + 9 + ... +(4 n  3) = n (2n  1)  n  N.

Problema Nº4: Prueba que:

1 – 4 + 9 – 16 + ... +(– 1)n+1 n2 = (– 1)n+1 (1 + 2 + 3 + 4 + ... +n)  n  N.

Problema Nº5: Observa las siguientes regularidades referidas a algunos números; pro-
porciona una proposición matemática que esté sugerida por estas observaciones y que
supones válida para todos los números naturales; luego prueba que es verdadera.
5.1)
1 = 1.
2 + 3 + 4 = 1 + 8.
5 + 6 + 7 + 8 + 9 = 8 + 27.
10 + 11 + 12 + 13 + 14 + 15 + 16 = 27 + 64.
17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 = 64 + 125.

226
 Teoría de Números e Inducción

5.2)
1 = (1 · 2 / 2 )2.
1 + 8 = (2 · 3 / 2 )2.
1 + 8 + 27 = (3 · 4 / 2 )2.
1 + 8 + 27 + 64 = (4 · 5 / 2 )2.
1 + 8 + 27 + 64 + 125 = (5 · 6 / 2 )2.

Problema Nº6: Usa inducción para mostrar que la salida del siguiente algoritmo es:
N (N + 1) / 2 ,  N  N.

ALGORITMO SUM
BEGIN
Read(N);
Ans := 0;
FOR J: = 1 TO N DO
Ans := Ans + J
ENDFOR
Write(Ans);
END

Problema Nº7: Usa inducción para mostrar que la salida del siguiente algoritmo es:
N ( 2 N 1 ) ,  N  N.

ALGORITMO FOURSUM
BEGIN
Read(N);
Ans := 0;
FOR J: = 1 TO N DO
T := 4* J  3;
Ans := Ans + T
ENDFOR
Write(Ans);
END

Problema Nº8: Dado el siguiente algoritmo, donde N es un entero no negativo.

ALGORITMO SUMAPOTDOS
BEGIN
Read(N);
Suma := 0;

227
Matemática Discreta

I:= 0;
WHILE (I  0) and (I  N) DO
P:= 1
FOR J: = 1 TO I DO
P := P*2;
ENDFOR
I:= I + 1;
Suma:= Suma + P
ENDWHILE
Write(Suma);
END
8.1) Sigue los pasos del algoritmo para N = 0 y N = 4 y verifica que la salida es 2N+11.
8.2) Indica la manera en que el algoritmo realiza esta tarea  N  N0.

Problema Nº9: Usa el principio de inducción matemática para mostrar que:

9.1) 3 es divisor de n3 + 3 n2 + 2 n,  n  N.
9.2) Si n  N y n  6, entonces 2n  (n + 1)2.
 2  3  4 i  n   n  1
9.3)          ...    ...      , n  N y n  2.
 2  2  2  2  2  3 
9.4) 3|n (n + 1) (2 n + 1)  n  N.
9.5) 3 divide a n3  n,  n  N.

Problema Nº10: Demuestra que:

10.1) 52n  1 es múltiplo de 24,  n  N.
10.2) 10n+1  9n 10 es múltiplo de 81,  n  N.
10.3) Si n, m son enteros positivos; a1, a2, b1, b2 enteros y a1  b1 (mod n) entonces:
a1m  b1m (mod n).

Problema Nº11: Se verifica 3 divide a n3  n,  n  N. También es cierto que 5 divide a

n5  n, y que 7 divide a n7  n,  n  N. ¿Será cierto que si p es impar, es divisor de np  n,
n  N?

3.10 Lectura complementaria

3.10.1 Lectura 1
En esta lectura presentamos ejemplos de otros algoritmos, no abordados previamente
con el propósito de mejorar el intento educativo en cuanto a dar respuestas a los problemas
de motivación, integración, comprensión, investigación y uso activo del conocimiento.
Un primer ejemplo permite descubrir un importante interjuego entre la teoría de números y

228
 Teoría de Números e Inducción

su relación con el algoritmo de Euclides. Los algoritmos, la inducción y el máximo común

divisor entre dos enteros positivos fueron integrados por Gabriel Lamé en 1844, cuando
descubrió una sorpresiva conexión entre los números de Fibonacci (1202) y el algoritmo de
Euclides.

El algoritmo de Euclides
Este algoritmo, que probablemente no haya sido descubierto por el propio Euclides (siglo
III, a.C.), aunque sí se tiene la certeza que fue usado por Eudoxo de Cnido, cerca del año
375 a.C., encuentra el máximo común divisor entre dos enteros positivos A y B mediante una
serie de divisiones sucesivas.

ALGORITMO EUCLIDES
BEGIN
Read(A);
Read(B);
M := A;
N := B;
R := 1;
IF (M < N) THEN
Aux := M;
M := N;
N := Aux;
ENDIF;
WHILE (M >= N) and (R<>0) DO
R:= M mod N;
IF (R = 0) THEN
write (‘El máximo común divisor entre ’,A, ‘ y ’,B, ‘ es: ’,N)
ELSE
M := N;
N := R;
ENDIF
ENDWHILE
END
Vamos a observar cómo funciona el algoritmo cuando A = 10 y B = 15.

Iteración A B M N R

10 15 10 15 1

1 15 10 5

2 10 5 0

229
Matemática Discreta

Vamos a observar cómo funciona el algoritmo cuando A = 220 y B = 284.

Iteración A B M N R

220 284 220 284 1

1 284 220 64

2 220 64 28

3 64 28 8

4 28 8 4

5 8 4 0

Desde el punto de vista discreto, interesa ciertamente, calcular el número de divisiones

que necesita este algoritmo en “el peor caso”, es decir, determinar un número máximo de
divisiones requeridas. Abordaremos estas cuestiones en el próximo capítulo.

A continuación diseñaremos dos algoritmos que permiten determinar si un número entero

dado es primo o compuesto.

Algoritmo 1
En principio recordemos que A es divisor de B si y sólo si B mod A = 0.
Para determinar si un número entero N es primo podemos verificar si tiene algún divisor
en el conjunto {2, 3, 4, ..., N div 2}. Si al menos uno de estos números cumple con la pro-
piedad, entonces el número N es compuesto, de lo contrario N es primo.
Para diseñar el algoritmo definamos una variable booleana, Primo, la cual nos indicará si
el número N dado es primo o no. Primo será verdadero (True) si N es primo y falso (False) en
caso contrario. En principio le asignaremos a la variable Primo el valor verdadero. Luego si
en la ejecución del programa encontramos al menos un divisor de N, mayor que 1 y menor
que N div 2, el algoritmo finaliza y el valor de la variable Primo será falso.

ALGORITMO NÚMERO_PRIMO_1
BEGIN
Read(N)
Primo := True;
Divisor := 2; Limite := N div 2;
WHILE ( ( Divisor  Limite ) and ( Primo ) ) DO
IF ( ( N mod Divisor ) = 0 ) THEN
Primo := False;
ENDIF
Divisor := Divisor + 1;
ENDWHILE

230
 Teoría de Números e Inducción

IF( Primo ) THEN

Write(‘El número ’, N, ‘ es primo’)
ELSE
Write(‘El número ’, N, ‘ es compuesto’)
ENDIF
END

Algoritmo 2
Para diseñar el siguiente algoritmo, tendremos en cuenta que: si un número entero positi-
vo N es compuesto, entonces tiene un divisor entre 2 y N . Además todo número par, ex-
cepto 2, es compuesto.
En forma análoga a lo expresado en el Algoritmo 1, se asigna a la variable booleana Pri-
mo el valor verdadero (True) porque se supone que todo número leído es primo. Se controla
si el número ingresado es par y distinto de 2. Si éste es impar, se comienza a evaluar si tiene
un divisor impar menor o igual que la cota N .
El algoritmo resulta ser:

ALGORITMO NÚMERO_PRIMO_2
BEGIN
Read(N);
Primo := True;
Limite := trunc( N );
Divisor := 3;
IF( ( N  2 ) and ( N mod 2 = 0 ) ) THEN
Primo := False;
ELSE
WHILE ( ( Divisor  Limite ) and ( Primo ) ) DO
IF ( ( N mod Divisor ) = 0 ) THEN
Primo := False;
ENDIF
Divisor := Divisor + 2;
ENDWHILE
ENDIF
IF ( Primo ) THEN
Write(‘El número ’, N, ‘ es primo’)
ELSE
Write(‘El número ’, N, ‘ es compuesto’)
ENDIF
END

231
Matemática Discreta

3.10.2 Lectura 2
Utilizando el principio de inducción matemática, hemos demostrado o propuesto para
demostrar que:
n (n + 1)
a) 1 + 2 + 3 + ... +n = ,  n  N.
2
n (n  1) (2n  1)
b) 12 + 22 + 32 + ... +n2 = , n  N.
6
n2 (n  1)2
c) 13 + 23 + 33 + ... +n3 = , n  N.
4
Estos enunciados establecen que tanto la suma de los primeros “n” números naturales, la
de sus cuadrados y la de sus cubos, se pueden expresar como polinomios en “n” de grados
2, 3 y 4 respectivamente. Por una simple inspección, se tiene además que el coeficiente
principal de cada uno de ellos es 1/2, 1/3 y 1/4 respectivamente.
Cabe aquí la siguiente pregunta, ¿se cumplirá lo mismo para las otras potencias natura-
les?
Este hecho, nos lleva a establecer la siguiente conjetura, la que mostraremos resulta cier-
ta por el principio de inducción matemática.

La suma de las h-ésimas potencias de los primeros n números naturales,

1h + 2h + 3h + ... + nh se puede expresar como un polinomio en “n” de grado h + 1, donde
el coeficiente del término principal es 1/ (h + 1).

Demostración:
Sabemos ya que para el caso base h = 1, se verifica: 1 + 2 + 3 + ... + n se puede ex-
n (n + 1)
presar como un polinomio de grado 2, , donde el coeficiente del término principal
2
es 1/2.
Supongamos que la conjetura es cierta para h = k, k  1. Debemos mostrar la veracidad
del enunciado para h = k + 1.
En efecto, para cualquier i real, por el teorema binomial:
k 2
(i + 1)k+2 =  C(k  2, j) i
j0
j

k 1
  C(k  2, j) i
j0
j
 C(k  2, k  2) ik  2 (i + 1)k+2 – ik + 2

= C(k  2, 0) i0  C(k  2, 1) i1  ... C(k  2, k  1) ik 1 [(i+1)k+2–ik+2]

 C(k  2, 0) i0  C(k  2, 1) i1  ... C(k  2, k) ik  C(k  2, k  1) ik1
Sumando para i desde 1 hasta n:
n n n n

[ (i  1)k 2  ik  2 ]  C(k  2, 0)
i1
i 1
i0  C(k  2, 1) 
i 1
i1  ... C(k  2, k) i
i 1
k

232
 Teoría de Números e Inducción

n
= C(k  2, k  1) i
i 1
k 1
. Operando:

n n
n(n  1)
(n + 1)k+2 – 1 – n – C(k + 2, 1)
2 
– ... – C(k  2, k) ik = (k + 2)
i 1
 i k 1
i1
n
Por hipótesis inductiva, C(k  2, k)  ik es un polinomio de grado k + 1.
i1

Así, los términos del lado izquierdo corresponden a polinomios de grados 0, 1, 2, … ,

k + 1, k + 2, donde el polinomio de mayor grado es (n + 1) k+2. Dividiendo miembro a miem-
n
bro por (k + 2): i k 1 = 1k+1 + 2k+1 + 3k+1 + ... + nk+1 es un polinomio de grado k + 2,
i 1

cuyo coeficiente es 1/(k + 2). De esta manera tenemos probado el enunciado  k  N.

3.11 Problemas complementarios

Problema Nº1: Sean A = {2, 3, 4, 5, 6, 7} y B = {10, 11, 12, 13, 14}. Lista los elementos
de la relación   AxB donde  está definida como a  b si “a es divisor de b”.

Problema Nº2: En el conjunto de los números enteros, definimos la siguiente relación:

x  y si y sólo si x  y es un múltiplo de 4.
Demuestra que es de equivalencia e indica las clases correspondientes.

Problema Nº3: Estudia las propiedades de las siguientes relaciones definidas en un con-
junto A e indica si son relaciones de equivalencias.
3.1) A = {1, 2, 3, 4, 6, 8} y a  b si y sólo si a es divisor de b.
3.2) A = {1, 2, 3, 4, 6} y a  b si y sólo si a es múltiplo de b.
3.3) A = {1, 2, 3, 4, 5} y a  b si y sólo si 3 es divisor de a  b.

Problema Nº4: Prueba que para cualquier n Z+, mcd (5n + 3, 7n + 4) = 1

Problema Nº5: Para cualquier n Z+, ¿Cuánto valen el mcd(n, n + 1) y el mcm(n, n + 1)?

Problema Nº6: Encuentre los enteros x, y, z que satisfagan el siguiente sistema de ecua-
ciones diofánticas:
6.1) x + y + z = 50
6.2) x + 13y + 31z = 116

Problema Nº7: Utiliza la inducción para demostrar que para todo número natural se verifi-
ca que: n2 + (n2 + 1) + (n2 + 2) + (n2 + 3) + ... +(n2 + n) = n (n + 1) (n + 1/2)

233
Matemática Discreta

Problema Nº8: Considerando el algoritmo siguiente:

BEGIN
Read(N); Ans := 0
FOR i:= 1 TO N DO
Ans := Ans + i3
ENDFOR
END
2
 n(n  1) 
La expresión que es igual a   es:
 2 
8.1) 1 + 23 + 33 + ... +(n + 1)3
8.2) 1 + 23 + 33 + ... +n3
8.3) 23 + 33 + ... +(n1)3
¿Puedes demostrarlo por inducción matemática?
p
Problema Nº9: Prueba que si p es primo y 0 < k < p1 entonces p|   . Concluye que
k 
para cualesquiera a, b enteros y p primo (a + b)p  ap + bp (mod p).

Problema Nº10: Prueba que si n es un entero positivo, entonces n, n + 2 o n + 4 es divi-

sible por 3.

Problema Nº11: Decide si la siguiente afirmación es verdadera o falsa.

La expresión ((N div 10) mod 10) = 2 indica que la cifra de la decena del número N es 2.

Problema Nº12: Utilizando los operadores mod y div escribe una expresión que permita
determinar si la cifra de la centena de un número N tiene un valor mayor que 5.

Problema Nº13: Utiliza inducción para probar que si a ≡ b (mod n) y m es un número natu-
ral entonces am ≡ bm (mod n).

3.12 Ejercicios de opción múltiple

n
Ejercicio 1:  2i  1 es:
i1
(n  1)n c) (n + 1)2
a)
2

b) n2 d) Ninguna de las anteriores.

234
 Teoría de Números e Inducción

Ejercicio 2: Si a y b son naturales, se puede asegurar que:

a) Si a < b entonces a + 1  b
b) Si a  1 existe x natural, que verifica x + 1 = a
c) Si c es natural y a = b c entonces b  a y a  c
d) Ninguna de las anteriores.

Ejercicio 3: Si a, b y c  Z se puede asegurar que:

a) a|b y b|c  a|c c) a|b + c  a|c y a|b
b) a|b y a|c  a|b + c y a | (b – c) d) Ninguna de las anteriores.

Ejercicio 4: Una solución para la ecuación diofántica 6 x + 10 y = 104 es:

a) x = 2, y =14 c) x = 9, y = 5
b) x = 8, y = 4 d) Ninguna de las anteriores.

Ejercicio 5: El número de divisores diferentes de 2.520.000 es:

a) 5 c) 45
b) 210 d) Ninguna de las anteriores.

Ejercicio 6: El número de divisores positivos de [Link] es:

a) 576 c) 1.728
b) 60 d) Ninguna de las anteriores.

Ejercicio 7: El mcd(10.672, 3.219) es:

a) 3 c) 1
b) 29 d) Ninguna de las anteriores.

Ejercicio 8: La ecuación 450 x + 372 y = 180:

a) No admite soluciones enteras.
b) Admite soluciones enteras únicas.
c) Admite exactamente las mismas soluciones que 75 x + 62 y = 30.
d) Ninguna de las anteriores.

Ejercicio 9: Para el plano de ecuación 8 x  48 y + 320 z = 140:

a) Existe un único punto del espacio, con coordenadas enteras, que le pertenece.
b) Existen infinitas ternas de coordenadas enteras que le pertenecen.
c) Todos sus puntos tienen alguna coordenada no entera.
d) Ninguna de las anteriores.

Ejercicio 10: El enunciado verdadero es:

a) 15  3 (mod 4) c) 17  3 (mod 4)

235
Matemática Discreta

b) 7  4 (mod 3) d) 17  3 (mod 5)

Ejercicio 11: El menor entero positivo que representa la suma:

5 + 3 + 2 + 1 + 8 (mod 7) es:
a) 1 c) 12
b) 5 d) Ninguna de las anteriores.

Ejercicio 12: El mcd(943, 414) es:

a) 23 c) 1
b) 46 d) Ninguna de las anteriores.

236