1 1.

3 Los números enteros

Axiomas de los números naturales ℕ

Los números naturales ℕ={1,2,3,4,5,...} cumplen las siguientes propiedades que son
conocidas como los axiomas de Peano:

i. 1 ∈ ℕ
ii. 𝑛 ∈ ℕ ⇒ 𝑠 𝑛 ∈ ℕ (la función “sucesor de” n)
iii. Para 𝑚, 𝑛 ∈ ℕ, si 𝑠 𝑚 = 𝑠 𝑛 ⇒ 𝑚 = 𝑛;
iv. 1 ≠ s 𝑛 , ∀𝑛 ∈ ℕ,
v. ℕ cumple el principio de inducción: si A ⊂ ℕ es tal que:
1) 1 ∈ 𝑎,
2) 𝑛 ∈ 𝐴 ⇒ 𝑠 𝑛 ∈ 𝐴,
Entonces A = ℕ .
2
Operaciones en los naturales ℕ={1,2,3,4,5,...} :
La suma 𝑎 + 𝑏 y el producto 𝑎 × 𝑏 de dos números naturales a y b también es un
número
natural, es decir, el conjunto de los números naturales es cerrado respecto de las
operaciones suma y producto y se cumplen las siguientes propiedades:

i. + es conmutativa
ii. + es asociativa
iii. * es conmutativa
iv. * es asociativa
v. Propiedad distributiva del producto respecto de la suma.

La operación sustracción de dos números naturales no siempre es un número

natural.

Por tanto, surge la necesidad de ampliar el conjunto de los números naturales al

conjunto de los números enteros.
3
Axiomas de los números enteros ℤ
Los números enteros son: ℤ = … , −3, −2, −1,0,1,2,3 = ℤ = ℤ+ ∪ 0 ∪ ℤ−
donde ℤ+ = ℕ (enteros positivos) coincide con los naturales: mientras que
ℤ− son los enteros negativos.

Las operaciones suma y producto sobre el conjunto de los números

enteros cumplen todas las propiedades para los números naturales,
además de:
i. Elemento neutro para la suma: el 0.
ii. Inverso aditivo: todo número entero tiene un número opuesto
(simétrico respecto de la suma).
iii. Elemento neutro para el producto: el 1.

La operación cociente de dos números enteros no se introduce aquí,

pues el Matemáticas
cociente no siempre esDra.
Discretas 2018-2019-I un número
Leonor Vázquez entero.
4 Orden en ℤ

❑ Dados 𝑎, 𝑏 ∈ ℤ, diremos que 𝑎 ≥ 𝑏 si 𝑎 − 𝑏 ∈ ℤ+ . También se define:

✓ La desigualdad estricta 𝑎 > 𝑏 sucede si 𝑎 ≥ 𝑏, pero 𝑎 ≠ 𝑏.
✓ La desigualdad: 𝑎 ≤ 𝑏 ssi 𝑏 ≥ 𝑎 (𝑏 − 𝑎 ∈ ℤ+ ).
❑ Un entero 𝑎 ∈ ℤ es positivo si 𝑎 > 0.
❑ [Tricotomía] Si 𝑎 ∈ ℤ entonces solo una de las siguientes afirmaciones se
cumple:
✓ 𝑎 es positivo.
✓ 𝑎=0
✓ 𝑎 es negativo
❑ En general, los números enteros se pueden escribir de la forma
• 2𝑎 (par) o
• 2𝑎 + 1 (impar)
5

❑ ∀𝑎 ∈ ℤ, se define su valor absoluto como:

𝑎, 𝑠𝑖 𝑎 ≥ 0
|𝑎| = ቊ
−𝑎, 𝑒𝑛 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
El valor absoluto cumple las siguientes propiedades:
❑ |𝑎| = 0 ssi 𝑎 = 0
❑ 𝑎 ⋅ b = 𝑎 ⋅ |𝑏|
❑ 𝑎 ≤ 𝑏 𝑠𝑠𝑖 − 𝑏 ≤ a ≤ 𝑏
6 Ej.

