Provas Resolvidas - Coutinho

UNIVERSIDADE FEDERAL DO RIO DE JANEIRO\nDEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO-UFRJ\nNúmeros inteiros e criptografia\nS. C. Coutinho\nProvas e gabaritos\nAté a página 25 você encontrará as provas do curso de Álgebra para a informática- que era basicamente uma versão anterior do mesmo curso.\n\nLembre-se: Nas provas não são aceitas respostas sem justificativa. Você deve saber explicar tudo o que fizer. DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO-UFRJ\nProva 1: segundo semestre de 1995\n\nQuestão. Determine:\n(1) o máximo divisor comum de e e inteiros e tais que\n(2) um fator de pelo algoritmo de Fermat;\n(3) um fator primo de ;\n(4) as soluções de ;\n(5) o resto da divisão de por ;\n(6) uma sequência de inteiros consecutivos que sejam todos compostos.\n\nQuestão. Chamamos de hexagonis os números definidos pela fórmula para . O nome vem do fato de que estes números podem ser dispostos em hexágonos regulares concêntricos.\n(1) Calcule a soma dos primeiros números hexagonais quando = . Use estes dados numéricos para adivinhar a fórmula da soma dos primeiros números hexagonais.\n(2) Prove a fórmula obtida no item anterior usando o método de indução finita. DCC-UFRJ\nProva 2: segundo semestre de 1995\n\nQuestão. Determine:\n(1) Um fator primo de :\n(2) Dois inteiros positivos que sejam solução de \n\nQuestão. Verifique se :\n(1) um número de Carmichael;\n(2) um pseudoprimo forte para a base ;\n(3) um pseudoprimo para a base :\n\nQuestão. Três satélites passarão sobre o Rio esta noite. O primeiro passará à 1 hora da madrugada, o segundo às 4 horas e o terceiro às 8 horas da manhã. Cada satélite tem um período diferente. O primeiro leva 13 horas para completar uma volta em torno da Terra, o segundo leva 15 horas e o terceiro 19 horas. Determine quantas horas teria que se passar, a partir da meia-noite, até que os três satélites passem ao mesmo tempo sobre o Rio.\n\nQuestão. Seja um grupo finito provido de uma operação . Suponha que um primo divide a ordem de e considere o subconjunto de formado pelo elemento neutro e pelos elementos de ordem contidos em .\n(1) Mostre que se é abeliano então é um subgrupo de :\n(2) Determine quando :\n(3) Dê um exemplo de um grupo não abeliano para o qual não é um subgrupo de . DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO-UFRJ\nProva Final: segundo semestre de 1995\n\nQuestão. Determine:\n(1) O resto da divisão de por .\n(2) O menor inteiro positivo que deixa resto na divisão por , resto na divisão por e resto na divisão por .\n(3) As soluções da equação .\n(4) O inverso de módulo .\n(5) Todas as soluções da equação .\n(6) Se é um número de Carmichael.\n\nQuestão. O objetivo desta questão é mostrar que os grupos são sempre cíclicos.\n(1) Mostre que é um gerador de .\n(2) Prove por indução em que se é gerador de , então .\n(3) Mostre, usando (2), que é gerado por . DCC-UFRJ\nProva 1: primeiro semestre de 1996\n\n1. Determine:\n(1) Um múltiplo de e um múltiplo de cuja soma seja .\n(2) Um fator primo de .\n(3) Um fator de pelo método de Fermat.\n(4) todos os possíveis algarismos de modo que o número cuja representação na base é seja divisível por .\n(5) O resto da divisão de por .\n(6) O maior número possível de fatores primos de um inteiro que não tem nenhum fator .\n\n2. O objetivo desta questão é obter e provar uma fórmula para a soma dos cubos dos primeiros inteiros positivos. Seja, então,\n(1) Tableau os valores de para de e compare-os com os valores correspondentes para a soma dos primeiros inteiros positivos. Use isto para adivinhar qual deve ser a fórmula para .\n(2) Prove a fórmula obtida em (1) por indução fina. DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO-UFRJ\nProva 2: primeiro semestre de 1996\n\n1. Seja\n(1) Verifique se é um número de Carmichael.\n(2) Calcule o resto da divisão de por pelo teorema chinês do resto.\n(3) Determine se é um pseudoprimo forte para a base .\n\n2. Em seu primeiro contato com um planetas com que a Federação deseja estabelecer relações diplomáticas, os oficiais da Enterprise foram convidados para um banquete. Infelizmente há um grupo de dissidente no planeta que deseja apoiar os Klingons e não a Federação. Um espaço desta façao é instruído a enviar um dos oficiais da Enterprise. O traidor é descoberto, mas foge a tempo. Em seu alojamento é encontrada a mensagem codificada que contém o nome oficial escolhido e um pedaço de papel com os números e usados na codificação. Como trabalhando contra o tempo verificou que se tratava de um código primitivo, utilizando na terra no século XX, quando era conhecido por RSA. Que foi o oficial autorizado para ainda embaraçar a cúpula.\n\nLembretes: no RSA\nA correspondência entre letras e números é\nA B C D E F G H I J K L M\n10 11 12 13 14 15 16 17 18 19 20 21 22\nN O P Q R S T U V W X Y Z\n23 24 25 26 27 28 29 30 31 32 33 34 35\n\n3. Determine os subgrupos de ordem de . Indique quais são cíclicos e quais não são.\n\n4. Seja um número primo e Seja um fator primo de .\n(1) Calcule a ordem de em .\n(2) Mostre que tem que ser da forma onde é um inteiro.\n(3) Use a fórmula de (2) para achar todos os fatores primos de . DCC-UFRJ\nProva Final: primeiro semestre de 1996\n\n1. Determine:\n(1) se é número de Carmichael;\n(2) o resto da divisão de por ;\n(3) um fator primo de ;\n(4) um fator de pelo algoritmo de Fermat;\n(5) o máximo divisor comum entre e ;\n(6) duas soluções da equação\n\n2. Verifique se cada uma das afirmações abaixo é verdadeira ou falsa. Justifique cuidadosamente suas respostas.\n\n(1) Se é primo ímpar e satisfaz então é primo.\n(2) Existem inteiros e tais que\n(3) Se juntamos aos elementos de ordem de o elemento neutro temos um subgrupo de ;\n(4) Qualquer que seja inteiro, o número é divisível por DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO-UFRJ\nProva 1: segundo semestre de 1996\n\n1. Determine:\n(1) Inteiros que satisfaçam a equação\n(2) A maior potência de que divide onde é um número primo. De que maneira o resultado depende do primo ?\n(3) Um fator de pelo método de Fermat.\n(4) Infinitos inteiros positivos tais que é um número composto.\n(5) O resto da divisão de que é primo. Verifique que o resultado que você obteve se aplica a qualquer primo\n\n2. Considere o produto\n\nTabela os valores de para . Use estes valores para adivinhar uma fórmula simples para o produto. Prove que a sua fórmula é verdadeira para qualquer usando indução forte. DCC-UFRJ\nProva 2: segundo semestre de 1996\n\nQuestão. Determine:\n(1) se é um número de Carmichael;\n(2) o resto da divisão de por , usando o teorema chinês do resto;\n(3) se é um pseudoprimo forte para a base ;\n(4) duas soluções de ;\n(5) um fator primo de ;\n(6) a fatoração de , sabendo-se que tem apenas dois fatores primos distintos, cada um dos quais tem multiplicidade e que\n\n3. O objetivo desta questão é mostrar que e são primos ímpares distintos, então não é um grupo cíclico.\n(1) Mostre que se é um inteiro então\n(2) Mostre, usando (1), que se então\n(3) Qual a maior ordem possivel de um elemento de\n(4) Use (3) para mostrar que não pode ser cíclico. 10\nDEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO-UFRJ\nProva Final: segundo semestre de 1996\n\nQuestão. Determine:\n(1) múltiplos de e cuja soma seja\n(2) o resto da divisão de por\n(3) a solução geral do sistema\n\n(4) a maior potência de que divide onde é um inteiro positivo. Explique como a resposta vai depender de justificando cuidadosamente seu argumento.\n(5) um fator primo de \n(6) um fator de pelo método de Fermat.\n\nQuestão. Seja um número primo. Determine se cada uma das afirmações abaixo é verdadeira ou falsa, justificando cuidadosamente suas respostas.\n(1) é composto, então existe apenas um inteiro positivo tal que\n(2) Se tem ordem , então é um gerador de \n(3) O menor divisor primo de é maior que \n(4) Se e então é primo.