ARITMÉTICA_E_TEORIA_DOS_NÚMEROS_-_TUTOR_-_U3 1

Prévia do material em texto

Disciplina:
Aritmética e Teoria dos Números
Docente:
Luiz Carlos Pitzer
Unidade 3: Congruência
Esta unidade está dividida em quatro tópicos:
 Tópico 1 – Congruências
 Tópico 2 – Aplicação de congruência
 Tópico 3 – Congruências lineares e classes residuais
 Tópico 4 – Noções de criptografia RSA
Unidade 3: Congruência
OBJETIVOS DA APRENDIZAGEM
A partir do estudo desta unidade, você deverá ser capaz de:
conhecer as propriedades e as estrutura de congruências;
reconhecer como a congruência pode ser aplicada na resolução de problemas;
desenvolver a capacidade para demonstração de propriedades e problemas com divisibilidade;
aplicar métodos de resolução em problemas com sistemas de congruência;
compreender o sistema de criptografia ao longo da história.
Unidade 3: Congruência
 Tópico 1 – Congruência
Neste tópico, apresentaremos uma das noções mais importantes na aritmética, introduzida pelo matemático alemão Johann Carl Friedrich Gauss (1777-1855). 
Trata-se da construção de uma aritmética desenvolvida a partir dos restos da divisão euclidiana, publicada no ano 1801, por Gauss, no seu livro Disquisitiones Arithmeticae.
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Definição: seja um número natural diferente de zero. Diremos que dois números inteiros e são congruentes módulo se os restos de sua divisão euclidiana por são iguais. Quando os inteiros e são congruentes módulo , denota-se: 
https://www.youtube.com/watch?v=qYqusyUOtF0
Antes de apresentarmos alguns exemplos, perceba que essa definição é bem intuitiva. Bastam ter dois números e que deixam o mesmo resto, quando divididos por um certo número .
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Exemplo: 
, pois os restos da divisão de 15 e de 7 por 2 são iguais a 1.
, pois os restos da divisão de 10 e de 24 por 7 são iguais a 3.
, pois os restos da divisão de 17 e de -1 por 6 são iguais a 5.
, pois os restos da divisão de -6 e de 14 por 5 são iguais a 4.
SE EU DIVIDO POR 2, OS RESTOS DE 15/2 E 7/2 SÃO IGUAIS, NESTE CASO IGUAL A 1;
SE EU DIVIDIR POR 7 O 10 E O 24, O RESTO É O MESMO;
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Quando a congruência não for atendida, diremos que e não são congruentes ou que são incongruentes, módulo . 
A notação feita para este caso é .
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Apresentaremos algumas propriedades que decorrem imediatamente da definição.
Proposição: seja um inteiro positivo fixo () e sejam , e inteiros quaisquer. Valem as propriedades:
 (Reflexiva);
Se , então (Simétrica);
Se e se , então (Transitiva).
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Proposição: suponha que, com . Tem-se que se, e somente se, .
Exemplo: verifique se vale a congruência .
Resolução: perceba que a congruência é válida se , ou seja, se , o que é verdade. Portanto, a congruência é válida.
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Propriedade: seja um inteiro positivo fixo e sejam inteiros quaisquer. Se e se , então . 
Exemplo: sejam as congruências e . Então, pela propriedade anterior, vale a relação entre as congruências, da seguinte forma:
O que é verdade, pois ambos deixam 1 como resto, ou, ainda, porque, conforme provado anteriormente, .
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Propriedade: seja um inteiro positivo fixo e sejam inteiros quaisquer. Se e se , então . 
Exemplo: sejam as congruências e . Então pela propriedade anterior, vale a relação entre as congruências, da seguinte forma 
O que é verdade, pois, ambos deixam 2 como resto, ou, ainda, porque, .
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Propriedade: seja um inteiro positivo fixo e sejam inteiros quaisquer. Se
Exemplo: usando da propriedade anterior podemos escrever a congruência como 
Note que o , logo, podemos cancelar o 2 nas multiplicações e dividir o valor do módulo também, obtendo 
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Propriedade: seja um inteiro positivo fixo e sejam inteiros quaisquer. ;
Exemplo: usando da propriedade anterior, a congruência pode ser multiplicada por 2 e apresentar a seguinte configuração:
 
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Propriedade: seja um inteiro positivo fixo e sejam inteiros quaisquer. Se então para todo .
https://www.youtube.com/watch?v=TrXZyg5Rr-Y
Exemplo: ache o resto da divisão de por 127.
Resolução: como , então 
Usando da proposição anterior, podemos elevar os dois lados a 7, obtendo 
Como , logo,
Portanto, é 126 o resto desta divisão.
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Propriedade: sejam . Se são inteiros maiores que 1, temos que 
Exemplo: encontre o menor múltiplo de 5, que deixa resto 1 quando dividido por 2, 3 e 4.
Unidade 3: Congruência
 Tópico 1 – Congruência