• ∀𝑎, 𝑏, 𝑐 ∈ ℤ, si 𝑎 + 𝑐 = 𝑏 + 𝑐 ⇒ 𝑎 = 𝑏
• ∀𝑎, 𝑏, 𝑐 ∈ ℤ, si 𝑎𝑐 = 𝑏𝑐 ∧ 𝑐 ≠ 0 ⇒ 𝑎 = 𝑏
• ∀ 𝑎 ∈ ℤ, 𝑎 ⋅ 0 = 0

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

7 Propiedades del orden en ℤ
1. ∀𝑎, 𝑏, 𝑐 ∈ ℤ, 𝑎 ≥ 𝑏 → 𝑎 + 𝑐 ≥ 𝑏 + 𝑐
2. ∀𝑎, 𝑏, 𝑐 ∈ ℤ, 𝑎 ≥ 𝑏 → 𝑎 − 𝑐 ≥ 𝑏 − 𝑐
3. ∀𝑎, 𝑏, 𝑐 ∈ ℤ, 𝑎 ≥ 𝑏 ∧ 𝑏 ≥ 𝑐 → 𝑎 ≥ 𝑐
4. ∀𝑎, 𝑏, 𝑐 ∈ ℤ, 𝑎 ≥ 𝑏 ∧ 𝑐 ∈ ℤ+ ∪ 0 → 𝑎𝑐 ≥ 𝑏𝑐
5. ∀𝑎, 𝑏, 𝑐 ∈ ℤ, 𝑎 ≥ 𝑏 ∧ 𝑐 ∈ ℤ− → 𝑎𝑐 ≤ 𝑏𝑐
6. ∀𝑎, 𝑏, 𝑐, 𝑑 ∈ ℤ, 𝑎 ≥ 𝑏 ∧ 𝑐 ≥ 𝑑 → 𝑎 + 𝑐 ≥ 𝑏 + 𝑑
7. [Elemento mínimo] Si A ⊂ ℤ, y 𝑚 ∈ ℤ es tal que 𝑚 ≤ 𝑥, ∀𝑥 ∈ ℤ, entonces
existe 𝑎 ∈ A tal que 𝑎 ≤ 𝑥, ∀𝑥 ∈ 𝐴.

Dem. de [1]. Sean 𝑎, 𝑏, 𝑐 ∈ ℤ arbitrarios tales que 𝑎 ≥ 𝑏. Deseamos

demostrar que 𝑎 + 𝑐 ≥ 𝑏 + 𝑐.
Como 𝑎 ≥ 𝑏 entonces 𝑎 − 𝑏 ∈ ℤ+ ⇒ 𝑎 − 𝑏 + 0 ∈ ℤ+ ⇒ 𝑎 − 𝑏 + 𝑐 − 𝑐 ∈ ℤ+ ⇒
𝑎 + 𝑐 − 𝑏 +Matemáticas 𝑎 + 𝑐 ≥ 𝑏 + 𝑐Dra.,Leonor
ℤ+ ⇒2018-2019-I
𝑐 ∈ Discretas como Vázquez se deseaba probar. □
Los demás son ejercicios.
8 Ej.

• ∀𝑎, 𝑏 ∈ ℤ, si 𝑎 ≤ 𝑏 ⇒ −𝑏 ≤ −𝑎
• Sean 𝐴 = {3𝑘 − 1|𝑘 ∈ ℤ} y 𝐵 = {3𝑛 + 2|𝑛 ∈ ℤ}. Mostrar que 𝐴 = 𝐵

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

 Algoritmo de la división
9

El algoritmo de la división habla sobre el hecho de que, no siempre un

entero divide a otro.
Teorema (Algoritmo de la división). Para cualesquiera 𝑎, 𝑏 ∈ ℤ, 𝑏 ≠ 0, existen
𝑞, 𝑟 ∈ ℤ únicos, tales que 𝑎 = 𝑏𝑞 + 𝑟 con 0 ≤ 𝑟 < |𝑏|.
Ejemplo: Dados a = 157, 𝑏 = 2 ∈ ℤ, entonces 157 = 12 78 + 1

𝑎
𝑞

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

 10
