Obs: Quem
Teorema Chinês do Restos. Dados dois inteiros m1 , m2 ≥ 2 primos entre si
é chinês é
(isto é, mdc(m1 , m2 ) = 1), e dados outros dois inteiros quaisquer a1 , a2 , o sistema
o teorema,
(
não os restos
x ≡ a1 mod m1
(1)
x ≡ a2 mod m2
possui uma solução x = x0 . Além disso, um inteiro x será solução do sistema se e
somente se x ≡ x0 mod m1 m2 .
A conclusão do Teorema também pode ser expressa assim: O conjunto
de soluções do sistema é sempre da forma {x0 + km1 m2 ; k ∈ Z}. Em particular, a
solução única modm1 m2 .
Exemplo 1. Considere o sistema
(
x ≡ 1 mod 2
x ≡ 5 mod 5
A primeira equação diz que x é ímpar, enquanto a segunda diz que o dígito
das unidades de x é 0 ou 5. Portanto as soluções do sistema são 0, ±5, ±15
etc. Ou seja, x é solução se e somente se x ≡ 5 mod 10. Em particular, a
solução é única mod 10, como previsto pelo Teorema Chinês dos Restos.
Exemplo 2. Para ver que a hipótese mdc(m1 , m2 ) = 1 é necessária no teorema, considere o sistema
(
x ≡ 2 mod 4
x ≡ 3 mod 6
Esse sistema não tem solução. Por outro lado, o sistema
(
x ≡ 0 mod 4
x ≡ 0 mod 6
tem soluções x = 0, ±12, ±24, . . . Porém a solução não é única mod m1 m2 =
24.
Este é o teo-
Corolário. Suponha m1 , m2 ≥ 2 primos entre si. Então temos x ≡ a mod m1 m2 reminha que
está nas nose e somente se valem as duas relações abaixo.
tas do Henri
(
x ≡ a mod m1
(2)
x ≡ a mod m2
Demonstração. Dado qualquer inteiro a, o sistema (2) de equações em x
obviamente possui uma solução x0 = a. Pelo TCR, todas as outras soluções
serão congruentes a esta mod m1 m2 . Portanto vale (2) se e somente se
x ≡ a mod m1 m2 .
1
Prova do TCR. Primeiro veremos que existe pelo menos uma solução. Um
inteiro x satisfaz o sistema (1) se e somente se existem inteiros y1 e y2 tais
que
x = m1 y1 + a1
(3)
x = m2 y2 + a2
(4)
Subtraindo as duas equações e reordenando temos
m1 y1 − m2 y2 = a2 − a1 .
(5)
Agora, como mdc(m1 , m2 ) = 1, sabemos [já foi explicado antes] que a equação (5) possui alguma solução (y1 , y2 ) ∈ Z2 . Fixe uma tal solução e defina
x = x0 pela equação (3). Então usando (5) vemos que também vale a equação (4). Portanto este x = x0 é uma solução do sistema (1).
Uma vez encontrada uma solução x0 , vejamos que qualquer x ≡ x0 mod
m1 m2 é solução: de fato x = x0 + km1 m2 implica x ≡ x0 mod m1 e x ≡
x0 mod m2 .
Por outro lado, veremos que todas as soluções são dessa forma. Suponha
x solução do sistema (1). Como x1 também é solução, temos que y = x − x0
satisfaz
y ≡ a1 − a1 ≡ 0 mod m1
(6)
y ≡ a2 − a2 ≡ 0 mod m2
(7)
Por (6), m1 divide y, isto é, existe ℓ tal que y = ℓm1 . Por (7), m2 divide
y = ℓm1 . Como m1 e m2 são primos entre si, m2 divide ℓ, isto é, existe k tal
que ℓ = km2 . Portanto y = km1 m2 ≡ 0 mod m1 m2 , ou seja, x ≡ x0 mod m1 m2 ,
como queríamos provar.
Observação. A prova do teorema dá um método para encontrar soluções dos
tais sistemas. Isso deve ser mostrado em aula com alguns exemplos.
Vejamos agora uma versão ainda melhor do TCR:
Teorema Chinês do Restos (Versão forte). Sejam m1 , . . . , mk inteiros ≥ 2 dois
a dois primos entre si (isto é, mdc(mi , m j ) = 1 sempre que i , j). Sejam a1 , . . . , ak
inteiros quaisquer. Então o sistema


x ≡ a1 mod m1


 x ≡ a mod m


2
2
(8)

 ···



 x ≡ a mod m
k
k
possui uma solução x = x0 . Além disso, um inteiro x é solução do sistema se e
somente se
x ≡ x0 mod m1 · · · mk .
2
Demonstração. A prova é por indução no número k ≥ 2 de equações. Já
vimos que o teorema vale para 2 equações. Agora fixe k > 2 e suponha que
o teorema vale para k − 1 equações. Dados m1 , . . . , mk dois a dois primos
entre si, e a1 , . . . , ak quaisquer, considere o sistema formado apenas pelas
k − 1 primeiras equações em (8). Pela hipótese de indução, existe um b tal
que este subsistema é equivalente a uma única equação, a saber,
x ≡ b mod M,
onde M = m1 · · · mk−1 .
Portanto o sistema inteiro (8) é equivalente a um sistema com duas equações:
(
x ≡ b mod M
x ≡ ak mod mk
Notando que M e mk são primos entre si, e usando que o teorema vale
para duas equações, temos que existe solução x0 . Além disso, x é solução se e somente se x ≡ x0 módulo Mmk = m1 · · · mk1 mk , como queríamos
demonstrar.
x3
Exemplo do
Exemplo 3. Resolver = 277 mod 360.
caderno
Note que 360 = 8 × 9 × 5, e esses três números são primos entre si. Pelo
TCR–versão forte, a equação é equivalente ao sistema
 3

x ≡ 277 mod 8


 3
x ≡ 277 mod 9



 x3 ≡ 277 mod 5
Aí resolvemos na força bruta. . .
Observação. Eu gostaria de mostrar na aula mais aplicações do TCR! Quem
sabe isto? www.cut-the-knot.org/blue/chinese.shtml Ver também o [GKP].
Prova dinâmica do Teorema Chinês dos Restos
Vamos dar uma outra prova do TCR, que esclarece o que acontece
quando m1 e m2 não são primos entre si.
Sejam m1 e m2 inteiros ≥ 2 quaisquer. Considere um retângulo de
lados m1 e m2 , dividido em quadrados 1 × 1. Cada quadrado é descrito por
coordenadas (x, y) onde x e y são inteiros com 0 ≤ x ≤ m1 −1 e 0 ≤ y ≤ m2 −1;
veja a Figura 1. Considere o seguinte passeio no retângulo:
• No tempo t = 0 começamos no quadrado (0, 0).
3
4
4
13
3
12
2
9
3
8
2
7
1
1
6
0
0
0
11
5
1
2
3
4
10
5
6
7
8
9
10
11
Figura 1: Passeio no retângulo 12 × 5. No tempo t = 13 estamos no quadrado
(1, 3).
• Se no tempo (inteiro não-negativo) t estamos no quadrado (x(t), y(t))
então no tempo t + 1 pulamos para o único quadrado (x(t + 1), y(t + 1))
no retângulo m1 × m2 cujas coordenadas satisfazem
x(t + 1) ≡ x(t) + 1 mod m1
e
y(t + 1) ≡ y(t) + 1 mod m2 .
Equivalentemente, x(t) ≡ t mod m1 e y(t) ≡ t mod m2 . Quando retornamos
pela primeira vez ao quadrado (0, 0)? Isso acontece no menor tempo t que é
congruente a zero módulo m1 e m2 , isto é, no mínimo múltiplo comum de m1
e m2 , chamemos p = mmc(m1 , m2 ). Observe também que o tempo t = p é a
primeira vez que visitamos um quadrado que já tinha sido visitado antes.
(Isso acontece pois não há dois quadrados diferentes que pulem para um
mesmo quadrado.) A partir do tempo p, visitaremos os mesmos quadrados
de novo, e na mesma ordem. Além disso, cada um desses quadrados é
visitado periodicamente uma vez a cada p unidades de tempo.
No caso que m1 e m2 são primos entre si, temos p = m1 m2 . Mas esse é
o número total de quadrados no retângluo; portanto visitaremos todos os
quadrados. Isto prova o Teorema Chinês dos Restos: Dados quaisquer x0 ,
y0 , o sistema t ≡ x0 mod m1 e t ≡ y0 mod m2 tem uma solução t0 , e as outras
soluções são exatamente os t’s tais que t ≡ t0 mod p. (Podemos pensar que
o passeio se estende indefinitamente no passado para incluir t’s negativos.)
No caso que m1 e m2 são primos entre si, temos p < m1 m2 e portanto
alguns quadrados jamais serão visitados.
Observação. Imagine o retângulo m1 × m2 feito de borracha. Aí colamos a
aresta de baixo com a de cima, obtendo um cilindro. Depois colamos os
dois círculos correspondentes às arestas laterais do retângulo, obtendo um
4
toro (superfície de uma rosquinha). Um vídeo do passeio no toro está aqui:
LINK YOUTUBE.
Observação. A prova acima também dá a versão forte do teorema, desde
que usemos um retângulo de dimensão maior. . .
Alguns comentários sobre equações quadráticas
Proposição (Raízes quadradas módulo p). Se p > 2 é primo então para qualquer
a, a equação x2 ≡ a mod p cai em um dos três casos:
a) ou não tem solução;
b) ou as soluções são da forma x ≡ 0 mod p;
c) ou as soluções são da forma x ≡ ±x0 mod p.
Demonstração. Basta mostrar que se x e x0 são soluções da equação então
x ≡ ±x0 mod p. Se x0 é solução então
0 ≡ a − a ≡ x2 − x20 ≡ (x − x0 )(x + x0 ) mod p
Suponha que x . x0 mod p. Então podemos multiplicar os dois lados
da equação acima pelo inverso multiplicativo mod p de x − x0 e obter
0 ≡ x + x0 mod p.
observar
Observação. Usando a proposição acima e a existência de inverso multiplicativo módulo p primo, podemos mostrar que a fórmula de Báscara vale
mod p.
A proposição é falsa se o módulo não é primo; no exemplo seguinte
veremos que um número pode ter mais de duas raízes quadradas módulo 35
incongruentes entre si:
que a “‘Lei
do
é
Corte”
falsa
quando
o
módulo não
é primo.
Exemplo 4 (Refazendo o exemplo 4 das notas do Henri, pag 12). . Resolver
a equação x2 ≡ 11 mod 35. Pelo TCR, isto é equivalente ao sistema
( 2
x ≡ 11 ≡ 1 mod 5
x2 ≡ 11 ≡ 4 mod 7
Como 1 e 4 já são quadrados em Z, pela proposição anterior este sistema é
equivalente a
(
x ≡ ±1 mod 5
x ≡ ±2 mod 7
Isso dá quatro sistemas estilo TCR:
(
(
x ≡ 1 mod 5
x ≡ −1 mod 5
x ≡ 2 mod 7
x ≡ 2 mod 7
(
x ≡ 1 mod 5
x ≡ −2 mod 7
que dão todas as soluções procuradas:
x ≡ ±9 mod 35
x ≡ ±16 mod 35.
5
(
x ≡ −1 mod 5
x ≡ −2 mod 7
Como 5 e 7
são primos,
uma
vez
encontradas
duas raízes
quadradas
não
pre-
cisamos
procurar
outras