14/10/2022

MATEMÁTICA DISCRETA I - ÁLGEBRA II

INGENIERÍA INFORMÁTICA
INGENIERÍA EN TELECOMUNICACIONES

MÓDULO VI: ENTEROS E INDUCCION MATEMATICA

El conjunto de números enteros Z tiene definidas

operaciones y propiedades con las que se trabaja
habitualmente. En este contexto se estudian algunas
situaciones especiales que se presentan en Z.

Z es un conjunto cerrado en las operaciones de suma,

diferencia y multiplicación ya que el resultado de las
mismas siempre es un elemento de Z. Sin embargo, Z no es
cerrado en la división entre números distintos de cero, se
presenta entonces una forma restringida de división.

Por otro lado los números enteros positivos Z+ tienen una

propiedad particular que permite establecer demostraciones
mediante una técnica denominada inducción matemática. 1

2
 14/10/2022

OPERACIONES ARITMETICAS EN Z
Existen operaciones elementales en Z, denominadas ARITMETICAS
Sean a, b y c números enteros con b distinto de cero
1) Adición (+). a + b = c
• Sumandos o términos de la suma: a y b.
• Suma o total de los sumandos: c

2) Multiplicación (x,*, . ). a x b = c
• Factores: a y b
• Producto: c
3) Sustracción (-). “a – b = c”
4) División (:). a:b=
• Minuendo: a
• Sustraendo: b con b≠0
• Resto o total de los sumandos =c
3

OPERACIONES ARITMETICAS EN Z
Esencialmente, toda operación puede expresarse como SUMA:

1. Siempre a un entero se le puede sumar 1 para saber el

siguiente ( ∈ ℤ → + 1 ∈ ℤ)
2. a + b = a + (1+1+1+1…) donde “1” se suma “b” veces.
3. a x b = (a + a + a + a + …) donde “a” se suma “b” veces.
4. a – b = c si y solo si a = c + b
5. a:b con b≠0 representa la cantidad de veces que “b” esta
contenido en “a” .
2

4
 14/10/2022

OPERACIONES ARITMETICAS EN Z

Las primeras tres operaciones son cerradas ya que al operar

dos números enteros da como resultado un numero entero, ya
sea suma o resta, en cambio, en la división no necesariamente
el resultado será entero.

La teoría de números es la parte de la matemática discreta

que trata de los números Z y sus propiedades.
o Conjunto de los números ℕ (∞)
ℕ={1,2,3,…}
o Conjunto de los números Z (∞)
Z={-3,-2,-1,0,1,2,3,…}

ENTEROS Y DIVISIÓN

Teorema 1:
TEOREMA DEL RESTO o Algoritmo de la división euclidea
Dados dos enteros a y b con b > 0, existen dos únicos números
enteros q y r tales a = b. q + r, con 0≤ r< b

Definición 1: En la igualdad dada por el algoritmo de la división o

teorema del resto, “a” se denomina dividendo, “b” divisor, “q”
cociente y “r” resto. La siguiente notación se usa para expresar el
cociente y el resto:

a div b = q ; a mod b = r

div y mod son operadores matemáticos utilizados en programación. 3

6
 14/10/2022

ENTEROS Y DIVISIÓN
EJEMPLO
a) Cuál es el cociente y el resto de dividir 101 y 11?
Se tiene que 101= 11.9 + 2
Entonces el cociente es 9= 101 div 11
y el resto es 2= 101 mod 11
b) Cuál es el cociente y el resto de dividir -11 y 3?
Se tiene que -11= 3. (-4) + 1
Entonces el cociente es -4 = -11 div 3
y el resto es 1= -11 mod 3
EJERCICIO 1
Cuál es el cociente y el resto de dividir por 17 los siguientes
números: 68, -84 y 357
7

ENTEROS POSITIVOS Y DIVISIÓN

Definición 2: Sean a y b dos números enteros positivos, se

dice que “b” divide a “a” y se escribe b|a si existe en Z+
un numero c tal que a=bc.

También se dice que “b” es divisor de “a” o que “b” es factor de

“a” o que “a” es divisible por “b” o que “a” es múltiplo de “b”.
Propiedades:
• Teorema 2: para cualquier entero a ∈ Z+ :
1|a ; a|a ; a|0

• Teorema 3: si a|b y b|c entonces a|c ,con a,b,c ∈ Z+

Observación: División( / ) ≠ divisibilidad (|). 4

8
 14/10/2022

ENTEROS POSITIVOS Y DIVISIÓN

