El valor dentro de un partido.Las pobres ovejas

dicen al pastor: Ve delante, que no nos faltará valor para
seguirte. Y el pobre pastor dice para sí: Seguidme y no
me faltará valor para guiaros
Universidad Simón Bolívar
Departamento de Computación
y Tecnología de la Información
Estructuras Discretas III
CI-2527 Abr-Jul 2016

Aurora, Federico Nietzsche.

Tarea 1Números Enteros

NOMBRE
CARNET
NOTA
1. Demostrar que si (a, b) = 1 ∧ (a, c) = 1, entonces (a, bc) = 1.
2. Demuestre que si a y b son dos enteros tales que (a, 4) = 2 y (b, 4) = 2, entonces 4|a + b.
3. Pruebe que para todos a, b, k ∈ Z se tiene que (a, b) = (a + bk, b).
4. Demuestre que si a|c, b|c y (a, b) = 1, entonces ab|c.
5. Demostrar que si b es un entero positivo compuesto, tiene un divisor primo positivo d ≤ √b.
6. interesante Dado un entero positivo n ̸= 1, basándose en su descomposición en primos, halle una
fórmula que permita saber cuántos divisores tiene el número n, sin tener que hallarlos.
7. interesante Demuestre que un número entero positivo n es un cuadrado perfecto si y sólo si tiene un
número impar de divisores positivos.
8. interesante Demuestre que para todo par de números enteros positivos a, b se cumple que ab =
mcd (a, b) · mcm (a, b).

Ejercicios Complementarios

1. Use el principio de buena ordenación para probar que no existe ningún entero positivo entre los enteros
cero y uno.
2. Si a y b son enteros positivos y b = p p · · · p , donde los p son todos primos distintos y los β 's son
enteros positivos, entonces a|b si y sólo si a = p p · · · p , y se tiene que 0 ≤ α ≤ β .
3. Cuantos divisores positivos tiene n si n = p , p es primo y α ≥ 0
4. Decimos que un número entero positivo n es perfecto si la suma de sus divisores es 2n, por ejemplo, 6
es perfecto porque 1 + 2 + 3 + 6 = 12.
a) Verique que 28 y 496 son perfectos.
b) Demuestre que si m ∈ Z y 2 −∑1 es primo, entonces 2 (2 − 1) es un entero perfecto.
r =
(
)
5. Demuestre que los enteros n , n , n son coprimos dos a dos si y sólo si (n , n n ) = (n n , n ) = 1.
6. Exprese el máximo común divisor de los pares de números siguientes como combinación lineal de dichos
números. Esto es, escriba en cada caso (x, y) = sx + ty, con s y t enteros.
a) (36, 9)
b) (11, 35)
c) (48, 18).
7. Computacional:√ Use el resultado del Ejercicio 5 (de la tarea) para diseñar un algoritmo ecienteDe
orden exacto: Θ( n) que permita decidir si el entero positivo n es primo.
βk
k
α1 α2
1
2

β1 β2
1 2

αk
k

i

i

i

i

α

+

m

m−1

n
i
i=0

Sug.: Tal vez necesite usar esta fórmula:

1

2

3

m

r n+1 −1
r−1

1

2 3

1 2

3

Si yo amo el mar y todo lo que es como el mar, y le amo más cuando colérico me contradice: Si dentro de mí se agita aquel placer del que
hincha sus velas en busca de lo desconocido, y me gustan los viajes del navegante: Si jamás gritó mi alegría: La costa desaparece: he roto
mi última cadena; la inmensidad me rodea; el tiempo y el espacio brillan lejos de mí. ½Vamos! ½En marcha, viejo corazón!, ½Oh, cómo no
he de sentir anhelos de eternidad y del anillo nupcial de los anillos: el anillo del Eterno Retorno! Nunca encontré la mujer de quien quisiera
tener hijos, a no ser la mujer a quien yo amo: ½pues yo te amo, eternidad! ½PUES YO TE AMO ETERNIDAD!
Así habló Zaratustra. Federico Nietzsche.