INTRODUÇÃO À
RECIPROCIDADE QUADRÁTICA
GABRIEL BUJOKAS
Questão. Seja p um primo ímpar. Para quais valores de a a seguinte equação tem solução:
x2 ≡ a
(∗)
mod p
Definição 0.1. Seja p um primo ímpar, e a um inteiro. O símbolo de
Legendre é definido como:


0, se p divide a,
a
= 1, se a equação (∗) tem solução,

p

−1, caso contrário.
Hoje a gente vai aprender a calcular o símbolo de Legendre.
1. Raízes Primitivas
Antes de estudar o símbolo de Legendre, vai ser útil ter mais uma ferramenta: raízes primitivas.
Definição 1.1. Para a ∈ (Z/pZ)∗ , defina a ordem de a
ordp a = min{d > 0 | ad ≡ 1
mod p}
Exercício 1. Prove a propriedade básica da ordem:
ad ≡ 1
mod p =⇒ ordp a|d
Como ap−1 ≡ 1 mod p,
ordp a|p − 1
Definição 1.2. A gente chama a de raiz primitiva se ordp a = p − 1.
Exercício 2. Seja α ∈ (Z/pZ)∗ uma raiz primitiva. Prove que
{1, 2, . . . , p − 1} = {α0 , α1 , . . . , αp−2 }
Isso é, qualquer a ∈ (Z/pZ)∗ , existe um único 0 ≤ k ≤ p − 2 tal que
αk ≡ a mod p
Teorema 1.1. Se p é um primo ímpar, Z/pZ tem raiz primitiva.
Na seção 8 tem um exercício guiando uma demonstração desse teorema.
Date: Sexta Feira, 22 de Junho de 2012.
1
2
G. BUJOKAS
2. Calculando o símbolo de Legendre
Nessa seção, p é um primo ímpar.
Exercício 3. Prove as seguintes propriedades básicas do símbolo de Legendre.
0
(1) a ≡ a0 mod p =⇒ ap = ap
2
(2) ap = 1
(3) Use raízes primitivas para provar o Critério de Euler:
p−1
a
mod p
≡a 2
p
b
(4) ab
= ap
p
p p−1
(5) −1
= (−1) 2
p
Para calcular o símbolo de Legendre, nós precisamos de mais duas fórmulas:
Teorema 2.1.
p2 −1
2
= (−1) 8
p
Teorema 2.2 (Reciprocidade Quadrática). Seja p 6= q > 0 primos ímpares
positivos. Então
p−1 q−1
q
p
= (−1) 2 2
p
q
Exercício 4. Calcule os seguintes símbolos de Legendre.
37
−26
91
−13
,
,
,
89
41
101
53
3. A ideia
Vamos tentar provar o teorema 2.1. Vamos assumir o seguinte:
Hipótese (H). Existe ω ∈ Z/pZ, tal que ordp ω = 8.
Exercício 5. Assuma a hipótese (H). Seja y = ω + ω −1 ∈ Z/pZ. Mostre
que
(a) y 2 ≡ 2 mod p
(b) É claro que pelo item anterior, 2 é um resíduo quadrático. Mas vamos
ignorar esse fato, e continuar o argumento. Mostre que
2
p−1
y
≡
mod p
p
(c) p2 y ≡ y p ≡ ω p + ω −p mod p
(
ω + ω −1 , se p ≡ ±1 mod p
2
(d) p y ≡
ω 3 + ω −3 , se p ≡ ±3 mod p
(e) ω 3 + ω −3 = −(ω + ω −1 )
RECIPROCIDADE QUADRÁTICA
3
(f ) Conclua
p2 −1
2
= (−1) 8
p
Agora a gente tem que justificar a hipótese (H). Como (H) implica que 2
é um resíduo quadrático, (H) não é sempre verdade. O que fazer quando (H)
não é verdade? A ideia é introduzir formalmente um símbolo ω que satisfaz
ordp ω = 8
por definição. A gente vai aprender a formalizar esse processo na próxima
seção.
4. Corpos finitos
Um corpo k é um conjunto equipado com operações +, × satisfazendo
as regras usuais, tal que qualquer elemento não nulo de k tem um inverso
multiplicativo.
Exemplo 4.1. Esses são corpos: R, Q, C, Z/pZ.
Esses não são corpos: Z, Z/nZ, quando n não é primo.
Vamos usar a notação Fp = Z/pZ, para ressaltar que estamos pensando
em Z/pZ como um corpo.
A construção que a gente precisa é muito semelhante a construção dos
números complexos a partir dos números reais.
4.1. Dos números reais para os números complexos. Vamos relembrar
a construção dos números complexos. Nós começamos com os números reais
R, e introduzimos o símbolo i, e definimos
C = {a + bi | a, b ∈ R}
Nós definimos i2 = −1, e extendemos a multiplicação e soma dos reais para
o conjunto C.
A gente pode reinterpretar essa construção da seguinte maneira. Considere
o conjunto de polinômios R[x] com coeficientes reais. Observer que a soma
e multiplicação de poliníomios já são definidas! Agora a gente olha módulo
x2 + 1.
C = R[x]/(x2 + 1)
isso é: dois polinômios f e g são equivalentes se x2 + 1 | f − g.
Observe que qualquer polinômio f é equivalente módulo x2 + 1 ao polinômio ax + b para algum a, b ∈ R. E note também que a multiplicação e soma
definidas em R[x] coincidem com a soma e multiplicação usual em C.
Uma analogia útil nessa construção é a seguinte. O anél Z é muito semelhante ao anel k[x], onde k é um corpo. Por exemplo, o conceito de número
primo corresponde ao conceito de polinômio irredutível. Nesse contexto, o
teorema de fatoração única é verdade nos dois anéis!
A construção de
k[x]/(f (x))
é análoga a construção
Z/nZ
Além disso, Z/nZ é um corpo exatamente quando n = p um primo. O
teorema correspondente no contexto k[x] é o seguinte:
4
G. BUJOKAS
Teorema 4.1. Seja k um corpo, f (x) ∈ k[x] um polinômio irredutível. Então
F = k[x]/(f (x))
é um corpo. Nós chamamos F de extensão de k.
Exemplo 4.2.
C = R[x]/(x2 + 1)
é a extensão de R com um elemento i(= x) tal que i2 + 1 = 0.
4.2. Construção de corpos finitos. Nós vamos usar o teorema 4.1 para
k = Fp .
Exemplo 4.3. Vamos extender k = F5 para conter uma raiz cúbica de unidade
ω, isso é, ω 3 = 1, mas ω 6= 1. Note que isso implica ω 2 + ω + 1 = 0. Como
o polinômio x2 + x + 1 é irredutível em F5 [x] [por que?], o teorema acima
prova que
F = F5 [x]/(x2 + x + 1)
é um corpo, com um elemento 1 6= ω(= x) tal que ω 3 = 1.
Exemplo 4.4. O que ia acontecer se k já tivesse uma raiz cúbica da unidade?
Por exemplo, para k = F7 , o número 2 é uma raiz cúbica da unidade. Isso
quer dizer que
x3 − 1 = (x − 1)(x − 2)(x − 4)
Em particular,
x2
mod 7
+ x + 1 = (x − 2)(x − 4) não é irredutível.
Nós podemos usar essa construção para provar o seguinte teorema:
Teorema 4.2. Para qualquer primo p, e inteiro n > 1, existe um corpo F
que é uma extensão de Fp = Z/pZ que contém uma raiz n-ésima da unidade.
Por exemplo, se p = 5 e n = 3, então
F = F5 [x]/(x2 + x + 1)
Por outro lado, se p = 7 e n = 3, então
F = F7
já que 2 já é uma raiz cúbica da unidade.
Esses corpos construídos pelo teorema 4.2 são muito semelhantes a Fp .
Uma propriedade que eles têm em comum é a seguinte:
Lema 4.3 (Sonho de todo estudante). Seja Fp ⊂ F uma extensão de corpos.
Então
(a + b)p = ap + bp
Demonstração. O argumento é exatamente o mesmo usado para provar essa
identidade quando F = Fp . Use o binômio de Newton, e o fato que
p
p|
, se 0 < k < p
k
A observação é que p = 0 em qualquer extensão de Fp .
Exercício 6. Seja F a extensão de Z/pZ que contém a raiz oitava de unidade, ω. Use o argumento do exercício 5, no contexto do corpo F , para
provar o teorema 2.1.
RECIPROCIDADE QUADRÁTICA
5
5. Somas de Gauss
Vamos provar o teorema 2.2. A idéia da demonstração é muito parecida
com a demonstração do teorema 2.1.
Seja F a extensão de Z/pZ que contém a raiz q-ésima de unidade, ω.
Defina
X x
y=
ωx ∈ F
q
x∈Z/qZ
Expressões como essa são chamadas de somas de Gauss.
Exercício 7. Mostre as seguintes identidades (em F ):
y 2 = (−1)
y
Conclua
q−1
2
q
p−1 q−1
2
2
p−1
q
p
= (−1)
X x
yp =
ω px
q
x∈Fq
X p
px
=
(
ω px )
q
q
x∈Fq
p
=
y
q
p−1 q−1
p
q
2
2
= (−1)
q
p
6. Um problema mais geral
Questão. Quando a equação
x2 ≡ a mod n
A gente já aprendeu como resolver esse problema para n = p primo ímpar.
Teorema 6.1 (Teorema chinês dos restos). Seja n = pα1 1 pα2 2 . . . pαk k . Para
qualquer a1 , a2 , . . . , ak ∈ Z, mostré que existe x ∈ Z tal que
x ≡ a1
mod pα1 1
x ≡ a2
...
mod pα2 2
x ≡ ak
mod pαk k
Use o teorema chinês dos restos para mostrar:
Exercício 8. Seja n = pα1 1 pα2 2 . . . pαk k . Mostre que a equação
x2 ≡ a mod n
tem solução se, e somente se, as equações
x2 ≡ a mod pαi i
tem solução para todos i = 1, . . . k.
6
G. BUJOKAS
6.1. O caso n = pα , para p primo ímpar. A gente vai precisar de uma
ferramenta nova.
Exemplo 6.1. Considere a equação
x2 ≡ −1
mod 25
A gente começa resolvendo a equação módulo 5. Ela tem uma solução x = 2.
Vamos extender essa solução para módulo 25.
Vamos achar x ≡ 2 mod 5 tal que
x2 ≡ −1
mod 25
É fácil de achar esse x:
x≡2
mod 5 =⇒ x = 5z + 2
Substituindo em x2 + 1,
(5z + 2)2 + 1 ≡ 25z 2 + 20z + 5 ≡ 5(4z + 1)
mod 25
Essa equação é equivalente a
4z + 1 ≡ 0
z≡1
mod 5 ⇐⇒
mod 5
Por exemplo, z = 1 é uma solução, o que significa x = 7 é uma solução de
x2 ≡ −1
mod 25
A gente pode extender esse exemplo para a seguinte proposição:
Proposição 6.2. Se p é um primo ímpar que não divide a, e xk é tal que
x2k ≡ a mod pk
então existe xk+1 tal que
xk+1 ≡ xk
mod pk
x2k+1 ≡ a mod pk+1
Corolário 6.3. Seja p um primo ímpar, e a ∈ Z tal que p não divide a.
Então
a
= 1 ⇐⇒ x2 ≡ a mod pk , para qualquer k > 0
p
Exercício 9. Prove a proposição 6.2.
Observação. Nós podemos generalizar a proposição 6.2 para o seguinte lema:
Lema 6.4 (Lema de Hensel). Seja p um primo, e f (x) um polinômio. e
n, k ∈ Z tal que 0 ≤ 2k < n.
Se pk ||f 0 (xn ), e pn |f (xn ), então existe xn+1 tal que
xn+1 ≡ xn
mod pn−k
f (xn+1 ) ≡ 0
mod pn+1
Exercício 10. Prove o lema de Hensel 6.4.
RECIPROCIDADE QUADRÁTICA
7
6.2. O caso n = 2k . Considere a equação
x2 ≡ a mod 2k
(6.1)
para a ∈ Z ímpar.
Exercício 11. Mostre que a equação 6.1 tem solução se, e somente se,
(a) k = 1, ou
(b) k = 2, e a ≡ 1 mod 4, ou
(c) k ≥ 3 e a ≡ 1 mod 8.
Dica: Para o último item, use o lema de Hensel (ou uma indução como
na demonstração da proposição 6.2).
7. Algoritmo
Agora nós temos todas as ferramentas para resolver o seguinte problema:
Quando
ax2 + bx + c ≡ 0 mod n
têm solução?
A gente segue os seguintes passos:
(1) Complete quadrados e reduza para uma equação da forma
x2 ≡ a mod n
(2) Use o teorema chinês dos restos para reduzir
x2 ≡ a
mod pk
(3) Use o lema de Hensel para reduzir para os seguintes casos:
x2 ≡ a mod p, onde p é um primo ímpar,
x2 ≡ a mod 2k , para k = 1, 2 ou 3
(4) Use resíduos quadráticos para resolver as equações acima.
Exercício 12. Determine se as seguintes equações tem solução:
(a) x2 + 4x − 3 ≡ 0 mod 51
(b) 2x2 − 4x + 1 ≡ 0 mod 13
(c) x2 − x + 1 ≡ 0 mod 91
(d) x2 − 3x + 5 ≡ 0 mod 16
(e) x2 − 6x + 7 ≡ 0 mod 15
8. Apêndice: Demonstração da existência de raízes primitivas
Teorema. Se p é um primo ímpar, Z/pZ tem raiz primitiva.
Exercício 13. Vamos provar o teorema acima.
(a) Seja f (x) um polinômio de grau d. Mostre que a equação
f (x) ≡ 0
tem no máximo d soluções.
(b) Mostre que
xp−1 − 1 =
mod p
Y
a∈(Z/pZ)∗
(x − a)
8
G. BUJOKAS
(c) Para d|p − 1, mostre que
xd ≡ 1
tem exatamente d soluções.
(d) Mostre que
X
mod p
φ(d) = n
d|n
(e) Mostre que
#{a ∈ (Z/pZ)∗ | ordp a = d} = φ(d)
(f ) Conclua o teorema 1.1.
E-mail address: [email protected]