• Teorema 4: todo entero positivo que es divisor de otros, es
divisor de la suma de ellos.
Si d|a y d|b y d|c entonces d|(a+b+c)

• Teorema 5: todo entero positivo que es divisor de otro , es

también divisor de los múltiplos de ese otro.
Si d|a entonces d|n.a donde n ∈ Z+

• Teorema 6: todo entero positivo que es divisor de otros dos es

también divisor de su diferencia.
Si d|a y d|b entonces d|(a-b) con a>b

• Teorema 7: todo entero positivo que es divisor de otros dos es

también divisor del resto de la división de estos.

ENTEROS POSITIVOS Y DIVISIÓN

EJEMPLO: Teorema 4:
Si d|a y d|b y d|c entonces d|(a+b+c)
Demostración
Si d|a , d|b y d|c ⟹ por definición de divisibilidad existen s, t y
v tales que a= d.s , b= d.t y c= d.v
Por tanto (a+b+c)= ds + dt + dv = d(s+t+v)

Si (a+b+c)= d(s+t+v) ⟹ d|(a+b+c)

EJERCICIO 2
Demostrar el teorema 3 y teorema 5 5

10
 14/10/2022

ENTEROS POSITIVOS Y DIVISIÓN

Definición 3: Un entero positivo p ≠ 1 se dice que es primo

absoluto o directamente primo si sus únicos divisores
positivos son p y 1. Un entero positivo mayor que 1 que no es
primo se denomina numero compuesto.

Teorema 8: TEOREMA FUNDAMENTAL DE LA ARITMETICA

Todo entero positivo mayor que 1 puede ser escrito como producto
de números primos y la factorización es única, menos en el orden
de los factores.
Sea a∈ Z+ y a>1, entonces

11

ENTEROS POSITIVOS Y DIVISIÓN

EJEMPLO

a) 100= 22. 52 (factorización)

b) 641=641 (es primo)
c) 999= 33. 37 (factorización)

Observación: el número 1 no se considera primo y

tampoco compuesto, no puede ni dividirse, ni
factorizarse con números distintos del mismo.

12
 14/10/2022

ENTEROS POSITIVOS Y DIVISIÓN

Teorema 9: si n es un numero compuesto; entonces n tiene un
divisor primo menor o igual a | |
Algoritmo para probar si un entero n > 1 es primo.

1. n=2 ⟶ n es primo
2. 2|n ⟶ n es par por tanto no es primo
3. n=impar calcular el entero K ≤ | |
4. para todo número impar D tal que 1<D ≤ K , verificar si
D|n? caso afirmativo n no es primo y sino es primo.
EJERCICIO 3
Determinar si son primos por teorema 9 y factorizar:
a) 103 b) 57 c) 641 d ) 989

13

ENTEROS POSITIVOS Y DIVISIÓN

Definición 4: Sean a y b ∈ Z+ , se dice que un entero positivo d

es un divisor común de a y b si d|a y d|b.

Definición 5: dados dos números enteros positivos a y b, se

denomina máximo común divisor de a y b , al mayor de los
divisores comunes de a y b. Se denota mcd(a,b) ∈ Z+

Definición 6: Dos números enteros positivos a y b son primos

relativos o primos entre si, si su máximo común divisor es 1.
No necesariamente a y b son números primos.

Observación: Existe un algoritmo eficiente para calcular el

mcd(a,b), que es el algoritmo de Euclides basado en el lema de
Euclides. 7

14
 14/10/2022

ENTEROS POSITIVOS Y DIVISIÓN

ALGORITMO DE EUCLIDES

• Lema: Dados dos enteros positivos a y b con a > b , entonces

el mcd(a,b)=mcd(b,r), donde r es el resto de dividir a entre b.

• Algoritmo: Dados dos enteros positivos a y b con a > b

1) Se divide el número mayor con el menor

2) Si la división es exacta, el divisor es el mcd(a,b) y si la
división no es exacta , se divide el divisor por el resto obtenido y
se continua de esta forma hasta obtener una división exacta,
siendo el ultimo divisor mcd.
3) En términos del teorema del resto a =bq + r, el mcd(a,b)
es el ultimo resto no nulo.
15

16
 14/10/2022

ENTEROS Y DIVISIÓN
EJEMPLO
Sean 250 y 111. Como:
250 =2. 111 + 28 con 0 < 28 < 111
111 = 3.28 + 27 con 0 < 27 < 28
28 = 1. 27 + 1 con 0 < 1 < 27
27 = 1. 27 + 0 Entonces 1 es el último resto no nulo
Por tanto el mcd(250,111) = 1 entonces 250 y 111
son primos entre si
EJERCICIO 4
Mediante el algoritmo de Euclides, determinar el mcd:
a) 126 y 78 b) 105 y 90 c) 468 y 264