ARITMÉTICA DOS RESTOS
Resolução: o problema pode ser descrito pelas congruências
,
.
Usando da propriedade anterior, e como , o problema torna-se Entretanto, resolver está congruência é equivalente a resolver uma Equação Diofantina, dada por
Cuja solução você já sabe como chegar!
Unidade 3: Congruência
 Tópico 2 – Aplicação de Congruência
PROVA DOS NOVE
A “prova dos nove” ou “noves fora” é um método para identificar erros em cálculos manuais, envolvendo qualquer uma das quatro operações básicas.
Para isso, devemos comparar os restos na divisão por 9.
Como exemplo, suponhamos que efetuamos a adição de 131 com 79 cujo resultado é 210.
A verificação acontece da seguinte forma:
Somando os restos, no resto da divisão por 9.
Como , o mesmo resultado, a prova dos 
nove foi verificada.
Unidade 3: Congruência
 Tópico 2 – Aplicação de Congruência
PROVA DOS NOVE
É importante relembrar que a regra dos noves fora não indica que resolução está correta, pois, um conjunto de erros pode não ser detectado. 
Por outro lado, caso a regra não seja satisfeita, a resolução estará incorreta. 
Esse método não serve apenas para adição e multiplicação, mais para as quatro operações básicas, como já comentado.
Unidade 3: Congruência
 Tópico 2 – Aplicação de Congruência
PEQUENO TEOREMA DE FERMAT
Teorema (Pequeno Teorema de Fermat): dado um número primo , então Além disso, se , então 
Exemplo: determine o resto da divisão de por 11.
Resolução: pelo PTF, podemos escrever que
Portanto, o resto da divisão de por 11 é 4.
Unidade 3: Congruência
 Tópico 2 – Aplicação de Congruência
TEOREMA DE EULER
Antes de anunciarmos o Teorema de Euler, necessitamos de alguns conhecimentos prévios.
Um sistema completo de resíduos é um conjunto que apresenta por meio de números, todos os possíveis restos da divisão por um certo número. Exemplo para o 4: 
 ou . 
Perceba que ambos possuem todas as possibilidades de restos.
Enquanto 0, 1 é um sistema reduzido de resíduos módulo 4.
Unidade 3: Congruência
 Tópico 2 – Aplicação de Congruência
TEOREMA DE EULER
Proposição: sejam tais que . 
Então 
Lema: se é um número primo e , um número natural, então se tem que
Unidade 3: Congruência
 Tópico 2 – Aplicação de Congruência
TEOREMA DE EULER
Exemplo: encontre a quantidade de elementos do conjunto reduzido de resíduos para 81
Resolução: encontrar a quantidade de elementos no conjunto reduzido de resíduos é exatamente encontrar o valor para . Portanto, pelo lema anterior e sabendo que , segue
 
Unidade 3: Congruência
 Tópico 2 – Aplicação de Congruência
TEOREMA DE EULER
Teorema: seja e seja a decomposição de em fatores primos. Então:
ou pode ser reescrita como:
Unidade 3: Congruência
 Tópico 2 – Aplicação de Congruência
TEOREMA DE EULER
Exemplo: encontre o 
Resolução: usando do último teorema e sabendo que , temos:
 
Unidade 3: Congruência
 Tópico 2 – Aplicação de CongruênciaTEOREMA DE EULER
Teorema (Euler): sejam com e . Então, 
Exercício: encontre o resto da divisão de por .
Resolução: como o podemos usando o teorema de Euler para escrever 
Vamos, então, determinar o , obtendo 
Unidade 3: Congruência
 Tópico 2 – Aplicação de Congruência
TEOREMA DE EULER
Resolução:
Com isso, podemos escrever a congruência como sendo 
Perceba também que , então, podemos proceder com a congruência anterior da seguinte forma:
Portanto, resto da divisão de por 21 é 16.
Unidade 3: Congruência
 Tópico 2 – Aplicação de Congruência
TEOREMA DE WILSON
Teorema de Wilson: se é um número primo, então 
Exemplo: mostre que a divisão de por deixa resto ?.
Resolução: pelo Teorema de Wilson, sabemos que 
Usando a definição de fatorial, obtemos 
Note que então, trocando no resultado anterior 
 
