1º ITIS

Matemática discreta

Relación 4

NÚMEROS NATURALES Y ENTEROS 1. Probar por inducción que si c es un número real, c ³ 1 , y n Î ¥ , entonces (1 + c )n ³ 1 + nc . 2. Probar

n(n + 1) 2 n n(n + 1)(2n + 1) c) å i =0 i 2 = 6 2 n n (n + 1)2 c) å i =0 i 3 = 4 n d) å i =0 (2i + 1) = (n + 1)2 a)

å

n

i =0

i=

n é n(n - 1) ù å i=1 i5 + å i =1 i7 = 2 êë 2 úû f) 13 (n3 + 2n) Î ¥ , "n Î ¥

e)

n

4

3. Demostrar que si r es un número natural y a0 ,..., a j naturales menores que r, entonces, para todo j ³ 0 , se tiene: a0 + a1r + a2 r 2 + L + a j r j < r j +1 . 4. Sea ( S , £ ) un conjunto totalmente ordenado. Demostrar que ( S , £ ) está bien ordenado si y sólo si no existen en S sucesiones estrictamente decrecientes, es decir, no existe ninguna aplicación f : ¥ ® S tal que f (n) > f (n + 1) "n Î ¥ . 5. ¿Para qué números naturales se verifica 2n > 2n ? Probar la respuesta. 1+ 5 1- 5 y b= . 2 2 a) Demostrar que a y b son las únicas soluciones reales de la ecuación x n + 2 = x n+1 + x n , para todo natural n (además de la solución nula, cuando n>0). b) Se define la sucesión de números de Fibonacci, como la aplicación F : ¥ ® ¥ , tal que F (0) = 0 , F (1) = 1 y F (n + 1) = F (n) + F (n - 1) , para n ³ 2 . Probar que para todo número natural n se cumple la relación an - bn F ( n) = . 5

6. Sean los números reales a =

7. Demostrar que existe un número infinito de números primos (Teorema de Euclides). 8. Probar que todo producto de números de la forma 4n + 1 es de nuevo de esa forma. Deducir que hay infinitos números primos de la forma 4n - 1 . (Observar que todo primo impar es de la forma 4n + 1 o 4n - 1 .)

Números naturales y enteros

1

1º ITIS

Matemática discreta

Relación 4

n

9. Si pn es el n-ésimo primo, probar que pn < 22 . 10. Probar que el m.c.m. de dos números enteros es único salvo el signo. Demostrar: a) (a, b) = 1 Û [a, b] = ab . b) [ka, kb] = k[a, b] (k > 0) . c) ab = [a, b](a, b) . 11. Sean a, b Î ¢ + , con descomposiciones en primos a = p1e1 L prer , b = p1f1 L prf r . Definimos d = p1g1 L prg r , con gi = min {ei , fi } y m = p1t1 L prtr , con ti = max {ei , fi } . Demostrar que d = (a, b) y m = [a, b] .

12. Probar que si r y s son enteros primos relativos y n es divisible por ambos, entonces también es divisible por su producto. 13. Sean q, m, n Î ¢ + . Probar que q - 1| q n - 1 . Deducir que m | n Þ q m - 1| q n - 1 . Demostrar que también es cierto el recíproco cuando es q > 1 . 14. Probar que si q n - 1 es primo, entonces q = 2 y n es primo. 15. Si q > 1 y n > 0, probar que q + 1| q n + 1 sii n es impar, y 2 | q n + 1 sii q es impar. Deducir que q n + 1 puede ser primo sólo si q es par y n = 2m . (Los n

números Fn = 22 + 1 se denominan números de Fermat.) 16. Sea Fn es n-ésimo número de Fermat. Comprobar que "k ³ 0 , k

Fn + k - 1 = ( Fn - 1) 2 . Deducir que dos números de Fermat distintos son primos relativos y, a partir de aquí, dar otra demostración del Teorema de Euclides. 17. Demostrar que la congruencia x 2 + y 2 º 4 3 no tiene soluciones. 18. Construir las tablas de suma y producto de ¢ 8 y mostrar con un ejemplo que la multiplicación no verifica la ley cancelativa. 19. Probar que m2 º8 0, 1 ó 4, "m Î ¢ . 20. Calcular en ¢ 7 el inverso de todos sus elementos no nulos. 21. Calcular el m.c.d. de los enteros a y b y expresaros como combinación lineal entera de éstos en los siguientes casos: a) a = 4519, b = 1519. b) a = 144, b = 1024. c) a = 6099, b = 2166. 22. Hallar la solución general de las siguientes ecuaciones sobre ¢ : a) 3x + 5y = 7. Números naturales y enteros

2

1º ITIS

Matemática discreta

Relación 4

b) 12x – 10y = 16. 23. Calcular la mínima solución positiva de la ecuación: 14655 x º 20157 17586 . ¿Cuáles son todas las soluciones? 24. Resolver los siguientes sistemas de congruencias enteras: a) x º 3 1 ; x º 5 3 . b) x º 3 2 ; x º 4 1 ; x º 5 3 ; x º13 4 . c) x º 4 1 ; x º 6 5 . 25.

