MAT1310_TCR
5 pág.

MAT1310_TCR


DisciplinaMatemática Discreta4.178 materiais81.594 seguidores
Pré-visualização2 páginas
MAT1310 \u2013 Matema´tica Discreta \u2013 2012.1
Teorema Chine\u2c6s do Restos. Dados dois inteiros m1, m2 \u2265 2 primos
entre si (isto e´, mdc(m1,m2) = 1), e dados outros dois inteiros quaisquer
a1, a2, o sistema {
x \u2261 a1 mod m1
x \u2261 a2 mod m2 (1)
possui uma soluc¸a\u2dco x = x0. Ale´m disso, um inteiro x sera´ soluc¸a\u2dco do
sistema se e somente se x \u2261 x0 mod m1m2.
A conclusa\u2dco do Teorema tambe´m pode ser expressa assim: O conjunto
de soluc¸o\u2dces do sistema e´ sempre da forma {x0 + km1m2; k \u2208 Z}. Em
particular, a soluc¸a\u2dco e´ u´nica modm1m2.
Exemplo 1. Considere o sistema{
x \u2261 1 mod 2
x \u2261 5 mod 5
A primeira equac¸a\u2dco diz que x e´ \u131´mpar, enquanto a segunda diz que o d´\u131gito
das unidades de x e´ 0 ou 5. Portanto as soluc¸o\u2dces do sistema sa\u2dco 0, ±5, ±15
etc. Ou seja, x e´ soluc¸a\u2dco se e somente se x \u2261 5 mod 10. Em particular, a
soluc¸a\u2dco e´ u´nica mod 10, como previsto pelo Teorema Chine\u2c6s dos Restos.
Exemplo 2. Para ver que a hipo´tese mdc(m1,m2) = 1 e´ necessa´ria no
teorema, considere o sistema {
x \u2261 2 mod 4
x \u2261 3 mod 6
Esse sistema na\u2dco tem soluc¸a\u2dco. Por outro lado, o sistema{
x \u2261 0 mod 4
x \u2261 0 mod 6
tem soluc¸o\u2dces x = 0, ±12, ±24, . . . Pore´m a soluc¸a\u2dco na\u2dco e´ u´nica modm1m2 =
24.
Corola´rio. Suponha m1, m2 \u2265 2 primos entre si. Enta\u2dco temos x \u2261 a mod
m1m2 se e somente se valem as duas relac¸o\u2dces abaixo.{
x \u2261 a mod m1
x \u2261 a mod m2 (2)
Demonstrac¸a\u2dco. Dado qualquer inteiro a, o sistema (2) de equac¸o\u2dces em x
obviamente possui uma soluc¸a\u2dco x0 = a. Pelo TCR, todas as outras soluc¸o\u2dces
sera\u2dco congruentes a esta mod m1m2. Portanto vale (2) se e somente se
x \u2261 a mod m1m2.
1
Prova do TCR. Primeiro veremos que existe pelo menos uma soluc¸a\u2dco. 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\u2dces e reordenando temos
m1y1 \u2212m2y2 = a2 \u2212 a1. (5)
Agora, como mdc(m1,m2) = 1, sabemos [ja´ foi explicado antes] que a
equac¸a\u2dco (5) possui alguma soluc¸a\u2dco (y1, y2) \u2208 Z2. Fixe uma tal soluc¸a\u2dco e
defina x = x0 pela equac¸a\u2dco (3). Enta\u2dco usando (5) vemos que tambe´m vale
a equac¸a\u2dco (4). Portanto este x = x0 e´ uma soluc¸a\u2dco do sistema (1).
Uma vez encontrada uma soluc¸a\u2dco x0, vejamos que qualquer x \u2261 x0 mod
m1m2 e´ soluc¸a\u2dco: de fato x = x0 + km1m2 implica x \u2261 x0 mod m1 e x \u2261
x0 mod m2.
Por outro lado, veremos que todas as soluc¸o\u2dces sa\u2dco dessa forma. Suponha
x soluc¸a\u2dco do sistema (1). Como x1 tambe´m e´ soluc¸a\u2dco, temos que y = x\u2212x0
satisfaz
y \u2261 a1 \u2212 a1 \u2261 0 mod m1 (6)
y \u2261 a2 \u2212 a2 \u2261 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\u2dco primos entre si, m2 divide `, isto e´, existe k tal que
` = km2. Portanto y = km1m2 \u2261 0 mod m1m2, ou seja, x \u2261 x0 mod m1m2,
como quer´\u131amos provar.
Observac¸a\u2dco. A prova do teorema da´ um me´todo para encontrar soluc¸o\u2dces dos
tais sistemas.
Vejamos agora uma versa\u2dco ainda melhor do TCR:
Teorema Chine\u2c6s do Restos (Versa\u2dco forte). Sejam m1, . . . , mk inteiros
\u2265 2 dois a dois primos entre si (isto e´, mdc(mi,mj) = 1 sempre que i 6= j).
Sejam a1, . . . , ak inteiros quaisquer. Enta\u2dco o sistema\uf8f1\uf8f4\uf8f4\uf8f2\uf8f4\uf8f4\uf8f3
x \u2261 a1 mod m1
x \u2261 a2 mod m2
· · ·
x \u2261 ak mod mk
(8)
possui uma soluc¸a\u2dco x = x0. Ale´m disso, um inteiro x e´ soluc¸a\u2dco do sistema
se e somente se
x \u2261 x0 mod m1 · · ·mk.
2
Demonstrac¸a\u2dco. A prova e´ por induc¸a\u2dco no nu´mero k \u2265 2 de equac¸o\u2dces. Ja´
vimos que o teorema vale para 2 equac¸o\u2dces. Agora fixe k > 2 e suponha que
o teorema vale para k \u2212 1 equac¸o\u2dces. Dados m1, . . . , mk dois a dois primos
entre si, e a1, . . . , ak quaisquer, considere o sistema formado apenas pelas
k \u2212 1 primeiras equac¸o\u2dces em (8). Pela hipo´tese de induc¸a\u2dco, existe um b tal
que este subsistema e´ equivalente a uma u´nica equac¸a\u2dco, a saber,
x \u2261 b modM, onde M = m1 · · ·mk\u22121.
Portanto o sistema inteiro (8) e´ equivalente a um sistema com duas equac¸o\u2dces:{
x \u2261 b modM
x \u2261 ak mod mk
Notando que M e mk sa\u2dco primos entre si, e usando que o teorema vale
para duas equac¸o\u2dces, temos que existe soluc¸a\u2dco x0. Ale´m disso, x e´ soluc¸a\u2dco
se e somente se x \u2261 x0 mo´dulo Mmk = m1 · · ·mk1mk, como quer´\u131amos
demonstrar.
Exemplo 3. Resolver x3 = 277 mod 360.
Note que 360 = 8× 9× 5, e esses tre\u2c6s nu´meros sa\u2dco primos entre si. Pelo
TCR\u2013versa\u2dco forte, a equac¸a\u2dco e´ equivalente ao sistema\uf8f1\uf8f2\uf8f3
x3 \u2261 277 mod 8
x3 \u2261 277 mod 9
x3 \u2261 277 mod 5
A\u131´ resolvemos na forc¸a bruta. . .
Prova dina\u2c6mica do Teorema Chine\u2c6s dos Restos
Vamos dar uma outra prova do TCR, que esclarece o que acontece
quando m1 e m2 na\u2dco sa\u2dco primos entre si.
Sejam m1 e m2 inteiros \u2265 2 quaisquer. Considere um reta\u2c6ngulo de
lados m1 e m2, dividido em quadrados 1 × 1. Cada quadrado e´ descrito
por coordenadas (x, y) onde x e y sa\u2dco inteiros com 0 \u2264 x \u2264 m1 \u2212 1 e
0 \u2264 y \u2264 m2\u2212 1; veja a Figura 1. Considere o seguinte passeio no reta\u2c6ngulo:
\u2022 No tempo t = 0 comec¸amos no quadrado (0, 0).
\u2022 Se no tempo (inteiro na\u2dco-negativo) t estamos no quadrado (x(t), y(t))
enta\u2dco no tempo t+1 pulamos para o u´nico quadrado (x(t+1), y(t+1))
no reta\u2c6ngulo m1 ×m2 cujas coordenadas satisfazem
x(t+ 1) \u2261 x(t) + 1 mod m1 e y(t+ 1) \u2261 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\u2c6ngulo 12 × 5. No tempo t = 13 estamos no quadrado
(1, 3).
Equivalentemente, x(t) \u2261 t mod m1 e y(t) \u2261 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\u131´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\u2dco 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\u2dco primos entre si, temos p = m1m2. Mas esse
e´ o nu´mero total de quadrados no reta\u2c6ngluo; portanto visitaremos todos
os quadrados. Isto prova o Teorema Chine\u2c6s dos Restos: Dados quaisquer
x0, y0, o sistema t \u2261 x0 mod m1 e t \u2261 y0 mod m2 tem uma soluc¸a\u2dco t0, e
as outras soluc¸o\u2dces sa\u2dco exatamente os t\u2019s tais que t \u2261 t0 mod p. (Podemos
pensar que o passeio se estende indefinitamente no passado para incluir t\u2019s
negativos.)
No caso que m1 e m2 sa\u2dco primos entre si, temos p < m1m2 e portanto
alguns quadrados jamais sera\u2dco visitados.
Observac¸a\u2dco. Imagine o reta\u2c6ngulo m1 × m2 feito de borracha. A\u131´ colamos
a aresta de baixo com a de cima, obtendo um cilindro. Depois colamos os
dois c´\u131rculos correspondentes a`s arestas laterais do reta\u2c6ngulo, obtendo um
toro (superf´\u131cie de uma rosquinha). Um v´\u131deo do passeio no toro esta´ aqui:
LINK YOUTUBE.
Observac¸a\u2dco. A prova acima tambe´m da´ a versa\u2dco forte do teorema, desde
que usemos um reta\u2c6ngulo de dimensa\u2dco maior. . .
4
Alguns comenta´rios sobre equac¸o\u2dces quadra´ticas
Proposic¸a\u2dco (Ra´\u131zes quadradas mo´dulo p). Se p > 2 e´ primo enta\u2dco para
qualquer a, a equac¸a\u2dco x2 \u2261 a mod p cai em um dos tre\u2c6s casos:
a) ou na\u2dco tem soluc¸a\u2dco;
b) ou as soluc¸o\u2dces sa\u2dco da forma x \u2261 0 mod p;
c) ou as soluc¸o\u2dces sa\u2dco da forma x \u2261 ±x0 mod p.
Demonstrac¸a\u2dco. Basta mostrar que se x e x0 sa\u2dco soluc¸o\u2dces da equac¸a\u2dco enta\u2dco
x \u2261 ±x0 mod p. Se x0 e´ soluc¸a\u2dco enta\u2dco
0 \u2261 a\u2212 a \u2261 x2 \u2212 x20 \u2261 (x\u2212 x0)(x+ x0) mod p
Suponha que x 6\u2261 x0 mod p. Enta\u2dco podemos multiplicar os dois lados da
equac¸a\u2dco acima pelo inverso multiplicativo mod p de x \u2212 x0 e obter 0 \u2261
x+ x0 mod p. observar
que a \u201c\u2018Lei
do Corte\u201d
e´ falsa
quando o
mo´dulo na\u2dco
e´ primo.
Observac¸a\u2dco. Usando a proposic¸a\u2dco acima e a existe\u2c6ncia de inverso multipli-
cativo mo´dulo p primo, podemos mostrar que a fo´rmula de Ba´scara vale
mod p.
A proposic¸a\u2dco e´ falsa se o mo´dulo na\u2dco e´ primo; no exemplo seguinte
veremos que um nu´mero pode ter mais de duas ra´\u131zes quadradas mo´dulo 35
incongruentes entre si:
Exemplo 4. Resolver a equac¸a\u2dco x2 \u2261 11 mod 35.