Trabajo práctico 3 (soluciones) PDF

Preview

Summary

Trabajo practico 3 de la materia Matematica Discreta, dada en el 2017.
El mismo esta resulto. ...

Description

Universidad Abierta Interamericana Matemática Discreta y Autómatas – 2017

Soluciones Trabajo práctico 3: Aritmética modular. 1) Para hallar la descomposición puede usarse la herramienta online de Wolfram Alpha en: http://www.wolframalpha.com Para hallar la factorización de un número n, ingresar Factor[n]. Para saber si un número n es primo, ingresar PrimeQ[n] 491891 = 19 . 25889

92400 = 24 .3 . 52 . 7. 11

2541 = 3.7.112 94017 = 3.7.112.37 4 2 7! = 2 .3 .5.7 153 = 33.53 491891 tiene 4 divisores positivos. 92400 tiene 5*2*3*2*2 = 120 divisores positivos 2541 tiene 2*2*3 = 12 divisores positivos 94017 tiene 2*2*3*2=24 divisores positivos 7! tiene 5*3*2*2 = 60 divisores positivos 153 tiene 4*4=16 divisores positivos 2) 250 = 2. 110 + 30 110 = 3 . 30 + 20 30 = 1 . 20 + 10 20 = 2 .10 + 0 ----> mcd(250,110)=10 Para escribir 10 como combinación lineal entera de 250 y 110, remplazamos hacia atrás: 10 = 30 - 1 . 20 = 30 - 1.(110 - 3 . 30) = 4*30-1*110 = 4(250-2*110)-1*110 = 4*250 - 9* 110 10 = 4 . 250 - 9 . 110 3) 1820 = 7 . 231 + 203 231 = 1 . 203 + 28 203 = 7 . 28 + 7 28 = 4 . 7 + 0 -----> mcd(1820,231) = 7 Para escribir 7 como combinación lineal entera de 1820 y 203 remplazamos hacia atrás: 7 = 203-7 . 28 = (1820 - 7 . 231) - 7. (231 - 1 . 203) = 1820 - 14 . 231 + 7 . 203 = 1820 - 14 . 231 + 7 . (1820 - 7. 231) = 1820 - 14.231 + 7 . 1820 - 49 . 231 = 8 . 1820 -63.231 7 = 8 . 1820 - 63 . 231 4) Como ya tenemos la factorización de los números en el problema 2, se puede hallar el mcd mirando los factores primos repetidos. mcd(491891,92400) = 1 mcd(7!,2541) = 3.7 = 21 mdc(94017,153) = 3 5) Algoritmo más eficiente Entrada: entero n Salida: lista L de divisores de n Para i desde 1 hasta n

Algoritmo menos eficiente Entrada: entero n Salida: lista L de divisores de n Para i desde 1 hasta n

Universidad Abierta Interamericana Matemática Discreta y Autómatas – 2017 Si n/i es entero Si n/i es entero Agregar i a la lista L Agregar i a la lista L fin si Agregar n/i a la lista L fin si fin para fin para El algoritmo de la izquierda ejecuta el ciclo para n veces. El de la derecha ejecuta el ciclo n veces. Para n grande, la diferencia del costo computacional (cantidad de operaciones ejecutadas) es notable: si n=1000000, el primer algoritmo ejecuta 1000 veces el ciclo, y el segundo lo hace 1000000 veces! 6) Un algoritmo para hallar el mcd puede encontrarse en el libro de Grimaldi, sección 4.4 (de la 3º edición). 7) a. No tiene solución. Porque mcd(2,12)=2, y 2 no divide a 1. b. Sí tiene solución, ya que mcd(33,17)=1, divide a 1. 33 = 1*17+16 17= 1*16+1. ----> 1 = 17-16 = 17-(33-17) = 2*17-33 1 = 33*(-1)+2*17---> x0=-1, y0=2 Solución general: x = -1+17k, y = 2-33k c. Sí tiene solución. Buscamos mcd(87,14): 87 = 6*14 + 3 14 = 4*3 + 2 3=1*2+1----------> 1=3-2 = 3-(14-4*3) = 5*3-14 = 5*(87-6*14)-14 = 5*87-31*14 1 = 5*87-14*31----->x0=5, y0 = 31 Sol general: x = 5+(-14)k, y=31-87k d. mcd(540,100)=20 no divide a 1201, entonces no tiene solución. e. mcd(-107,-106)=1 divide a 13, tiene solución. como 1 = -107*(-1)-106*1 ------> x0 = -1, y0 = 1 Sol general: x = -1-106k; y = 1-(-107)k f. mcd(126,819) = 63, no divide a 21: no tiene solución. 8) ..., -16, -9, -2, 5, 12, 19, 26, 33, ... 9) En Z7: 1 es inverso de sí mismo, 2 y 4 son inversos, 3 y 5 son inversos, 6 es inverso de sí mismo. En Z6: 1 es inverso de sí mismo, 5 es inverso de sí mismo. 2, 3 y 4 no tienen inversos En Z11: 1 inverso de sí mismo, 2 y 6 son inversos, 3 y 4 son inversos, 5 y 9 son inversos, 7 y 8 son inversos, 10 es inverso de sí mismo. En Z15: 1 es inverso de sí mismo, 2 y 8 son inversos, 4 es inverso de sí mismo, 7 y 13 son inversos, 11 es inverso de sí mismo, 14 es inverso de sí mismo. 3, 5, 6, 9, 10,12 no tienen inversos (no son coprimos con 15) 10) En Z11 no hay divisores propios de cero. En Z15 los divisores propios de cero son: 3, 5, 6, 9, 10, 12.

