47. c. “Maneras y Medios” Sección 8.4 1. a. GRQGH QRV HQFRQWUDUHPRV b. EN LA CAFETERÍA 3. a. La relación 3 (25 ฀ 19) es verdadera porque 25 ฀ 19...

47. c. “Maneras y Medios” Sección 8.4 1. a. GRQGH QRV HQFRQWUDUHPRV b. EN LA CAFETERÍA 3. a. La relación 3 (25 ฀ 19) es verdadera porque 25 ฀ 19 6 y 3 6 (6 3 2). b. Por definición de congruencia módulo n, para demostrar que 25 19 (mod 3), se debe demostrar que 3 (25 ฀ 19). Esto se comprobó en el inciso a). c. Para demostrar que 25 19 3k para algún entero k, se resuelve la ecuación para k y se comprueba que el resultado sea un entero. En este caso, k (25 ฀ 19) 3 2, que es un entero. Así 25 19 2 3. d. Cuando 25 se divide por 3, el residuo es 1 porque 25 3 8 1. Cuando 19 se divide por 3, el residuo también es 1 porque 19 3 6 1. Así 25 y 19 tienen el mismo residuo cuando son divididos por 3. e. Por definición, 25 mod 3 es el residuo que se obtiene cuando 25 se divide por 3 y 19 mod 3 es el residuo que se obtiene al dividir 19 por 3. En el inciso d ) se probó que ambos números son iguales. 6. Sugerencias: 1) Use el teorema cociente-residuo y el teorema 8.4.1 para demostrar que dado cualquier entero a, éste se encuentra en una de las clases [0], [1], [2], …, [n฀1]. 2) Con el teorema 4.3.1 demuestre que si 0 a n, 0 b n y a b (mod n), entonces a b. 7. a. 128 2 mod 7 porque 128฀ 2 126 7 18, y 61 5 mod 7 porque 61฀ 5 56 7 8 b. 128 61 2 5 mod 7 porque 128 61 189, 2 5 7, y 189฀ 7 182 7 26 c. 128฀ 61 2฀ 5 mod 7 porque 128฀ 61 67, 2฀ 5 ฀3, y 67฀ ฀3 70 7 10 d. 128 61 2 5 (mod 7) porque 128 61 7808, 2 5 10, y 7808฀ 10 7798 7 1114 e. 1282 22(mod 7) porque 1282 16384, 22 4, y 16384฀ 4 16380 7 2340. 9. a. Demostración: Suponga que a, b, c, d y n son enteros con n 1, a c(mod n) y b d(mod n). Por el teorema 8.4.1, a ฀ c nr y b ฀ d ns para algunos enteros r y s. Entonces (a + b) − (c + d) = (a − c) + (b − d) = nr + ns = n(r + s). Pero r s es un entero y así, por el teorema 8.4.1, a b (c d ) (mod n). 12. a. Demostración (por inducción matemática): Aceptemos que la propiedad P(n) sea la congruencia 10n 1 (mod 9). Demostración de que P(0) es verdadero: Cuando n 0, el lado izquierdo de la congruencia es 100 1 y el lado derecho también es 1. Demostración de que para todos los enteros k 0, si P(k) es verdadera, entonces P(k 1) también es verdadera. Sea k cualquier entero con k 0 y suponga que P(k) es verdadera. Es decir, acepte que 10 k 1 (mod 9). (*) [Esto es la hipótesis inductiva.] Por el teorema 8.4.1, 10 1 (mod 9) (**) porque 10 ฀ 1 9 9 1. Y por el teorema 8.4.3, podemos multiplicar el lado izquierdo y derecho de (*) y (**) para obtener que 10 k 10 1 1 (mod 9) o, equivalentemente, 10 k 1 1 (mod 9). Así que P(k 1) es verdadera. Demostración alternativa: Observe que 10 1 (mod 9) porque 10 ฀ 1 9 y 9 9. Entonces por el teorema 8.4.3 (49, 10 n 1n 1 (mod 9). 14. 141 mod 55 = 14 142 mod 55 = 196 mod 55 = 31 144 mod 55 = (142 mod 55)2 mod 55 = 312 mod 55 = 26 148 mod 55 = (144 mod 55)2 mod 55 = 262 mod 55 = 16 1416 mod 55 = (148 mod 55)2 mod 55 = 162 mod 55 = 36 15. 427 mod 55 = 1416+8+2+1 mod 55 = { (1416 mod 55)(148 mod 55)(142 mod 55) (141 mod 55) } mod 55 = (36 ·16 ·31 ·14) mod 55 = 249984 mod 55 = 9 16. Observe que: 307 256 32 16 2 1. 675 1 mod 713 675 675 2 mod 713 18 675 675 4 mod 713 182 mod 713 324 675 675 8 mod 713 3242 mod 713 165 675 675 16 mod 713 165 2 mod 713 131 675 675 32 mod 713 1312 mod 713 49 675 675 64 mod 713 492 mod 713 262 675 675 128 mod 713 2622 mod 713 196 675 675 256 mod 713 1962 mod 713 627 Así 675 307 mod 713 675 256 32 16 2 1 mod 713 675 256 675 32 675 16 675 2 675 1 mod 713 627 49 131 18 675 mod 713 3 19. Las letras HOLA se trasladan numéricamente en 08, 15, 12 y 01. Por el ejemplo 8.4.9, la H se encripta como 17. Para encriptar la O, calculamos 15 3 mod 55 20. Para encriptar la L, determina- mos 123 mod 55 23. Y para encriptar la A, obtenemos 13 mod 55 01. Así el texto cifrado es 17 20 23 01. (En la práctica, las letras individuales del alfabeto se agrupan en bloques durante la encriptación para que así el descifrado no se pueda lograr conociendo los patrones de frecuencia de letras o palabras). 22. Por el ejemplo 8.4.10, la clave para el descifrado es 27. Así, los residuos módulo 55 para 0827, 2127, 15 27, 4927 y 2027 se deben encontrar y traducirse a las letras del alfabeto. 8.4 Soluciones y sugerencias para los ejercicios seleccionados A-71 A-72 Apéndice B Soluciones y sugerencias para los ejercicios seleccionados Como 27 16 8 2 1, primero efectuamos las siguientes operaciones: 081 8 (mod 55) 211 21 (mod 55) 15 1 15 (mod 55) 082 9 (mod 55) 212 1 (mod 55) 15 2 5 (mod 55) 084 26 (mod 55) 214 1 (mod 55) 15 4 25 (mod 55) 088 16 (mod 55) 218 1 (mod 55) 15 8 20 (mod 55) 0816 36 (mod 55) 2116 1 (mod 55) 15 16 15 (mod 55) 491 49 (mod 55) 201 20 (mod 55) 492 36 (mod 55) 202 15 (mod 55) 494 31 (mod 55) 204 5 (mod 55) 498 26