a) Probar que todo entero positivo escrito como an an -1 K a0 en notación decimal es congruente con a0 + L + an -1 + an módulo 9. Deducir de aquí un método rápido para calcular el resto de la división por 9 de cualquier entero. b) Un conocido método para verificar la corrección de cálculos aritméticos es la llamada prueba del 9: se trata de efectuar cálculos módulo 9 de acuerdo con la regla anterior y examinar después la coincidencia de los restos. Concluir que la trasposición de dos dígitos no puede ser detectada por este método. c) Utilizando el método anterior, comprobar que dos de las siguientes igualdades son falsas. ¿Qué se puede decir de la otra igualdad? 5783 ´ 40162 = 233256846 9787 ´1258 = 12342046 8901´ 5743 = 52018433 d) Hallar un método análogo para el 11, basado en el hecho de que an an -1 K a0 º11 a0 - a1 + L + (-1)n an . Probar que este método sí detecta la trasposición de dos dígitos contiguos. e) Comprobar si 1213141516171819 y 192837465564738291 son divisibles por 11. ¿Qué cifra falta en la igualdad 871782 _1200 = 14! ?

26. ¿Por qué el sistema de congruencias siguiente no tiene solución positiva entre 1 y 100? x º3 0 x º5 0 x º7 0 27. Calcular la menor solución positiva del siguiente sistema de congreuencias: x - 6 º5 4 2 x º9 -5 3 x + 5 º11 -3 28. Calcular la solución general del siguiente sistema de congruencias:

Números naturales y enteros

3

1º ITIS

Matemática discreta

Relación 4

x º3 -1 2 x º7 1 5 x - 4 º11 2 5 x º5 -1 29. Calcular 7 -1 en ¢ 31 y

7 15

en ¢ 23 .

30. Hallar todas las soluciones enteras de: a) 2 x + 3 y = 7 b) 21x - 35 y = -14 31. ¿De cuántas formas distintas podemos pagar 3,5€ usando monedas de 20 y 50 céntimos? 32. Resolver, si es posible, el siguiente sistema de congruencias: x º2 1 x º6 5 33. Resolver el siguiente sistema de congruencias: 5 x - 7 y º12 9 2 x + 3 y º12 10 34. Usar el algoritmo de Euclides para calcular d = mcd {a, b} , y encontrar u y v tales que d = au + bv en los siguientes casos: a) a = 1312, b = 800 b) a = 322, b = 406 c) a = 721, b = 448 35. Calcular las soluciones enteras de las siguientes ecuaciones diofánticas: a) 28 x + 36 y = 44 b) 66 x + 550 y = 88 c) 966 x + 686 y = 70 36. Determinar los valores c Î ¢ + , 10 < c < 20 , para los cuales la ecuación 84 x + 990 y = c tiene solución, y determinarla, en su caso. 37. Comprobar mediante un ejemplo que en ¢ 6 , ¢ 8 y ¢15 existen elementos x e y tales que xy = 0 , siendo x ¹ 0 ¹ y . ¿Existe algún ejemplo en ¢ 7 ? 38. Hallar las unidades de ¢ 6 , ¢ 7 y ¢ 8 . 39. Hallar los inversos de: 6 en ¢11 , 6 en ¢17 , 3 en ¢10 , 5 en ¢12 , 4 en ¢11 , 7 en ¢15 , 7 en ¢16 , 5 en ¢13 y 777 en ¢1009 .

Números naturales y enteros

4

1º ITIS

Matemática discreta

Relación 4

40. Si p es primo, demostrar que los únicos elementos de ¢ p que coinciden con su inverso son 1 y -1 . a) Demostrar que 10! º11 -1 . b) Demostrar que ( p - 1)! º p -1 (Teorema de Wilson). Utilizar este resultado para calcular el resto de dividir 15! entre 17. 41. Una banda de 17 piradas se reúne para repartirse un cofre con más de cien monedas de oro. Efectuado equitativamente el reparto, sobra una moneda. En la pelea resultante para adjudicarla, muere un pirata. Vuelven a realizar el reparto y sigue sobrando una moneda. ¿Cuál es el número mínimo de monedas que puede contener el cofre? Supongamos que el valor anterior es el número real de monedas que contenía el cofre y que la historia continúa. Siempre que sobran monedas en el reparto, hay pelea y muere un pirata. ¿Cuántos piratas quedarán vivos cuando en el reparto no sobre ninguna moneda? 42. Se reparten cuatro bolsas iguales de caramelos entre tres grupos de niños. En el primer grupo, que consta de cinco niños, se parten dos bolsas y sobra un caramelo. En el segundo grupo, de seis niños, se reparte una bolsa y sobran dos caramelos. En el tercer grupo, de siete niños, se reparte una bolsa y sobran tres caramelos. Sabiendo que, en total, el número de caramelos no llegaba a 500, ¿cuántos caramelos había en cada bolsa? 43. Comprobar que 2340 º11 1 y que 2340 º31 1 . Concluir que 2340 º341 1 . ænö 44. Sea ç ÷ el número de subconjuntos distintos con k elementos que existen en un èk ø æ n ö æ n - 1ö æ n - 1ö conjunto con n elementos ( 0 £ k £ n ). Demostrar que ç ÷ = ç ÷+ç ÷. è k ø è k - 1ø è k ø (Idea: si llamamos X al conjunto con n elementos, considerar dos clases de subconjuntos con k elementos: los que contienen a un elemento fijado, y los que no contienen a dicho elemento.) 45. Demostrar la fórmula del binomio de Newton: n n æ ö n (a + b) = å ç ÷ a ib n -i , "a, b Î ¥ i =0 è i ø 46. Se define la función de Euler, j (m) , como el número de unidades de ¢ m . æ 1ö Demostrar la fórmula j (m) = mÕ ç1 - ÷ , con p primo. (Idea: probar que pø p|m è j (ab) = j (a)j (b) cuando a y b son primos relativos.) 47. Probar la siguiente igualdad para todo natural n ³ 1 :

