MAT1310_TCR

Prévia do material em texto

MAT1310 – Matema´tica Discreta – 2012.1
Teorema Chineˆs do Restos. Dados dois inteiros m1, m2 ≥ 2 primos
entre si (isto e´, 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 soluc¸a˜o x = x0. Ale´m disso, um inteiro x sera´ soluc¸a˜o do
sistema se e somente se x ≡ x0 mod m1m2.
A conclusa˜o do Teorema tambe´m pode ser expressa assim: O conjunto
de soluc¸o˜es do sistema e´ sempre da forma {x0 + km1m2; k ∈ Z}. Em
particular, a soluc¸a˜o e´ u´nica modm1m2.
Exemplo 1. Considere o sistema{
x ≡ 1 mod 2
x ≡ 5 mod 5
A primeira equac¸a˜o diz que x e´ ı´mpar, enquanto a segunda diz que o d´ıgito
das unidades de x e´ 0 ou 5. Portanto as soluc¸o˜es do sistema sa˜o 0, ±5, ±15
etc. Ou seja, x e´ soluc¸a˜o se e somente se x ≡ 5 mod 10. Em particular, a
soluc¸a˜o e´ u´nica mod 10, como previsto pelo Teorema Chineˆs dos Restos.
Exemplo 2. Para ver que a hipo´tese mdc(m1,m2) = 1 e´ necessa´ria no
teorema, considere o sistema {
x ≡ 2 mod 4
x ≡ 3 mod 6
Esse sistema na˜o tem soluc¸a˜o. Por outro lado, o sistema{
x ≡ 0 mod 4
x ≡ 0 mod 6
tem soluc¸o˜es x = 0, ±12, ±24, . . . Pore´m a soluc¸a˜o na˜o e´ u´nica modm1m2 =
24.
Corola´rio. Suponha m1, m2 ≥ 2 primos entre si. Enta˜o temos x ≡ a mod
m1m2 se e somente se valem as duas relac¸o˜es abaixo.{
x ≡ a mod m1
x ≡ a mod m2 (2)
Demonstrac¸a˜o. Dado qualquer inteiro a, o sistema (2) de equac¸o˜es em x
obviamente possui uma soluc¸a˜o x0 = a. Pelo TCR, todas as outras soluc¸o˜es
sera˜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 soluc¸a˜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 equac¸o˜es e reordenando temos
m1y1 −m2y2 = a2 − a1. (5)
Agora, como mdc(m1,m2) = 1, sabemos [ja´ foi explicado antes] que a
equac¸a˜o (5) possui alguma soluc¸a˜o (y1, y2) ∈ Z2. Fixe uma tal soluc¸a˜o e
defina x = x0 pela equac¸a˜o (3). Enta˜o usando (5) vemos que tambe´m vale
a equac¸a˜o (4). Portanto este x = x0 e´ uma soluc¸a˜o do sistema (1).
Uma vez encontrada uma soluc¸a˜o x0, vejamos que qualquer x ≡ x0 mod
m1m2 e´ soluc¸a˜o: de fato x = x0 + km1m2 implica x ≡ x0 mod m1 e x ≡
x0 mod m2.
Por outro lado, veremos que todas as soluc¸o˜es sa˜o dessa forma. Suponha
x soluc¸a˜o do sistema (1). Como x1 tambe´m e´ soluc¸a˜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 e´, existe ` tal que y = `m1. Por (7), m2 divide y =
`m1. Como m1 e m2 sa˜o primos entre si, m2 divide `, isto e´, existe k tal que
` = km2. Portanto y = km1m2 ≡ 0 mod m1m2, ou seja, x ≡ x0 mod m1m2,
como quer´ıamos provar.
Observac¸a˜o. A prova do teorema da´ um me´todo para encontrar soluc¸o˜es dos
tais sistemas.
Vejamos agora uma versa˜o ainda melhor do TCR:
Teorema Chineˆs do Restos (Versa˜o forte). Sejam m1, . . . , mk inteiros
≥ 2 dois a dois primos entre si (isto e´, mdc(mi,mj) = 1 sempre que i 6= j).
Sejam a1, . . . , ak inteiros quaisquer. Enta˜o o sistema
x ≡ a1 mod m1
x ≡ a2 mod m2
· · ·
x ≡ ak mod mk
(8)
possui uma soluc¸a˜o x = x0. Ale´m disso, um inteiro x e´ soluc¸a˜o do sistema
se e somente se
x ≡ x0 mod m1 · · ·mk.
2
Demonstrac¸a˜o. A prova e´ por induc¸a˜o no nu´mero k ≥ 2 de equac¸o˜es. Ja´
vimos que o teorema vale para 2 equac¸o˜es. Agora fixe k > 2 e suponha que
o teorema vale para k − 1 equac¸o˜es. Dados m1, . . . , mk dois a dois primos
entre si, e a1, . . . , ak quaisquer, considere o sistema formado apenas pelas
k − 1 primeiras equac¸o˜es em (8). Pela hipo´tese de induc¸a˜o, existe um b tal
que este subsistema e´ equivalente a uma u´nica equac¸a˜o, a saber,
x ≡ b modM, onde M = m1 · · ·mk−1.
Portanto o sistema inteiro (8) e´ equivalente a um sistema com duas equac¸o˜es:{
x ≡ b modM
x ≡ ak mod mk
Notando que M e mk sa˜o primos entre si, e usando que o teorema vale
para duas equac¸o˜es, temos que existe soluc¸a˜o x0. Ale´m disso, x e´ soluc¸a˜o
se e somente se x ≡ x0 mo´dulo Mmk = m1 · · ·mk1mk, como quer´ıamos
demonstrar.
Exemplo 3. Resolver x3 = 277 mod 360.
Note que 360 = 8× 9× 5, e esses treˆs nu´meros sa˜o primos entre si. Pelo
TCR–versa˜o forte, a equac¸a˜o e´ equivalente ao sistema
x3 ≡ 277 mod 8
x3 ≡ 277 mod 9
x3 ≡ 277 mod 5
Aı´ resolvemos na forc¸a bruta. . .
Prova dinaˆmica do Teorema Chineˆs dos Restos
Vamos dar uma outra prova do TCR, que esclarece o que acontece
quando m1 e m2 na˜o sa˜o primos entre si.
Sejam m1 e m2 inteiros ≥ 2 quaisquer. Considere um retaˆngulo de
lados m1 e m2, dividido em quadrados 1 × 1. Cada quadrado e´ descrito
por coordenadas (x, y) onde x e y sa˜o inteiros com 0 ≤ x ≤ m1 − 1 e
0 ≤ y ≤ m2− 1; veja a Figura 1. Considere o seguinte passeio no retaˆngulo:
• No tempo t = 0 comec¸amos no quadrado (0, 0).
• Se no tempo (inteiro na˜o-negativo) t estamos no quadrado (x(t), y(t))
enta˜o no tempo t+1 pulamos para o u´nico quadrado (x(t+1), y(t+1))
no retaˆngulo m1 ×m2 cujas coordenadas satisfazem
x(t+ 1) ≡ x(t) + 1 mod m1 e y(t+ 1) ≡ y(t) + 1 mod m2.
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 retaˆngulo 12 × 5. No tempo t = 13 estamos no quadrado
(1, 3).
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 e´
congruente a zero mo´dulom1 em2, isto e´, no mı´nimo mu´ltiplo comum dem1
e m2, chamemos p = mmc(m1,m2). Observe tambe´m que o tempo t = p e´
a primeira vez que visitamos um quadrado que ja´ tinha sido visitado antes.
(Isso acontece pois na˜o ha´ dois quadrados diferentes que pulem para um
mesmo quadrado.) A partir do tempo p, visitaremos os mesmos quadrados
de novo, e na mesma ordem. Ale´m disso, cada um desses quadrados e´
visitado periodicamente uma vez a cada p unidades de tempo.
No caso que m1 e m2 sa˜o primos entre si, temos p = m1m2. Mas esse
e´ o nu´mero total de quadrados no retaˆngluo; portanto visitaremos todos
os quadrados. Isto prova o Teorema Chineˆs dos Restos: Dados quaisquer
x0, y0, o sistema t ≡ x0 mod m1 e t ≡ y0 mod m2 tem uma soluc¸a˜o t0, e
as outras soluc¸o˜es sa˜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 sa˜o primos entre si, temos p < m1m2 e portanto
alguns quadrados jamais sera˜o visitados.
Observac¸a˜o. Imagine o retaˆ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 a`s arestas laterais do retaˆngulo, obtendo um
toro (superf´ıcie de uma rosquinha). Um v´ıdeo do passeio no toro esta´ aqui:
LINK YOUTUBE.
Observac¸a˜o. A prova acima tambe´m da´ a versa˜o forte do teorema, desde
que usemos um retaˆngulo de dimensa˜o maior. . .
4
Alguns comenta´rios sobre equac¸o˜es quadra´ticas
Proposic¸a˜o (Ra´ızes quadradas mo´dulo p). Se p > 2 e´ primo enta˜o para
qualquer a, a equac¸a˜o x2 ≡ a mod p cai em um dos treˆs casos:
a) ou na˜o tem soluc¸a˜o;
b) ou as soluc¸o˜es sa˜o da forma x ≡ 0 mod p;
c) ou as soluc¸o˜es sa˜o da forma x ≡ ±x0 mod p.
Demonstrac¸a˜o. Basta mostrar que se x e x0 sa˜o soluc¸o˜es da equac¸a˜o enta˜o
x ≡ ±x0 mod p. Se x0 e´ soluc¸a˜o enta˜o
0 ≡ a− a ≡ x2 − x20 ≡ (x− x0)(x+ x0) mod p
Suponha que x 6≡ x0 mod p. Enta˜o podemos multiplicar os dois lados da
equac¸a˜o acima pelo inverso multiplicativo mod p de x − x0 e obter 0 ≡
x+ x0 mod p. observar
que a “‘Lei
do Corte”
e´ falsa
quando o
mo´dulo na˜o
e´ primo.
Observac¸a˜o. Usando a proposic¸a˜o acima e a existeˆncia de inverso multipli-
cativo mo´dulo p primo, podemos mostrar que a fo´rmula de Ba´scara vale
mod p.
A proposic¸a˜o e´ falsa se o mo´dulo na˜o e´ primo; no exemplo seguinte
veremos que um nu´mero pode ter mais de duas ra´ızes quadradas mo´dulo 35
incongruentes entre si:
Exemplo 4. Resolver a equac¸a˜o x2 ≡ 11 mod 35.Pelo TCR, isto e´ equiva-
lente ao sistema {
x2 ≡ 11 ≡ 1 mod 5
x2 ≡ 11 ≡ 4 mod 7
Como 1 e 4 ja´ sa˜o quadrados em Z, pela proposic¸a˜o anterior este sistema e´ Como 5 e 7
sa˜o primos,
uma vez
encontradas
duas ra´ızes
quadradas
na˜o pre-
cisamos
procurar
outras
equivalente a {
x ≡ ±1 mod 5
x ≡ ±2 mod 7
Isso da´ 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 da˜o todas as soluc¸o˜es procuradas:
x ≡ ±9 mod 35 x ≡ ±16 mod 35.
5