Teorema chino del residuo

Tarea #6 Fundamentos de Inform´tica I a El peligro amarillo
Carlos Bugueño 9 de noviembre de 2011

Problemas
1. Calcule a) 7401 m´d 41 o 41 es primo, por lo que φ(41) = 40. 401 = 40 · 10 + 1 107401 ≡ (740 ) · 71 (mod 41) 7401 ≡ 110 · 71 (mod 41) ≡7 b) 5050 m´d 45 o φ(50) = φ(5 · 5 · 2) = φ(52 ) · φ(2) = (25 − 5) · 1 = 20 50 = 20 · 2 + 10 50 ≡ 5(mod45) ⇔ 5050 ≡ 550 (mod 45) 2 550 ≡ (520 ) ·510 (mod 45) ≡ 12 · 510 (mod 45) φ(10) = φ(5) · φ(2) = 4 10 = 4 · 2 + 2 2 510 ≡ (54 ) · 52 (mod 45) ≡ 12 · 52 ≡ 25 2. El profesor Carroll quiere dividir su curso en grupos. Pero al dividirlo en tresgrupos, hay dos estudiantes que quedan fuera. Al intentar con cinco grupos, sobran tres. Finalmente intenta con siete grupos, y quedan dos sin grupo. ¿Cu´l es el m´ a ınimo n´mero de estudiantes en elcurso? u Grupo de 3 personas y 2 personas que quedan fuera: x = 2(mod 3) Grupo de 5 personas y 3 personas que quedan fuera: x = 3(mod 5) Grupo de 7 personas y 2 personas que quedan fuera: x = 2(mod 7)La congruencia en este caso es h = 3 · 5 · 7 = 105 S3 = 5 · 7 (5 · 7) 3 −1 = 5 · 7 (2 · 1) 3 = 35 · 2 (Existe inverso) = 70
−1

S5 = 3 · 7 (3 · 7) 5 −1 = 3 · 7 (3 · 2) 5 = 21 · 1 (Existe inverso)= 21 S7 = 3 · 5 (3 · 5) 7 −1 = 3 · 5 (3 · 5) 7 = 15 · 1 (Existe inverso) = 15 x = 70 · 2 + 21 · 3 + 15 · 2 = 233 + 105k (k = 0, 1, 2 ... n) ∴ El n´mero m´ u ınimo de estudiantes es de 233. 3.Encuentre todas las soluciones enteras (x, y) para la ecucaci´n 119x + 399y = gcd(119, 399). o Primero, hay que encontrar el gcd (119, 399): gcd (119, 399) : 399 = 119 · 3 + 42 ⇒ gcd (119, 399) = gcd (119,42) gcd (119, 42) : 119 = 42 · 2 + 35 ⇒ gcd (119, 42) = gcd (42, 35) gcd (42, 35) : 42 = 35 + 7 ⇒ gcd (42, 35) = gcd (35, 7) = 7 ⇒ 119x + 399y = 7. Simplificando la ecuaci´n, queda: o 17x + 57y = 1Ahora, despejo x: 1 x = 17 · (−57y + 1) De aca se deduce y0 = 3 y x0 = −10 por lo que todas las soluciones enteras se da de la forma x = −10 − 57k y = 3 + 17k , k = 0, 1, 2, ... n 4. La ecuaci´n de Pell...