aula12_2010

Prévia do material em texto

A´lgebra A - Aula 12
Sistemas de congrueˆncias
Elaine Pimentel
Departamento de Matema´tica, UFMG, Brazil
2o Semestre - 2010
Equac¸o˜es lineares
ax ≡ b (mod n)
Se a possui um inverso α em Zn, enta˜o:
α(ax) ≡ αb (mod n)
x ≡ αb (mod n)
Em particular, se n e´ primo e a 6≡ 0 (mod n), enta˜o a equac¸a˜o
acima sempre tem (uma u´nica) soluc¸a˜o.
Equac¸o˜es lineares
Se mdc(a, n) = d 6= 1, a equac¸a˜o:
ax − ny = b
so´ tem soluc¸a˜o quando b e´ divis´ıvel por d .
Suponhamos enta˜o que d divide b. Escreveremos a = da′, b = db′
e n = dn′. Cancelando os d ’s:
a′x − n′y = b′
Ou seja,
a′x ≡ b′ (mod n′)
Observe que agora mdc(a′, n′) = 1, e essa equac¸a˜o sempre tem
soluc¸a˜o.
Exemplo
Seja 6x ≡ 4 (mod 8). Dividindo pelo mdc(6, 8) = 2, obtemos
3x ≡ 2 (mod 4)
Logo,
x ≡ 2 (mod 4) ou x = 2 + 4k
Duas possibilidades:
I k e´ par. Nesse caso, x ≡ 2 (mod 8) e 2 e´ uma soluc¸a˜o.
I k e´ ı´mpar (k = 2m + 1). Nesse caso, x ≡ 6 (mod 8) e 6 e´
outra soluc¸a˜o.
Equac¸a˜o linear possui mais de uma soluc¸a˜o!
Um exemplo astronoˆmico
Treˆs sate´lites passara˜o sobre o Rio essa noite. O primeiro a` uma
hora, o segundo a`s 4 horas e o terceiro a`s 8 horas da manha˜. O
primeiro leva 13 horas para completar uma volta em torno da terra,
o segundo 15 horas e o terceiro 19 horas. Determine quantas horas
decorrera˜o, a` partir de meia noite, ate´ que os treˆs sate´lites passem
ao mesmo tempo sobre o Rio.
Um exemplo astronoˆmico
x = nu´mero de horas quando os treˆs sate´lites passara˜o juntos sobre
o Rio. Enta˜o:
x ≡ 1 (mod 13)
x ≡ 4 (mod 15)
x ≡ 8 (mod 19)
Podemos re-escrever a primeira equac¸a˜o cmo x = 1 + 13t,
Substituindo a primeira equac¸a˜o na segunda, obtemos:
t ≡ 6 (mod 15)
Um exemplo astronoˆmico
Logo x = 79 + 195u. Substituindo essa equac¸a˜o na terceira:
u ≡ 1 (mod 19)
Logo,
x = 79 + 195u
= 274 + 3705v
Logo os sate´lites passara˜o juntos pela primeira vez 274 horas
depois da meia noite de hoje.
Algoritmo chineˆs do resto
A soluc¸a˜o de um sistema de muitas equac¸o˜es e´ obtida atrave´s da
soluc¸a˜o de va´rios sistemas de duas equac¸o˜es.
Considere enta˜o o sistema
x ≡ a (mod m)
x ≡ b (mod n)
Podemos re-escrever a primeira equac¸a˜o na forma:
x = a + my
Substituindo x na segunda equac¸a˜o, obtemos:
my ≡ (b − a) (mod n)
Sabemos que essa equac¸a˜o tem soluc¸a˜o se e somente se o
mdc(n,m) divide b − a.
Algoritmo chineˆs do resto
Vamos assumir que mdc(n,m) = 1. Seja α o inverso de m mo´dulo
n. Enta˜o:
y ≡ α(b − a) (mod n)
y = α(b − a) + nz
x = a + mα(b − a) + mnz
x = a(1−mα) + mαb + mnz
x = aβn + mαb + mnz
Teorema Chineˆs do resto. Sejam n1, . . . , nk inteiros positivos,
dois a dois primos entre si. Enta˜o o sistema
x ≡ a1 (mod n1)
...
x ≡ ak (mod nk)
sempre tem uma soluc¸a˜o u´nica em Zn1...nk .
Mo´dulos na˜o co-primos
Considere o sistema:
x ≡ 3 (mod 12)
x ≡ 19 (mod 8)
Da primeira equac¸a˜o, obtemos x = 3 + 12y . Substituindo isso na
segunda equac¸a˜o, temos 12y ≡ 16 (mod 8). Dividindo essa
equac¸a˜o por 4, obtemos 3y ≡ 4 (mod 2). Logo,
x ≡ 3 (mod 24)
Observe que 24 e´ o mmc entre 8 e 12...
Partilha de senhas
Senha s partilhada entre n pessoas: cada pessoa possui um
elemento (uma parte) da senha. Elemento: escolhido de um
conjunto S de n pares de inteiros positivos de modo que, para um
inteiro positivo k ≤ n previamente escolhido temos:
1. qualquer subconjunto de S com k elementos permite
determinar s facilmente;
2. e´ muito dif´ıcil determinar s conhecendo menos de k elementos
de S.
Partilha de senhas
Conjunto L de n inteiros positivos, dois a dois primos entre si.
Seja N o produto dos k menores nu´meros de L e M o produto
dos k − 1 maiores nu´meros de L. Dizemos que esse conjunto tem
limiar k se
N > s >M
Observe que essa condic¸a˜o implica que o produto de k ou mais
elementos de L e´ sempre maior que N e o produto de menos de k
elementos e´ sempre menor que M. O conjunto S sera´ formado
pelos pares da forma (m, sm) onde m ∈ L e sm e´ a forma reduzida
de s mo´dulo m. Observe que limiar k ≥ 1 implica s > m para
qualquer m ∈ L. Logo sm < s para qualquer m ∈ L.
Partilha de senhas
Suponhamos que sejan conhecidos t elementos, ≥ k :
(m1, s1), . . . , (mt , st). Vamos resolver o sistema de congrueˆncias:
x ≡ s1 (mod m1)
x ≡ s2 (mod m2)
. . .
x ≡ st (mod mt)
obtendo x0 como soluc¸a˜o. Pelo teorema chineˆs do resto,
x0 ≡ s (mod m1. . . . .mt)
Partilha de senhas
Observac¸o˜es:
1. E´ poss´ıvel escolher os mo´dulos de modo que fique
praticamente imposs´ıvel encontrar s atrave´s de uma busca.
2. E´ sempre poss´ıvel escolher um conjunto L que satisfac¸a todas
as condic¸o˜es.
Partilha de senhas
Exemplo. Digamos que em um banco ha´ 5 funciona´rios e pelo
menos 2 teˆm que estar presentes para que o cofre seja aberto.
Logo o conjunto L deve ter 5 elementos, e seu limiar deve ser 2.
Uma escolha poss´ıvel escolhendo apenas primos pequenos e´
L = {11, 13, 17, 19, 23}
O valor de s pode ser escolhido como sendo qualquer inteiro no
intervalo que vai de 23 a 143. Digamos s = 30. Enta˜o:
S = {(11, 19), (13, 17), (17, 13), (19, 11), (23, 7)}
Se os funciona´rios que possuem as senhas (17, 13) e (23, 7) esta˜o
no banco, para obter a senha e´ preciso resolver o sistema
x ≡ 13 (mod 17)
x ≡ 7 (mod 23)
A soluc¸a˜o e´ x = 30 + 391k ...
Exerc´ıcios propostos - Cap´ıtulo 7
1,2,4