Lista de Exercicios Resolvidos Matematica Discreta e Teoria dos Numeros

1 Suponha que X Y e Z são conjuntos nãovazios e subconjuntos de Ω Utilizando uma tabela de pertinência verifique se os conjuntos X Yᶜ X Z e X Y Z são iguais 2 Utilizando o Algoritmo da Divisão represente as seguintes divisões inteiras a 318 54 b 128 3 c 10 001 999 3 Utilizando o Algoritmo de Euclides calcule a mdc891005 b mdc514511 c mdc1820 036 4 Suponha que certa identificação é composta por sete números sendo os dois últimos dígitos verificadores DVs Sendo ABCDEXY o formato dessa identificação suponha que os DVs são calculados da seguinte maneira X A 2B 3C 4D 5E mod 10 Y N mod 10 sendo N o primeiro nome da pessoa a ser identificada desconsiderandose acentos e sinais gráficos e convertido de acordo com a tabela ao fim da página Obtenha os DVs para alguém cujo primeiro nome é igual ao seu e cujos cinco primeiros dígitos da identificação são 22452 5 Obtenha os números pseudoaleatórios x₁ x₂ x₅ obtidos por meio da sequência recursiva x₀ p xₙ 23xₙ₁ 12 mod 101 sendo a p 1 b p 2 6 Resolva a equação 8x 15 mod 63 18 sendo x um número inteiro 7 Faça a codificação da frase CODIFIQUE A FRASE convertendo cada caractere de acordo com a tabela abaixo aplicando a cada valor obtido a função fx 9x 5 mod 32 e transcrevendo cada um desses valores para um caractere novamente 8 Obtenha a função d 0131 0131 que decodifica uma palavra codificada de acordo com a função dada no Exercício 7 Tabela de conversão de letrassímbolos para sequências decimais A 00 I 08 Q 16 Y 24 B 01 J 09 R 17 Z 25 C 02 K 10 S 18 26 D 03 L 11 T 19 27 E 04 M 12 U 20 28 F 05 N 13 V 21 29 G 06 O 14 W 22 30 H 07 P 15 X 23 Espaço 31 1 Obtenha a inversa modular se existir de a 19₁₀₁ b 54₈₉ c 23₁₀₀₁ 2 Resolva a equação modular 3x 7 mod 16 12 3 Um número de CPF é constituído de 11 dígitos sendo os dois últimos dígitos verificadores DVs Se representarmos um número de CPF por ABCDEFGHIXY os DVs X e Y são calculados da seguinte maneira Calculase P 11 10A 9B 8C 7D 6E 5F 4G 3H 2I mod 11 Se P 9 então X 0 caso contrário X P Calculase Q 11 11A 10B 9C 8D 7E 6F 5G 4H 3I 2X mod 11 Se Q 9 então Y 0 caso contrário Y Q Calcule os DVs X e Y para 123456789 XY 4 Um número de RG é constituído de 9 dígitos sendo o último o dígito verificador DV Se representarmos um número de RG por ABCDEFGHW o DV W é calculado da seguinte maneira Calculase P 9A 8B 7C 6D 5E 4F 3G 2H mod 11 Se P 10 então utilizase a letra X como DV Se P 10 então W P Calcule o DV W para 12345678W 5 Obtenha os cinco primeiros números pseudoaleatórios x₁ a x₅ gerados por meio da recorrência x₀ 15 xₙ 13 xₙ₁ 54 mod 103 6 Um sistema de codificação é utilizado da seguinte forma cada letra de uma palavra é codificada em sequências decimais de dois dígitos de acordo com a tabela ao fim da página desconsiderandose acentos e sinais gráficos em seguida para cada sequência x calculase fx 21x 15 mod 32 e o valor decimal resultante é convertido de volta para uma letra ou símbolo de acordo com a mesma tabela a Converta as letras de seu primeiro nome para sequências decimais utilizando a tabela citada b Utilize o processo descrito no enunciado para codificar seu primeiro nome escrevendo a versão codificada 7 Suponha que EDEPPΝTP é uma mensagem de acordo com o processo descrito no Exercício 6 a Obtenha uma função gy que recebe a sequência decimal y de uma letra codificada e devolve a sequência decimal da letra decodificada Dica gy é da forma gy ay 15 mod 32 sendo a₃₂ a inversa de 21₃₂ com 0 a 31 b Decodifique a mensagem 8 Uma codificação em sistema RSA foi feita da seguinte maneira os caracteres de uma palavra foram separados de dois em dois formando um bloco e cada caractere desse bloco foi convertido de acordo com a tabela ao fim da página Então dois primos foram multiplicados resultando em n 1073 e escolheuse um valor c 19 Cada bloco B já codificado numericamente foi então criptografado calculandose W Bᶜ mod n Sabendo que 02581031054302150698 é uma mensagem criptografada como acima obtenha a mensagem original Tabela de conversão de letrassímbolos para sequências decimais para os exercícios 6 7 e 8 A 00 I 08 Q 16 Y 24 B 01 J 09 R 17 Z 25 C 02 K 10 S 18 26 D 03 L 11 T 19 27 E 04 M 12 U 20 28 F 05 N 13 V 21 29 G 06 O 14 W 22 30 H 07 P 15 X 23 Espaço 31