Matemáticas Discretas Taller 8 2015

Matem´
aticas Discretas
Taller 8 2015-01
1. Use el algoritmo de la divisi´on (llamado Teorema del cociente-residuo por
Johnsonbaugh) para probar que:
a.) Cada entero impar es de la forma 4k + 1 ´o 4k + 3;
b.) El cuadrado de cualquier entero es de la forma 4k ´o 4k + 1;
2. Para n ≥ 1, pruebe que n (n + 1) (2n + 1) /6 es un entero. (Ayuda: Por
el algoritmo de la divisi´on, n es de una de las formas 6k, 6k + 1, · · · , 6k + 5;
pruebe el resultado en cada uno de los casos.)
3. Para cada entero a, pruebe que
a.) 2 | a (a + 1) y que 3 | a (a + 1) (a + 2) .
b.) Pruebe que 4 - a2 + 2 , es decir, 4 no divide a a2 + 2 .
4. Para n ≥ 1, use inducci´on matem´atica para probar que
a.) 7 divide a 23n − 1;
b.) 8 divide a 32n + 7;
c.) 2n + (−1)
n+1
es divisible por 3.
5. Encuentre la factorizaci´on prima de 14!
6. De un ejemplo de primos consecutivos p1 = 2, p2 , p3 , ..., pn para los que
p1 p2 p3 ...pn + 1
no es primo.
7. Utilice el algoritmo para decidir si un entero es primo (algoritmo 5.1.8 en
la sexta edici´
on del libro de Johnsonbaugh) con los siguientes n´
umeros:
a.) 103
b.) 147
c.) 1433
8. Encuentre el m´
aximo com´
un divisor y el m´ınimo com´
un m´
ultiplo de las
siguientes parejas de n´
umeros enteros:
a.) 1575, 231
b.) 140, 180
c.) -1575, -231
d.) -93, 119
9. Sean n, c y d enteros. Demuestre que si dc | nc, entonces d | c.
10. Decida la verdad o falsedad de las siguientes afirmaciones. Justifique su
respuesta
a.) Si a | b y b | −c entonces a | c
b.) Si a | b y c | b entonces ac | b
1
11. Confirme que se cumplen las siguientes propiedades del m´aximo com´
un
divisor de dos enteros:
a.) Si mcd (a, b) = 1 y mcd (a, c) = 1, entonces mcd (a, bc) = 1.
b.) Si mcd (a, b) = 1 y c | a entonces mcd (b, c) = 1.
c.) Si mcd (a, b) = 1 entonces mcd (ac, b) = mcd (c, b) .
d.) Si mcd (a, b) = 1 y c | (a + b) entonces mcd (a, c) = mcd (b, c) = 1.
12. Sean a y b enteros no nulos con mcm (a, b) = t. Sea m un m´
ultiplo com´
un
de a y b. Demuestre que t | m.
13. Demuestre que la suma de dos primos consecutivos nunca es igual a un
primo multiplicado por dos.
14. Defina una funci´
on f de los naturales en los naturales que a cada n´
umero
natural n le asigna su mayor divisor primo.
(a) Encuentre el rango de f.
(b) Decida si la funci´on f es uno a uno. Justifique.
(c) Decida si la funci´on f es sobre. Justifique.
15. Demuestre que la suma de dos primos impares no puede ser un n´
umero
primo. Reflexione acerca del mismo enunciado sin la condici´on de que
ambos primos sean impares.
16. De un ejemplo que pruebe que la siguiente conjetura es falsa: Cada entero
positivo puede ser escrito en la forma p+a 2 , donde p es 1 o un n´
umero
primo y a≥ 0.
17. Una pregunta que no se ha resuelto es si existen infinitos n´
umeros primos
de la forma 2k + 1, como por ejemplo 5 = 22 + 1. Encuentre otros 3 primos
de esta forma.
18. Se ha conjeturado que todo entero par puede ser escrito como la diferencia
de 2 primos consecutivos en un infinito n´
umero de formas. Por ejemplo
6 = 29 − 23 = 137 − 131 = 599 − 593 = 1019 − 1014 = · · · .
Exprese el entero 10 como la diferencia de 2 primos consecutivos en 15
formas diferentes.
19. Pruebe que el producto de 2 o m´as enteros de la forma 4n + 1 es de la
misma forma.
2