Este post tem como objetivo as demonstrações das principais propriedades das operações da aritmética modular.
Sejam , e . é congruente a módulo quando e deixam o mesmo resto quando divididos por . Simbolicamente,
Demonstração: por hipótese, ( ) e pela prop , temos que
Como , logo e portanto, ( )
Sejam , e . é congruente a módulo quando e deixam o mesmo resto quando divididos por . Simbolicamente,
( )
Congruência módulo é uma relação de equivalência onde valem as propriedades reflexiva, simétrica e transitiva:
Propriedade Reflexiva
( )
Propriedade Simétrica
Se ( ), então ( )
Propriedade Transitiva
Se ( ) e ( ), então ( )
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 e , com , significa "" divide "" ( resto );
* dados e , máximo divisor comum de e .
Nas provas, todas as variáveis envolvidas com exceção do módulo que .
Notação: * dados e , com , significa "" divide "" ( resto );
* dados e , máximo divisor comum de e .
Nas provas, todas as variáveis envolvidas com exceção do módulo que .
_*_
)
Se ( ),
então ( )
Demonstração: como e deixam o mesmo resto, temos
,
e
logo, e já que para todo não-nulo, temos por definição, que ( ), pois e deixam o mesmo resto (), na divisão por . Assim, as seguintes expressões são equivalentes:
( ) ( )
) De modo geral, se então ( ) porque .
)
Se ( ) e
( ), então
( )
Obs: o sinal 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,
e
e
com e
com e
Assim,
e
Como nos dois casos para , segue que e deixam o mesmo resto , logo ( ).
)
Se ( ) e
( ), então
( )
Demonstração: Por hipótese,
e
e
com e
com e
Assim,
e
ou
e
ou
e
Como nos dois produtos para , segue que e deixam o mesmo resto , logo ( ).
)
Se ( ), então
( )
para todo
Demonstração: este resultado é decorrente da propriedade reflexiva e da propriedade .
( )
( )
e pela prop , temos
( )
)
( )
e pela prop , temos
( )
Obs: a recíproca não é de toda verdadeira pois a propriedade do cancelamento é válida apenas se , ou seja, se e forem primos entre si, como será demonstrado a seguir.
)
Dado , onde e se
( ), então
( )
Demonstração: por hipótese, ( ) e pela prop , temos que
( ),
( )
e
e
( ),
então
então
( )
Demonstração: resultado da propridade transitiva e prop :
) ( ) e ( ) ( );
) ( ) ( );
E, novamente, pela propriedade transitiva:
) ( ) e ( ) ( )
Obs: Este último resultado é interessante para simplificar uma equação de congruência como, por exemplo,
( )
Temos, então, que ( ) e ( ), assim,
( ) ( )
Logo, todas as soluções da equação original são da forma , com .
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/
Imagem ( fundo ): http://www.lacosdeminas.com.br/
Olá, Aloísio!!!!
ResponderExcluirPassando 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!!!!!
Oi, Valdir!
ResponderExcluirObrigado 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!