En el bosquejo de la demostración del Teorema, se distinguen casos según
sean 𝑎 y 𝑏. Aquí se ejemplificara la demostración con ejemplos de cada
caso.
División por restas repetidas
Caso 1 ❑ [Caso 𝑎 ≥ 0, 𝑏 > 0]𝑎 = 86, 𝑏 = 15; se desea: 𝑞 y 𝑟 con 86 = 15𝑞 + 𝑟 0 ≤ 𝑟 < |𝑏|
𝑎 = 86
𝑏 = 15
𝑞: = 0
𝑟 ≔ 𝑎 = 86
¿𝑟 ≥ 𝑏? 86 ≥ 15 ⇒ {𝑟 = 86 − 𝑏 = 71; 𝑞 ++= 1} Entonces 86 = 15(5) + 11
¿𝑟 ≥ 𝑏? 71 ≥ 15 ⇒ {𝑟 = 71 − 𝑏 = 56; 𝑞 ++= 2}
¿𝑟 ≥ 𝑏? 56 ≥ 15 ⇒ {𝑟 = 56 − 𝑏 = 41; 𝑞 ++= 3}
¿𝑟 ≥ 𝑏? 41 ≥ 15 ⇒ {𝑟 = 41 − 𝑏 = 26; 𝑞 ++= 4}
¿𝑟 ≥ 𝑏? 26 ≥ 15 ⇒ {𝑟 = 26 − 𝑏 = 11; 𝑞 ++= 5}
¿𝑟 ≥ 𝑏? 11 ≥ 15 ⇒ 𝐹𝐼𝑁
Cociente 𝑞 = 5
Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez
Residuo 𝑟 = 11
 11
❑ [Caso 𝑎 ≥ 0, 𝑏 < 0]𝑎 = 86, 𝑏 = −15; se desea: 𝑞 y 𝑟 con 86 = (−15)𝑞 + 𝑟,
Caso 2
Analicemos la expresión: 0 ≤ 𝑟 < |𝑏|

86 = −15( )+( )
𝑟≥0
𝑞 será negativo

Note que en el caso de antes, Entonces, en el caso actual:

86 = +15(+5) + 11 86 = −15(−5) + 11
∴ 𝑞 = −5 y r=11

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

 0 ≤ 𝑟 < |𝑏|
12

𝑎 = 86
𝑏 = −15
𝑞: = 0
𝑟 ≔ 𝑎 = 86
¿𝑟 ≥ |𝑏|? 86 ≥ 15 ⇒ {𝑟 = 86 − 𝑏 = 71; 𝑞 −−= −1}
¿𝑟 ≥ |𝑏|? 71 ≥ 15 ⇒ {𝑟 = 71 − 𝑏 = 56; 𝑞 −−= −2}
¿𝑟 ≥ |𝑏|? 56 ≥ 15 ⇒ {𝑟 = 56 − 𝑏 = 41; 𝑞 −−= −3}
¿𝑟 ≥ |𝑏|? 41 ≥ 15 ⇒ {𝑟 = 41 − 𝑏 = 26; 𝑞 −−= −4}
¿𝑟 ≥ |𝑏|? 26 ≥ 15 ⇒ {𝑟 = 26 − 𝑏 = 11; 𝑞 −−= −5}
¿𝑟 ≥ |𝑏|? 11 ≥ 15 ⇒ 𝐹𝐼𝑁
Entonces 86 = −15(−5) + 11
Cociente 𝑞 = −5
Residuo 𝑟 = 11

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

 13
Caso 3
❑ [Caso 𝑎 < 0, 𝑏 > 0]𝑎 = −86, 𝑏 = 15; analizamos:
0 ≤ 𝑟 < |𝑏|
−86 = +15( )+( )
𝑟≥0
𝑞 será negativo

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

 0 ≤ 𝑟 < |𝑏|
