Atividade de Teoria dos Números

TAREFA DE TEORIA DOS NÚMEROS Matematica Discreta Teoria dos Numeros Prof Matheus 1 Iremos completar o quadrado do trinˆomio a2 abb2 Ou seja vamos expressa lo na forma de um quadrado perfeito a2 ab b2 a b 22 3b2 4 A expressao dentro dos parˆenteses e um quadrado perfeito e como o quadrado de qualquer numero real e nao negativo entao a b 22 0 Alem disso 3b2 4 0 para qualquer valor de b ja que estamos elevando ao quadrado e multiplicando por um coeficiente positivo Portanto a soma desses dois termos e nao negativa o que implica que a2 ab b2 0 Assim provamos que 0 a2 ab b2 7 Vamos testar os primos p 13 Para p 2 2 1 1 e 1 1 mod 22 nao e verdade Para p 3 3 1 2 e 2 1 mod 32 nao e verdade Para p 5 5 1 24 e 24 1 mod 52 e verdade Para p 7 7 1 720 e 720 1 mod 72 nao e verdade Para p 11 11 1 362880 e 362880 1 mod 112 e verdade Portanto os primos p 13 para os quais a congruˆencia e valida sao p 5 e p 11 8 Para decifrar a mensagem usaremos o conceito de inverso modular O inverso modular de k modulo p e o numero k1 tal que kk1 1 mod p Vamos en contrar o inverso de 43 modulo 2551 Usando o algoritmo de Euclides estendido podemos encontrar o inverso modular de 43 modulo 2551 2551 59 43 1443 3 14 114 14 1 0 O MDC de 43 e 2551 e 1 o que significa que 43 e 2551 sao primos entre si Portanto podemos usar o algoritmo de Euclides estendido para encontrar x e y tal que 43x 2551y 1 1 Resolvendo as equacoes do algoritmo de Euclides estendido encontramos x 67 e y 1 Portanto o inverso modular de 43 modulo 2551 e 67 Para decifrar a mensagem usamremos a formula de decifragem da cifra exponencial M Cd mod p onde M e a mensagem original C e o texto cifrado d e o expoente de decifragem e p e o modulo A mensagem original M pode ser encontrada como Cd mod p Para o primeiro numero do texto cifrado 1518 M1 151867 mod 2551 M1 1127 mod 2551 Para o segundo numero do texto cifrado 2175 M2 217567 mod 2551 M2 1442 mod 2551 Para o terceiro numero do texto cifrado 1249 M3 124967 mod 2551 M3 1064 mod 2551 Para o quarto numero do texto cifrado 0823 M4 082367 mod 2551 M4 1303 mod 2551 Para o quinto numero do texto cifrado 2407 M5 240767 mod 2551 M5 2118 mod 2551 Portanto a mensagem original e 1127 1442 1064 1303 2118 2