02 Congruências e Inteiros Módulo m.pdf

Conteúdo de Álgebra e Teoria dos Números

1. Capítulo 2
Congruências e os Inteiros Módulom
As congruências são extremamente úteis no sentido de estabelecer importantes resul-
tados da Teoria dos Números. Em linhas gerais, a Teoria das Congruências ou Aritmética
Modular é um meio de abordar propriedades da divisibilidade por meio da aritmética dos
restos.
Tanto o conceito quanto a notação de congruência foram introduzidos por Johann Carl
Friedrich Gauss (1777 - 1855) em seu famoso livroDisquisitiones Arithmeticae(Investiga-
ções Aritméticas) publicado em 1801. Desde então, os conceitos e notações introduzidos
por ele são usados atualmente.
2.1 Congruências
2.1.1 Propriedades Básicas das Conguências
Denição 2.1.1.Sejam6= 0um inteiro xo. Dois inteirosaebdizem-se congruentes
módulosmsemdivide a diferençaab.
Nesse caso, escrevemosab(mod m). Para indicar queaebnãosão congruentes
módulom, escrevemosa6b(mod m).
Exemplo 2.1.1.Temos que95 (mod2)pois2j(95). Também temos que
206 (mod2)pois2j(206). De fato, é fácil vericar que dois números são congru-
entes módulo2se e somente se eles são ambos pares ou ambos ímpares.
Exemplo 2.1.2.Temos que561 (mod3)pois3-(51). Também temos que
8624 (mod5)pois5-(824).
18

2. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 19
Gauss usou o símbolopara indicar a congruência devido à analogia com a igualdade
algébrica. Com essa denição,ab(mod m)se e somente semj(ab), ou equivalen-
temente, se existe um inteiroqtal quea=b+mq.
Comomj(ab)se e somente sejmj j(ab), consideraremos o caso em quem >0.
Podemos dar uma outra caracterização da noção de congruência.
Proposição 2.1.1.Sejamum inteiro xo em6= 0. Dois inteirosaebsão congruentes
módulomse e somente se eles têm como resto o mesmo inteiro quando divididos porm.

3. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 20
Utilizando uma circunferência divida emmpartes, podemos obter uma representação
pictórica da congruência módulom.
Fonte: Milies e Coelho (2006, p.105).
Associamos cada número inteiro a um único ponto da circunferência. Com essa corres-
pondência, dois inteiros são congruentes módulomse e somente se estiverem representados
pelo mesmo ponto da circunferência.
Uma coleção deminteirosfa1; a2; : : : ; amgdiz-se umsistema de resíduos módulos
mse cada inteiro é congruente móduloma um únicoai. É claro que o sistema completo de
resíduos mais simples que podemos obter éf0;1;2; : : : ; m1g. Mas não é o único possível.
Exemplo 2.1.3.Os seguintes conjuntos são sistemas completos de resíduos módulo 5:
f0;1;2;3;4g;
f5;6;7;8;9g;
f12;24;35;4;18g.
O conceito de congruência módulomestabelece uma relação sobre o conjunto dos
números inteiros, a relação de congruência módulom, que indicaremos por
(mod m):
Essa relação tem muitas propriedades em comum com a relação de igualdade entre
inteiros. De início, temos:
Proposição 2.1.2.Sejamm >0um inteiro xo ea; b; c; dinteiros quaisquer. Então,
valem as seguintes propriedades:
(i)Reexiva:aa(mod m).
(ii)Simétrica:Seab(mod m)entãoba(mod m).
(iii)Transitiva:Seab(mod m)ebc(mod m)entãoac(mod m).

4. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 21
Demonstração da Proposição 2.1.2.

5. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 22
Os resultados da proposição anterior nos mostram que(mod m)é uma relação de
equivalência sobreZ, algo que é extremamente importante. Este fato tem uma estreita
relação com o conjunto nitoZm, obtido por meio desta relação e que será estudado a
seguir.
2.2 Inteiros Módulom
Neste capítulo consideraremos as congrências sob um novo ponto de vista que permi-
tirá reinterpretar os resultados dos capítulos anteriores.
Em todo este capítulo,mindicará um inteiro maior que1.
Denição 2.2.1.Sejaaum inteiro. Chama-seclasse de congruência deamódulom
o conjunto formado por todos os inteiros que são congruentes aamódulom. Denotaremos
esse conjunto pora. Temos então
a=fx2Zjxa(mod m)g:
Comoxa(mod m)se e somente sexé da formax=a+tm, para algumt2Z,
também podemos escrever
a=fa+tmjt2Zg:
Mostraremos a seguir que a relação de congruência entre números se traduz em igual-
dade no sentido estrito entre classes.
Proposição 2.2.1.Sejamaebinteiros. Entãoab(mod m)se e somente sea=b.

6. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 23
Corolário 2.2.2.Sejamaebinteiros. Sea6=bentãoa\b=;.
Dada uma classea, para qualquer inteiroxtal quex2a, temos quex=a. Por causa
disso, cada inteiro pertencente a uma dada classe diz-se umrepresentanteda classe. Por
exemplo,10e2são representantes da classe4módulo6.
Consideremos um sistema completo de resíduos módulosm, por exemplo, os inteiros
f0;1; : : : ; m1ge suas respectivas classes:
0 =f0;m;2m;3m; : : :g
1 =f1;1m;12m;13m; : : :g
.
.
.
.
.
.
.
.
.
m1 =fm1; m1m; m12m; m13m; : : :g:
Assim, cada inteiro pertence a uma e apenas uma dasmclasses.

7. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 24
Por exemplo, sem= 6, todas as classes possíveis, módulo6são as seguintes:
0 =f0;6;6;12;12; : : :g
1 =f1;7;5;13;11; : : :g
2 =f2;8;4;14;10; : : :g
3 =f3;9;3;15;9; : : :g
4 =f4;10;2;16;8; : : :g
5 =f5;11;1;17;7; : : :g
Denotaremos pelo símboloZmo conjunto das classes de congruências módulome
chamá-lo-emos o conjunto dos inteiros módulom.
Assim,Z6=f0;1;2;3;4;5g.
Em geral, sea1; a2; : : : ; amé um sistema completo de resíduos módulom, temos
Zm=fa1;a2; : : : ;amg:
Tomando o sistema de resíduos mais simples, podemos escrever
Zm=f0;1; : : : ;m1g:
Note que, o conjuntoZmtem precisamentemelementos.
Vamos introduzir as operações de adição e multiplicação emZme estudar suas pro-
priedades.
Exemplo 2.2.1.Existe uma forma natural de adicionar e multiplicar elementos emZm.
Por exemplo, para adicionar e multiplicar3e5emZ6faríamos,
Assim, efetuar a adição de duas classes módulom, tomamos representantes quaisquer
aebdessas classes, fazemos a adição emZe consideramos como resultado da adição a
classe dea+bmódulom. A operação de multiplicação se faz de forma análoga.
Denição 2.2.2.Dadas duas classesa;b2Zm, chama-se aba classea+b.
Denição 2.2.3.Dadas duas classesa;b2Zm, chama-se aba classe
ab.
Uma questão natural que surge é: será que o resultado das operações não depende dos
representantes escolhidos?

8. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 25
Exemplo 2.2.2.Por exemplo, ao adicionarmos3e5emZ6, poderíamos ter escolhido
63e23emZ6e o resultado seria o mesmo?
Vamos mostrar que essas operações não dependem dos representantes das classes, ou
seja, estão bem denidas.
Lema 2.2.1.Sejama1; a2; b1eb2inteiros tais quea1=a2eb1=b2. Então,a1+b1=
a2+b2ea1b1=a2b2.

9. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 26
As operações que acabamos de denir gozam das seguintes propriedades:
Teorema 2.2.3.A operaçãode adição sobreZmtem, para quaisquera;b;c2Zm, as
seguintes propriedades:
A1.Propriedade Associativa:a(bc) = (ab)c.
A2.Propriedade Comutativa:ab=ba.
A3.Existência do elemento Neutro:Existe um único elemento emZm, que é pre-
cisamente0, a classe do0, tal que
a0 =a, para todoa2Zm.
A4.Existência do Simétrico:Para cada inteiro módulom,a, existe um único ele-
mento emZm, que chamaremos simétrico deae indicaremos pora, tal que
a(a) =0.

10. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 27
Continuação da demosntração.

11. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 28
Teorema 2.2.4.A operaçãode multiplicação sobreZmtem, para quaisquera;b;c2
Zm, as seguintes propriedades:
M1.Propriedade Associativa:a(bc) = (ab)c.
M2.Propriedade Comutativa:ab=ba.
M3.Existência do elemento Neutro:Existe um único elemento emZm, que é pre-
cisamente1, a classe do1, tal que
a1 =a, para todoa2Zm.
D.Propriedade Distributiva da operação de multiplicação em relação a ope-
ração de adição:
a(bc) =abac:

12. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 29
Continuação da demosntração.

13. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 30
O conjuntoZmmunido das operações de adição e de multiplicação é umanel, cha-
madoanel das classes residuais módulomouanel dos inteiros módulom.
Denição 2.2.4.Um elemento não-nuloa2Zmdiz-se umdivisor de zerose existe
b2Zm, também não-nulo, tal queab=0.
Por exemplo, emZ6temos que23 =6 =0.
Vamos determinar quais são os divisores de zero emZm.
Lema 2.2.2.Um elemento não-nuloadeZmé divisor de zero se e somente semdc(a; m)6=
1.

14. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 31
Corolário 2.2.5.Sejap >1um inteiro primo. EntãoZpnão contém divisores de zero.
Na verdade vale a recíproca também.
Lema 2.2.3.SeZmnão contém divisores de zero entãomé um inteiro primo.
Proposição 2.2.6.A propriedade cancelativa do produto vale emZmse e somente sem
é primo.

15. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 32
Denição 2.2.5.Um elementoadeZmdiz-se inversível se existex2Zmtal queax=1.
Um elementoxnessas condições diz-se uminversodea.
Já vimos que os únicos elementos inversíveis deZsão1e1. Agora, consideremos
Z5, quais são os elementos que admitem inverso neste anel? E emZ6?

16. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 33
Proposição 2.2.7.Sejaaum elemento não-nulo deZm. Então,aé inversível se e
somente semdc(a; m) = 1.

17. CAPÍTULO 2. CONGRUÊNCIAS E OS INTEIROS MÓDULO M 34
Exemplo 2.2.3.Calcule o inverso de4emZ37.
Corolário 2.2.8.Sejap >1um inteiro primo. Então, todo elemento não-nulo deZpé
inversível.