1
Introdução
Definição 1 (Resto quadrático) Seja n um inteiro positivo. Um elemento x ∈ Un diz-se um
resto quadrático módulo n se ∃y ∈ Un tal que y 2 = x, ou seja, se existe y ∈ Z tal que (y, n) = 1
e y 2 ≡ x(mod n).
Ao conjunto dos restos quadráticos módulo n chamamos Qn
Exercício 1 Seja a ∈ Qn . Prova que o número de soluções em Un de x2 = a é o número de
soluções em Un de x2 = 1.
Lema 1 Qn é um subrupo de Un .
Demonstração.Como Un é finito, basta provar que é fechado para o produto. Sejam a e
b restos quadráticos módulo n. Sejam x e y tais que x2 = a e y 2 = b. Então (xy)2 = ab, logo
ab ∈ Qn e Qn é um subgrupo.
Exercício 2 Seja n > 2 tal que existe uma raíz primitiva módulo n. Prova que Qn é um grupo
cíclico de ordem
φ(n)
2 .
Definição 2 (Símbolo de Legendre) Seja p um primo ímpar e a ∈ Zn . O símbolo de Legendre de a é:

 0 se p|a



a
=
1 se a ∈ Qp

p


 −1 se a ∈ U \ Q
p
p
Lema 2 (Critério de Euler)
p−1
a
=a 2
p
Demonstração.Se a ∈ Qn , então existe x ∈ Un tal que a = x2 . Então, pelo pequeno teorema
p−1
p−1
de Fermat, a 2 = x2 2 = xp−1 = 1 = ap .
Se a ∈
/ Qn , seja g uma raíz primitiva e s tal que g s = a. s não pode ser par, porque então
2
a = g s/2 o que contradiz a hipótese de que a ∈
/ Qn .
Então a
p−1
2
= gs
p−1
2
s
. Como s é ímpar, s p−1
2 não é múltiplo de p − 1, logo g
p−1
2
não pode ser
1. Por outro lado, o quadrado desse número é 1 (pelo pequeno teorema de Fermat), logo tem de
ser −1 = ap e está demonstrado.
Se a = 0 o resultado é imediato.
1
Lema 3 (Lema de Gauss)
a
= (−1)l
p
onde a ∈ Up e l é a quantidade de j ∈ Up com j ≤ r tais que aj > r, com r =
p−1
2 .
Demonstração.Para x ∈ Up definimos |x| = x se x ≤ r e |x| = −x se x > r. Assim
verifica-se que |aj| quando 1 ≤ j ≤ r é uma reordenação de {1, ..., r}, porque 1 ≤ |aj| ≤ r e são
distintos, visto que |aj| = |ak| ⇒ (aj = ak ∨ aj = −ak) ⇒ (j = k ∨ j + k = n), mas são todos
menores ou iguais a r.
Assim ar .r! = (a.1).(a.2).(a.3).....(a.r) = (−1)l r!, logo ar = (−1)l ⇒
a
p
= (−1)l , a última
implicaão vem do critério de Euler.
Exercício 3 Seja p um primo ímpar.
2
p2 −1 /8
p = (−1)
Teorema 1 (Reciprocidade quadrática)
(p−1)(q−1)
p
q
4
= (−1)
q
p
n
Exercício 4 Se n ≥ 1, Fn = 22 + 1 é primo se e só se
3(Fn −1)/2 ≡ −1(mod Fn )
Demonstração do Teorema 1.
To be added, but it’s a useful result! :)
Teorema 2 Seja p um primo ímpar e s ≥ 1. Então a ∈ Z é quadrado módulo ps se e só se a é
quadrado módulo p.
Demonstração.Seja g uma raíz primitiva de ps .
Se a ∈ Qps , ∃x ∈ Z tal que pr |x2 − a ⇒ p|x2 − a ⇒ a ∈ Qp .
Se a ∈ Qp , a = x2 para algum x ∈ Up e x = g r para algum r, porque x ∈ Up ⇒ x ∈ Ups .
Então a = g 2r , logo a = (g r )2 , logo a ∈ Qps .
Exercício 5 Encontra as raízes quadradas de 6 módulo 54
2
Teorema 3 Seja a um inteiro ímpar. Então
1. a ∈ Q2
2. a ∈ Q4 se e só se a ≡ 1(mod 4)
3. a ∈ Q2e se e só se a ≡ 1(mod 8) para e ≥ 3.
Demonstração.Os casos (1) e (2) são imediatos. Para (3) usamos o facto, previamente
demonstrado, de que todo o elemento de U2e é da forma ±5i . Quadrando, vemos que os quadrados
de U2e são as potencias pares de 5, como 52 ≡ 1(mod 8) então todos os quadrados são 1 modulo
8. Como ambos os conjuntos são um quarto de U2e então são o mesmo.
Teorema 4 Seja n = n1 n2 ...nk onde os inteiros ni são coprimos dois a dois. Então a ∈ Qn se
e só se a ∈ Qni para todo o 1 ≤ i ≤ k.
Demonstração.Se a ∈ Qn , então existe x ∈ Z tal que n|x2 − a ⇒ ni |x2 − a para todo o i.
Se para todo o i existe xi ∈ Z tal que ni |x2i − a, então, pelo teorema chinês dos resíduos,
existe x ∈ Z tal que x ≡ xi (mod ni , logo n|x2 − a e a ∈ Qn .
Teorema 5 Seja a ∈ Un . a ∈ Qn se e só se
1. a ∈ Qp para todo o primo p ímpar que divide n, e
2. a ≡ 1(mod 4) se 22 ||n, e
3. a ≡ 1(mod 8) se 8|n.
(Repare-se que a segunda e terceira condição só são necessárias se 4|n.)
Demonstração.Pelo teorema 4, a ∈ Qn se e só se a ∈ Qpe para cada potência de primo que
divide n. Para p ímpar tal condição é equivalente a a ∈ Qp , pelo teorema 2, o que nos dá a
condição 1; para p = 2, pelo teorema 3, a ∈ Q2e é equivalente às condições (2) e (3).
Exercício 6 Sejam p e q primos distintos, tais que p ≡ q ≡ 1(mod 4) e
q
p
= 1. Seja h(x) =
(x2 − q)(x2 − p)(x2 − pq). Prova que o polinómio h não tem raízes inteiras mas que a congruência
h(x) ≡ 0(mod n) tem solução para todo o n ≥ 1.
3