14
Caso 3
❑ [Caso 𝑎 < 0, 𝑏 > 0]𝑎 = −86, 𝑏 = 15; analizamos:
−86 = +15( )+( )
𝑟≥0
𝑎 = −86 𝑞 será negativo
𝑏 = 15
𝑞: = 0
𝑟 ≔ 𝑎 = −86
¿r < 0? −86 < 0 ⇒ {𝑟 = −86 + 𝑏 = −71; 𝑞 −−= −1}
¿r < 0? −71 < 0 ⇒ {𝑟 = −71 + 𝑏 = −56; 𝑞 −−= −2}
¿ r < 0? −56 < 0 ⇒ {𝑟 = −56 + 𝑏 = −41; 𝑞 −−= −3}
¿r < 0? −41 < 0 ⇒ {𝑟 = −41 + 𝑏 = −26; 𝑞 −−= −4}
𝐸𝑛𝑡𝑜𝑛𝑐𝑒𝑠:
¿ r < 0? −26 < 0 ⇒ {𝑟 = −26 + 𝑏 = −11; 𝑞 −−= −5} −86 = +15(−6) + (4)
¿ r < 0? −26 < 0 ⇒ {𝑟 = −11 + 𝑏 = 4; 𝑞 −−= −6}
¿r < 0? 4 < 0 ⇒ 𝐹𝐼𝑁
Cociente 𝑞 = −6
Residuo 𝑟=4
Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez
 15
Caso 4 ❑ [Caso 𝑎 < 0, 𝑏 < 0) 𝑎 = −86, 𝑏 = −15
0 ≤ 𝑟 < |𝑏|

86 = −15( )+( )
𝑟≥0
𝑞 será positivo

Note que en el caso de antes, Entonces, en el caso actual:

−86 = +15(−6) + 4 86 = −15 +6 + 4
∴ 𝑞 = −6 y 𝑟 = 11
¿Qué modificaciones hay que hacer?
Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez
16
• Hacer otros ejemplos para comprender el procedimiento (al menos 2
ejemplos por caso)
• Hacer un par de ejemplos con a=0
• Implementar el algoritmo de la división por substracciones sucesivas.

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

 Algoritmo de la división: Divisibilidad
17

Si 𝑎, 𝑏 ∈ ℤ entonces se dice que 𝒂 divide a 𝒃 si ∃𝑐 ∈ ℤ tal que 𝑏 = 𝑎𝑐, y se denota por

𝑎|𝑏. También se dice que 𝑎 es un divisor de 𝑏.
Ejemplo: 2|20 porque 20 = 2(10)
3|12897 porque 12897 = 3(4299)

Si 𝑎, 𝑏 ∈ ℤ entonces se dice que 𝒃 es múltiplo de 𝒂 si ∃𝑐 ∈ ℤ tal que 𝑏 = 𝑎𝑐.

Ejemplo: 20 es múltiplo de 2 porque 20 = 2(10)
12897 es múltiplo de 3 porque 12897 = 3(4299)

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

 Algoritmo de la división: Divisibilidad
18

Propiedades de la divisibilidad
❑ ∀𝑎 ∈ ℤ, se verifica que 1|𝑎 y 𝑎|0 divide a la suma
❑ ∀𝑎, 𝑏 ∈ ℤ, si 𝑎 divide a 𝑏1 , 𝑏2 , … , 𝑏𝑘 ⇒ 𝑎 divide a la suma
❑ ∀𝑎, 𝑏 ∈ ℤ, si 𝑎 divide a 𝑏 entonces 𝑎 divide a ualquier múltiplo de 𝑏
❑ ∀𝑎, 𝑏, 𝑐 ∈ ℤ, si 𝑎 divide a 𝑏 y 𝑎 divide a 𝑐 entonces 𝑎 divide a 𝑏 − 𝑐

❑ Mostrar por inducción que 62𝑛 − 1 es divisible por 35

❑ Mostrar por inducción que 22𝑛−1 + 32𝑛−1 es divisible por 5
❑ Si 𝑛 es entero positivo, entonces 𝑛(𝑛 + 1) es divisible por 2
❑ a|1 ↔ |a|=1.
❑ (a|b ∧ b|a) ↔ |a|=|b|.

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