17

ENTEROS POSITIVOS Y DIVISIÓN

Dados los enteros positivos a y b por teorema 8 siempre

es posible obtener la descomposición de los mismos en
sus factores primos. Sean sus factorizaciones las
siguientes:

Entonces

Observación: mcd(a,b) es el producto de los factores primos

comunes elevados al menor exponente.
9

18
 14/10/2022

ENTEROS POSITIVOS Y DIVISIÓN

Definición 7: dados dos números enteros a y b positivos, se

denomina mínimo común múltiplo de a y b , al menor entero
positivo que es divisible tanto por a como por b o que es múltiplo
tanto de a como de b. Se denota mcm(a,b) ∈ +Z
Dados los enteros positivos a y b sean sus factorizaciones
las siguientes:

Entonces

Observación: mcm(a,b) es el producto de los factores primos

comunes y no comunes elevados al mayor exponente.
19

ENTEROS POSITIVOS Y DIVISIÓN

• Teorema 10: existe una cantidad infinita de primos.

• Teorema 11: sean a y b enteros positivos, entonces:

a.b = mcd(a,b) x mcm(a,b)

EJERCICIO 5
a) Determinar el mcd y mcm entre: a= 22.3. 52 y b= 22. 53
b) Dados a= 23. 3. 52 112 y b= 2. 32 5. 72 . Determinar
el mcd y mcm entre a y b.
c) Utilizar el algoritmo de Euclides para probar que:
8n +3 y 5n + 2 son primos entre si con n ∈ Z+
10

20
 14/10/2022

ENTEROS POSITIVOS E INDUCCION

El conjunto Z+ se diferencia de los otros conjuntos numéricos
Q+ y R+ por el hecho que cualquier conjunto no vacío A de Z+
contiene un entero a ∈ A tal que a ≤ x para todo x ∈ A, es decir
A contiene un elemento menor o mínimo. Esto da lugar a la
siguiente propiedad:

El principio del buen orden: Cualquier conjunto no vacío de Z+

contiene un elemento mínimo. Se dice entonces que Z+ es un
conjunto bien ordenado.

Es esto particularmente interesante para la matemática?

SI MUY INTERESANTE porque es la base de una técnica de

demostración denominada inducción matemática.

21

ENTEROS POSITIVOS E INDUCCION

PRINCIPIO DE INDUCCIÓN FINITA O PRINCIPIO DE
INDUCCIÓN MATEMÁTICA

• Teorema 12: Sea P(n) una proposición matemática abierta en

la que aparece varias veces la variable n que representa a un
entero positivo.
I) Si P(1) es verdadera y
II) siempre que P(k) sea verdadera (para algún k ∈ Z+ elegido
al azar), entonces P(k+1) es verdadera;
Entonces P(n) es verdadera para todo n ∈ Z+

Se tiene entonces:
(P(1) ˄ ⩝ k(P(k) → P (k+1))) → ⩝ n P(n) 11

22
 14/10/2022

ENTEROS POSITIVOS E INDUCCION

Teorema 12: Demostración:
Sea P(n) una proposición matemática abierta que cumple I) y II)
y sea F = {t ∈ Z+ / P(t) es falsa}.
Se quiere mostrar que F= . Entonces, para arribar a una
contradicción se supone que F≠ .
Si F≠ entonces, por el principio del buen orden F tiene un
elemento mínimo s, tal que P(s) es falsa. Como por condición
I) P(1) es verdadera, s≠1 y por tanto s>1 entonces (s-1)∈ Z+ .
Como s es el mínimo de F ocurre que (s-1)∉F, por tanto P(s-1)
es verdadera.
Entonces por la condición II) se tiene que P((s-1)+1)= P(s) es
verdadera y esto contradice s∈ F .
La contradicción surge de suponer que F≠ , por tanto F= y se
cumple entonces que P(n) es verdadera para todo n ∈ Z+
23

ENTEROS POSITIVOS E INDUCCION

En la demostración se utiliza
Observación: la regla de inferencia
“contradicción”
El teorema 12 dice: (¬p → 0) → p

(P(1) ˄ ⩝ k(P(k) → P(k+1))) → ⩝ n P(n)

Donde, la condición de la parte:

I) se conoce como la base de la inducción (se muestra que

P(1) es verdadera) y la de la parte:

II) se conoce como el paso a la inducción (se muestra que

P(k)⟹ P (k+1) es verdadera).
12

24
 14/10/2022

Intuitivamente el
método inductivo se
asemeja a piezas que
caen, k empuja a
k+1 y parece que se
desencadena un
proceso.
La verdad de P(no)
proporciona el
empuje inicial la
base. La verdad de
P(k) y de P(k+1)
proporciona el paso
inductivo.

25

ENTEROS POSITIVOS E INDUCCION

EJEMPLO DE DEMOSTRACION POR INDUCCION
Demostrar por inducción que la suma de los primeros n enteros
positivos pares, es igual a n(n+1) para todo n ∈ Z+. Es decir que:
n
P(n) =  2i = n(n + 1) ∀n ∈ Z +
i =1
Demostración por inducción:
I) base de la inducción (Verificar que P(1) es verdadera)
n
Se tiene P(n) =  2i = 2.1 + 2.2 + 2.3 + ... + 2.n = n(n + 1)
i =1n

Es decir P(n) =  2i = 2 + 4 + 6 + 8 + ... + 2n = n(n + 1)

i =1
1
Si n = 1  P(1) =  2i = 2.1 = 1(1 + 1) y como 2=2⟹ P(1) es verdadera 13
i =1
26
 14/10/2022

ENTEROS POSITIVOS E INDUCCION

EJEMPLO DE DEMOSTRACION POR INDUCCION
II) paso a la inducción (suponer que P(k) es verdadera y
mostrar que P(k)⟹ P (k+1) es verdadera)
k
Sea P(k) =  2i = 2 + 4 + 6 + ... + 2 k = k(k + 1) verdadera
i =1

Se debe demostrar que:

Es decir mostrar que a partir de la expresión P(k), que se

supone verdadera, es posible obtener la misma forma o
estructura para la expresión en k+1
27

ENTEROS POSITIVOS E INDUCCION

EJEMPLO DE DEMOSTRACION POR INDUCCION
Entonces , se tiene que: 2 + 4 + 6 +...+ 2k = k(k+1) es igualdad verdadera
Se suma en ambos miembros de la igualdad el termino
siguiente de la sumatoria, es decir en este caso 2(k+1)
Se obtiene 2+4+6+...+2k + 2(k+1) = k(k+1) + 2(k+1)
Se extrae factor (k+1)  2+4+6+...+2k + 2(k+1) = (k+1)(k+2)
Se expresa 2 como 1+1  2+4+6+...+2k+2(k+1) = (k+1)(k+1+1)
Entonces se verifica que:

Por tanto, por inducción es:

14

28
 14/10/2022

ENTEROS POSITIVOS E INDUCCION

EJERCICIO 6
a) Escribir con el operador sumatoria y utilizar el método de
inducción matemática para demostrar que:
n(n + 1)
para todo n ∈ Z+. 1 + 2 + 3 + ... + n =
2
n
b) Demostrar por inducción: n(3n + 1) para todo n ∈ Z+.
P( n) =  (3i − 1) =
i =1 2
c) Utilizar el método de inducción matemática para demostrar
n
que: n p 2 para todo n ∈ Z+.
d) Considerar la suma de los primeros n enteros positivos
impares consecutivos. Demostrar que la suma de los primeros n
enteros positivos impares es igual a n2 para todo n ∈ Z+. Es
n
decir que:
S (n) =  (2i − 1) = n
2
para todo n ∈ Z+.
i =1
29

ENTEROS POSITIVOS E INDUCCION

EJERCICIO 6
e) Escribir factores de la productoria y utilizar el método de
inducción matemática para demostrar que:
para todo n ∈ Z+.
f) Escribir con el operador sumatoria y utilizar el método de
inducción matemática para demostrar que:
n( n + 1)(2n + 1)
para todo n ∈ Z+ 1 + 4 + 9 + ... + n 2 =
6
g) Determinar si el producto de 3 números enteros positivos
consecutivos impares es siempre múltiplo de 6

h) Determinar si la suma de 3 números enteros consecutivos es

siempre divisible por 6.
15

30
 14/10/2022

ENTEROS POSITIVOS E INDUCCION

EJERCICIO 6

i) Utilizar el método de inducción matemática para demostrar

que: 2n+1 < 2n

para todo entero n ≥ 3

j) Utilizar el método de inducción matemática para demostrar

que:

para todo entero n ≥ 4

OBSERVACION: la base de la inducción no tiene que ser

necesariamente 1 puede ser cualquier otro entero. Es siempre el
primer elemento del conjunto considerado para la demostración.
31

16