AritmeticaModular-Congruencias

Prévia do material em texto

Aritme´tica Modular e Congrueˆncias
Romulo Lins
1 Definic¸o˜es e propriedades fundamentais
Definic¸a˜o 1.1 Dados inteiros a, b quaisquer, e m > 1, diremos que a e´ congru-
ente (ou coˆngruo) a b mo´dulo m se m | (a− b), e escreveremos a ≡ b (mod m).
Teorema 1.1 Vale que:
i. a ≡ b (mod m)⇔ os restos das diviso˜es inteiras de a e b por m sa˜o iguais.
ii. a ≡ b (mod m)⇔ a = b+mk para algum inteiro k.
Demonstrac¸a˜o:
i. (⇒) Se a = mq1 + r1 e b = q2m+ r2, a− b = (q1 − q2)m+ (r1 − r2). Como
m | (a− b) e m | (q1 − q2)m, m | (r1 − r2), o que so´ e´ poss´ıvel se r1 = r2, ja´
que 0 ≤ r1, r2 < m⇒ | r1 − r2 | < m.
(⇐) Imediato.
ii. Imediato.
Definic¸a˜o 1.2 Dado um inteiro a, sua classe de equivaleˆncia a, segundo a
relac¸a˜o de congrueˆncia mo´dulo m, e´ {x ∈ Z | x ≡ a (mod m)}.
Teorema 1.2 A congrueˆncia e´ uma relac¸a˜o de equivaleˆncia, isto e´, com relac¸a˜o
a estas treˆs propriedades, ela se comporta como a igualdade:
i. a ≡ a (mod m);
ii. a ≡ b (mod m)⇔ b ≡ a (mod m); e,
iii. a ≡ b (mod m) e b ≡ c (mod m)⇒ a ≡ c (mod m)
Demonstrac¸a˜o:
i. m | a− a = 0.
1
ii. m | (a− b)⇒ m | −(a− b) = b− a.
iii. m | (a− b) e m | (b− c)⇒ m | [(a− b) + (b− c)] = a− c.
Teorema 1.3 Se a ≡ b (mod m), c ≡ d (mod m) e k ∈ Z, valem as seguintes
propriedades:
i. a+ c ≡ b+ d (mod m);
ii. a− c ≡ b− d (mod m);
iii. ac ≡ bd (mod m);
iv. em particular, ak ≡ bk (mod m);
v. em particular, a ≡ b (mod m) ⇒ an ≡ bn (mod m) (mas, como nos intei-
ros, na˜o vale a inversa: 22 ≡ 12 (mod 3), mas 2 6≡ 1 (mod 3)).
Demonstrac¸a˜o:
i. a = b+ k1m, c = d+ k2m⇒ a+ b = (c+ d) + (k1 + k2)m.
ii. Como em (i).
iii. a = b+ k1m, c = d+ k2m⇒ ac = (b+ k1m)(d+ k2m) = bd+ (bk2 + dk1 +
k1k2m)m.
iv. Imediato.
v. Imediato.
Estes resultados mostram que as operac¸o˜es independem de quais representan-
tes tomamos para ”fazer as contas”, pensando em classes de equivaleˆncia.
Valem tambe´m a comutatividade e a associatividade da adic¸a˜o e da multi-
plicac¸a˜o; vale a distributividade da multiplicac¸a˜o sobre a adic¸a˜o. A classe do 0 e´
o elemento neutro da adic¸a˜o, e a do 1 e´ o elemento neutro da multiplicac¸a˜o.
Estas propriedades permitem que falemos de uma aritme´tica mo´dulo m;
formalmente podemos falar das aritme´ticas dos ane´is Zm. No entanto, estas
aritme´ticas diferem em um aspecto fundamental da aritme´tica usual em Z:
Teorema 1.4 Se ac ≡ bc (mod m) e (c,m) = 1, enta˜o a ≡ b (mod m).
2
Demonstrac¸a˜o: m | (ac− bc) = (a− b)c e (c,m) = 1⇒ m | (a− b).
Um exemplo mostra que a ”lei do cancelamento” na˜o vale se (c,m) 6= 1 (o
que inclui o caso c = 0, como na aritme´tica usual): 14 × 3 ≡ 4 × 3 (mod 6),
mas 14 6≡ 4 (mod 6). Isto se deve ao fato de que < Zm,+,× > e´ dominio de
integridade (na˜o tem divisores de zero) sse m e´ primo; neste caso < Zm,+,× >
e´ um corpo finito (e na˜o-ordenado), ja´ que vale o
Teorema 1.5 Se (a,m) = 1 enta˜o existe a−1 ∈ Z tal que a a−1 ≡ 1 (mod m).
Demonstrac¸a˜o: Se (a,m) = 1, enta˜o existem x0, y0 tais que ax0 +my0 = 1, de
onde ax0 +my0 ≡ ax0 ≡ 1 (mod m). Temos a−1 ≡ x0 (mod m).
Se a tem inverso, basta multiplicar os dois membros da congrueˆncia por a−1
para realizar o ”cancelamento”. Uma consequeˆncia imediata disto e´ que se a ≡ b
(mod m), d | a, d | b e (d,m) = 1 enta˜o a
d
≡ b
d
(mod m).
Outras propriedades u´teis das congrueˆncias:
Teorema 1.6 Valem (atenc¸a˜o com a notac¸a˜o de ”frac¸a˜o”: so´ faz sentido se
representa um inteiro):
i. Se a ≡ b (mod m) e D e´ um divisor de m, enta˜o a ≡ b (mod D);
ii. Se a ≡ b (mod m) e D e´ um divisor comum de a, b,m, enta˜o a
D
≡ b
D
(mod m
D
);
iii. a ≡ b (mod m)⇒ ak ≡ bk (mod mk), para todo k inteiro > 0.
iv. Se

