A Aldeia Numaboa ancestral ainda está disponível para visitação. É a versão mais antiga da Aldeia que eu não quis simplesmente descartar depois de mais de 10 milhões de pageviews. Como diz a Sirley, nossa cozinheira e filósofa de plantão: "Misericórdia, ai que dó!"

Se você tiver curiosidade, o endereço é numaboa.net.br.

Leia mais...

Aritmética modular

Seg

25

Jun

2007


22:00

(268 votos, média 4.15 de 5) 


Image

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:

a Image b (mod m)

Por exemplo:

20 Image 14 (mod 6)
-1 Image 9 (mod 5)
1100 Image 2 (mod 9)

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 Image 10 (mod 5), ou seja, 15/5=3 com resto 0 e 10/5=2 com resto 0. Do mesmo modo, 5 Image 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 Image 2 (mod 5) porque 5 divide (12-2).

Propriedades das congruências

Note que a Image 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 Image a (mod m)
  • A propriedade simétrica: Se a Image b (mod m), então b Image a (mod m)
  • A propriedade transitiva: Se a Image b (mod m) e b Image c (mod m), então a Image c (mod m)
Devido a estas três propriedades sabemos que o conjunto dos números inteiros é dividido em m diferentes classes de congruência módulo m.

Se a, b, c e d são inteiros quaisquer com a Image b (mod m) e c Image d (mod m), então

  • a + c Image b + d (mod m)
  • a - c Image b - d (mod m)
  • ac Image bd (mod m)
  • Se MDC(c,m) Image 1 e ac Image bc (mod m), então a Image 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

relógio

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.

mfx broker вывод средствсковородки тима официальный сайталександр лобановский супермаркет классcrm управлениегриль с крышкойtranslate videoхарьков никас

Informações adicionais