Teorema Chinês do Resto

Prévia do material em texto

Obs: Quem
é chinês é
o teorema,
não os restos
Teorema Chinês do Restos. Dados dois inteiros m1, m2 ≥ 2 primos entre si
(isto é, mdc(m1,m2) = 1), e dados outros dois inteiros quaisquer a1, a2, o sistema{
x ≡ a1 mod m1
x ≡ a2 mod m2
(1)
possui uma solução x = x0. Além disso, um inteiro x será solução do sistema se e
somente se x ≡ x0 mod m1m2.
A conclusão do Teorema também pode ser expressa assim: O conjunto
de soluções do sistema é sempre da forma {x0 + km1m2; k ∈ Z}. Em particular, a
solução única modm1m2.
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 teo-
rema, 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 m1m2 =
24.
Este é o teo-
reminha que
está nas no-
tas do Henri
Corolário. Suponha m1, m2 ≥ 2 primos entre si. Então temos x ≡ a mod m1m2
se e somente se valem as duas relações abaixo.
{
x ≡ a mod m1
x ≡ a mod m2
(2)
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 m1m2. Portanto vale (2) se e somente se
x ≡ a mod m1m2. �
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 = m1y1 + a1 (3)
x = m2y2 + a2 (4)
Subtraindo as duas equações e reordenando temos
m1y1 − m2y2 = 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) ∈ Z
2. 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
m1m2 é solução: de fato x = x0 + km1m2 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 = km1m2 ≡ 0 mod m1m2, ou seja, x ≡ x0 mod m1m2,
como queríamos provar. �
Observação. Aprova do teorema dá ummétodopara 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 ≡ a2 mod m2
· · ·
x ≡ ak mod mk
(8)
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 aumsistemacomduas 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 · · ·mk1mk, como queríamos
demonstrar. �
Exemplo do
cadernoExemplo 3. Resolver x3 = 277 mod 360.
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

x3 ≡ 277 mod 8
x3 ≡ 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
13
0 1 2 3 4 5 6 7 8 9 10 11
0
1
2
3
4
0
1
2
3
4
5
6
7
8
9
10
11
12
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 = m1m2. 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 < m1m2 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 quadradasmó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
que a “‘Lei
do Corte”
é falsa
quando o
módulo não
é primo.Observação. Usando a proposição acima e a existência de inverso multipli-
cativo 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 umnúmeropode termais de duas raízes quadradasmódulo 35
incongruentes entre si:
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{
x2 ≡ 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 é Como 5 e 7
são primos,
uma vez
encontradas
duas raízes
quadradas
não pre-
cisamos
procurar
outras
equivalente a {
x ≡ ±1 mod 5
x ≡ ±2 mod 7
Isso dá quatro sistemas estilo TCR:{
x ≡ 1 mod 5
x ≡ 2 mod 7
{
x ≡ −1 mod 5
x ≡ 2 mod 7
{
x ≡ 1 mod 5
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