a ≡ b (mod m1)
a ≡ b (mod m2)
a ≡ b (mod m3)
. . .
a ≡ b (mod mk)
enta˜o a ≡ b (mod M) onde M = mmc(m1, . . . ,mk).
Demonstrac¸a˜o:
i. Se m = m1D, a = b+ qm = b+ q(m1D) = b+ (qm1)D.
ii. Se a = a1D, b = b1D, m = m1D e a = b+ qm, enta˜o a1 = b1 + qm1.
3
iii. a = b+ qm⇒ ak = bk + q(mk).
iv. Usamos uma recorreˆncia. Se a−b = m1q1 = m2q2, enta˜o a−b e´ um mu´ltiplo
comum de m1,m2, de modo que
a− b = m1m2
(m1,m2)
t2 = [m1,m2] t2
para algum t2 inteiro, como vimos no cap´ıtulo sobre divisibilidade, sec¸a˜o so-
bre MMC. Agora, considerando que a− b = [m1,m2] t2 = m3q3, conclu´ımos
que a − b = [m1,m2,m3] t3 para algum t3 inteiro, e assim sucessivamente,
ate´ incorporarmos todos os mi ao mmc.
2 Crite´rios de divisibilidade e outras contas
Nesta sec¸a˜o, n = dkdk−1 . . . d1d0 e´ a representac¸a˜o do inteiro n em alguma
base b, b > 1; os di sa˜o d´ıgitos, de modo que 0 ≤ di < b.
Teorema 2.1 Crite´rios de divisibilidade para nu´meros escritos na base 10; n =
dkdk−1 . . . d1d0. (atenc¸a˜o para a forc¸a da linguagem de congrueˆncias)
i. 2 | n⇔ 2 | d0, isto e´, d0 = 0, 2, 4, 6, 8.
ii. 3 | n⇔ 3 |∑ki=0 di.
iii. 5 | n⇔ 5 | d0, isto e´, d0 = 0, 5.
iv. 6 | n⇔ 2 | n e 3 | n.
v. 9 | n⇔ 9 |∑ki=0 di.
vi. 10 | n⇔ d0 = 0.
vii. 11 | n⇔ 11 |∑ki=0(−1)idi.
Demonstrac¸a˜o:
i. 10 ≡ 0 (mod 2)⇒ 10n ≡ 0 (mod 2) para todo n > 0. Assim,
n = dkdk−1 . . . d1d0 = 10kdk + 10k−1dk−1 + . . .+ 10d1 + d0 ≡ d0 (mod 2)
ii. 10 ≡ 1 (mod 3)⇒ 10n ≡ 1 (mod 3) para todo n ≥ 0. Assim,
n = dkdk−1 . . . d1d0 = 10kdk+10k−1dk−1+ . . .+10d1+d0 ≡ dk+ . . .+d1+d0
(mod 3).
4
iii. Como no caso de 2.
iv. Imediato, das propriedades de divisibilidade.
v. Como no caso de 3.
vi. 10 | n⇒ 2 | n e 5 | n, de onde d0 = 0.
vii. Este e´ um caso interessante! Como 10 ≡ −1 (mod 11) ⇒ 10n ≡ (−1)n
(mod 11), para todo n ≥ 0, temos
n = dkdk−1 . . . d1d0 = 10kdk + 10k−1dk−1 + . . .+ 10d1 + d0
≡ (−1)kdk + (−1)k−1dk−1 . . .+ (−1)d1 + d0 (mod 11)
Mas e quais sa˜o os crite´rios de divisibilidade para 4, 7 e 8, que na˜o nos
ensinaram? No caso da divisibilidade por 7, a investigac¸a˜o pode ser generalizada
se usarmos Teoria dos Grupos.
Teorema 2.2 Para um nu´mero n escrito na base 1000, 37 | n⇔ 37 |∑ki=0 di.
Demonstrac¸a˜o: 1000 ≡ 1 (mod 37).
Problema 1 Considere nu´meros escritos na base 100. Para quais m vale um
crite´rio de divisibilidade por m igual ao de por 3 e 9, para a base 10, e ao de por
37, para a base 1000?
Problema 2 Qual o resto da divisa˜o de
∑1000
i=1 i! por 12?
Problema 3 Qual o resto da divisa˜o de 2100 + 3100 por 7?
A prova dos 9
Na escola prima´ria (antigamente os primeiros quatro anos da educac¸a˜o ba-
sica), nos ensinavam uma te´cnica para saber se uma soma ou subtrac¸a˜o tinha
sido feita corretamente. Por exemplo,
1 9 6 4
+ 7 6 5
2 7 2 9
5
Comec¸ando do primeiro nu´mero, pela esquerda, recita´vamos: ”1 mais 9, dez,
noves fora 1. 1 mais 6, 7. 7 mais 4, 11, noves fora 2” e segu´ıamos com o segundo
nu´mero: ”2 mais 7, 9, noves fora nada. Nada mais 6, 6. 6 mais 5, 11, noves fora,
2.”. Agora o resultado: ”2 mais 7, 9, noves fora, nada. Nada mais 2, 2. 2 mais
9, 11, noves fora 2”.
Como o noves fora dos nu´meros somados coincidiu com o noves fora do resul-
tado, era prova´vel, nos diziam, que a conta estivesse certa.
Perguntinhas:
i. Por que meus professores me ensinaram isto? E´ certo que me ajudava a
saber se eu errei ou na˜o?
ii. Discuta a possibilidade de o noves fora dar certo, mas a soma estar errada.
iii. Por que na˜o era cincos fora ou seis fora? Poderia ser? Ou outro?
3 Sistemas de res´ıduos
Se estivermos trabalhando em um Zm, chamaremos os inteiros a, b, c, . . ., de
res´ıduos mo´dulo m.
Definic¸a˜o 3.1 Um conjunto de inteiros {a1, . . . , at} e´ chamado de sistema
completo de res´ıduos mo´dulo m se ele consiste em exatamente um represen-
tante de cada uma das distintas classes a mo´dulo m. Por exemplo, {0, 11, 22, 33}
e´ um sistema completo de res´ıduos mo´dulo 4.
Um conjunto de inteiros {a1, . . . , at} e´ chamado de sistema reduzido de
res´ıduos mo´dulo m se ele consiste em exatamente um representante de cada
uma das distintas classes a mo´dulo m tais que (a,m)= 1. Por exemplo,
{1, 11, 13, 23} e´ um sistema reduzido de res´ıduos mo´dulo 8.
Observe que se a ≡ b (mod m), enta˜o (a,m) = (b,m).
Teorema 3.1 Valem:
i. Todo sistema completo de res´ıduos mo´dulo m tem m elementos;
ii. Qualquer conjunto {a1, . . . , am} de inteiros que sa˜o dois a dois na˜o congru-
entes, forma um sistema completo de res´ıduos mo´dulo m;
iii. Denotando por ϕ(m) (func¸a˜o ϕ de Euler) a quantidade de nu´meros k, 0 ≤
k < m, tais que (k,m) = 1, temos que todo sistema reduzido de res´ıduos
mo´dulo m tem ϕ(m) elementos;
6
iv. Qualquer conjunto {a1, . . . , aϕ(m)} de inteiros que sa˜o dois a dois na˜o con-
gruentes e sa˜o primos com m, forma um sistema reduzido de res´ıduos
mo´dulo m.
Demonstrac¸a˜o:
i. Sa˜o m os poss´ıveis restos na divisa˜o euclideana por m, e a cada um corres-
ponde uma classe distinta das demais.
ii. Como os ai sa˜o dois a dois na˜o congruentes, seus restos na divisa˜o por m
sa˜o distintos, e como sa˜o em quantidade m, correspondem a todos os restos
poss´ıveis.
iii. Se (a,m) = 1, enta˜o a e´ congruente, mo´dulo m, a algum dos nu´meros
contados pela func¸a˜o ϕ, caso contra´rio, se a ≡ b (mod m) e (b,m) = d > 1,
enta˜o de m | a− b deduzimos que d | a.
iv. Basta combinar a ide´ia de (ii) e o resultado de (iii).
Ha´ duas maneiras usuais de se representar um sistema completo de res´ıduos
mo´dulo m. A primeira e´ tomar
{0, 1, 2, . . . ,m− 1}
A outra e´ tomar
{−m− 1
2
, . . . , 0, . . . ,
m− 1
2
}
se m e´ ı´mpar, e
{−m− 2
2
, . . . , 0, . . . ,
m
2
} ou {−m
2
, . . . , 0, . . . ,
m− 2
2
}
se m e´ par.
Teorema 3.2 i. Se (a,m) = 1 e x percorre um sistema completo de res´ıduos
mo´dulo m, enta˜o ax + b, com b um inteiro qualquer, tambe´m percorre um
sistema completo de res´ıduos mo´dulo m;
ii. Se (a,m) = 1 e x percorre um sistema reduzido de res´ıduos mo´dulo m,
enta˜o ax tambe´m percorre um sistema reduzido de res´ıduos mo´dulo m.
Demonstrac¸a˜o:
7
i. Os m elementos xi do sistema completo geram m nu´meros axi + b. Basta
mostrar que eles sa˜o dois a dois na˜o congruentes. Suponha i 6= j e axi+b ≡
axj+b (mod m). Enta˜o axi ≡ axj (mod m) e, como (a,m) = 1, deduzimos
que xi ≡ xj (mod m), uma contradic¸a˜o, ja´ que os elementos do sistema
completo sa˜o dois a dois na˜o congruentes.
ii. Como em (i), os ϕ(m) elementos do sistema reduzido geram ϕ(m) nu´meros
que, tomando b = 0 em (i), sa˜o dois a dois na˜o congruentes. Ale´m disto,
se (a,m) = 1 e (xi,m) = 1, enta˜o (axi,m) = 1, como verifica-se facilmente,
pensando em fatores primos.
Teorema 3.3 (Teorema de Euler) Se (a,m) = 1 enta˜o aϕ(m) ≡ 1 (mod m).
Demonstrac¸a˜o: Seja R = {r1, r2, . . . , rϕ(m)} um sistema reduzido de res´ıduos
mo´dulo m, com 1 ≤ ri ≤ m− 1. Se x percorre um sistema reduzido, ax tambe´m
percorre; seja K = {k1, k2, . . . , kϕ(m)} o conjunto dos restos das diviso˜es de axi
por m. Evidentemente R = K, talvez na˜o na mesma ordem. Temos, enta˜o,