19
1. Demostrar las siguientes propiedades sobre divisibilidad de números enteros:
a) a|b y c|d ⇒ ac|bd
b) ac|bc y c\neq 0 ⇒ a|b
c) a|b y a|c ⇒ a| (b·c)
2. Si 4𝑛 es múltiplo de 2 y 2𝑛 es múltiplo de 2, ¿será su suma múltiplo de 2? ¿Y su
diferencia?
3. Si un número 𝑎 es divisible por otro 𝑏, ¿lo es también por todos los divisores de 𝑏?
Compruébalo para 180 y 30.
4. Escribe un número de tres cifras (𝑎𝑏𝑐). Vuelve a escribirlo a continuación(𝑎𝑏𝑐𝑎𝑏𝑐).
Divide el número resultante por 13, luego el cociente obtenido por 11.
Finalmente, el nuevo cociente lo divides por 7. ¿Por qué todas las divisiones
son exactas? ¿A qué se debe que el cociente final sea el que es?
5. Demostrar o poner un contraejemplo para las siguientes afirmaciones:
a) Si 𝑑 es divisor de 𝑎 + 𝑏, entonces 𝑑 divide a 𝑎 y 𝑑 divide 𝑎𝑏.
b) Si 𝑎 es divisor de 𝑏 y 𝑏 es divisor de 𝑎, entonces 𝑎 = 𝑏.

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

20
Algoritmo de la división: Sistemas Numéricos
La representación de los números naturales junto con el cero, se llama
escritura posicional en base decimal. Cada numero se expresa en
función de los símbolos (dígitos) 0,1,2,...,9, las cuales, dependiendo de la
posición que ocupen, tienen un determinado valor en base 10. Así:
1234 = 1𝑥103 + 2𝑥102 + 3 𝑥101 + 4𝑥100
Un sistema de numeración es un conjunto de reglas que permiten
escribir a los numero en 𝑁 ∪ {0} y hacer operaciones entre ellos.
Si queremos escribir a el numero 1234 en, por ejemplo, base 8, primero
se requieren los símbolos (o cifras) que se van a necesitar en este
sistema de numeración, a saber: 0,1,...,7. Luego, el numero x se debe
escribir de la forma:
1234 = 𝑏𝑘 × 8𝑘 + ⋯ + 𝑏2 × 82 + 𝑏1 × 81 + 𝑏0 × 80

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

 Algoritmo de la división: Cambio de bases
21

1234 = 𝑏𝑘 8𝑘 + ⋯ + 𝑏2 82 + 𝑏1 8 + 𝑏0 80
Para hacer esto, podemos proceder como sigue:
• Si suponemos que ya hemos realizado el proceso, entonces 1234 = 𝑞0 × 8 + 𝑏0 ; donde 𝑏_0
es el residuo de dividir 1234 entre 8; y 𝑞0 = 𝑏𝑘 8𝑘−1 + ⋯ + 𝑏2 81 + 𝑏1 80
• Si repetimos el proceso anterior ahora para 𝑞0 , entonces obtenemos el valor de 𝑎1 , así,
hasta llegar a determinar todas las cifras del numero 1234 en base 8.
En concreto:
1234 = 154*8+2 ➔ 𝑏0 = 2
154 = 19*8+2 ➔ 𝑏1 = 2 Determinar:
1234 =
19 = 2*8+3 ➔ 𝑏2 = 3 2
1234 = 3
2 = 0*8 + 2 ➔ 𝑏3 = 2 1234 = 4
Así: 1234 = 2 × 83 +2 × 82 +3× 81 +2 × 80 1234 = 5
Entonces 1234 en base 8 se escribe: 1234 = 6
1234 = 7
1234 = 2322 8
Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez
 Algoritmo de la división: Cambio de bases
22
Teorema. 𝑆𝑒𝑎𝑛 𝑎, 𝑏 ∈ ℕ con 𝑎 ≠ 0 y 𝑏 ≥ 2. Entonces existen únicos 𝑚 ∈ ℕ y 𝑎0 , 𝑎1 , … , 𝑎𝑚 ∈ ℕ tales
que:
• 𝑎𝑚 ≠ 0.
• 𝑎 =\sum𝑚 𝑘 𝑚
𝑘=0 𝑎𝑘 𝑏 = 𝑎𝑚 𝑏 + ⋯ + 𝑎1 𝑏 + 𝑎0
• 𝑎𝑖 < 𝑏
Demostración: Inducción sobre a.

