Aritmética modular
|
Seg 25 Jun 2007 22:00 |
- Detalhes
- Categoria: Matemática Numaboa
- Atualização: Domingo, 12 Abril 2009 23:14
- Autor: vovó Vicki
- Acessos: 37136
Uma das ferramentas mais importantes na teoria elementar dos números é a aritmética modular ou congruências. Congruência é a relação entre dois números inteiros que, divididos por um terceiro, chamado módulo de congruência, deixam o mesmo resto. Por exemplo, 20 é côngruo ou congruente de 14 com relação a 6 (20/6=3 restando 2 e 14/6=2 restando 2).
Suponha que a, b e m sejam números inteiros diferentes de zero. Dizemos que a é congruente de b módulo m se m dividir a-b. Escrevemos isto como:
b (mod m)Por exemplo:
20
e o quadrado de qualquer número ímpar é 1 modulo 8.
Encontramos congruências em todos os cantos. Por exemplo, os relógios trabalham com módulos 12 ou 24 para as horas e módulo 60 para os minutos e segundos. Calendários usam módulo 7 para os dias da semana e módulo 12 para os meses. A linguagem da congruência foi desenvolvida por Karl Friedrich Gauss no início do século XIX.
Entendendo a congruência
Como nos exemplos do relógio e dos meses do ano, o módulo representa o número de elementos que compõem cada grupo (ou subconjunto). Explico melhor: digamos que queremos formar 4 subconjuntos de 5 elementos a partir do conjunto dos 20 primeiros inteiros. Neste caso, o módulo é igual a 5 e podemos criar a seguinte tabela:
1º Subconjunto 0 1 2 3 4 2º Subconjunto 5 6 7 8 9 3º Subconjunto 10 11 12 13 14 4º Subconjunto 15 16 17 18 19
As linhas desta tabela correspondem aos subconjuntos obtidos. Agora observe as colunas: na primeira coluna da esquerda encontram-se os inteiros 0, 5, 10 e 15, todos CONGRUENTES no módulo 5. Experimente com qualquer dois deles: 15 10 (mod 5), ou seja, 15/5=3 com resto 0 e 10/5=2 com resto 0. Do mesmo modo, 5 10 (mod 5) porque, de acordo com a definição, 5 divide (5-10), etc.
Da mesma maneira, as outras quatro colunas também são compostas por números congruentes no módulo 5. Como último teste: 12 2 (mod 5) porque 5 divide (12-2).
Propriedades das congruências
Note que a b (mod m) se, e somente se houver um inteiro q de modo que a b + qm. Desta forma, as congruências podem ser transformadas em igualdades com a adição de uma incógnita.
As três propriedades mais importantes das congruências provavelmente são:
- A propriedade reflexiva: Se a é qualquer inteiro, a a (mod m)
- A propriedade simétrica: Se a b (mod m), então b a (mod m)
- A propriedade transitiva: Se a b (mod m) e b c (mod m), então a c (mod m)
Se a, b, c e d são inteiros quaisquer com a b (mod m) e c d (mod m), então
- a + c b + d (mod m)
- a - c b - d (mod m)
- ac bd (mod m)
- Se MDC(c,m) 1 e ac bc (mod m), então a b (mod m)
Aritmética finita ou modular
A aritmética finita é um tipo de aritmética na qual se opera com um conjunto limitado de números. Também é conhecida como aritmética circular porque, quando se chega ao último número, retorna-se ao primeiro.
Exemplo: considere o relógio. As horas sucedem-se de 1 a 12 e, após 12 horas, recomeçando o ciclo, voltamos para 1 hora.
A aritmética finita módulo m faz uso de todos os números que constituem o conjunto dos restos de uma divisão por m: 0, 1, 2...m-1. Por exemplo, a aritmética finita (ou circular) módulo 12 opera sobre o conjunto numérico constituído pelas cifras 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 e 11.
A regra de cálculo é muito simples. A soma algébrica e o produto são anotados como na aritmética "normal", como 7+8 ou 5×6, e o resultado é expresso pela divisão por m. Mantendo o exemplo do módulo 12, 7+8=3 (porque 7+8=15 e 15÷12=1 com resto 3) e 5x6=6 (porque 5x6=30 e 30÷12=2 com resto 6).
Aritmética modular na criptografia
Voltemos novamente ao exemplo do relógio. Como contamos o tempo de 12 em 12 horas, o conjunto de cifras para expressar as horas são 12 (vão de 0 a 11). Se o conjunto de cifras disponíveis no mostrador é limitado, sabemos imediatamente que estamos lidando com a aritmética modular e que o relógio trabalha com módulo 12.
Ver as horas no mostrador é um procedimento imediato: mostrador no 3 indica que são 3 horas; mostrador no 8 indica que são 8 horas. Mas quando o mostrador chega nas 11 horas, a próxima hora será 0. Que conta é esta? Somamos 11 + 1. Agora apliquemos o módulo 12: 11 + 1 = 12 e 12 ÷ 12 = 1 com resto 0. Da mesma forma, 11 + 5 = 16 e 16 ÷ 12 = 1 com resto 4. Ou seja, sempre que o resultado da soma ultrapassar o maior valor do conjunto (maior que 11), aplicamos o módulo 12. Por exemplo, 5 + 3 = 8 não precisa de ajuste.
Sabemos também que uma divisão nada mais é do que uma sucessão de subtrações. Veja o exemplo: 36 ÷ 12 = 3 com resto 0 ou 36 - 12 = 24, 24 - 12 = 12 e 12 - 12 = 0. Fizemos três subtrações até obtermos um número menor do que 12, ou seja, o resto. Parece bobagem, mas é muito importante - e principalmente muito prático.
Nos exemplos acima sempre somamos horas. Se, por exemplo, quisermos subtrair 15 de 3 horas, teríamos o seguinte cálculo: 3 - 15 = -12. Novamente caímos fora do conjunto de 0 a 11, portanto, precisamos aplicar um ajuste: -12 ÷ 12 = -1 com resto 0. Agora considere subtrair 17 de 3 horas, ou seja, 3 - 17 = -14 e -14 ÷ 12 = -1 com resto -2, o que nos deixa novamente fora do conjunto de 0 a 11. É neste ponto que é importante entender o complemento de 12 (porque estamos trabalhando com módulo 12). Observe:
Conjunto das cifras 0 1 2 3 4 5 6 7 8 9 10 11 Complemento 12 11 10 9 8 7 6 5 4 3 2 1 Módulo 12 12 12 12 12 12 12 12 12 12 12 12 12
Analisando a tabela dos complementos verificamos que o complemento de 0 é 12, de 1 é 11 e assim sucessivamente. Ao mesmo tempo podemos notar que, subtraindo o complemento do módulo 12, obtemos a cifra do conjunto correspondente, ou seja: 12 - 12 = 0, 12 - 11 = 1, etc, ou seja, o processo é reversível. Se quisermos encontrar a cifra correspondente a -2 no módulo 12, basta calcular 12 - 2 = 10. Ficou mais fácil?
Considerando que o número de caracteres disponíveis para se escrever (e cifrar) uma mensagem seja finito, já entramos na seara da aritmética modular. O alfabeto latino completo possui 26 letras, portanto, vamos trabalhar com módulo 26. Numerando as letras de 0 a 25, qualquer cálculo que se queira efetuar segue as mesmas regras explicadas para o relógio. Imagine que você queira "subtrair" F de J: J corresponde a 9 e F a 5, então J - F = 9 - 5 = 4 que corresponde a E.
Da mesma forma, T + 10 será 19 + 10 = 29 e 29 ÷ 26 = 1 com resto 3, que corresponde ao D. Ou então T + 38 = 57 e 57 - 26 = 31 - 26 = 5, que corresponde ao F. C - 10 será 2 - 10 = -8 e a letra correspondente será 26 - 8 = 18 (pelo complemento) que é o S.
Aritmética modular na música
É isto mesmo, não se espante. Como a música é aritmética pura, é claro que os princípios da aritmética se aplicam a ela... e a aritmética modular tem um efeito muito melodioso. Difícil de acreditar? Então dê uma verificada num site espetacular que achei na web e que explica tudo sobre música. Está em espanhol e chama-se Musica y Matemáticas. A aritmética modular você encontra em Simetría y Música. Aritmética Modular.