Congruências Lineares

Filipe Rodrigues de S. Moreira

Graduando em Engenharia Mecânica –

Instituto Tecnológico de Aeronáutica (ITA)

Agosto 2006

Congruências Lineares

Introdução

A idéia de se estudar congruências lineares pode vir a facilitar (e muito) a vida

de um estudante, na hora de resolver questões de Teoria dos Números e até Polinômios.

Esse assunto merece uma atenção especial, pois em geral os livros que estão no

mercado, mostram do que se trata, porém vão logo para uma abordagem mais

abrangente e acabam saindo do foco de um aluno que não se interessa pelo assunto

como estudo puro e sim está apenas buscando, alternativamente, outra ferramenta para

resolver questões de vestibulares mais rebuscados como IME e ITA. Esse artigo tem por

objetivo atender a necessidade de bons alunos que não se interessam por Olimpíadas de

Matemática (puro e simplesmente), mas querem descobrir novos métodos para tornar

simples questões difíceis, que à priori exigiriam muito raciocínio e genialidade.

Definição da palavra e notação

Dizemos que dois números inteiros são congruentes, em relação a algum outro,

quando deixam o mesmo resto na divisão por esse outro, ou seja, diz-se que “a é

congruente a b módulo m” quanto tanto “a” quanto “b” deixam o mesmo resto na

divisão por “m”. Veja a notação usual: )(modmba=. Aplicando!!!!

)5(mod212=, pois 2 é o resto da divisão de 12 por 5.

)5(mod712=, pois 7 e 12 deixam o mesmo resto na divisão por 5.

)7(mod324=, pois 3 é o resto da divisão de 24 por 7.

)9(mod128=, pois 1 é o resto da divisão de 28 por 9.

Veja esse último exemplo....sabe-se que 13.928+=, mas por que não

escrevermos que ? Sendo assim, o resto da divisão de 28 por 9 poderia ser

“-8”. De fato, na divisão Euclidiana, isso não é permitido, pois se trata do menor resto

positivo, porém, podemos trabalhar com restos negativos na teoria de congruência, ou

seja, é possível escrever que

84.928-=

)9(mod828-=. Acredite! isso vai tornar a sua vida muito

mais tranqüila na hora de resolver questões de teoria dos números.

Exercícios propostos

P1. Resolva as congruências abaixo:

a) b) )4(mod12=)3(mod32= c) )8(mod71=

d) e) )13(mod38=)6(mod48= f) )11(mod27=

Algumas propriedades de congruências

1P-) Sejam dois números inteiros tais que )(modmba= e outros dois inteiros tais que

. Assim, )(modmdc=)(modmdbca±=±.



Prova:

Se então )(modmba=bmka+=.(com Zk.) e se )(modmdc= então

(com ) Logo temos que dmtc+=.Zt.()(dbmtkca±+±=±).(, logo

. )(modmdbca±=±

2P-) Sejam dois números inteiros tais que )(modmba= e outros dois inteiros tais que

. Assim, . )(modmdc=)(mod..mdbca=

Prova:

Se então )(modmba=bmka+=.(com Zk.) e se )(modmdc= então

(com dmtc+=.Zt.) Logo temos que dbbmtdmkmtkcamdemúltiplo........2+++=

..................

, logo

. )(mod..mdbca=

3P-) Sejam dois números inteiros tais que )(modmba=. Logo sendo r outro número

inteiro tem-se que . )(modmrbra±=±

Prova:

Se então )(modmba=bmka+=., com Zk.. Logo temos que

, logo ()(rbmkra±+=±.)(modmrbra±=±.

4P-) Sejam dois números inteiros tais que )(modmba=. Logo sendo r outro número

inteiro tem-se que . )(mod..mrbra=

Prova:

Se então ).(modmba=bmka+=., com Zk.. Logo temos que ,

logo .

rbrmkra....+=

)(mod..mrbra=

5P-) Sejam dois números inteiros tais que ).(modmba=. Seja n um número natural

logo, . ).(modmbann=

Prova