Observaciones:
• Cada símbolo de la representación de un número se denomina cifra.
• Normalmente se elige como representación de 𝑎 = 𝑎𝑚 ⋯ a1 𝑎0 𝑏 , aquella para la que la
cifra de la izquierda sea distinta de cero (si esto es posible).
• Si 𝑎 = 𝑎𝑚 ⋯ a1 𝑎0 𝑏 y 𝑎𝑚 ≠ 0, diremos que el número 𝑎 tiene 𝑚 + 1 cifras en base 𝑏.
• Cuando no se especifique la base en que está expresado un número ,supondremos que
está en base decimal, salvo que el contexto deje suficientemente claro la base en que
estamos trabajando.

Ejercicio. Obtenga el algoritmo para sumar enteros cuando se representan en base b.

Podría obtener el algoritmo de la multiplicación?
Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez
 23

Operaciones en base b.

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

 Algoritmo de la división: Números Primos
24
Definición: Un entero positivo 𝑝 > 1, se dice que es primo si los únicos divisores de 𝑝 son 1
y 𝑝.
Ejemplo: Los números 2, 3, 19 son primos.
Los números enteros positivos mayores que 1, que no son primos, se les llama
compuestos, como por ejemplo 6. Es decir, todo número compuesto es de la forma
𝑚 = 𝑚1 𝑚2 ; donde 1 < 𝑚1 < 𝑚 y 1 < 𝑚2 < 𝑚.
Existen muchos problemas que involucran el uso de números primos, por lo que ha sido
relevante el estudio de los mismos.
Primos de Fermat
Fermat conjeturó que todo número de la forma
𝑛
𝑠(𝑛) = 22 + 1
era primo. Esto se comprobó para n= 1,2,3 y 4. Sin embargo en 1732 Euler demostró que
s(5) no era primo. A la fecha están las siguientes cuestiones abiertas:
• ¿Existen infinitos primos de Fermat? o
• ¿𝑠(𝑛) es compuesto para todo n?
Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

.
25
Primos de Mersenne
Un primo de Mersenne es un primo de la forma
2𝑛 + 1

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

26
Teorema Fundamental de la aritmética. Todo entero n>1 puede escribirse de
manera única como producto de números primos

Ejemplo: 32625 = 32 53 29

Proposición: Sean 𝑝, 𝑝1 , 𝑝2 , … , 𝑝𝑛 números primos, tales que 𝑝|𝑝1 𝑝2 ⋯ 𝑝𝑛 . Entonces

𝑝 = 𝑝𝑖 para algún 𝑖.

Teorema: Si 𝑛 > 1 es un entero compuesto y 𝑝 es un factor primo de 𝑛, entonces

𝑝 ≤ √𝑛

Teorema: El numero de primos es infinito.

✓ Construir la criba de Eratóstenes.

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez
27

1. Hallar la descomposición en factores primos de: (a) 615, (b) 540., (c) 214, (d) 1167,
(e) 444.
2. Por medio de la Criba de Eratóstenes, hallar todos los primos menores que 200.
3. Probar que si n no es primo, entonces n tiene un divisor primo, el cual es menor o
igual a √𝑛
4. Usando el resultado anterior, implemente un algoritmo de computación para
determinar cuándo un número es primo.
5. Determine cuáles de los siguientes números son primos: (a) 941(b) 1009 (c) 1123 (d)
1111 (e) 671 (f) 821.
6. Algunos primos son de la forma 4k + 1, como por ejemplo, 5, 17, 101, ... etc. Probar
que hay infinitud de ellos.
7. Demostrar que 2^524-1 no es primo.

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

28
Algoritmo de la división: mcd
Máximo común divisor: 𝒎𝒄𝒅(𝒂, 𝒃)

Def. Dados 𝑎, 𝑏 ∈ ℤ, se dice que 𝑑 ∈ ℤ es un máximo común divisor de 𝑎 y 𝑏 si:

i. 𝑑|𝑎 & 𝑑|𝑏.
ii. Si 𝑑1 |𝑎 & 𝑑1 |𝑏 entonces 𝑑1 |𝑑.
𝑚𝑐𝑑 𝑎, 𝑏 = gcd 𝑎, 𝑏 denota al máximo común divisor de a y b que se encuentra en
ℕ ∪ {0}
Def. Dados 𝑎, 𝑏 ∈ ℤ, se dice que 𝑚 ∈ ℤ es un mínimo común múltiplo de 𝑎 y 𝑏 si:
i. 𝑎|𝑚 & 𝑏|𝑚.
ii. Si 𝑎|𝑛 & 𝑏|𝑛 entonces 𝑚|𝑛.
𝑚𝑐𝑚(𝑎, 𝑏) o 𝑙𝑐𝑚(𝑎, 𝑏) denota al mínimo común multiplo que se encuentra en ℕ ∪ {0}

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

29 • Un faro se enciende cada 12 segundos, otro cada 18 segundos y un tercero
cada minuto. A las 6.30 de la tarde los tres coinciden. Averigua las veces que
volverán a coincidir en los cinco minutos siguientes.
➔Coinciden en tiempo múltiplo común de los 3 tiempos.
• Un viajero va a Guadalajara cada 18 días y otro cada 24 días. Hoy han estado los dos en
Guadalajara. ¿Dentro de cuantos días volverán a estar los dos a la vez en Guadalajara?
• ¿Cuál es el menor número que al dividirlo separadamente por 15, 20, 36y 48, en cada caso,
da de resto 9?
• En una bodega hay 3 toneles de vino, cuyas capacidades son: 250l, 360l,y 540l. Su contenido
se quiere envasar en cierto número de garrafas iguales. Calcular las capacidades máximas
de estas garrafas para que en ellas se pueden envasar el vino contenido en cada uno de
los toneles, y el número de garrafas que se necesitan.
➔La capacidad de las garrafas debe dividir a cada tonel, además de ser máxima.
El suelo de una habitación, que se quiere embaldosar, tiene 5 m de largo y 3 m de ancho.
Calcula el lado y el número de la baldosas, tal que el número de baldosas que se coloque sea
mínimo y que no sea necesario cortar ninguna de ellas.
Un comerciante desea poner en cajas 12 028 manzanas y 12 772 naranjas, de modo que cada
caja contengaMatemáticas
el mismo número de manzanas
Discretas 2018-2019-I
o de naranjas y, además, el mayor número
Dra. Leonor Vázquez
posible. Hallar el número de naranjas de cada caja y el número de cajas necesarias
30
Propiedades:
1. 𝑚𝑐𝑑(𝑎; 𝑏) = 𝑚𝑐𝑑(𝑎; −𝑏) = 𝑚𝑐𝑑(−𝑎; 𝑏) = 𝑚𝑐𝑑(−𝑎; −𝑏) = 𝑚𝑐𝑑(|𝑎|; |𝑏|).
2. 𝑚𝑐𝑑(𝑎; 0) = |𝑎| y 𝑚𝑐𝑑(𝑎; 1) = 1
3. Si 𝑎|𝑏 entonces 𝑚𝑐𝑑(𝑎; 𝑏) = |𝑎|.
4. 𝑚𝑐𝑑(𝑎, 𝑚𝑐𝑑(𝑏, 𝑐)) = 𝑚𝑐𝑑(𝑚𝑐𝑑 𝑎, 𝑏 , 𝑐) = 𝑚𝑐𝑑(𝑎, 𝑏, 𝑐).
5. 𝑚𝑐𝑑(𝑎𝑐, 𝑏𝑐) = 𝑚𝑐𝑑(𝑎, 𝑏)𝑐

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

31
Algoritmo de la división: Algoritmo de Euclides
Algoritmo de Euclides (mcd)
Sean 𝑎; 𝑏 ∈ ℤ. Puesto que 𝑚𝑐𝑑(𝑎, 𝑏) = 𝑚𝑐𝑑(|𝑎|, |𝑏|), podemos suponer que 𝑎, 𝑏 ∈ ℕ ∪
{0}. Comenzamos a efectuar divisiones:

