Re: [obm-l] Congruência, módulo m

["Ronaldo Alonso" <ronaldo.luiz.alonso@xxxxxxxxx>]

   Vou dar uma explicação básica, embora os problemas envolvendo congruencia possam ser bem complexos.

 

   Dois números inteiros são congruentes modulo m se apresentam

o mesmo resto da divisão por m

   Em programação de computadores,  temos o operador mod, que

calcula o resto da divisão de dois inteiros:

 

  6 mod 2 = 0  (resto da divisão é zero)

  7 mod 2 = 1 (resto da divisão é um).

 

   O símbolo de congruencia é representado por 3 traços.  Não tenho um caracter aqui em meu teclado para

esse símbolo, portanto vou usar o símbolo ~

   Assim exemplificando:

 

    4 mod 2 = 0

    6 mod 2 = 0 

 

 isso significa que 6 e 4 são congruentes modulo 2 e escrevemos:

 

   6 ~ 4 mod 2 

 

   Note que eu escolhi o símbolo de equivalência, porque a congruencia modulo m é uma relação de equivalência.

Ela é reflexiva, simétrica e transitiva (mais explicações sobre isso eu posso dar depois).

  

   No caso de conguencia modulo 2 temos dois casos (classes de equivalência):  Os números que

são congruentes módulo 2 (os números

pares, cujo resto da divisão é zero) e os que não

são congruentes módulo 2 (os ímpares).   No caso de módulo 3 teríamos 3 classes de

equivalência, os números cujo resto da divisão é zero, cujo resto é um e cujo resto é 2.

     Certo.  

     Agora note que essas classes tem elementos disjuntos  (números pares,

por exemplo não são impares, etc).  Quando isso acontece, dizemos que o conjunto,

no caso os inteiros, foi PARTICIONADO.   

    Isso não acontece só no caso da congruência módulo m, mas de qualquer relação

de equivalência.  Essa relação induz uma divisão ou partição no conjunto.  O quociente

desta divisão, no caso da congruência modulo 2, são os números pares e os números

impares.

    Podemos escrever algo sugestivo como :  Z / ~ (mod 2)  =  (pares) + (ímpares)

 

Ok agora é só generalizar para mod m. 

       Os pares por exemplo, podemos chamar de [0] e os ímpares de [1]

 

  Podemos inclusive definir operações com as classes de equivalência:   A soma de um

par com um ímpar é sempre um ímpar: [0] + [1] = [1].

 

      [0] + [0] = [0]

      [0] + [1] = [1]

      [1] + [0] = [1]

      [1] + [1] = [0]

 

    A operação é associativa, comutativa, possui elemento neutro, é fechada e

possui elemento inverso e portanto  forma um grupo abeliano.

   Bem. Vou ficando por aqui.  Qualquer dúvida pergunte!

 

Abraço!

 

Ronaldo Luiz Alonso

  

 

 

 

 

      

 

 

 

 

On 3/23/07, Bruna Carvalho <bruna.carvalho.pink@gmail.com> wrote:

Alguém poderia me ajudar em como usar, para que serve a tal de congruência mod m, alguns exemplos de apliacação.

--
Bjos,
Bruna

--
Ronaldo Luiz Alonso
------------------------------------------

Analista de Desenvolvimento

CREA-SP