ax1 ≡ k1 (mod m)
ax2 ≡ k2 (mod m)
ax3 ≡ k3 (mod m)
. . .
axϕ(m) ≡ kϕ(m) (mod m)
e multiplicando membro a membro todas as congrueˆncias obtemos
aϕ(m)r1 . . . rϕ(m) ≡ k1 . . . kϕ(m) (mod m)
o que, uma vez que os ri e os kj sa˜o primos com m, e sa˜o os mesmos em alguma
ordem (logo podem ser ”cancelados”), implica
aϕ(m) ≡ 1 (mod m)
Teorema 3.4 (Teorema de Fermat) Se p e´ primo e p - a, enta˜o ap−1 ≡ 1
(mod m).
Demonstrac¸a˜o: Se p e´ primo e na˜o divide a, enta˜o (a,m) = 1 e ϕ(p) = p − 1.
Basta aplicar o teorema de Euler.
Corola´rio 3.1 Para todo inteiro a, e todo primo p, ap ≡ a (mod p)
8
4 Soluc¸a˜o de congrueˆncias lineares
Dada a congrueˆncia ax + b ≡ c (mod m), resolver esta congrueˆncia para x e´
encontrar um x inteiro (logo, sua classe de equivaleˆncia) que satisfaz a relac¸a˜o
dada. Como o termo b pode ser sempre passado para a direita, consideraremos
apenas o caso ax ≡ b (mod m).
Teorema 4.1 Se (a,m) = 1, congrueˆncia ax ≡ b (mod m) tem soluc¸a˜o e e´
u´nica .
Para resolver estas congrueˆncias, ”basta” achar a−1. Mencionaremos, aqui,
treˆs me´todos para encontrar (se existir) o inverso de a mo´dulo m:
(I) Se m e´ ”pequeno”, teste todos os nu´meros de 2 a m−1. Por exemplo, para
resolver 5x ≡ 7 (mod 11),
x 5x (mod 11)
2 10
3 4
4 9
5 3
6 8
7 2
8 7
9 1
10 6
Voceˆ pode considerar que 5×9 ≡ 1 (mod 11), e multiplicar os dois membros
por 9:
5x ≡ 7 (mod 11)⇒ 9× 5x ≡ 9× 7 (mod 11)⇒
⇒ 45x ≡ 63 (mod 11)⇒ x ≡ 8 (mod 11)
ou pode concluir, diretamente, que
5× 8 ≡ 40 ≡ 7 (mod 11)
(II) Use o algor´ıtimo de Educlides para determinar (a,m). Se for 1, use o
me´todo das substituic¸o˜es para determinar x0, y0 tais que ax0+my0 = 1. x0
e´ o inverso de a mo´dulo m.
(III) (computacionalmente, um algor´ıtimo bastante eficiente) Use o algor´ıtimo
de Euclides para determinar os quocientes qi na expansa˜o de
m
a
em frac¸a˜o
9
cont´ınua simples; use as relac¸o˜es de recorreˆncia para determinar os con-
vergentes. Se os u´ltimos dois sa˜o
Pk−1
Qk−1
,
Pk
Qk
=
m
a
(lembre que como
(a,m) = 1, Pk = m e Qk = a, na˜o e´ apenas uma equivaleˆncia de frac¸o˜es),
enta˜o
mQk−1 − aPk−1 = (−1)k
aPk−1 ≡ (−1)k−1 (mod m)
a(−1)k−1Pk−1b ≡ b (mod m)
de onde a soluc¸a˜o e´
x ≡ (−1)k−1Pk−1b (mod m)
ou seja, a−1 ≡ (−1)k−1Pk−1 (mod m)
Teorema 4.2 Se (a,m) = d, a congrueˆncia ax ≡ b (mod m) tem soluc¸a˜o sse
d | b. Neste caso ha´ d soluc¸o˜es distintas mo´dulo m.
Sendo a = a1d , b = b1d, m = m1d,
ax ≡ b (mod m)⇒ a1x ≡ b1 (mod m1)
e como (a1,m1) = 1, determinamos x0, a (u´nica) soluc¸a˜o mo´dulo m1. Mo´dulo m,
no entanto, os nu´meros x ≡ x0 (mod m1) constituem d res´ıduos distintos:
x0, x0 +m1, x0 + 2m1, . . . , x0 + (d− 1)m1
que sa˜o todas as soluc¸o˜es mo´dulo m.
5 Sistemas de congrueˆncias lineares; Teorema
Chineˆs do Resto.
Teorema 5.1 (Teorema Chineˆs do Resto) Sejam m1,m2, . . . ,mk inteiros > 1,
primos entre si dois a dois, isto e´, (mi,mj) = 1 se i 6= j. Neste caso, o sistema
de congrueˆncias

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
x ≡ a3 (mod m3)
. . .
x ≡ ak (mod mk)
10
sempre tem soluc¸a˜o.
O nome do teorema vem do fato de que sua apresentac¸a˜o mais antiga aparece
no Sun Tzu Suan-ching (”O cla´ssico matema´tico de SunTzu”), segundo Hersh e
Davis, em seu excelente livro ”A experieˆncia Matema´tica” (recomendo a todos!).
Demonstrac¸a˜o: Se os nu´meros a,m sa˜o ’pequenos’ e sa˜o poucas con-
grueˆncias no sistema, podemos tentar resolver por inspec¸a˜o. Por exemplo, consi-
deremos o sistema {
x ≡ 2 (mod 5)
x ≡ 5 (mod 7)
Considerando apenas as soluc¸o˜es positivas, a primeira congrueˆncia tem por
soluc¸a˜o os nu´meros {2, 7, 12, 17, 22, 27, 32, 37, 42, 47, . . . } e a segunda os nu´meros
{5, 12, 19, 26, 33, 40, 47, 54, . . . }. A intersecc¸a˜o dos dois conjuntos e´ {12, 47, . . . }.
Se estendermos suficientemente os dois conjuntos, nos convenceremos de que to-
das as soluc¸o˜es sa˜o caracterizadas por x = 12+35t, para t inteiro (na˜o necessari-
amente positivo), o que parece ser verdadeiro verificando que 12+35t ≡ 2+0 ≡ 2
(mod 5) e 12+35t ≡ 5+0 ≡ 5 (mod 7); o que esta verificac¸a˜o na˜o garante e´ que
todas as soluc¸o˜es sejam desta forma.
Generalizando o caso de duas congrueˆncias, a pergunta e´: se m1,m2 sa˜o
primos entre si, e´ sempre verdade que as PAs a1+ tm1 e a2+sm2 teˆm intersecc¸a˜o
na˜o nula? Em outras palavras,
a1 + tm1 = a2 + sm2
tem soluc¸a˜o? A resposta e´ sim, pois, como (m1,m2) = 1 existem x0, y0 tais que
m1x0 +m2y0 = 1, e disto segue
(a2 − a1)m1x0 + (a2 − a1)m2y0 = (a2 − a1)
e basta tomarmos t = (a2 − a1)x0 e −s = (a2 − a1)y0. Encontrada uma soluc¸a˜o
X, as outras sera˜o da forma X +m1m2k.
Se (m1,m2) = d > 1, poder´ıamos investigar em que condic¸o˜es as duas PAs
teˆm intersecc¸a˜o na˜o vazia.
Embora pude´ssemos seguir este me´todo, resolvendo{
x ≡ X (mod m1m2)
x ≡ a3 (mod m3)
11
e assimpor diante, o caso geral de va´rias congrueˆncias e´ melhor tratado de outra
maneira. Para o sistema 
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
x ≡ a3 (mod m3)
. . .
x ≡ ak (mod mk)
vamos construir, diretamente, uma soluc¸a˜o S = S1 + S2 + . . . + Sk. O fato de a
representarmos como soma de k parcelas ja´ expressa nossa intenc¸a˜o de que cada
uma delas ira´ resultar em ai (mod mi) e 0 (mod mj) para j 6= i. A construc¸a˜o e´
a seguinte:
Comec¸amos definindo Mi, 1 ≤ i ≤ k:
Mi =
∏k
t=1mt
mi
Assim, Mi e´ divis´ıvel por todo mj, j 6= i (Mi ≡ 0 (mod mj)). Ale´m disto, como
os m sa˜o primos dois a dois,
(Mi,mi) = 1
de modo que Mi tem inverso multiplicativo M
′
i mo´dulo mi. Agora definimos
Si = aiMiM
′
i
para 1 ≤ i ≤ k, e, finalmente,
S = S1 + S2 + . . .+ Sk =
= a1M1M
′
1 + a2M2M
′
2 + · · ·+ akMkM
′
k
E´ imediato que
aiMiM
′
i ≡ ai × 0×M
′
i ≡ 0 (mod mj)
para j 6= i (ja´ que mj |Mi), e que
aiMiM
′
i ≡ ai × 1 ≡ ai (mod mi)
ja´ que M
′
i e´ o inverso multiplicativo de Mi, (mod mi), de modo que
S ≡ ai (mod mi), 1 ≤ i ≤ k
Como S ≡ S +∏kt=1mt (mod mi), ficam caracterizados todos os inteiros que
sa˜o soluc¸a˜o do sistema dado.
12
6 O Teorema Chineˆs do Resto e a representac¸a˜o
de inteiros
O Teorema Chineˆs do Resto diz que, dados inteiros m1,m2, . . . ,mk, primos
dois a dois, existe um u´nico inteiro 0 ≤ n <∏mi tal que

n ≡ a1 (mod m1)
n ≡ a2 (mod m2)
n ≡ a3 (mod m3)
. . .
n ≡ ak (mod mk)
Se tomarmos 0 ≤ ai < mi, isto equivale a dizer que cada inteiro n,
0 ≤ n < ∏mi pode ser representado, de maneira u´nica, pelas ”coordena-
das” a1, a2, a3, . . . , ak: a cada 0 ≤ n <
∏
mi corresponde exatamente uma
k-upla (a1, a2, . . . , ak) ∈ Zm1 × Zm2 × . . . × Zmk , onde estamos representando
Zm = {0, 1, 2, . . . ,m− 1}.
13