quarta-feira, 13 de junho de 2012

048-Fundamentos de Congruência Modular



Este post tem como objetivo as demonstrações das principais propriedades das operações da aritmética modular.
  
Sejam [;a;] , [;b;] [;\in \mathbb{Z};] e [;m \neq 0;] [;\in \mathbb{N};] . [;a;] é congruente a [;b;] módulo [;m;] quando [;a;] e [;b;] deixam o mesmo resto quando divididos por [;m;]. Simbolicamente,

[;a \equiv b;] ([;mod;] [;m;]

Congruência módulo [;m;] é uma relação de equivalência onde valem as propriedades reflexiva, simétrica e transitiva:

[;<;]Propriedade Reflexiva [;>;] 

[;a \equi a;] ([;mod;] [;m;]


[;<;]Propriedade Simétrica [;>;]

Se [;a \equiv b;] ([;mod;] [;m;] ), então [;b \equiv a;] ([;mod;] [;m;]


[;<;]Propriedade Transitiva [;>;] 

Se [;a \equiv b;] ([;mod;] [;m;] ) e [;b \equiv c;] ([;mod;] [;m;] ), então [;a \equiv c;] ([;mod;] [;m;] )

[;\rightarrow;] Estas propriedades não são demonstradas por serem intuitivas.

_*_

A seguir, as Propriedades Operativas Básicas e suas respectivas demonstrações.

Notação: * dados [;u;] e [;v;] [;\in \mathbb{Z};], com [;u \neq 0;], [;u|v;] significa "[;u;]" divide "[;v;]" ( resto [;0;] );
               * dados [;u;] e [;v;] [;\in \mathbb{Z};], [;(u,v)=;]máximo divisor comum de [;u;] e [;v;]

Nas provas, todas as variáveis envolvidas [;\in \mathbb{Z};] com exceção do módulo [;m \neq 0;] que [;\in \mathbb{N};].

_*_ 


[;1;])

           Se [;a \equiv b;] ([;mod;] [;m;] ), 

 então [;a-b \equiv 0;]([;mod;] [;m;]


Demonstração: como [;a/m;] e [;b/m;] deixam o mesmo resto, temos

[;a=qm+r;],

[;b=q^'m+r;] 
 e
 [;a-b=(qm+r)-(q^'m+r) \Rightarrow a-b=(q-q^')m;]

logo, [;m|(a-b);] e já que [;m|0;] para todo [;m;] não-nulo, temos por definição, que  [;a-b \equiv 0;]([;mod;] [;m;] ), pois [;a-b;] e [;0;] deixam o mesmo resto ([;r^'=0;]), na divisão por [;m;]. Assim, as seguintes expressões são equivalentes:

[;a \equiv b;] ([;mod;] [;m;] ) [;\Longleftrightarrow;][;m|(a-b);] [;\Longleftrightarrow;] [;a-b \equiv 0;]([;mod;] [;m;] )

[; 1.1;] ) De modo geral, se [;m|n;] então [;n \equiv 0;] ([;mod;] [;m;] ) porque [;m|(n-0);].


[;2;] )

 Se [;a \equiv b;] ([;mod;] [;m;] ) e 

               [;c \equiv d;] ( [;mod;] [;m;] ), então 

        [;a \pm c \equiv b \pm d;] ( [;mod;] [;m;]
 

Obs: o sinal [;\pm;] em ambos os membros significa, neste caso, que ou usa-se o sinal [;+;] nos dois membros ou usa-se o sinal [;-;] nos dois membros ( nunca alternados ).

 Demonstração: Por hipótese,

[;a=q_1m+r;]  e  [;b=q_2m+r;] 
[;c=q_3m+r^';]  e  [;d=q_4m+r^';]

com [;0 \leq r < m;] e [;0 \leq r^' < m;]

Assim,

[;a \pm c= (q_1\pm q_3)m + r \pm r^';]e [;b \pm d= (q_2\pm q_4)m + r \pm r^';]

Como nos dois casos [;r \pm r^' = qm+r^'';] para [;0 \leq r^'' < m;], segue que [;(a \pm c)/m;] e [;(b \pm d)/m;] deixam o mesmo resto [;r^'';] , logo [;a \pm c \equi c \pm d;] ([;mod;] [;m;] ).


[;3;])

 Se [;a \equiv b;] ([;mod;] [;m;] ) e 

               [;c \equiv d;] ( [;mod;] [;m;] ), então 

      [;ac \equiv bd;]  ( [;mod;] [;m;] )  


Demonstração: Por hipótese,

[;a=q_1m+r;]  e  [;b=q_2m+r;] 
[;c=q_3m+r^';]  e  [;d=q_4m+r^';]


com [;0 \leq r < m;] e [;0 \leq r^' < m;]

Assim,

[;ac=q_1q_3m^2+q_1r^'m+q_3rm+rr^';][;bd=q_2q_4m^2+q_2r^'m+q_4rm+rr^';]

ou

[;ac=(q_1q_3m+q_1r^'+q_3r)m+rr^';][;bd=(q_2q_4m+q_2r^'+q_4r)m+rr^';]


Como nos dois produtos [;rr^' = qm+r^'';] para [;0 \leq r^'' < m;], segue que [;(ac)/m;] e [;(bd)/m;] deixam o mesmo resto [;r^'';], logo [;ac \equiv bd;] ([;mod;] [;m;] ).


[;4;] )

 Se [;a \equiv b;] ([;mod;] [;m;] ), então

[;as \equiv bs;] ([;mod;] [;m;] )

para todo [;s \in \mathbb{Z};]  


Demonstração: este resultado é decorrente da propriedade reflexiva e da propriedade [;3;].

[;s \equiv s;] ([;mod;] [;m;])

[;a \equi b;] ([;mod;] [;m;])

e pela prop [;3;], temos

[;as \equiv bs;]  ([;mod;] [;m;])

Obs: a recíproca não é de toda verdadeira pois a propriedade do cancelamento é válida apenas se [;(s,m)=1;] , ou seja, se [;s;] e [;m;] forem primos entre si, como será demonstrado a seguir. 


[;5;] )

Dado [;s \in \mathbb{Z};], onde [;(s,m)=1;] e se

          [;as \equiv bs;] ([;mod;] [;m;]), então

[;a \equi b;] ([;mod;] [;m;]


Demonstração: por hipótese, [;as \equiv bs;] ([;mod;] [;m;] ) e pela prop [;1;], temos que

[;m|(as-bs) \Rightarrow;] 

[;m|[s.(a-b)];] 

Como [;(s,m)=1;], logo [;m|(a-b);] e portanto, [;a \equi b;] ([;mod;] [;m;])


[;6;] )

Se 

      [;ax \equiv b;]  ([;mod;] [;m;]),

         [;a \equiv a^';] ([;mod;] [;m;]

 e 

         [;b \equiv b^';] ([;mod;] [;m;] ), 


 então 

       [;a^'x \equiv b^';]  ([;mod;] [;m;]
 

Demonstração: resultado da propridade transitiva e prop [;4;]:  

[;I;]) [;ax \equiv b;] ([;mod;] [;m;]) [;b \equiv b^';] ([;mod;] [;m;]) [;\Rightarrow;] [;ax \equiv b^';] ([;mod;] [;m;]);

[;II;]) [;a \equiv a^';] ([;mod;] [;m;]) [;\Rightarrow;] [;ax \equiv a^'x;] ([;mod;] [;m;]);

E, novamente, pela propriedade transitiva:

[;III;] ) [;ax \equiv a^'x;] ([;mod;] [;m;]) e  [;ax \equiv b^';] ([;mod;] [;m;]) [;\Rightarrow;] [;a^'x \equiv b^';] ([;mod;] [;m;])

Obs: Este último resultado é interessante para simplificar uma equação de congruência como, por exemplo,

[;37x \equiv 58;]  ([;mod;] [;6;] )

Temos, então, que [;37 \equiv 1;] ([;mod;] [;6;] ) e [;58 \equiv 4;] ([;mod;] [;6;] ), assim, 

[;37x \equiv 58;]  ([;mod;] [;6;] ) [;\Rightarrow;] [;x \equiv 4;] ([;mod;] [;6;] )

Logo, todas as soluções da equação original são da forma [;x=6k+4;], com [;k \in \mathbb{Z};].



Referência Bibliográfica 

Teoria dos Números, de Salahoddim Shokranian, Marcus Soares e Hemar Godinho; Editora UNB, 1999.
O que é a Matemática?, de Richard Courant e Herbert Robbins, Editora Ciência Moderna, 2000.


Imagem ( fundo ): http://www.lacosdeminas.com.br/




2 comentários:

  1. Olá, Aloísio!!!!
    Passando por aqui, para conferir essa boa postagem sobre operações modulares!!!!Parabéns, está de ótima qualidade em todos os aspectos!!!

    Você não pensa em fazer um curso superior em matemática??? Rapaz, acredito que não teria a menor dificuldade, meu amigo!!!!

    Aproveitando o momento, lhe aviso que já troquei o seu antigo banner que parecia uma arara vermelha, KKKKKKKK, por esse mais moderno e ecologicamente correto!!!! KKKKKKKKK!!!!!!
    Aloísio???? Vai mesmo fazer a postagem sobre o "pulo do cavalo" de Euller, no jogo do xadrez??? ? Seria um ótimo posto, imagino!!!!!

    Um abraço!!!!!

    ResponderExcluir
  2. Oi, Valdir!

    Obrigado pelos elogios. Verifiquei, na net, que há uma certa carência deste assunto que seja mais acessível a quem tem apenas o ensino médio. Resolvi, então, investir neste aspecto. A matemática que publico no blog não visa provas e nem concursos e destina-se aos amantes da matemática que desejam aprofundar-se descompromissamente nesta arte,que, assim como eu, estudam por prazer.

    Penso em cursar Bacharelado, Mestrado, Doutorado em matemática quando me aposentar ( e falta pouco ) apenas para passar o tempo e não atrofiar a mente. Não penso em dar aulas. Talvez publique um livro ou dois.

    Arara vermelhar?? kkkkkkkkkkkkkkkkk. De fato era mesmo ( e ninguém me dava o toque do ridículo rs ). E agora está ecologicamente correto? Então está bom! kkk. Ora, mas se antes parecia uma arara vermelha também era ecologicamente correto, kkkkkkkk

    Valdir, o material sobre o pulo do cavalo de Euler é escasso, mas vou ver se consigo reunir material necessário.

    Sou muito cauteloso em decidir falar de xadrez em Elementos porque como também gosto muito deste esporte, se começar não paro mais..rsrs. Em xadrez me agrada mais a História dos Campeonatos Mundiais, também sobre a biografia de grandes jogadores como Capablanca, Tal, Fischer, etc.

    Valeu, meu nobre colega blogueiro, um grande abraço!

    ResponderExcluir