Números naturales y enteros

5

1º ITIS

Matemática discreta

Relación 4

æ 1ö æ 1 ö æ 1 ö æ 1 ö ç 1 + ÷ × ç1 + ÷ × ç 1 + ÷L ç1 + ÷ = n + 1 è 1ø è 2 ø è 3 ø è n ø 48. ¿Cuántos números naturales hay, menores que 10000, que acaben en 7, y que al dividirlos entre 55 den de resto 12? 49. Calcular el inverso de 244 en ¢ 2749 . 50. ¿Cuándo es múltiplo de 4 un número escrito en base 8? 51. ¿Cuántos subconjuntos de {1, 2, 3, 4,5, 6, 7,8,9,10} contienen siempre entre sus elementos exactamente dos números impares? 52. Se define la sucesión: x0 = 0 , xn+1 = - xn + (-1) n . Demostrar que xn = (-1) n+1 n . 53. Calcular al inverso de 4874 módulo 37. 54. Demostrar por inducción que para cualquier número natural n ³ 0 , el número n(n 2 + 2) es múltiplo de 3. 55. ¿Cuántas soluciones tiene la ecuación 210 x - 91 y = 77 tales que -500 £ x, y £ 500 ? 56. Calcular de forma exacta la suma de todos los números de la forma 3 + 5k , con k ³ 0 , que sean menores o iguales a 12345. 57. Calcular cuántos números naturales hay, menores o iguales a 2000, que no sean múltiplos de 8 ni de 14. 58. ¿Cuál es el resto de dividir 4343 entre 15? a) 1 b) 3 c) 7 d) 12 e) 13 59. Sea n el número de 400 dígitos, que se construye al concatenar ochenta veces el bloque 15163. Entonces, el resto de dividir n entre 9 es: a) 3 b) 0 c) 1 d) 2 e) 6 60. ¿Cuál de los siguientes números enteros no tiene un inverso multiplicativo módulo 87? a) 6 b) 7 c) 8 d) 10 e) 14 61. Sean n = 1 + 2 + 3 + L + 1010 y 2k la mayor potencia de 2 que divide a n. Hallar el valor de k. 62. Sea R la relación binaria definida en ¢ 8 así: aRb Û $z Î ¢ 8 tal que a × x = b . Entonces: a) R es una relación de equivalencia cuyo conjunto cociente consta de dos elementos. Números naturales y enteros

6

1º ITIS

Matemática discreta

Relación 4

b) R no es una relación de equivalencia al no verificarse la propiedad transitiva. c) R es una relación de equivalencia cuyo conjunto cociente consta de cuatro elementos. d) R no es una relación de equivalencia al no verificarse la propiedad simétrica. 63. Obtener la descomposición canónica de la aplicación f : ¢ 8 ® ¢ 8 definida por f ( x) = x 2 . Hacer los mismo para g : ¥ ® ¥ , con g (n) = n mód 4 .

64. Sea f : ¢ 3 ´ ¢ 6 ® ¢ 3 ´ ¢ 6 la aplicación definida por f (a, b) = (b, 2a) . El conjunto f * ({2, 4} ) es: a) Æ

b) {(2, 2)}

c) {(1, 4)}

d) {(2, 2), (2,5)}

65. Sea f : {0,1, 2,K ,14} ® ¢15 , dada por f (a) = 2 a mód 15 . El cardinal de Im( f ) es: a) 1 b) 4 c) 10 d) 15

(

)

66. Dada la aplicación f : ¢ 8 ® ¢ 8 definida por f ( x) = x 2 + 5 , f * f* ({1, 6}) es: a) {0,1, 4,6}

b) {1, 2,3,5, 6, 7}

c) ¢ 8 d) {1, 6}

Números naturales y enteros

7