Se obtiene una sucesión de números naturales 𝑟1 , 𝑟2 , … que es decreciente, donde

existe un k ∈ ℕ tal que r𝑘 ≠ 0 y 𝑟𝑘+1 = 0. Tenemos entonces:

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

32

Vamos a calcular el máximo común divisor de

48 y 30. Al ser a y b positivos, no es
necesario multiplicar por -1.
48 = (30)*1 + 18
30 = (18)*1 + 12
18 = (12)*1 + 6
12 = (6)*2 + 0
Por tanto, el máximo común divisor de 48 y 30
es a = 6

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

33

Vamos a calcular el máximo común divisor de Algoritmo de Euclides

48 y 30. Al ser a y b positivos, no es Entrada: 𝑎, 𝑏
necesario multiplicar por -1. Salida: 𝑚𝑐𝑑(𝑎, 𝑏)
48 = (30)*1 + 18 (𝑞, 𝑟) ← 𝑎𝑙𝑔_𝑑𝑖𝑣(𝑎, 𝑏);
30 = (18)*1 + 12 𝑎1 = 𝑏;
𝑏1 = 𝑟;
18 = (12)*1 + 6
mientras 𝑏1 ≠ 0
12 = (6)*2 + 0
(𝑞, 𝑟) ← 𝑎𝑙𝑔_𝑑𝑖𝑣(𝑎1, 𝑏1);
Por tanto, el máximo común divisor de 48 y 30
𝑎1 = 𝑏1;
es a = 6
𝑏1 = 𝑟;
Fin Mientras
𝑚𝑐𝑑(𝑎, 𝑏) = 𝑎1

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

34
Algoritmo de la división: Algoritmo de Euclides

Ejemplo: Un hombre va a una tienda de ropa y compra 12 trajes, unos negros y

otros grises, por $24,000. Si los trajes negros valen $600 más que los grises y ha
comprado el mínimo posible de estos últimos, ¿cuántos trajes ha comprado de
cada color?

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

35
Algoritmo de la división: Algoritmo de Euclides

Ejemplo: Un hombre va a una tienda de ropa y compra 12 trajes, unos negros y

otros grises, por $24,000. Si los trajes negros valen $600 más que los grises y ha
comprado el mínimo posible de estos últimos, ¿cuántos trajes ha comprado de
cada color?

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

36
Algoritmo de la división: Algoritmo de Euclides

Ejemplo: Un hombre va a una tienda de ropa y compra 12 trajes, unos negros y

otros grises, por $24,000. Si los trajes negros valen $600 más que los grises y ha
comprado el mínimo posible de estos últimos, ¿cuántos trajes ha comprado de
cada color?

Teorema: Una ecuación lineal

diofántica 𝑎𝑥 + 𝑏𝑦 = 𝑛 tiene
solución entera si y sólo si el
𝑚𝑐𝑑(𝑎, 𝑏) es un divisor de 𝑛.

Teorema [Identidad de Bezout]. Dados 𝑎, 𝑏 ∈ ℤ, con al menos uno diferente de

cero, entonces el gcd(𝑎; 𝑏) existe y gcd(𝑎; 𝑏) = 𝑑 = 𝑎𝑥 + 𝑏𝑦 para algunos 𝑥, 𝑦 ∈ ℤ.

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

37

Ej. Diseñar un algoritmo para la identidad de Bezout.

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

38
Definición. 𝑎, 𝑏 ∈ ℤ son primos relativos si 𝑚𝑐𝑑(𝑎, 𝑏) = 1.

Propiedades
• Si c|ab y a,c son coprimos ➔ c|b
• Si a y b son coprimos y a, c son coprimos -> a y bc son coprimos
• Si 𝑚𝑐𝑑(𝑎, 𝑏) = 1 y 𝑐|𝑏, entonces 𝑐|𝑏.
• Si 𝑝 es primo y 𝑝 † 𝑎, entonces 𝑚𝑑𝑐(𝑎; 𝑝) = 1.

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez

39 Divisibilidad en ℤ (congruencias modulo m)

Matemáticas Discretas 2018-2019-I Dra. Leonor Vázquez