Lista - Matemática Discreta - 2023-1

10 exercícios da apostila ‘Criptografia de S.C.Coutinho’ Exercício 38. Na encenação de uma batalha, duas tropas se enfrentam, posicionando-se, atirando com festim, e recarregando seus mosquetes, cada uma a sua vez. Cada lado começa com o mesmo número de cartuchos. Uma tropa tem 100 mosquetes e, depois de atirar tantos tiros de festim quanto possíveis, lhe sobram 13 cartuchos. A outra tropa tem 67 mosquetes, e ao fim da exibição, sobram-lhe 32 cartuchos. Supondo que a cada salva de tiros todos os soldados de cada lado atiraram exatamente uma vez, determine o número mínimo de cartuchos com que cada tropa iniciou a exibição. Exercício 42. Calcule o resto da divisão por 31 das potências 2⁶⁵⁵⁶⁴²³ e 2⁷⁹⁸⁷⁶⁶⁸. Exercício 43. Calcule o resto da divisão por 31 das potências 2¹⁵⁴⁹⁸⁷⁶⁶⁵⁴³³³⁵²³¹ e 6⁴³⁹⁸⁷⁶. Exercício 50. Calcule o resto da divisão de 3⁹⁸⁷⁴⁵ por 43 usando o Teorema de Fermat. Exercício 52. Calcule o resto da divisão de 31! por 307. Exercício 53. Calcule o resto da divisão de 1ᵖ⁻¹ + 2ᵖ⁻¹ + ⋯ + (p - 1)ᵖ⁻¹ por p, sabendo-se apenas que p > 2 é primo. Exercício 54. Calcule o resto da divisão de (a) 2⁴⁹⁵ por 15841; Exercício 57. Decodifique os demais blocos da mensagem 34 - 129 - 228 - 37 - 105 - 44 - 386 - 125, usando o procedimento acima. Lista de Exercícios Cálculo 3 Problema 1 Resposta Vamos observar quem é (n − 1)2 módulo n. Primeiro note que (n − 1)2 = n2 − 2n + 1 ≡ n2 + 1 mod n Claramente 2n ≡ 0 mod n, portanto temos a simplificação acima. Por outro lado, temos que n2 + 1 ≡ 1 mod n, pois n2 ≡ 0 mod n e assim fica claro que n − 1 é seu próprio inverso módulo n. Problema 2 Resposta 1. O inverso de 2 é 3k + 1, pois 2 · (3k + 1) = 6k + 2 ≡ (6k + 1) + 1 ≡ 1 mod 6k + 1 2. O inverso de 3 é 4k + 1, pois 3 · (4k + 1) = 12k + 3 ≡ 2(6k + 1) + 1 ≡ 1 mod 6k + 1 3. O inverso de 6 é 5k + 1, pois 6 · (5k + 1) = 5(6k + 1) + 1 ≡ 1 mod 6k + 1 Problema 3 Resposta Problema 4 Resposta Aqui vamos usar o teorema de Fermat: sendo p primo e p ∤ a, temos que a30 ≡ 1 mod 31. Assim: 26556426 = 230·218547+16 ≡ (230)218547 · 216 mod 31 Assim 216 ≡ (25)3 · 2 mod 31 ⇒ 216 ≡ (32)3 · 2 mod 31 ⇒ 216 ≡ 2 mod 31 Usando as mesmas propriedades 27987668 = (230)266255 · 218 ≡ 218 mod 31 1 27987668 ≡ 218 ≡ (25)3 · 23 mod 31 Assim temos 27987668 ≡ 8 mod 31. Problema 5 Resposta 1. Observe a aplicação de Fermat a relação 21445231 ≡ 230·q+20 ≡ (25)4 ≡ 1 mod 31 Precisamos observar que, pelo teorema de Euler, vale 1445231 ≡ (1429)1559 · 1420 mod 30 2. Observe a aplicação de Fermat a relação 215498766543335231 ≡ 230·q+15 ≡ (2)15 ≡ 1 mod 31 Precisamos observar que, pelo teorema de Euler, vale 15498766543335231 ≡ (1529)p · 1515 ≡ (152)7 · 15 ≡ 15 mod 30 3. Primeiro note que 26 ≡ 2 mod 31. Assim sendo temos que 239876 ≡ 230q+21 ≡ (25)4 · 2 ≡ 2 mod 31 temos que (329)340 · 316 ≡ 316 ≡ (35)3 · 3 mod 31 (329)340 · 316 ≡ 33 · 3 ≡ 21 mod 30 2