Como o , podemos dividir ambos os lados por 18, obtendo 
Portanto, o resto da divisão de por é 1.
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
CONGRUÊNCIAS LINEARES
https://www.youtube.com/watch?v=e6uvdgYuiW4&list=PLvLkxtdUefNw0FNEpcb2OhkTkPEIsml1o&index=11
Neste ponto de nossas análises, iremos, inicialmente, dedicar para a resolução de equações do tipo: , em que 
Proposição: dados , a congruência: admite solução, se e somente se, 
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
CONGRUÊNCIAS LINEARES
Exemplo: resolva a congruência linear .
Resolução: como , temos que a congruência possui 4 soluções. Sabendo que Isolando , temos:
 
 
logo, .
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
CONGRUÊNCIAS LINEARES
Corolário: se , temos que a congruência , possui uma única solução módulo .
Exemplo: resolver a congruência .
Resolução: como , temos que a congruência possui apenas 1 solução. Sabendo que 13 Isolando , temos:
logo, a solução única é para , e, consequentemente, .
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
TEOREMA CHINÊS DOS RESTOS
No primeiro século da nossa era, o matemático chinês Sun-Tsu propôs o seguinte problema:
Qual é o número que deixa restos 2, 3 e 2 quando dividido, respectivamente, por 3, 5 e 7?
A resposta dada por Sun-Tsu para este problema foi 23.
Traduzido em linguagem matemática, o problema de Sun-Tsu equivale a procurar as soluções do seguinte sistema de congruências:
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
TEOREMA CHINÊS DOS RESTOS
https://www.youtube.com/watch?v=JGW7JHEgrXw
Teorema (chinês dos restos): dado o sistema de congruências: 
Em que , para todo , possuirá uma única solução módulo . Essa solução pode ser obtida com: 
 onde, 
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
TEOREMA CHINÊS DOS RESTOS
Exemplo: Digamos que o general chinês tivesse 2000 soldados em um front de guerra. Após a batalha, o general, para contabilizar as perdas, ordenou que os soldados realizassem a formação de 7 em 7 soldados, sobrando 5 soldados. Em seguida, ordenou que as filas fossem de 9 em 9 soldados, sobrando 4, e, por fim, filas de 10 em 10, sobrando 5 soldados. Deste modo, qual a quantidade de soldados (ainda vivos), que satisfazem estas condições?
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
TEOREMA CHINÊS DOS RESTOS
Resolução: para o caso, teremos:
Desta forma, montamos as seguintes congruências:
que possuem, respectivamente, . Dessa forma, uma solução módulo 630 é dada por: 
.
Sendo assim, o general chinês ainda dispunha de 14845 soldados. 
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
ARITMÉTICA DAS CLASSES RESIDUAIS
Definição: o conjunto é chamado de classe residual de módulo do elemento , em . O conjunto de todas as classes residuais de módulo será representado por . 
Exemplo: para temos:
Isso quer dizer que:
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
ARITMÉTICA DAS CLASSES RESIDUAIS
Definiremos, agora, em as seguintes operações:
 
Adição: 
Multiplicação: 
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
ARITMÉTICA DAS CLASSES RESIDUAIS
Propriedades da adição
 
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
ARITMÉTICA DAS CLASSES RESIDUAIS
Propriedades da multiplicação
 
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
ARITMÉTICA DAS CLASSES RESIDUAIS
Conhecidas essas propriedades, dizemos que um conjunto que é munido das operações de adição e multiplicação (e suas respectivas propriedades), será chamado de anel. 
Desse modo, é um anel, chamado de anel das classes residuais de módulo .
Como consequência disso, um elemento , é dito invertível, quando existir , onde: , diremos, assim, que são inversos.
Unidade 3: Congruência
 Tópico 3 – Congruência Lineares e Classes Residuais
ARITMÉTICA DAS CLASSES RESIDUAIS
Exemplo: Construa as tabelas de adição e multiplicação em 
Unidade 3: Congruência
 Tópico 4 – Noções de Criptografia
INTRODUÇÃO
Este tópico é dedicado para apresentar uma das principais aplicações da aritmética das congruências, a criptografia. 
Basicamente, todos os sistemas cibernéticos de acessos e de segurança de dados, recorrem a algum dispositivo de criptografia para que estes dados não possam ser acessados (ou decifrados) por qualquer pessoa sem a devida permissão (chave de acesso).
Em especial, dedicaremos a compreender a criptografia RSA, que possui esse nome pois foi criada por três matemáticos computacionais, Ron Rivest, Adi Shamir e Leonard Adleman. 
Note que RSA é justamente as iniciais de cada sobrenome.
Unidade 3: Congruência
 Tópico 4 – Noções de Criptografia
CRIPTOGRAFIA RSA
O passo a passo para o método segue a seguir:
1. Tomam-se, a escolher, dois primos , distintos.
2. Calcula-se um valor 
3. Escolhe-se um valor , que fará parte da chave pública, que deverá seguir a regra em que , com 
4. Resolve-se a congruência em que se encontra , que será a chave privada.
Unidade 3: Congruência
 Tópico 4 – Noções de Criptografia
CRIPTOGRAFIA RSA
5. Utilizando uma tabela (pré-formulada), e de domínio público, é feita a transição de todos os caracteres da mensagem em números, em que se obtém uma mensagem numérica. Esses números devem ser colocados em blocos , em que . Esse processo garante a unicidade do resultado.
6. Tendo a Chave Pública o próximo passo é criptografar os blocos com a congruência: , onde é a mensagem criptografada.
7. Para descriptografar, basta ter a posse da Chave Privada realizando o processo de acordo com a congruência: em que é a mensagem descriptografada, 
8. Por fim, cada bloco tem que ser colocado em sequência, e utilizando a mesma tabela citada no item 5 os números conseguem ser transformados novamente em caracteres.
Unidade 3: Congruência
 Tópico 4 – Noções de Criptografia
CRIPTOGRAFIA RSA
Como o exemplo é complexo, deixaremos para que você possa acompanhar o realizado no livro.
Bons estudos!
“