Universidad Abierta Interamericana Matemática Discreta y Autómatas – 2017

11) Hallar los inversos multiplicativos (si existen) de 13, 54 y 102 módulo 200. El inverso de 13 es el x tal que 13x  1 (200) 200=15*13 + 5 13=2 * 5 + 3 5= 1*3 + 2 3=1*2 + 1 mcd(200,13) = 1 = 3-2 = 3-(5-3)=2*3-5 = 2*(13-2*5) -5 = 2*13 -5*5 = 2*13-5(200-15*13) = -5*200+77*13 ---- entonces un inverso de 13 es 77. Todos los inversos se obtienen de sumar un multiplo de 200 a 77: x = 77+200k El inverso de 54 es el x tal que 54x  1 (200). Como 54 no es coprimo con 200 (mcd(54,200)=2), no tiene inverso módulo 200. 102 no es coprimo con 200, no tiene inverso módulo 200. 12) Inverso de 2: 209 = 104*2+1-----> mcd(209,2)= 1 = 209-104*2-----> Un inverso de 2 módulo 209 es -104. O cualquier entero que se obtenga sumando un múltiplo de 209: x=-104+209k Inverso de 10: 209 = 20*10+9 10 = 1*9+1 ---> mcd(209,10) = 1 = 10-9 = 10-(209-20*10) = -1*209 + 21*10. El inverso de 10 módulo 209 es 21 o cualquier entero que tenga resto 21 en la división por 209: x = 21+209k. Inverso de 102: 209 = 2*102+5 102 = 20*5+2 5=2*2+1-------> mcd(209,102) = 1 = 5-2*2 = 5-2*(102-20*5)=-2*102+41*5 = = -2*102+41*(209-2*102)=-84*102 + 41*209. El inverso de 102 módulo 209 es -84, o cualquiera que sea congruente con él módulo 102: x = -84+209k. 13) El último dígito de 1321 es 3, ya que 133(10), 13232(10), es decir, 1329(10); 1333*9(10), es decir, 1337(10); 1343*7(10), es decir, 1341(10). Luego, 1320=(134)515(10). Finalmente, 1321=1320131*3(10), es decir, 13213(10) 14) a. 2

b. 3

c. 4

d. 0

e. 17

f. 4

15) a. no tiene solución b. x = 3 + 6k, kZ c. x = 5 + 11k, kZ d. x = 23 + 101k, kZ e. x = 0 + 5k, kZ f. x = 0 + k, kZ g. no tiene solución h. x = 450 + 56k, kZ i. x = 24 + 11k, kZ j. x = 1560 + 103k, , kZ

Universidad Abierta Interamericana Matemática Discreta y Autómatas – 2017 17) Entrada: Los 10 dígitos del ISBN: x1 , x2, ..., x10 Salida: " válido" si es un ISBN correcto, "inválido" si es incorrecto si x10 = "X" hacer x10 = 10 fin si suma=0 para i=1 a 10 hacer suma := suma + i*xi fin para si (resto de suma dividido 11 = 0) hacer return "válido" si no return "inválido" fin si 18) Entrada: Los 13 dígitos del código de barras: x1 , x2, ..., x13 Salida: " válido" si es un código correcto, "inválido" si es incorrecto suma=0 para i=1 a 6 hacer suma := suma + x2i-1 + 3*x2i fin para suma := suma + x13 si (resto de suma dividido 10 = 0) hacer return "válido" si no return "inválido" fin si...