equacao raizes primitivas

Prévia do material em texto

A congrueˆncia xn ≡ amod m
Comec¸arei com uma observac¸a˜o importante. Suponha que a e m sa˜o coprimos e que om(a) = e;
afirmo que para 1 ≤ k, l ≤ e− 1 vale que se
ak ≡ al mod m
enta˜o k e l sa˜o iguais.
De fato, suponha (sem perda de generalidade) que 1 ≤ l ≤ k ≤ e− 1. Enta˜o
ak ≡ al mod m
⇐⇒ akae−l ≡ alae−l mod m multiplicando por ae−l
⇐⇒ ae+k−l ≡ ae mod m
⇐⇒ aeak−l ≡ 1 mod m pois om(a) = e
⇐⇒ aeak−l ≡ 1 mod m
⇐⇒ ak−l ≡ 1 mod m pois om(a) = e
Como e e´ a ordem multiplicativa de a mo´dulo m, segue da u´ltima congrueˆncia que e e´ um divisor de
k − l. Por outro lado, ja´ que 1 ≤ l ≤ k ≤ e − 1 segue que 0 ≤ k − l ≤ e − l − 1 < e, e portanto
conclui-se que k − l = 0, ou seja, que k = l.
Agora suponha que g e´ uma raiz primitiva de m, ou seja, que sua ordem mo´dulo m e´ φ(m). Pelo
que acabamos de ver, as poteˆncias
g, g2, g3, . . . , gφ(m)
sa˜o todos distintas mo´dulo m (isto e´, se k 6= l enta˜o gk /≡ glmod m). Isso e´ importante nos ca´lculos
que seguem.
O resultado a seguir fornece um crite´rio que permite determinar imediatamente se a congrueˆncia
xn ≡ a mod m
possui alguma soluc¸a˜o, e no caso positivo diz o nu´mero de soluc¸o˜es.
Sua demonstrac¸a˜o fornece um me´todo para resolver esta equac¸a˜o. Este me´todo e´ descrito logo
apo´s o resultado principal.
Teorema 1 Seja m um inteiro positivo tal que exista uma raiz primitiva mo´dulo m. Sejam a um
inteiro tal que mdc(a,m) = 1, n um inteiro positivo, d = mdc(n, φ(m)) e t = φ(m)/d.
1. A congrueˆncia
xn ≡ a mod m (1)
possui soluc¸a˜o se e somente
at ≡ 1 mod m.
2. Caso tenha soluc¸a˜o, a equac¸a˜o (1) tem exatamente d soluc¸o˜es incongruentes mo´dulo m.
Demonstrac¸a˜o. Escolha uma raiz primitiva g de m; lembre que isso significa que g tem φ(m) como
ordem multiplicativa mo´dulo m.
Se
r1, r2, . . . , rφ(m)
sa˜o os restos da divisa˜o por m que sa˜o coprimos com m, enta˜o para cada ri existe um u´nico si com
1 ≤ si ≤ φ(m) tal que gsi ≡ rimod m.
Como mdc(a,m) = 1 temos que a ≡ rimod m para algum i, e por isso
a ≡ gsi mod m.
Daqui em diante s = si.
Se existe uma soluc¸a˜o de
xn ≡ a mod m
enta˜o esta soluc¸a˜o x e´ coprima com m (verifique). Por isso podemos escrever x ≡ gymod m e procurar
uma soluc¸a˜o y para a congrueˆncia
gny ≡ gs mod m. (2)
Por sua vez, se ny ≥ s enta˜o
gny ≡ gs mod m
⇐⇒ gφ(m)−sgny ≡ gφ(m)−sgs mod m
⇐⇒ gφ(m)−s+ny ≡ gφ(m) mod m
⇐⇒ gφ(m)gny−s ≡ gφ(m) mod m
⇐⇒ gny−s ≡ 1 mod m
pois gφ(m) ≡ 1mod m pelo Teorema de Euler (ou pelo fato de que g e´ raiz primitiva). Observe que
pedimos ny ≥ s apenas para ter um expoente ny− s na˜o negativo; se s ≥ ny pode-se fazer uma conta
ana´loga.
Agora, da u´ltima congrueˆncia
gny−s ≡ 1 mod m
segue que φ(m) divide ny − s por conta da seguinte propriedade:
• Se ak ≡ 1mod m enta˜o om(a) divide k.
Mas dizer que φ(m) divide ny − s e´ o mesmo que dizer que
ny ≡ s mod φ(m). (3)
Reciprocamente, se a equac¸a˜o (3) e´ va´lida enta˜o a equac¸a˜o (2) tambe´m vale; ou seja,
As equac¸o˜es (2) e (3) e teˆm as mesmas soluc¸o˜es.
Portanto podemos aplicar a teoria das congrueˆncias lineares para resolver (3), e portanto resolver
(1).
A equac¸a˜o (3) tem soluc¸a˜o se e somente se d = mdc(n, φ(m)) divide o termo constante s. Deste
modo a equac¸a˜o original
xn ≡ a mod m
tem soluc¸a˜o se e somente se d divide s.
Por outro lado, considere agora a congrueˆncia
at ≡ 1 mod m
onde t = φ(m)/d. Como a ≡ gsmod m, podemos reescreveˆ-la como
gst ≡ 1 mod mod m.
Como a ordem de g e´ φ(m), esta congrueˆncia vale se e somente se φ(m) divide st. Levando em conta
que φ(m) = d · φ(m)
d
= dt,
φ(m) | st ⇐⇒ dt | st ⇐⇒ d | s.
Resumindo, sa˜o equivalentes:
1. xn ≡ amod m tem soluc¸a˜o
2. d | s
3. at ≡ 1mod m.
Finalmente, quando ha´ soluc¸a˜o, vimos acima que ha´ uma correspondeˆncia entre as soluc¸o˜es de
xn ≡ amod m e yn ≡ smod φ(m). Como esta segunda congrueˆncia tem exatamente d soluc¸o˜es
incongruentes mo´dulo φ(m) 1, a congrueˆncia original tera´ d soluc¸o˜es incongruentes mo´dulo m.2
Corola´rio 1 Seja m um inteiro positivo tal que exista uma raiz primitiva mo´dulo m e seja d =
mdc(n, φ(m)) A congrueˆncia
xn ≡ a mod m
possui d soluc¸o˜es distintas mo´dulo m.
Me´todo para resolver a congrueˆncia (1).
Este me´todo vem da demonstrac¸a˜o do teorema acima.
1. Verifique se at ≡ 1mod m, pois ha´ soluc¸o˜es de (1) se e somente se esta congrueˆncia e´ va´lida.
2. Supondo que ha´ soluc¸o˜es, encontre uma raiz primitiva g de m (e´ por tentativa e erro; lembre
que basta testar poteˆncias gd com d divisor de φ(m)).
3. Determine o s tal que gs ≡ amod m. Novamente, e´ por tentativa e erro, mas e´ poss´ıvel que voceˆ
tenha encontrado uma soluc¸a˜o no item anterior.
4. Agora resolva a congrueˆncia linear
ny ≡ s mod φ(m).
que veio da congrueˆncia (2). Se as d soluc¸o˜es distintas mo´dulo φ(m) desta congrueˆncia acima
sa˜o
c1, c2, . . . , cd
enta˜o as d soluc¸o˜es soluc¸o˜es distintas mo´dulo m correspondentes de (1) sa˜o
gc1 , gc2 , . . . , gcd .
(... pode ser necessa´rio ainda “reduzi-las” mo´dulo m para que fiquem entre 1 e m− 1).
Um exemplo
(exerc´ıcio da lista 7) Considere a congrueˆncia
x12 ≡ 16 mod 17.
Neste caso m = 17 (primo), n = 12, a = 16,
d = mdc(n, φ(m)) = mdc(12, 16) = 4
e t = φ(m)/d = 16/4 = 4.
1Isso esta´ provado no livro do Polcino, mas tente provar voceˆ mesmo: isso vale para uma congrueˆncia linear qualquer
ax ≡ b mod m.
2Verifique.
Verificando se existe soluc¸a˜o: observando que 16 ≡ −1mod 17 temos
164 ≡ (−1)4 ≡ 1 mod 17
e portanto temos d = 4 soluc¸o˜es.
Ha´ um exerc´ıcio da lista que mostra que g = 3 e´ uma raiz primitiva de 17. Tem-se
a = 16 ≡ −1 ≡ 38 mod 17.
Portanto basta resolver
12y ≡ 8 mod 16.
Cancelando 4, obtemos
3y ≡ 2 mod 4.
Multiplicando por 3, que e´ o inverso de 3 mo´dulo 4, obtemos
y ≡ 6 ≡ 2 mod 4
e portanto as soluc¸o˜es inteiras sa˜o y = 2 + 4k, k ∈ Z.
Quatro soluc¸o˜es distintas mo´dulo 16 sa˜o 2, 6, 10, 14. Utilizando-as como expoentes da raiz primitiva
3 obtemos as quatro soluc¸o˜es distintas mo´dulo 17:
32 ≡ 9 mod 17, 36 ≡ 15 mod 17, 310 ≡ 8 mod 17, 314 ≡ 2 mod 17.
Portanto, a menos de somar mu´ltiplos de 17, as soluc¸o˜es de x12 ≡ 16mod 17 sa˜o 2, 8, 9, 15.