Congruências Quadráticas

Universidade Federal da Paraíba
Centro de Ciências Exatas e da Natureza

Departamento de Matemática
Mestrado Prossional em Matemática em Rede Nacional - PROFMAT
Congruências Quadráticas,
Reciprocidade e Aplicações em
Sala de Aula †
por
Leonardo Rodrigues de Araújo
sob orientação
Prof. Dr. Bruno Henrique Carvalho Ribeiro
Trabalho de Conclusão de Curso apresen-

tado ao Corpo Docente do Mestrado Pro-
ssional em Matemática em Rede Nacio-
nal PROFMAT CCEN-UFPB, como re-
quisito parcial para obtenção do título de
Mestre em Matemática.
Agosto/2013
João Pessoa - PB
†
O presente trabalho foi realizado com apoio da CAPES, Coordenação de Aperfeiçoamento de
Pessoal de Nível Superior.

Agradecimentos
- A Deus por proporcionar força, poder e proteção nos momentos mais desaa-
dores da vida.
- Ao Prof. Dr. Bruno Henrique Carvalho Ribeiro não somente pela orientação ex-
tremamente competente, mas, principalmente, pela prova inesquecível de dedicação,
incentivo e de incansável disposição em todas as etapas deste trabalho.
- À Profa. Dra. Miriam da Silva Pereira e ao Prof. Dr. José Anderson Valença
Cardoso pelas excepcionais contribuições para a evolução deste trabalho.
- Ao Prof. Dr. João Marcos Bezerra do Ó e à Profa. Me. Flávia Jerônimo

Barbosa pelo pulso rme em iniciar a coordenação deste curso proporcionando o
encorajamento necessário para vencer as diculdades.
- À minha família, em particular aos meus pais José Marcelino de Araújo e

Flávia Rodrigues de Meneses Araújo, o eterno reconhecimento pelo apoio, conselhos,
incentivos e afetividade.
- À Eneida Rodrigues de Araújo Coêlho e a Breno Rodrigues de Araújo pelo

estímulo.
- Ao Rvmo. Pe. Marisaldo Barbosa de Lima pelo incentivo e oração nos mo-
mentos de tribulação.
- A todos os colegas do curso de Mestrado, pela amizade e companheirismo

particularmente aos amigos e companheiros: Alex Cristophe Cruz da Silva, Gildeci
José Justino, Márcio Alves Marinho e Salatiel Dias da Silva.
- Aos professores da Pós−Graduação, pelos conhecimentos matemáticos cons-

truídos durante o curso.
- À Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

pelo apoio nanceiro.
Dedicatória
A Deus, fonte de inesgotável inspira-

ção.
A minha família, em especial a meus
pais José Marcelino de Araújo e Flávia
Rodrigues de Meneses Araújo.
Ao Prof. Dr. Bruno Henrique Carva-
lho Ribeiro.
Resumo
Neste estudo, vamos avaliar se a congruência x2 ≡ a (mod m), onde m é primo

e (a, m) = 1, apresenta ou não solução, destacando a importância dos Resíduos
Quadráticos e, consequentemente da cooperação do Símbolo de Legendre, do Critério
de Euler e do Lema de Gauss. Também, demonstraremos a Lei de Reciprocidade
Quadrática generalizando situações para números compostos, ou seja, o Símbolo de
Jacobi e suas propriedades. Apresentamos algumas propostas de atividades para o
Ensino Médio envolvendo o assunto abordado e suas possíveis aplicações, através de
uma linguagem compreensível aos alunos deste nível de ensino.
Palavras−Chaves: Congruência − Resíduos Quadráticos − Lei de Reciproci-

dade Quadrática.
v
Abstract
In this study, we evaluate if the congruence x2 ≡ a (mod m), where m is prime

and (a, m) = 1, has or not solutions, highlighting the importance of Quadratic
Residues and consequently the cooperation of the Legendre's Symbol, the Euler's
Criterion and the Gauss' Lemma. Also, we demonstrate the Law of Quadratic Reci-
procity generalizing situations for composite numbers, that is, the Jacobi's Symbol
and its properties. We present some proposals of activities for the High School in-
volving the subject matter and its possible applications, through an understandable
language for students of this level.
Keywords: Congruence − Quadratic Residues − Law of Quadratic Reciprocity.
vi
Sumário
1 Congruências Quadráticas 1
1.1 Resíduos Quadráticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Símbolo de Legendre e o Critério de Euler . . . . . . . . . . . . . . . 7
1.3 Lema de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2
1.4 O Símbolo de Legendre . . . . . . . . . . . . . . . . . . . . . . 14
p
2 Lei de Reciprocidade Quadrática 17

2.1 Provas da Lei de Reciprocidade Quadrática . . . . . . . . . . . . . . . 17
2.2 Símbolo de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3 Extraindo Raízes Quadradas módulo n . . . . . . . . . . . . . . . . . 36
3 Aplicações em Sala de Aula 40
3.1 Atividade 1 − A Utilização da Simbologia de Congruência e os Resí-
duos Quadráticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2 Atividade 2 − A Congruência x2 ≡ a (mod n) e a Criptograa: Mé-
todo de Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
A Coletânea: Provas da Lei de Reciprocidade Quadrática 48
B Pequeno Teorema de Fermat, Teorema de Wilson e Teorema do
Resto Chinês 56
B.1 Pequeno Teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . . 56
B.2 Teorema de Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
B.3 Teorema do Resto Chinês . . . . . . . . . . . . . . . . . . . . . . . . 59
Referências Bibliográcas 62
vii
Notações
≡ Congruente
6≡ Incongruente
| Divide
- Não Divide
(a, p) Máximo Divisor Comum de a e p
# Cardinalidade
Z Conjunto dos Números Inteiros
Zp Anel dos inteiros módulo p

a
Símbolo de Legendre para Reciprocidade Quadrática
p
bac Menor inteiro menor do que ou igual a a
hai
Símbolo de Jacobi
n
viii
Introdução
A Matemática é a rainha das Ciências, e a Teoria dos Números é a rainha da
Matemática. (Carl Friedrich Gauss)
Muitos matemáticos desempenharam um papel de destaque no desenvolvimento

da Teoria dos Números sendo que Euclides (cerca de 300 a.C), em Elementos de
Geometria, preservou o conhecimento matemático dos antigos gregos e Diofanto
(cerca de 250 a.C), em Arithmetica, representou o primeiro tratado sobre álgebra.
O que os tornam os fundadores da Teoria dos Números clássica.
Os Elementos de Euclides, especialmente nos livros VII, VIII e IX, apresentaram
uma riqueza de informações sobre as propriedades fundamentais da divisibilidade e
conceitos teóricos de papel central no estudo da Teoria dos Números, enquanto que
Diofanto desenvolveu métodos para obter soluções racionais para equações polino-
miais simples que podemos hoje denominar de equações diofantinas.
A Matemática na Europa teve uma renovação vigorosa após a Idade Média,
onde a Teoria dos Números por representar uma área particular da Matemática de
grande desenvolvimento apresenta matemáticos de destaque, como Pierre de Fermat,
Leonhard Euler, Adrien−Marie Legendre e Carl Friedrich Gauss que através de suas
contribuições signicativas aprimoraram a Teoria dos Números.
Sendo p um primo maior que 2, veremos que alguns elementos do conjunto
{0, 1, . . . , p − 1} possuem uma característica especial que abordaremos neste tra-
balho. Tais elementos são denominados resíduos quadráticos sendo, portanto, uma
forte ferramenta para o estudo da representação de inteiros. Mais especicamente,
dizemos que a é um resíduo quadrático módulo p se x2 ≡ a (mod p) para algum
x ∈ {0, 1, . . . , p − 1}.
Assim, a será um resíduo quadrático módulo p se a congruência tiver x2 ≡
a (mod p) solução, com (a, p) = 1. Veremos que no conjunto supracitado, é possí-
vel vericar que metade são considerados resíduos quadráticos, outra metade não.
Estudaremos métodos como o Símbolo de Legendre, Critério de Euler e Lema de
Gauss como forma de caracterizá−los e assim procurar soluções para as congruências
quadráticas.
ix
Introdução
O primeiro matemático a estudar reciprocidade quadrática foi Fermat, que tinha

a Matemática como uma atividade de lazer em uma época em que não existiam
revistas matemáticas. Fermat tinha um costume curioso de apresentar resultados
matemáticos em margens de livros que ele leu e em cartas de correspondências com
outros matemáticos. Ainda assim, esta forma peculiar de estudar matemática muito
contribuiu na direção da demonstração da reciprocidade quadrática.
A Lei de Reciporicidade Quadrática pode ser enunciada, em palavras, da seguinte
forma: se p e q são dois números primos distintos, de modo que p ≡ q ≡ 3 (mod 4),
temos q como resíduo quadrático módulo p, se, e somente se, p é não resíduos
quadrático módulo q , como também se p e q são dois números primos distintos, tais
que p ≡ 1 (mod 4), ou q ≡ 1 (mod 4), então q é resíduo quadrático módulo p, se, e
somente se, p é resíduo quadrático módulo q .
Fermat foi crucial na dedução do caráter quadrático de −1, ±2, ±3, mas foi
Euler que prosseguiu com o trabalho de provar as conjecturas de Fermat. Podemos
perceber em [9] que o autor considera Euler como um matemático de notável desta-
que no desenvolvimento histórico da Reciprocidade Quadrática por ser responsável
em provar e contestar grande parte das conjecturas de Fermat.
Devido ao grande interesse na Teoria dos Números e por começar a desenvolver
os trabalhos de Fermat, tendo contato com Christian Goldbach, Euler percebeu a
relação entre a Lei de Reciprocidade Quadrática e os estudos dos diversos binários
de certas formas quadráticas. Em [16], encontramos a armação de que a primeira
prova de Euler sobre a Lei de Reciprocidade Quadrática é conhecida hoje como
Critério de Euler.
Joseph Lagrange teve participação fundamental em inspirar Euler a continuar a
trabalhar na Teoria dos Números e especialmente na tentativa em provar a Lei de
Reciprocidade Quadrática completa que, com sua morte, Euler não pode encontrar
nenhuma prova concreta. Além disso, o Critério de Euler foi bastante útil para
Legendre e Gauss aprofundarem o problema dos resíduos quadráticos em contexto
geral dando um enfoque mais rigoroso.
Legendre não cou satisfeito em estudar apenas os resultados descobertos por
Fermat e Euler e por isso escreveu, em 1798, seu primeiro trabalho denominado
"Essal sur la Theorie des nombres" que se preocupou em interligar a Teoria dos Nú-
meros desde a Arithmetica de Diofanto ao Quadratorum Liber de Fibonacci. Dessa
maneira, inúmeros trabalhos sobre a Lei de Reciprocidade Quadrática permitiram
ao mundo conhecer uma notação ainda usada atualmente para simbolizar conveni-
entemente a Lei de Reciprocidade Quadrática de forma moderna, a saber, o símbolo
de Legendre.
Legendre não conseguiu colocar suas provas em um contexto teórico consistente,
mas desenvolveu um símbolo que levou a uma série de maneiras de provar a Re-
ciprocidade Quadrática. Em [4], encontramos a indicação de que isto foi essencial
x
Introdução
nos estudos de leis superiores de reciprocidade tendo o símbolo de Legendre como

origem para o desenvolvimento de Jacobi e símbolos de Hilbert.
Em 1801, Gauss, "o príncipe da Matemática", publicou seu trabalho inovador
"Disquisitiones Arithmeticae" introduzindo de forma clara e concisa a notação mo-
derna de congruência a ≡ b (mod n) sendo a e b múltiplo de n e n chamado módulo
de congruência. Nesta obra, Gauss trás uma demonstração do Teorema Fundamen-
tal da Aritmética e apresenta uma revisão de tudo que se conhecia em Teoria dos
Números até aquele momento.
Na seção IV desta obra, Gauss contempla a primeira prova completa de reci-
procidade quadrática, tesouro da Matemática do século XVIII e XIX, por meio
de indução cuja prova seguiu o raciocínio da prova de Legendre sendo descoberta
independentemente do trabalho de Legendre. Com isso, comprova−se que Euler
descobriu a Lei de Reciprocidade Quadrática cabendo a Legendre continuar a ten-
tar prová−la, mérito este atribuído a Gauss mesmo sendo uma primeira prova longa
e deselegante. Tal teorema recebeu posteriormente a denominação de Theorema
Aureum ("teorema de ouro").
Gauss denitivamente provou a Lei de Reciprocidade Quadrática, em 18 de Abril
de 1796, no entanto só conseguiu publicá-la em 1801, através de sua obra "Disqui-
sitiones Arithmeticae" e por se sentir atraído pela beleza do "Teorema de Ouro"
ele encontrou oito demonstrações, sendo a quinta demonstração considerada pelos
matemáticos como a mais elegante e direta.
Já na seção V de sua obra, Gauss destaca a teoria de formas quadráticas binárias
que segundo [2] trata−se de polinômios homogêneos de grau dois em duas variáveis,
sendo que esta seção representa mais da metade do livro tornando−se uma prova
da Lei de Reciprocidade Quadrática.
Em [14], Mota arma a existência de 2071 provas da Lei de Reciprocidade Qua-
drática das quais apresentaremos, no nal deste trabalho, uma listagem com 221
demonstrações contento os autores e os métodos. Contudo, é conveniente ressal-
tar que a prova considerada mais elementar é dada por Eisenstein, por meio de
argumentos geométricos.
Com a demonstração da Lei de Reciprocidade Quadrática, Gauss alcançou im-
portantes conquistas que expandiram os horizontes da Teoria dos Números princi-
palmente quando apresentou a primeira prova. Ele considerou que, a partir dessa
lei, haveria reciprocidades com graus superiores. Mesmo sendo provada há mais
de 200 anos ainda desperta grande interesse dos matemáticos. Em [4], estuda-se
a utilização em criptograa e no algoritmo de fatoração de inteiros que fazem uso
da lei da reciprocidade quadrática, além de os resíduos quadráticos serem bastante
utilizados em acústica.
Estruturamos este trabalho em partes. A primeira consta−se desta introdução.
Em seguida, a segunda parte compreende as congruências quadráticas estendendo−se
xi
Introdução
aos Resíduos Quadráticos, Símbolo de Legendre, Critério de Euler, Lema de Gauss

para que possamos determinar as soluções destas congruências como também reunir
subsídios para as demonstrações da Lei de Reciprocidade Quadrática e assim anali-
sar o Símbolo de Jacobi e suas propriedades para números compostos. Logo depois,
apresentamos atividades propostas para aperfeiçoar o conhecimento matemático dos
alunos, na quarta parte, e nalmente na parte pós-texto, apresentamos os apêndices
e as referências.
xii
Capítulo 1
Congruências Quadráticas
Neste capítulo, vamos examinar se um inteiro é ou não um resíduo quadrático

módulo p primo a partir das congruências quadráticas x2 ≡ a (mod p). Além
disso, exploraremos procedimentos ecazes para alcançar esta nalidade, tais como
o Critério de Euler, o Símbolo de Legendre com suas propriedades e o Lema de
Gauss. As demonstrações foram inspiradas em [7],[11],[18],[19],[21],[23],[24] e [27].
1.1 Resíduos Quadráticos

Consideremos a equação
ax2 + bx + c ≡ 0 (mod p) (1.1)
de modo que a, b, c ∈ Z, p é um primo ímpar e a 6≡ 0 (mod p). Podemos observar

que (a, p) = 1 e como p é ímpar teremos (4a, p) = 1. Assim, (1.1) será equivalente a
4a(ax2 + bx + c) ≡ 0 (mod p) que ao completarmos quadrados obtemos (2ax + b)2 −
(b2 − 4ac) ≡ 0 (mod p), e consequentemente ao fazermos y = 2ax + b e d = b2 −4ac,
teremos
y 2 ≡ d (mod p). (1.2)
Com isso, para encontrarmos solução para (1.1) é suciente descobrir a solução
de equações na forma
1
Congruências Quadráticas Capítulo 1
x2 ≡ a (mod p) (1.3)
pelo fato de se p | a obtemos a desinteressante equação x2 ≡ 0 (mod p), e por essa

razão x ≡ 0 (mod p) o que torna indispensável assumir que p - a para evitarmos
soluções triviais.
Exemplo 1.1 Resolva a congruência 8x2 + 5x + 1 ≡ 0 (mod 23).
Solução: Como (8, 23) = 1 e p = 23 é primo ímpar temos que (4· 8, 23) =
(32, 23) = 1, no qual ao multiplicarmos a congruência em questão e completar qua-
drados obtemos (16x + 5)2 + 32 − 25 ≡ 0 (mod 23) ⇒ (16x + 5)2 ≡ 16 (mod 23).
Com isso, encontramos 16x + 5 ≡ ± 4 (mod 23) onde ao resolvermos a congruência
linear 16x ≡ −1 (mod 23) temos x ≡ 10 (mod 23), enquanto que a partir da con-
gruência linear x ≡ −9 (mod 23) obteremos x ≡ 21 (mod 23). Dessa maneira, 10 e
21 são as únicas soluções incongruentes de 8x2 + 5x + 1 ≡ 0 (mod 23).
Então, caso a congruência (1.3) apresente solução terá exatamente duas soluções
incongruentes. Isso é exatamente o que vamos provar no teorema seguinte.
Teorema 1.1 Para p um primo ímpar e a um inteiro não divisível por p, a

congruência (1.3), caso tenha solução, tem exatamente duas soluções incongruentes
modulo p.
Demonstração: Consideremos que a congruência (1.3) tenha x1 como solução,

então podemos escrever que −x1 também será solução, pelo fato de
(−x1 )2 = x21 ≡ 0 (mod p).
Agora, mostremos que estas soluções x1 e −x1 são incongruentes módulo p.

Supondo que x1 ≡ −x1 (mod p) obtemos 2x1 ≡ 0 (mod p). Uma vez que, por
hipótese, p é primo e p não divide x1 temos que 2x1 ≡ 0 (mod p) é impossível, e x1
é incongruente a −x1 módulo p, sendo necessário mostrarmos que apenas existem
duas soluções incongruentes. Suponha agora que y é uma solução de x2 ≡ a (mod p).
Daí, temos y 2 ≡ a (mod p) e como x1 é solução podemos escrever x21 ≡ a (mod p).
Como x21 ≡ y 2 ≡ a (mod p), obteremos x21 − y 2 = (x1 + y) (x1 − y) ≡ 0 (mod p) que
2
resultará em p | (x1 + y) ou p | (x1 − y), o que implicará em y ≡ −x1 (mod p) ou

y ≡ x1 (mod p) e, por consequência, caso exista uma solução, existem exatamente
duas soluções incongruentes módulo p, e as demais soluções serão congruentes a uma
dessas duas.
Exemplo 1.2 Determine todas as soluções da congruência x2 ≡ 1 (mod 3).
Solução: Como 3 é um primo ímpar e 1 não é divisível por 3 poderá existir, pelo
Teorema 1.1, apenas duas soluções incongruentes módulo 3. Assim, observemos
que x1 = 2 satisfaz a congruência e −x1 = −2 também satisfaz essa congruência.
Portanto, x1 = 2 não é congruente a −x1 = −2 módulo 3 o que implicará em as
outras soluções são congruentes à x1 = 2 ou à x1 = −2 módulo 3, por existir apenas
duas soluções incongruentes módulo 3 para a congruência em questão. Com isso,
fazendo s uma solução diferente de x1 e −x1 obtemos s ≡ 2 (mod 3) ou s ≡ −2
(mod 3). Enm, todas as soluções serão dadas por s = 3k + 2 ou s = 3k − 2, para
k ∈ Z.
Denição 1.1 O conjunto dos inteiros {r1 , r2 ,r3 ,..., rv } é um sistema completo
de resíduos modulo p se:
(i) rt não for congruente a ru módulo p para t 6= u ;
(ii) para todo inteiro k , existe um rt , tal que k ≡ rt (mod p).
Denição 1.2 Sejam a e m inteiros com (a, m) = 1. Dizemos que a é um

resíduo quadrático módulo m se a congruência x2 ≡ a (mod m) tiver solução. Caso
x2 ≡ a (mod m) não tenha solução, dizemos que a não é um resíduo quadrático
módulo m ou que a é um resíduo não−quadrático.
Como 42 ≡ 6 (mod 10), então 6 é resíduo quadrado quadrático módulo 10, assim
como 122 ≡ 1 (mod 13) e assim 1 é resíduo quadrático módulo 13. Agora, consi-
deremos o primo 17 vamos obter os números que são resíduos quadráticos módulo
17. Para tanto, é suciente considerar os quadrados dos números 1, 2, 3, 4, . . . , 16
pelo fato destes números formarem um sistema reduzido de resíduos módulo 17.
Portanto,
3
12 ≡ 1 (mod 17) 92 ≡ 13 (mod 17)

22 ≡ 4 (mod 17) 102 ≡ 15 (mod 17)
32 ≡ 9 (mod 17) 112 ≡ 2 (mod 17)
42 ≡ 16 (mod 17) 122 ≡ 8 (mod 17)
52 ≡ 8 (mod 17) 132 ≡ 16 (mod 17)
62 ≡ 2 (mod 17) 142 ≡ 9 (mod 17)
72 ≡ 15 (mod 17) 152 ≡ 4 (mod 17)
82 ≡ 13 (mod 17) 162 ≡ 1 (mod 17)
Podemos observar que na coluna da esquerda das congruências acima temos os

quadrados dos números 1 até 16 e na coluna da direita apenas 8 números 1, 2, 4, 8, 9,
13,15 e 16. Portanto, estes números são todos os resíduos quadráticos módulo 17.
Também, é possível notar que estes números aparecem na metade superior da tabela
acima e que eles se repetem na metade inferior, cuja repetição ocorre a partir de 92 .
Tal curiosidade é proveniente da congruência (17 − k)2 ≡ k2 (mod 17) de vericação
imediata. Logo, ao termos um número primo ímpar qualquer podemos imaginar que,
dentre os elementos, 1, 2, 3,..., p − 1, que formam um sistema reduzido de resíduos
(p − 1) (p − 1)
módulos p, metade, ou seja, são resíduos quadráticos e restantes não
2 2
são. Isso é exatamente o que iremos demonstrar em seguida.
p−1
Teorema 1.2 Seja p um primo ímpar. No conjunto {1, 2, ..., p − 1}, são
2
p−1
resíduos quadráticos enquanto que não são.
2
Demonstração: Consideremos a congruência x2 ≡ ai (mod p), para i = 1, 2, 3, ...,
p − 1 com p primo onde desejamos obter todos os ai 0 s que são resíduos quadráticos
módulo p. Então, vamos considerar os quadrados dos números de 1 a p − 1 que ao
escrevermos 12 ≡ 1 (mod p) temos a1 = 1 como resíduo quadrático módulo p, mas
também −1 é solução pelo fato de (−1) ≡ p − 1 (mod p). Agora, pelo Teorema
1.1, temos que 1 e p − 1 são as únicas soluções incongruentes módulo p, e sendo
os números 1, 2, 3, . . . , p − 1 todos incongruentes módulo p, por formar um sistema
reduzido de resíduos módulo p, tem−se que 1 e p − 1 são as únicas soluções da
congruência x2 ≡ 1 (mod p) dentre os números 1, 2, 3, . . . , p − 1.
Ao tomarmos 22 , este será congruente a algum número r diferente de 1 e obvi-
4
amente (−2)2 também será congruente a esse número r. Uma vez que −2 ≡ p − 2
(mod p), pelo teorema 1.1, vericamos que 2 e p − 2 são as únicas soluções incon-
gruentes de x2 ≡ r (mod p) dentre os números 1, 2, 3,..., p − 1. Agora, ao tomarmos
32 que será congruente a algum número s diferente de 1 e de r percebe−se que
(−3)2 também será congruente a esse número s e como −3 ≡ p − 3 (mod p) , pelo
Teorema 1.1, tem−se que 3 e p − 3 são as únicas soluções incongruentes de x2 ≡ s
(mod p) dentre os números 1, 2, 3, . . . , p − 1 e assim observemos que temos 1,r e s
como resíduos quadráticos das respectivas congruências:
(1) x2 ≡ 1 (mod p) , que tem soluções (1, p − 1);

(2) x2 ≡ r (mod p) , que tem soluções (2, p − 2);
(3) x2 ≡ s (mod p) , que tem soluções (3, p − 3).
p−1
Ao prosseguir desta maneira teremos pares de soluções
2

p−1 p+1
(1, p − 1), (2,p − 2), (3, p − 3), ..., , ,
2 2
p−1
em que cada par é solução para uma dentre as congruências x2 ≡ ai (mod p),
2
p−1 p−1
relacionadas exatamente a dos números 1, 2, 3,. . . , p − 1 e, portanto os
2 2
p−1 p−1
números a'i s são os resíduos quadráticos e os restantes não são resíduos
2 2
quadráticos.
Exemplo 1.3 Sendo o primo 7, encontre, dentre os números {1,2,3,4,5,6}, os

três números que são resíduos quadráticos e os outros três que não são resíduos
quadráticos.
Solução:
12 ≡ 1 (mod 7)
22 ≡ 4 (mod 7)
32 ≡ 2 (mod 7)
42 ≡ 2 (mod 7)
5
52 ≡ 4 (mod 7)
62 ≡ 1 (mod 7)
Assim, os números que são resíduos quadráticos são 1,4 e 2, enquanto os números
que não que são resíduos quadráticos são 3,5 e 6.
Teorema 1.3 A congruência x2 ≡ −1 (mod p), para p primo, tem solução se, e
somente se, p = 2 ou p ≡ 1 (mod 4).
Demonstração: (⇒) Sendo p = 2, pode−se vericar que x = 1 é uma solução,

pois 12 ≡ −1 (mod p). Assim, é necessário supor agora que a congruência x2 ≡ −1
(mod p) apresenta solução e que p > 2. Elevando ambos os membros a potência
(p − 1)
tem−se:
2
( x2 ) ≡ (−1)
(p−1) p−1
2 2 (mod p)
e como x2 2 ≡ x(p−1) (mod p) podemos escrever, pelo Pequeno Teorema de Fer-

(p−1)
mat, (Anexo B), que
xp−1 ≡ 1 (mod p) ⇒ (−1) ≡ 1 (mod p)

p−1
2
(p − 1)
resultando no fato de ser par temos:
2
(p − 1)
= 2k ⇒ p − 1 = 4k ⇒ p = 4k + 1, k ∈ Z e, então p ≡ 1 (mod 4).
2
(⇐) Agora, é preciso encontrar uma solução para a congruência x2 ≡ −1 (mod p)
no momento em que p ≡ 1 (mod 4), onde p é um número primo ímpar que, através
do Teorema de Wilson, (Anexo B), podemos organizá−los como sendo
p−1 p+1
( 1 ·2 · 3 · · · j · · · )( · · · (p − j ) · · · (p − 2)(p − 1)) ≡ −1 (mod p).
2 2
O produto (p − 1)! está dividido em duas partes, cada uma com a mesma quan-
(p − 1)
tidade de fatores, ou seja, cada uma tem fatores que ao reescrever este
2
produto formando pares, cada fator j na primeira parte equivalerá ao fator (p − j )
na segunda parte podendo, pelo Teorema de Wilson, (Anexo B), ser escrito como:
6
(p−1)/2
j(p − j) ≡ −1 (mod p).
Y
j=1
Como j(p − j) ≡ −j 2 (mod p), pois jp − j 2 ≡ − j 2 (mod p) obtemos:
 2
(p−1)/2 (p−1)/2
j  (mod p).
Y Y
−1 ≡ −j 2 ≡ (−1)(p−1)/2 
j=1 j=1
(p − 1)
Mas, sendo p ≡ 1 (mod 4), então p é da forma 4k + 1, com k ∈ Z, e como
2
é par teremos
(p−1)/2
Y p−1
x= j= !,
j=1
2
que é uma solução de x2 ≡ −1 (mod p).

1.2 Símbolo de Legendre e o Critério de Euler

Adrien−Marie Legendre (1752−1833) desenvolveu um símbolo para vericar se
uma congruência do tipo x2 ≡ a (mod p), com p primo possui solução simplicando os
cálculos e sendo uma possibilidade de os termos resíduos quadráticos e não-resíduos
possam ser denotados de modo muito conveniente, bem como útil.
Denição 1.3 Seja p um inteiro primo ímpar. Para

um inteiro a deni−se o
a
Símbolo de Legendre de a módulo p e denotamos por como sendo
p
7
1 se p - a e a é um resíduo quadrático de p;


a 
= 0 se p | a;
p
−1 se p - a e a não é um resíduo quadrático de p.


É possível observar que na denição acima considera−se p ímpar uma vez que
qualquer número inteiro é um quadrado módulo 2. O próximo resultado, descoberto
por Euler possibilita o cálculo do Símbolo de Legendre.
Teorema 1.4 (Critério de Euler) Seja p > 2 um primo e a um inteiro. Então

a
≡ a 2 (mod p).
(p−1)
Demonstração: Para a ≡ 0 (mod p) o resultado é evidente, de modo que deve-

mos supor p - a. Com isso, ao considerarmos primeiramente que a = 1 verica−se
que a congruência x2 ≡ a (mod p) apresenta solução, pelo Teorema 1.1, e consequen-
temente teremos y 2 ≡ a (mod p) para algum y ∈ Z resultando em p divide (y 2 −a).
Mas, p não divide a, p não divide y 2 e portanto, p não divide y . Concluímos assim
que (y, p) = 1 e assim, pelo Pequeno Teorema de Fermat, (Anexo B), y p−1 ≡ 1
(mod p), podemos escrever que
(p−1) (p−1) (p−1)
y 2 ≡ a (mod p) ⇒ (y 2 ) 2 ≡ a 2 (mod p) ⇒ a 2 ≡ y p−1 (mod p)
⇒ a 2 ≡ 1 (mod p)
(p−1)

a
o que comprova o teorema para o caso em que = 1.
p

a
Agora, mostremos para o caso em que = −1, ou seja, a não é um resíduo
p
quadrático de p e se s é um dos inteiros de {1,2,3,· · ·,p − 1} podemos admitir que,
pela Teoria das Congruências Lineares, existe uma solução s0 de sx ≡ a (mod p),
com s0 também no conjunto {1,2,3, · · ·,p
− 1}. Mas, s e s0 devem ser distintos para
a
evitarmos que s2 ≡ a (mod p), já que = −1. Então, os inteiros entre a e p − 1
p
8
(p − 1)
podem ser divididos em pares, s e s0 , onde ss0 ≡ a (mod p) nos levará às
2
congruências
s1 s01 ≡ a (mod p)
s2 s0 2 ≡ a (mod p)
.. ..
. .
s (p−1) s0(p−1) ≡ a (mod p).
2 2
Ao multiplicarmos as congruências acima obtemos
(p−1)
s1 · s0 2 · s2 · s0 2 · . . . · s (p−1) · s0 (p−1) ≡ a 2 (mod p)
2 2
que representa um rearranjo de 1 · 2 · 3 · . . . · (p − 1) resultando em (p − 1)! ≡

a 2 (mod p) e, teremos, pelo Teorema de Wilson, (Anexo B), a 2 ≡ −1 (mod p)
(p−1) (p−1)
se referindo
ao Critério de Euler quando a não é um resíduo quadrático, ou seja,
a
= −1.
p

Exemplo 1.4 Vericar que a = 3 é um resíduo não quadrático módulo 7, mas é

resíduo quadrático módulo 11.
Solução: Pelo Critério de Euler é possível escrever que

3
= 3 2 ≡ −1 (mod 7);
(7−1)
7

3
= 35 = 33 · 32 ≡ 5(−2) ≡ 1 (mod 11).
(11−1)
=3 2
11
Vamos introduzir algumas propriedades que permitem o cálculo do Símbolo de

Legendre.
Teorema 1.5 Seja p primo ímpar e a, b, c ∈ Z. Então, pelo Critério de Euler e

pela denição do Símbolo de Legendre, seguem as seguintes propriedades:
9

a b
1. se a ≡ b (mod p), então = ;
p p
a2

2. = 1 se p - a;
p

ab a b
3. = se p - a e p - b.
p p p
1 se p ≡ 1 (mod 4)

−1
=
(p−1)
4. = (−1)
−1 se p ≡ 3 (mod 4)
2
p
Demonstração: Para a propriedade 1 é suciente observar que

a b
(mod p),
(p−1) (p−1)
≡a 2 ≡b 2 ≡
p p
enquanto na propriedade 2 é evidente que a é resíduo quadrático de p pelo fato de,

pelo Pequeno Teorema de Fermat, (Anexo B), (a2 ) 2 ≡ a(p−1) ≡ 1 (mod p). Já as
(p−1)
propriedades 3 e 4 são consequências imediatas do Critério de Euler, pois

ab
(mod p).
(p−1)
≡ (ab) 2
p
Mas como
=a
(p−1) (p−1) (p−1)
(ab) 2 2 b 2
podemos escrever que

a b
(mod p) e
(p−1) (p−1)
≡a 2 ≡ b 2 (mod p)
p p
concluindo que

ab a b
=a (mod p).
(p−1) (p−1) (p−1)
= (ab) 2 2 b 2 ≡
p p p
Já a propriedade 4 possibilita
investigar todos os primos para os quais
− 1 são
−1 −1
resíduos quadráticos, onde ≡ (−1) 2 (mod p) signicando que seria
(p−1)
p p
10
(p − 1) (p − 1)
igual a 1 quando for par e igual a −1, quando for ímpar. Então,
2 2
se p é um primo ímpar, existem apenas duas possibilidades para p em termos de
congruência módulo 4 ou p ≡ 1 (mod 4) ou p ≡ 3 (mod 4) e se p ≡ 1 (mod 4)
(p − 1)
teremos p − 1 divisível por 4 e será par. Agora, se p ≡ 3 (mod 4), existe k
2
tal que p − 3 = p − 1 − 2 = 4k e, desse modo p −1 = 4k
+ 2 = 2(2k + 1) implicando
(p − 1) −1
em ímpar. Então, para p ≡ 1 (mod 4), = 1 e, para p ≡ 3 (mod 4),
2 p
−1
= −1.
p

Assim, através da propriedade 3 do Teorema 1.5, [21] revela que o produto de
dois resíduos quadráticos é um resíduo quadrático, que o produto de dois números
que não são resíduos quadráticos é um resíduo quadrático e que o produto de um que
não é resíduo quadrático por um que é resíduo quadrático não é resíduo quadrático.
1.3 Lema de Gauss

Nessa seção, analisaremos o resultado a seguir, conhecido como
Lema de Gauss,
a
que segundo [7], trata−se de um método capaz de determinar para todo primo
p
ímpar p e todo número natural a, tal que (a, p) = 1.
Lema 1.1 (Lema de Gauss) Sejam p um primo ímpar e a um inteiro não−divisível

por p. Então

a
= (−1)r ,
p
onde r é a quantidade de resíduos positivos módulo p dos números

p−1
a, 2a, 3a, . . . , a, (1.4)
2
p
que são maiores que .
2
Demonstração: Inicialmente observe que não podemos ter ab ≡ 0 (mod p) para
11
b ∈ {1, 2, · · · , p−1
2
} pois, caso contrário, teríamos p|ab, o que é uma contradição por
b < p e p - a. Com isso os elementos de (1.4) serão incongruentes dois a dois módulo
p, pois se ab ≡ ac (mod p), para b, c ∈ 1, 2, . . . , 2 obtemos p | (b − c)a, mas se
p−1

p - a temos p | (b − c), ou seja, b ≡ c (mod p) o que é impossível.

Agora, ao analisar a reordenação de (1.4) temos
(p − 1)
r1 , r2 , . . . , ri , s1 , s2 , . . . , sj , com i+j = , (1.5)
2
formada por resíduos positivos módulo p, em que os inteiros rk são menores que
(p − 1) (p − 1)
e os inteiros st maiores que .
2 2
Sendo
{r1 , r2 , . . . , ri , p−s1 , p−s2 . . . , p−sj } (1.6)
obtemos um conjunto de elementos positivos menores que p, e então quaisquer dois

elementos de (1.6) são incongruentes módulo p. Por outro lado, quando k 6= t, temos
p − sk 6≡ p − st (mod p) e rk 6≡ rt (mod p) pelo fato de os elementos de (1.4) serem
incongruentes módulo p. Por outro lado, temos p−sk 6≡ rt (mod p). Caso contrário,
st + rk ≡ 0 (mod p) e como cada elemento de (1.5) é congruente módulo p com
algum elemento de (1.4), obtemos
(p − 1)
st + rk ≡ ab + ac ≡ (b + c)a ≡ 0 (mod p), b, c ≤ .
2
Por hipótese, p - a e então
(p − 1) (p − 1)
p | (b + c) ≤ + = p − 1.
2 2
Isto é impossível, pois os elementos de (1.6) são incongruentes módulo p dois a dois.
Note−se que (1.6) tem p − 1 elementos positivos e menores que p. Isto implica que
(p − 1)
os elementos de (1.6) são forçosamente os elementos 1, 2, . . . , .
2
Multiplicando todos os elementos de (1.6) obtemos
j i
p−1
!(mod p).
Y Y
(p − sk ) · rt ≡
k=1 t=1
2
12
Como p−sk ≡ −sk (mod p), vem que
j i
p−1
! (mod p),
Y Y
r
(−1) (sk ) · rt ≡
k=1 t=1
2
e como cada elemento de (1.5) é congruente módulo p com algum elemento de (1.4),
a congruência anterior é equivalente a

p−1 p−1
(−1) !a ! (mod p).
(p−1)
r 2 ≡
2 2
Com isso, da congruência anterior resulta que (−1)r a 2 ≡

1 (mod p) e, como
(p−1)

a a
≡ a 2 (mod p), (Critério de Euler), conclui− se que
(p−1)
= (−1)r .
p p

Vamos agora ilustrar a demonstração do Lema de Gauss. Portanto, ao conside-

rarmos o caso particular em que a = 5 e p = 17 teremos que calcular os menores
(17 − 1)
resíduos positivos módulo 17 dos seguintes múltiplos de 5, uma vez que 8 = :
2
1 · 5, 2 · 5, 3 · 5, 4 · 5, 5 · 5, 6 · 5, 7 · 5 e 8 · 5. Então,
1 · 5 ≡ 5 (mod 17) 5 · 5 ≡ 8 (mod 17)

2 · 5 ≡ 10 (mod 17) 6 · 5 ≡ 13 (mod 17)
3 · 5 ≡ 15 (mod 17) 7 · 5 ≡ 1 (mod 17)
4 · 5 ≡ 3 (mod 17) 8 · 5 ≡ 6 (mod 17)
Podemos vericar que dentre estes resíduos, que são 1,3,5,6,8,10,13 e 15, apenas
17
cinco, 1,3,5,6 e 8, são menores do que , e consequentemente ao tomarmos os
2
que são maiores, ou seja,10,13 e 15 e ao considerarmos os números 17−10, 17−13 e
17−15, obtemos 7,4 e 2, respectivamente que associando com 1,3,5,6 e 8 constituem
todos os números de 1 a 8.
Desse modo, na demonstração do Lema de Gauss deveremos fazer o que foi

a
feito acima com p primo ímpar qualquer para provarmos que (−1)r = , onde r
p
13
(p − 1)
representa o número de resíduos positivos de 1· a, 2 · a, 3· a, · · · , · a que são
2
maiores que p. Partindo de caso particular r = 5 tem−se

5
= (−1)5 = −1
17
o que está coerente com o Critério de Euler, uma vez que

5
=5 ≡ 58 ≡ 52 · 52 · 52 · 52 ≡ 8 · 8 · 8 · 8 ≡ 16 ≡ −1 (mod 17).
(17−1)
2
17

2
1.4 O Símbolo de Legendre
p

2
Nesta seção, vamos determinar uma fórmula válida para .
p
Teorema 1.6 Para p um primo ímpar, temos

1 se p ≡ ± 1 (mod 8)

2
=
p −1 se p ≡ ± 3 (mod 8)
Demonstração: Usando o Critério de Euler, vamos vericar que 2 ≡ 1

(p−1)
2
(mod p) se, e somente se, p ≡ ± 1 (mod 8). Assim, observemos que

p−1 p−1
2 ! =2 2 = 2 · 4 · . . . · (p − 1).
(p−1) (p−1)
2 1· 2· 3· . . . ·
2 2

2
Agora, consideremos, pelo Critério de Euler, que = 2 2 (mod p) e, portanto
(p−1)
(p − 1)
∗ Se é par.
2

p−1
2 2 ! = 2 · 4 · . . . · (p − 1)
(p−1)
14
p−1 p+3
(2 · . . . · ) ( · . . . · (p − 3) · (p − 1))
= | {z 2 } | 2 {z }
p−1 p−1
f atores f atores
4 4

p−1 p−3
≡ 2· . . . · ( ) · ((− )· . . . · (−3)· (−1)) (mod p)
2 2
p−1 p−3 (p−1)
≡ (2· . . . · )· (1· 3 · . . . · )(−1) 4 (mod p)
2 2
p−1
≡ (−1) 4 ! (mod p).
(p−1)
(p − 1)
∗ Se é ímpar.
2

p−1
2 ! = 2 · 4 · 6 · . . . · (p − 1)
(p−1)
2
2
p−3 p+1
(2· . . . · ) ( ·. . . · (p − 3)· (p − 1))
2 } | 2
= | {z {z }
p−3 p+1
f atores f atores
4 4
p−3 p−1
≡ (2· . . . · )· ((− )· . . . · (− 3) · (− 1)) (mod p)
2 2
p−3 p−1 (p−1)
≡ (2· . . . · )· (1· 3 · . . . · )(−1) 4 (mod p)
2 2
p−1
≡ (−1) 4 ! (mod p).
(p−1)
2
Logo,

p−1 p−1 (p − 1)
2 ! ≡ (−1) 4 ! (mod p) se é par
(p−1) (p−1)
2
2 2 2

p−1 p−1 (p − 1)
2 ! ≡ (−1) 4 ! (mod p) se é ímpar.
(p−1) (p−1)
2
2 2 2

p−1
Ao cancelarmos ! nas congruências acima, temos
2

(p − 1)
(p−1)
(−1) (p−1)
 4 (mod p) se é par
2 2 = 2
(p − 1)
(−1) (p−1) (mod p) se é ímpar
 4
2
15
= (−1) (mod p).

(p−1)(p+1)
8
Ao analisarmos os diversos casos possíveis para p módulo 8, obtemos

(p − 1) (p − 1)
2 porque e são pares
(p−1)
p ≡ 1 (mod 8) ⇒ = 1

 2
2 4




p ≡ 3 (mod 8) ⇒ 2 (p−1) (p − 1) (p + 1)
= −1 porque e são ímpares

 2
2 (p−1)
2 4
=2 2 = (p − 1) (p − 1)
p 
p ≡ 5 (mod 8) ⇒ 2 2 = −1 porque
(p−1)
é par e é ímpar
2 4




 p ≡ 7 (mod 8) ⇒ 2 (p−1) (p − 1) (p + 1)
= 1 porque é ímpar e é par.

 2
2 4

Com o auxílio do Teorema 1.5 pode−se vericar que se p é um número primo

ímpar teremos que

−2
= 1⇔ p ≡ 1 (mod 8) ou p ≡ 3 (mod 8).
p
16
Capítulo 2
Lei de Reciprocidade Quadrática
Neste capítulo, iniciaremos uma investigação da Lei de Reciprocidade Quadrá-

tica, um dos primeiros resultados da Teoria dos Números Moderna, conjecturada
por Euler e por Legendre, na primeira metade do século XVIII. No entanto, Gauss
forneceu a primeira demonstração e, ao longo de sua vida, encontrou outras demons-
trações. Também o estudo dessa lei foi construído por meio de várias demonstrações
inspiradas em [6],[7],[8],[10],[11],[15],[18],[20],[21],[22] e [25], atribuindo um destaque
ao estudo do Símbolo de Jacobi para inteiros módulo de um número composto e,
em particular, a resolução de raízes quadradas módulo n.
2.1 Provas da Lei de Reciprocidade Quadrática
Teorema 2.1 Se p e a são números ímpares diferentes, em que p é primo e não

divide a, então,
a
= (−1)M
p
onde
0
a 2a pa (p − 1)
M= + + ··· + e p0 = .
p p p 2
Demonstração: O Algoritmo da Divisão permite determinar os menores resí-

duos positivos de a, 2a, 3a,. . .,p0 a por meio das seguintes divisões:
17
Lei de Reciprocidade Quadrática Capítulo 2

a
a=p + r1
p

2a
2a = p + r2
p

3a
3a = p + r3
p
..
.
p0 a

0
pa=p + rp0
p
em que r1 , r2 , ..., rp0 são, respectivamente, os restos da divisão por p dos números
a, 2a, 3a,. . .,p0 a. Ao somarmos, membro a membro, as p0 igualdades acima obtemos
0
0 a 2a pa
(1 + 2 + 3 + ... + p )a = p ( + + ··· + ) +r1 + r2 + ... + rp0
p p p
ou ainda, ao colocarmos pelo Lema de Gauss (Lema 1.1), B = b1 + b2 + . . . + bh e

C = c1 + c2 + . . . + ck , teremos r1 + r2 + ... + rp0 = B + C ; e, então,
(p2 − 1)
a = pM + B + C . (2.1)
8
Mas, como os números b1 , b2 , . . . , bh , p − c1 , p − c2 , . . . , p − ck são, a menos da
ordem, os números 1, 2, 3, . . . , p0 pode−se escrever que
(p2 − 1)
1 + 2 + . . . + p0 = = b1 + b2 + . . . + bh + rp − (c1 + c2 + . . . + ck )
8
e consequentemente
(p2 − 1)
=−B + rp + C. (2.2)
8
Ao subtrairmos, membro a membro, as equações (2.1) e (2.2) obtemos para
M ≥r
(p2 − 1)
(a − 1) = p(M − r) + 2B (2.3)
8
18
e, para r > M
(p2 − 1)
(a − 1) = p(r − M ) + 2B. (2.4)
8
(p2 − 1)
Dessa maneira, como a e p são ímpares, por hipótese, o termo (a − 1)
8
será par o que resultará em p(M − r) também será par pelo fato desta diferença
ser par por serem ambos pares ou ambos ímpares. Logo, o Lema de Gauss permite
escrever que

a
= (−1)M
p
já que M e r apresentam a mesma paridade.

O Teorema 2.1 nos permite fornecer uma demonstração alternativa do Teorema

1.6 apresentado no Capítulo anterior.
Demonstração: Fazendo uso

das
notações
dademonstração
do Teorema 2.1,
2 4 p−1
tomamos a = 2, temos M = + + ... + = 0.
p p p
Da equação (2.3), obtemos
p2 − 1
≡ − pr (mod 2).
8
p2 − 1
Logo, r será par ou ímpar de acordo com é par ou ímpar, respectivamente
8
2 p2 −1
e assim, pelo Lema de Gauss, = (−1)M = (−1) 8 .
p

Exemplo 2.1 Mostre que a equação diofantina X 2 − 13Y = 5 não apresenta

soluções.
Solução: Caso essa equação diofantina possua alguma solução 5 será resíduo
quadrático módulo 13, e então
19

5 10 15 20 25 30
M= + + + + + = 5.
13 13 13 13 13 13
Portanto,

5
= (−1)M = (−1)5 = −1,
13
resultando em que 5 não é resíduo quadrático módulo 13.
Agora, vamos provar a Lei de Reciprocidade Quadrática. O próprio Gauss pro-

porcionou pelo menos 8 demonstrações e a literatura abrange várias dessas, atri-
buindo ao matemático alemão Ferdinand Gotthold Max Eisenstein (1823−1852) a
origem da demonstração que apresentaremos a seguir.
Teorema 2.2 (Lei de Reciprocidade Quadrática de Gauss) Sejam p e q dois

números primos ímpares distintos, então

p q
= (−1) 2 2 .
p−1 q−1
q p
Demonstração: Usando argumentos geométricos, consideremos um sistema re-

tangular de coordenadas. Marquemos sobre o eixo das abscissas os pontos dis-
(p − 1)
tantes 1, 2, . . . , unidades da origem A, e sobre o eixo das ordenadas, os
2
(q − 1)
pontos distantes 1, 2, . . . , unidades de A além de marcarmos os pontos de
2
p p q q
vértice A = (0, 0); B = ( , 0); C = ( , ) e D = (0, ) e, em seu interior,
2 2 2 2
(p − 1)
os pontos pertencentes ao produto cartesiano dos conjuntos {1, 2, 3, . . . , }
2
(q − 1)
e {1, 2, 3, . . . , } de acordo com a gura (2.1).
2
É possível vericar que o número de pontos de coordenadas naturais no interior

do retângulo (dentro do retângulo, mas não na fronteira) apresenta coordenadas de
p−1 q−1
números inteiros equivalentes a · .
2 2
q
Agora, a reta que passa por O e B tem por equação py = qx ⇒ y = x, enquanto
p
20
q
Figura 2.1: y = x
p
(p − 1)
que o fato de os números 1,2,. . ., serem todos primos com p acarreta em essa
2
reta não possuir nenhum dos pontos interiores contados acima e, por consequência
q
esta reta, y = x, intercepta as retas x = k, paralelas ao eixo y , nos pontos de
p
kq
coordenadas (k, ).
p
kq
Como não é inteiro e 1 ≤ k ≤ p − 1 obtemos que o número de pontos de
p
q
coordenadas naturais sobre a reta x = k, acima do eixo x e abaixo da reta y = x
p
kq
é representado por e, dessa maneira a quantidade de pontos de coordenadas
p
naturais no interior do triângulo ABC é dado por
21

q 2q 3q p−1 q
M= + + +··· + · .
p p p 2 p
De
forma
análoga, as interseções das retas y = k, paralelas ao eixo x, com a reta
q
y= x resulta que o número de pontos de coordenadas naturais no interior do
p
triângulo ACD é igual a

p 2p 3p q−1 p
N= + + +··· + · .
q q q 2 q
Então, M + N é igual ao total

p−1 q−1
·
2 2
de pontos no interior do retãngulo ABCD.
Dessa maneira, podemos escrever que

q p
= (−1) e
M
= (−1)N ,
p q
e consequentemente, pelo Teorema 1.6, temos

p q
= (−1)M +N = (−1) 2 2 .
p−1 q−1
q p

O Teorema da Lei de Reciprocidade Quadrática pode ser reenunciado das se-

guintes maneiras:
Corolário 1: Se p e q são dois números distintos, tais que p ≡ 1 (mod 4), ou q

≡ 1 (mod 4), então q é resíduo quadrático módulo p, se, e somente se, p é resíduo
quadrático módulo q;
Corolário 2: Se p e q são dois números distintos, tais que p ≡ q ≡ 3 (mod 4),

então q é resíduo quadrático módulo p, se, e somente se, p é não resíduo quadrático
módulo q.
Apresentaremos a seguir três demonstrações distintas da Lei de Reciprocidade
22
Quadrática. A primeira e a segunda demonstração, inspirada em [25]. Para efe-

tuar a terceira demonstração, [8] aponta a utilização da denição de um conjunto.
Para alcançar este propósito, vamos ressaltar a prova de dois lemas úteis a esta
demonstração.
Primeira Demonstração: Inicialmente, consideremos a gura (2.2) em que
Figura 2.2: O Retângulo R
q−1 q−1
Cpq = {x ∈ Z | 1 ≤ x≤ e− ≤ px ≤ 0 (mod q)}
2 2
p−1 p−1
Cqp = {y ∈ Z | 1 ≤ y ≤ e− ≤ qy ≤ 0 (mod p)}
2 2
23
M = # Cpq
N = #Cqp
Então, pelo Lema de Gauss (Lema 1.1), temos

p q
= (−1)M +N
q p
p−1 q−1
e, assim mostraremos que M + N e · apresentam a mesma paridade.
2 2
q−1
Para cada x ∈ Cpq existe um e apenas um y ∈ Z de modo que − ≤ px−qy <
2
p
0 e, simultaneamente 0 < y < . Ao observar que p é ímpar, temos
2
1 1 1
Cpq = {(x, y) ∈ Z2 | 0 < x < q e 0 < y < p e − q < px − qy < 0}.
2 2 2
De forma análoga,
1 1 1
Cqp = {(x, y) ∈ Z2 | 0 < x < q e 0 < y < p e − p < qy − px < 0}.
2 2 2
Caso,
1 1
R = {(x, y) ∈ Z2 | 0 < x < q e 0 < y < p},
2 2
obtemos
p−1 q−1
#R = · e #R = (M + N )
2 2
representando o número de pares (x, y) ∈ R de forma que
1 1
− q < px − qy < 0 ou − p < qy − px < 0,
2 2
sendo estas condições denitivas na construção de dois conjuntos disjuntos equipo-
tentes pelo fato de
24
1
(x, y) 7→ (q + 1, p + 1) − (x0 , y 0 )
2
p−1 q−1
denir uma bijeção entre ambas e portanto valida a condição de M +N e ·
2 2
tem a mesma paridade.

Segunda Demonstração: Na notação do Teorema 2.2, com p = q, para cada

p−1
j ∈ P , onde P = {1, 2, . . . , }, temos que εj = −1 se, e somemte se, existe
2
p−1
y ∈ Z de forma que − ≤ qj − py < 0, além de y deve pertencer a Q, sendo
2
q−1
Q = {1, 2, . . . , }.
2
Desse modo,
q
= (−1)M
p
(p − 1)
onde M = |R| e R = {(x, y) ∈ P × Q | − ≤ qx − py < 0 }. Observemos que
2
qx − py nunca assume valores 0 e, assim

p
= (−1)N
q
(q − 1)
em que N = |S| e S = {(x, y) ∈ P × Q | 0 < qx − py ≤ − }.
2
Logo,
p q
= (−1)K
q p
(p − 1) (q − 1)
onde K = M + N = |T |, e T = {(x, y) ∈ P × Q | − ≤ qx − py ≤ − }
2 2
porque qx − py nunca assume o valor 0. Então, k = |G| − |E| − |F | onde G = P × Q
e
(p − 1)
E = {(x, y) ∈ G | qx − py < − };
2
(q − 1)
F = {(x, y) ∈ G | qx − py > − }.
2
p−1 q−1
Como |G| = · , mostremos que |E| = |F |. Mas Ω : G → G é denida
2 2
25

(p + 1) (q + 1)
por Ω (x, y) = − x, −y o que representa uma bijeção entre E e
2 2
F.

Terceira Demonstração: Consideremos o conjunto C denido por C = {a :

p−1
}, sendo (a, pq) = 1 e, em seguida o conjunto A = a∈C a. Com isso,
Q
1≤a≤
2
temos

q p
Lema 2.1 A ≡ (−1) (mod p) e A ≡ (−1) 2 (mod q).
q−1 p−1
2
p q
Demonstração: Sendo conjunto

p−1 p−1
D = {a : 1 ≤ a ≤ }, onde (a, p) = 1, e E = {q· 1, q· 2, . . . , q· }
2 2
podemos admitir que E é um subconjunto de D porque
pq − 1 p−1 q−1
= q+ . (2.5)
2 2 2
Ao observar que C = D − E onde, pelo Critério de Euler, temos
p − 1
p−1
a= a=q !· A (mod p).
p−1
! · A ≡ pq
Q Q Q
a∈D a∈E a· a∈C
2
2 2
Podemos também escrever a expressão (2.5) de seguinte forma:
pq − 1 q−1 p−1
= p+ . (2.6)
2 2 2
Portanto,

Q q−1 p−1 q−1 p−1
a∈D a = ((p − 1)!) 2 · ! ≡ (−1) 2 ! · A (mod p)
2 2
onde, pelo Teorema de Wilson, (Anexo B), temos

q p−1 p−1
! · A ≡ (−1) ! · A (mod p),
q−1
· 2
p 2 2
26

q
e assim A ≡ (−1) (mod p).
q−1
2
p
As outras declarações do Lema

2.1 seguem por
simetria
e, dessa maneira segue-se
q p
consecutivamente que (−1) ⇔ A ≡ 1 ou − 1 (mod pq).
q−1 p−1
2 = (−1) 2
p q
Lema 2.2 A ≡ 1 ou −1 (mod pq) se, e somente se, p ≡ q ≡ 1 (mod 4).
Demonstração: Ao determinarmos z = pq, pelo teorema Chinês do Resto,

(Anexo B), a congruência x2 ≡ 1 (mod z) tem precisamente 4 soluções: x ≡
1, −1, n, −n (mod z). Já a congruência x2 ≡ −1 (mod z) apresenta uma solução,
x ≡ I (mod z), apenas se p ≡ q ≡ 1 (mod 4) e dessa forma haverá precisamente 4
soluções, isto é, x ≡ 1,− 1,n1 , − n1 (mod z).
Agora, para cada ”a” em G , existe um único a em G e 8a em {−1, 1} tal
que a· a0 ≡ 8a (mod z) cuja correspondência a → a0 é uma permutação de Ψ. Ao
escrevermos G = {a ∈ C: a = a'} = {a ∈ C : a2 ≡ ±1 (mod z)} observemos que
G = a∈C a ≡ ± a∈G a (mod z), se p ≡ q ≡ 1 (mod 4), e então a∈G a ≡ ±
Q Q Q
(1 · n· I· I· n)(n2 · I 2 ) ≡ ±1 (mod d). Caso contrário, teríamos a∈G a ≡ ± (1

Q
· n2 ) 6= ±1 (mod d).

q p
Ao combinarmos os Lemas 2.1 e 2.2 conclui−se que (−1) = (−1) 2
q−1 p−1
2
p q
se, e somente se, p ≡ q ≡ 1 (mod 4). O teorema agora segue pela consideração dos 4
casos: (p, q) ≡ (1, 1), (1, −1), (−1, 1), (−1, −1) (mod 4) ou através de fórmulas uma
vez que p ≡ q ≡ 1 (mod 4) se, e somente se, (−1) 2 2 = −1. Logo,
p+1 q+1

p q p−1 q−1 p+1 q+1
= −(−1) 2 (−1) 2 (−1) = (−1) 2 2 .
q p
Contudo,

p−1 q−1 pq − p − q + 1 pq + p + q + 1 p + q
= = −
2 2 4 4 2
p+1 q+1 p−1 q−1
= − + +1
2 2 2 2
p+1 q+1 p−1 q−1
= + + + 1 (mod 2)
2 2 2 2
27
o que resultará em
−(− 1) · (−1) · (−1)

p−1 q−1 p+1 q+1 p−1 q−1
2 2 2 2 = (−1) 2 2 .

402
Exemplo 2.2 Calcule .
991
Solução: Como 991 é um número primo e que 402 = 2 · 3 · 67, teremos que

2
=1 (991 ≡ −1 (mod 8))
991

3 991
=− (991 ≡ −3 (mod 4))
991 3
1
=− (991 ≡ −1 (mod 3))
3
= − 1.

67 991
=− (991 ≡ 67 ≡ 3 (mod 4))
991 67
−14
=− (991 ≡ −14 (mod 67))
67
−1 2 7
=− (−14 = (−1)· 2 · 7)
67 67 67
67
= −(−1) ·(−1)· (− ) (67 ≡ 3 (mod 8) e 7 ≡ 3 (mod 4))
7
4
= (67 ≡ 4 (mod 7))
7
= 1.

402 2 3 67
Portanto, = = 1· (−1)· 1 = −1.
991 991 991 991
Logo, a Lei de Reciprocidade Quadrática e o fato de já termos visto que
1 se p ≡ 1 (mod 4)
(
−1
= (Propriedade 3 do Teorema 1.5)
p −1 se p ≡ 3 (mod 4)
28
1 se p ≡ ± 1 (mod 8)
(
2
= (Teorema 1.6)
p −1 se p ≡ ± 3 (mod 8)
nos permite acrescentar mais alguns resultados parecidos para os seguntes Símbolos
de Legendre.
Exemplo 2.3 Mostre que se p é um primo ímpar, então,
1 se p ≡ ± 1 (mod 12)
(
3
=
p −1 se p ≡ ± 5 (mod 12)
Solução: Usando a Lei de Reciprocidade Quadrática temos

3 p
(−1) 2 .
p−1
=
p 3
Enquanto que o Teorema 1.5 (1) permite escrever


 1
p  =1 se p ≡ 1 (mod 3)
3

=
3 2
= −1 se p ≡ 2 (mod 3)


3

Por outro lado,
1 se p ≡ 1 (mod 4)
(
(−1)
p−1
2 =
−1 se p ≡ 2 (mod 4)
Assim,
1 se p ≡ 1 ou p ≡ 11 (mod 12)
(
3
=
p −1 se p ≡ 5 ou p ≡ 7 (mod 12)

5
Exemplo 2.4 Calcule , onde p é um número primo maior do que 5.
p
Solução: Com o auxílio da Lei de Reciprocidade Quadrática temos
29

5 p p
.
p−1
= (−1)2 2 =
p 5 5
Pelo Teorema 1.5 (1), temos


1

 =1 se p ≡ 1 (mod 5)
5




 2

se p ≡ 2 (mod 5)

p  = −1
5

=
5 3

 = −1 se p ≡ 3 (mod 5)
5




 4
se p ≡ 4 (mod 5)

=1


5

Teorema 2.3 Para todo primo p existem inteiros a, b e c, não todos nulos, tais
que se verica a seguinte congruência:
a2 + b2 + c2 ≡ 0 (mod p).
Demonstração: Quando zermos p = 2 e tomando a = b = 1 e c = 0 obtemos

1 + 12 + 02 ≡ 0 (mod 2). Agora, pelo Teorema 1.3, ao admitir que se p ≡ 1 (mod 4)
2
tomaremos a como uma solução de x2 ≡ 1 (mod p), b = 1 e c = 0 enquanto que

para p ≡ 3 (mod 4) adotaremos c = 1 para mostrar a existência de solução para a
congruência a2 + b2 ≡ −1 (mod p). Então, o Teorema 1.2 nos garante que sendo p
p−1 p−1
um primo ímpar teremos que serão os resíduos quadráticos e não serão,
2 2
dentre os números 1, 2, . . . , p − 1, mas se k for resíduo quadrático encontramos a
congruência x2 ≡ k (mod p) que apresenta solução, quando p é primo. Consideremos
dentre os números 1, 2,. . . , p−1 que d seja o menor resíduo positivo não−quadrático
módulo p em que 1 é resíduo quadrático para
d > 2, o Teorema 1.5 (3) possibilita
−1
observar que se p ≡ 3 (mod 4) teremos = −1. E se d não é resíduo quadrático
p
d
obtemos que = −1. Então, pelo Teorema 1.5 (4), podemos escrever que
p

−d −1 d
= = (−1)(−1) = 1.
p p p
o que permite armar que −d é um resíduo quadrático módulo p, ou seja, a congruên-
30
cia x2 ≡ −d (mod p) apresenta solução. Sendo b de maneira que b2 ≡ −d (mod p)

precisaremos encontrar um ”a” em que a2 ≡ d − 1 (mod p) e assim resulta em
(
a2 ≡ d − 1 (mod p)
⇒ a2 + b2 ≡ −1(mod p).
b2 ≡ −d (mod p)
No entanto, a congruência a2 ≡ d − 1 (mod p) possui claramente solução por d >

2, d−1 < d e d ser o menor resíduo não−quadrático positivo módulo p. Por isso, d−1
será resíduo quadrático módulo p e a congruência a2 + b2 ≡ −1 (mod p) apresentará
solução, resultando na demostração da congruência a2 + b2 + c2 ≡ 0 (mod p).

2.2 Símbolo de Jacobi

O Símbolo de Jacobi apresenta várias propriedades similares ao Símbolo de Le-
gendre. A generalização desta simbologia foi desenvolvida para valores não primos
por Carl Gustav Jakob Jacobi (1804-1851), em 1837, tendo como principal utilidade
na Teoria dos Números Computacional, especialmente no teste de primalidade e
fatoração de inteiros e com grande importância na criptograa.
Denição 2.1 Seja n um número positivo com respectiva fatoração em compo-

nentes primos p1 e1 p2 e2 · · · pk ek . Para qualquer valor a ≥ 0, o Símbolo de Jacobi
é denido como o produto dos Símbolos de Legendre relativamente aos componentes
primos de n, na forma da expressão
hai ei
Qk a
= i=1 ,
n pi

a
onde é o Símbolo de Legendre.
pi

3 81
Exemplo 2.5 Calcule e .
539 385
Solução:
31
2
3 3 3 3
= 2 = · = (−1)2 (−1) = −1;
539 7 .11 7 11

81 81 81 196 81
= = · ·
385 5.7.11 5 7 11
2 2
1 4 4 1 2 2
= · · = · · = 1.
5 7 11 5 7 11

a
Em [21], Santos ressalta que o símbolode Legendre nos informa sobre a
p
existência hde isoluções para a congruência x2 ≡ a (mod p), enquanto que o Símbolo
a
de Jacobi não fornece nenhuma informação a respeito da existência de soluções
n
para a congruência x2 ≡ a (mod n). Caso n seja primo o Símbolo de Jacobi será
idêntico ao Símbolo de Legendre. Agora, se p é um fator primo de n e se x2 ≡
a (mod n) possui solução concluímos que a congruência x ≡ a (mod p) também
2
a
terá solução, ou seja, = 1. Portanto,
p
hai ei
a
= 1.
Qk
= i=1
n pi
hai
Exemplo 2.6 Sendo a = 2 e n = 35 , mostre a existência de = 1 pode
n
ocorrer sem que a congruência x2 ≡ a (mod n) apresente solução.
Solução: Seja

2 2 2 2
= = · = (−1)(−1) = 1.
35 5.7 5 7
As congruências x2 ≡ 2 (mod 5) e x2 ≡ 2 (mod 7) não possuem nenhuma

solução e, por consequência a congruência x2 ≡ 2 (mod 35) não terá solução alguma.
Entretanto, o Símbolo de Jacobi cumpre as mesmas regras computacionais que o
Símbolo de Legendre, incluindo a demonstração da Lei de Reciprocidade Quadrática.
Teorema 2.4 Sejam a e n inteiros positivos ímpares e primos entre si. Pelas
propriedades do Símbolo de Legendre e pela denição de Jacobi, seguem as seguintes
propriedades:
32
hai
b
(1) Se a ≡ b (mod n), então = ;
n n
a2

(2) = 1;
n
hai b ab

(3) = ;
n n n
h a ihai h a i
(4) = ;
m n mn

−1
(5) = (−1) 2 ;
n−1
n

2 p2 −1
(6) = (−1) 8 ;
n
h n i hmi
(7) . (Lei de Reciprocidade Quadrática)
n−1 m−1
= (−1) 2 2
m n
Demostração: As propriedades (1) a (3) são consequências imediatas da de-
nição do Símbolo de Jacobi e do fato destas propriedades se aplicarem ao Símbolo
de Legendre. Já a propriedade (4) segue da denição do Símbolo de Jacobi em que
se m = p1 , · · · , pj e n = q1 , · · · , qk representam as decomposições em fatores primos
de m e n permitindo que os primos pi e qj possam aparecer repetidos. Portanto,
h a ihai h
a a a a a a i
= ··· ··· = = .
m n p1 pj q1 qk p1 · · · pj q1 · · · qk mn
Agora, para vericarmos as propriedades (5), (6) e (7) precisaremos do Lema a

seguir.
Lema 2.3 Se x e y são números inteiros ímpares, então

x−1 y−1 xy − 1
+ ≡ (mod 2) (2.7)
2 2 2
e
x2 − 1 y 2 − 1 x2 y 2 − 1
+ ≡ (mod 2). (2.8)
8 8 8
33
Demonstração: Como x e y são números ímpares, os números (x − 1) e (y − 1)

(x − 1)(y − 1)
são pares, e assim continuará sendo par, além de
2
(x − 1)(y − 1) xy − x − y + 1 xy − 1 − x + 1 − y + 1
0≡ ≡ ≡ (mod 2)
2 2 2
x−1 y−1 xy − 1
provando dessa maneira + ≡ (mod 2).
2 2 2
Em contrapartida, (x − 1) e (x + 1) são pares e consequentemente x2 −1 =
(x−1)(x+1) possui pelo menos dois fatores 2 e, por analogia, para y 2 −1 podemos ad-
(x2 − 1)(y 2 − 1)
mitir que (x2 −1)(y 2 −1) tem pelo menos 4 fatores 2 o resultará em
8
ser par e
(x2 − 1)(y 2 − 1) x2 y 2 − x2 − y 2 + 1 x2 y 2 − 1 − x2 + 1 − y 2 + 1
0≡ ≡ ≡ (mod 2)
8 8 8
x2 − 1 y 2 − 1 x2 y 2 − 1
provando dessa maneira que + ≡ (mod 2).
8 8 8
Vamos supor que m = p1 , · · · , pj e n = q1 , · · · , qk são decomposições em fatores
primos de m e n em que os primos pj e qk podem aparecer repetidos. Então,

−1 −1 −1 −1 qh −1
= (−1) h=1 2 = (−1) 2 .
Pj n−1
= = ···
n n q1 qj
Qj
Pela congruência (2.7) obtemos ( h=1 qh )−1
(mod 2).
Pj qh −1
h=1 2 = 2

2
De forma similar, é possível demonstrar, pela congruência (2.8), que =
n
p2 −1
(−1) sendo possível constatar que, para
8 h xo, a congruência (2.7) resultará em
Pk qi −1 ph −1 (Qki=1 qi )−1
(mod 2). Então, pelas propriedades
Pk ph −1 qi −1
i=1 2 2
≡ ph2−1
i=1 2 ≡ 2 2
3 e 4 podemos escrever
h a i h n i Q
qi

ph

qi ph
j Qk Qj Qk Qj Qk
= h=1 i=1 h=1 i=1 = h=1 i=1
n a ph qi ph qi
Qj Qk ph −1 qi −1 Pj Pk ph −1 qi −1
= h=1 i=1 (−1)
2 2 = (−1) h=1 i=1 2 2
34
ph −1 n−1
= (−1)
Pj m−1 n−1
h=1 2 2 = (−1) 2 2 .

Provamos assim a propriedade (7) que se refere à Lei da Reciprocidade Quadrá-

tica por meio do Símbolo de jacobi.

429 181
Exemplo 2.7 Avalie os Símbolos de Jacobi e .
563 991

429 181
Solução: Vamos analisar os Símbolos de Jacobi e , no qual faremos
563 991
uso da Lei da Reciprocidade Quadrática. Então,

429 563 563
= (−1)
429−1 563−1
2 2 =
563 429
429
134 2 67
= =
429 429 429
429 429
= (−1) 2 2
67−1 429−1
=
67 67
27 67 13
= (−1)
27−1 67−1
= 2 2 =−
67 27 27
27
= − (−1) 2 2 = −1.
13−1 27−1
13

181 991 991
= (−1)
181−1 991−1
2 2 =
991 181
181
86 2 43
= =
181 181 181
1812 −1 43 43
= (−1) 8 =−
81 81
181 181
= − (−1) 2 2
43−1 181−1
=−
43 43
2
9 3
=− =− = −1.
43 43
35
2.3 Extraindo Raízes Quadradas módulo n
Vamos desenvolver as ferramentas para encontrar as raízes quadradas modulares.

Sendo a uma função quadrática resíduo módulo p, com p primo ímpar, a congruência
x2 ≡ a (mod p) terá exatamente duas soluções dadas por [± x0 ] , para qualquer
solução particular x0 . Então, descobriremos o valor de x0 .

a
Teorema 2.4 Se
(p+3)
= 1 e p ≡ 5 (mod 8) em que s = a 8 teremos que a
p
(p−1)
congruência x ≡ a (mod p) apresentará como soluções s ou 2 4 · s.
2

2
Demostração: Sendo = −1, Teorema 2.7, podemos escrever, pelo Critério
p
de Euler, que 2 2 ≡ − 1 (mod p). Assim, a congruência s4 = a 2 a2 ≡
(p−1) (p−1)
a2 (mod p) resultará em s2 ≡ ±a (mod p) se s2 ≡ −a (mod p). Consequentemente

2 4 · s será solução para x2 ≡ a (mod p).
(p−1)
Exemplo 2.8 Resolva a congruência x2 ≡ 5 (mod 29).
Solução: É possível vericar que 29 ≡ 5 (mod 8) e, dessa maneira s = 5 8 =

(29+3)
5 = 625 ≡ 16 (mod 29). Mas também 162 = 256 ≡ 24 ≡ −5 (mod 29) que ao
4
fazermos 27 = 128 ≡ 12 (mod 29) teremos x0 = 12· 16 = 192 e, portanto a solução

particular será x0 ≡ 192 ≡ 11 (mod 29) e −x0 ≡ −11 ≡ 18 (mod 29).

a
Teorema 2.5 Se = 1 e p ≡ 3 (mod 4), então existe exatamente duas
p
(p+1)
soluções para a congruência x2 ≡ a (mod p), onde x ≡ ±a 4 (mod p).
Demonstração: O Critério de Euler nos fornece que (a )2 = a

(p+1) (p+1)
4 2 =
a ≡ a (mod p).
(p−1)
a 2
Uma aplicação bastante útil é o cálculo de raízes quadradas onde, através da tecla
de raiz quadrada, a maioria das calculadoras manuais a informam de maneira ins-
√
tantânea como, por exemplo, podemos observar que 29 ≈ 5,38516480. No entanto,
36
√
o resultado de 29 em Z71 é impossível de se obter na maiorias das calculadoras e
assim quando expressamos que 7 é raiz quadrada de 49 queremos armar que 7 é
raiz da equação x2 − 49 = 0 sendo que 49 tem duas raízes quadradas diferentes: +7
e −7.
A raiz positiva apresenta um tratamento preferencial, pois quando pesquisamos
as raízes quadradas de 29 mentalizamos que x ∈ Z71 e o resultado apresentado
pela calculadora não nos ajuda em nada. Podemos, então, utilizar a Lei de Re-
ciprocidade Quadrática para solucionar esse problema uma vez que existe apenas
71 elementos distintos em Z71 e por meio do Teorema 2.5 podemos enm decla-
rar as raízes quadradas de 29 em Z71 , ou seja,obter as soluções dacongruência

29 71 71
x2 ≡ 29 (mod 71). De modo inicial, temos
29−1 71−1
= (−1) 2 2 = =
71
29
29
13 13−1 29−1 29 29 3 3−1 13−1 13 13
= (−1) 2 2 = = = (−1) 2 2 = =1
29 13 13 13 3 3
e como 71 ≡ 3 (mod 4) obtemos como solução particular x0 = 29 4 = 2918 ≡
(71+1)
10 (mod 71). Logo, as soluções são dadas por x0 = 10 (mod 71) e −x0 = −10 ≡
61 (mod 71).
Essa aplicação é válida para Zp em que p é primo, mas também podemos obter a
√
raiz quadrada para um certo n de forma que n = pq . Então, para encontrar 500 em
Z589 é preciso visualizar que n = 589 = 19 · 31 onde podemos escrever as seguintes
congruências x2 ≡ 500 (mod 19), ou seja, x2 ≡ 6 (mod 19) e x2 ≡ 500 (mod 31),
isto é, x2 ≡ 4 (mod 31). O fato de termos, pelo
teorema
1.11, 19 ≡ 3 (mod 4) e
6 4
31 ≡ 3 (mod 4) nos permite concluir que =1e = 1. Portanto,
19 31
x0 = 6 4 = 65 ≡ 5 (mod 19) ⇒ x0 = 5 e −x0 = 14;

(19+1)
x1 = 4 4 = 48 ≡ 2 (mod 31) ⇒ x1 = 2 e −x1 = 29.

(31+1)
Com essa redução, caso x seja uma raiz quadrada de 500 em Z589 também
será uma raiz quadrada de 500 em Z19 e em Z31 de maneira que x satisfaça x ≡
5, 14 (mod 19) e x ≡ 2, 29 (mod 31) o que resulta nos quatro problemas a resolver:
x ≡ 5 (mod 19) (i) x ≡ 5 (mod 19) (ii)

x ≡ 2 (mod 31) x ≡ 29 (mod 31)
x ≡ 14 (mod 19) (iii) x ≡ 14 (mod 19) (iv)
37
x ≡ 2 (mod 31) x ≡ 29 (mod 31)
Para solucionar esses quatro problemas será preciso fazer uso do Teorema do
Resto Chinês, (Anexo B). Com isso, é posível vericar de imediado a presença de
quatro raízes quadradas de 500 em Z589 , ou seja, ao resolver cada sistema de con-
gruência por esse teorema obtemos as quatro raízes quadradas de 500, em Z589 ,
como sendo 157,556,33 e 432, nessa ordem. Agora, de forma semelhante, vamos
√
determinar todos os valores de 17985 em Z34751 em que n = 34751 = 19· 31· 59.
Isto implicará nas seguintes congruências:
x2 ≡ 17895 (mod 19) ⇒ x2 ≡ 11 (mod 19);
x2 ≡ 17895 (mod 31) ⇒ x2 ≡ 5 (mod 31);
x2 ≡ 17895 (mod 59) ⇒ x2 ≡ 49 (mod 59).
Como 19 ≡ 3 (mod 4), 31 ≡ 3 (mod 31) e 59 ≡ 3 (mod 4) podemos escrever que

x0 = 11 4 = 115 ≡ 7 (mod 19) ⇒ x0 = 7 e −x0 = 12;
(19+1)
x1 = 5 4 = 58 ≡ 25 (mod 31) ⇒ x1 = 25 e −x1 = 6;

(31+1)
x2 = 49 4 = 4915 ≡ 7 (mod 59) ⇒ x2 = 7 e −x2 = 52;

(59+1)
o que equivale dizer que como x é uma raiz quadrada de 17985 em Z34751 também será
uma raiz quadrada de 17985 em Z19 , em Z31 e em Z59 . Nesse caso, x coresponderá
a x ≡ 7, 12 (mod 19), x ≡ 25, 6 (mod 31), e x ≡ 7, 52 (mod 59) decorrendo em oito
problemas a resolver:
x ≡ 12 (mod 19) x ≡ 12 (mod 19)
x ≡ 25 (mod 31) (i) x ≡ 6 (mod 31) (ii)
x ≡ 7 (mod 59) x ≡ 52 (mod 59)
x ≡ 12 (mod 19) x ≡ 12 (mod 19)

x ≡ 25 (mod 31) (iii) x ≡ 6 (mod 31) (iv)
x ≡ 52 (mod 59) x ≡ 7 (mod 59)
x ≡ 7 (mod 19) x ≡ 7 (mod 19)

x ≡ 25 (mod 31) (v) x ≡ 6 (mod 31) (vi)
x ≡ 7 (mod 59) x ≡ 7 (mod 59)
38
x ≡ 7 (mod 19) x ≡ 7 (mod 19)

x ≡ 25 (mod 31) (vii) x ≡ 6 (mod 31) (viii)
x ≡ 52 (mod 59) x ≡ 52 (mod 59)
Então, para resolvermos esses oito problemas também será preciso fazer uso
do Teorema do Resto Chinês, (Anexo B). Observa−se de imediado a existência
de oito raízes quadradas de 17985 em Z34751 , isto é, solucionando cada sistema
de congruência por esse teorema é possível especicar as oito raízes quadradas de
17985,em Z34751 como sendo 19772, 16808, 28018, 8562, 17943, 6733, 26189 e 14979,
respectivamente. No entanto, é possível obter, de forma semelhante, raízes cúbicas
e biquadradas módulo n.
Dessa maneira, para determinarmos a raiz quadrada módulo n devemos usar a
fatoração, o cálculo da raiz quadrada em Zp e o Teorema do Resto Chinês, (Anexo B).
Já em uma visão computacional a fatoração é a etapa mais complicada enquanto que
as outras fases são desenvolvidas de forma eciente pelo computador. Portanto, o
processo de obtenção das raízes quadradas de números em Zn torna−se viável quando
n é um inteiro da forma n = pq com p e q primos de modo que p ≡ q ≡ 3 (mod 4).
Mas, se p e q forem primos com 100 algarismos a etapa da fatoração torna o processo
totalmente impraticável.
39
Capítulo 3
Aplicações em Sala de Aula
A Teoria dos Números abrange os fundamentos em Matemática sendo estes ne-

cessários para construir e para aprender mais Matemática. A resolução de certos
tipos de problemas aplicáveis à vida cotidiana necessita de estratégias que não se re-
sumem a simples cálculos mesmo que Teoria dos Números aparenta ser uma área da
Matemática que lida com problemas que são aparentemente simples. Dessa maneira,
[17] aponta a Teoria dos Números como uma ferramenta para outros campos da Ma-
temática assim como os conhecimentos e ferramentas desses campos são utilizados
na resolução de seus problemas ao mesmo tempo em que tem como foco resolver
os mistérios dos números e, para isso são utilizados métodos algébricos, métodos
analíticos ou também métodos geométricos.
Neste capítulo, vamos propor algumas atividades aplicáveis aos Ensinos Funda-
mental e Médio de modo a construir uma compreensão da simbologia de congruência
e, consequentemente analisar os resíduos quadráticos, além de fazer uma associação
com a Criptograa, em particular ao Método de Rabin, através da orientação de [1].
3.1 Atividade 1 − A Utilização da Simbologia de

Congruência e os Resíduos Quadráticos
Neste trabalho, estudamos que a congruência x2 ≡ a (mod m) apresentará solu-
ção se a for um resíduo quadrático módulo m, com (a, m) = 1. Caso contrário, ela
não possuirá solução. Então, vamos desenvolver uma linguagem acessível aos alunos
40
Aplicações em Sala de Aula Capítulo 3
do Ensino Médio para que possa realizar um ensino de Matemática mais dinâmico
e que os educandos participem ativamente de sua aprendizagem.
Atividade
(i) Encontre os restos da divisão de 102 por 7, 892 por 11 e 1252 por 19.
(ii) Agora, se escrevermos 102 ≡ 2 (mod 7), 892 ≡ 1 (mod 11) e 1252 ≡
7 (mod 19). Qual seria a semelhança com o item anterior?
(iii) Podemos obter o conjunto dos possíveis restos de cada divisão do item (i)?
(iv) Mas, se agora escrevermos x2 ≡ a (mod m). Qual será a compreensão?
(v) Qual regularidade podemos observar do item (v)?
(vi) Agora, podemos explicar o porquê de 42 ≡ 3 (mod 13) e 92 ≡ 3 (mod 13)
apresentar como resultado o mesmo resíduo quadrático, ou seja, o valor de 3 como
resposta?
(vii) Já com todos esses conhecimentos abordados, pode−se vericar os casos
em que há solução para a congruência x2 ≡ a (mod 7)?
Objetivo Geral
∗ Desenvolver a linguagem de congruência e a noção de resíduos quadráticos,
no Ensino Médio, como forma de contribuir para a expansão dos conhecimentos
matemáticos dos educandos.
Objetivos Especícos
∗ Obter o resto de uma divisão, envolvendo potências quadradas, em que iden-
ticaremos o conjunto dos possíveis restos;
∗ Associar que a congruência x2 ≡ a (mod n) descreve uma nova possibilidade
de escrita em que a é o resto da divisão de x2 por n;
∗ Conceituar a congruência x2 ≡ a (mod n);
∗ Detectar as regularidades no sistema reduzido de resíduos quadrados;
∗ Vericar se a congruência x2 ≡ a (mod n) possui ou não solução, ou seja, se é
ou não resíduo quadrático.
Público−Alvo e Materiais
Esta atividade possui como público alvo os discentes do Ensino Médio onde
41
consideraremos seus conhecimentos prévios sendo preciso saber das propriedades de

números inteiros, em particular a divisão e a potenciação. Com relação aos materiais
utilizados podemos destacar lápis, borracha, papel e cartolina para confecção de
cartazes.
Comentários
Com essa atividade o professor conseguirá completamente atribuir um signicado
a esse conhecimento matemático aperfeiçoando a aprendizagem de seus alunos. A
seguir, propomos a interpretação das questões abordadas.
(i) O aluno que possui uma percepção das propriedades dos números inteiros,
particularmente na divisão interligada à potenciação observará facilmente que as
divisões de 102 por 7, 892 por 11 e 1252 por 19 apresentam como restos 3,1 e 11,
respectivamente tendo que efetuar primeiramente a potenciação e, em seguida a
divisão.
(ii) Nesta fase, é fundamental que o professor enfatize que a escrita de congruên-
cia do tipo x2 ≡ a (mod n) representa uma alternativa mais elaborada. Também,
deve−se expressar que mesmo com a escrita diferenciada do item (i) exibe o mesmo
signicado.
(iii) Agora, ao entrarmos na Classe de Restos, ramo de estudo muito importante
da Matemática pura chamado Teoria dos Números, que trata do estudo dos números
inteiros, os alunos deverão perceber que ao efetuar uma divisão entre dois números
(inteiros) poderão acontecer duas possibilidades:
∗ se a divisão for exata, o resto será igual a zero;
ou
∗ se a divisão não for exata, o resto será diferente de zero.
Com a divisão exata, o resultado é evidente. Mas, caso a divisão não seja exata,
deveremos reetir nas possibilidades de valores (inteiros) para o resto. Então, se
dividirmos qualquer número (inteiro) por 2 tem−se os seguintes restos: zero (divisão
exata) ou 1. Isto, porque se o resto (r) for um número maior ou igual a 2 (r ≥ 2)
podemos continuar com a divisão. Assim, o conjunto dos possíveis restos da divisão
por 2 será r(2) = 0, 1.
Já quando dividirmos qualquer número (inteiro) por 3 poderemos ter os seguintes
42
restos: zero (a divisão é exata), 1 ou 2. Por essa mesma razão, se o resto for maior ou
igual a 3 (r > 3) podemos continuar com a divisão. Então, o conjunto dos possíveis
restos da divisão por 3 será: r(3) = 0, 1, 2.
E a partir destes resultados podemos conjecturar n como um inteiro não−nulo,
em que o conjunto dos possíveis restos de uma divisão por n será: r(n) = {0, 1, 2, 3,
. . . , n − 1}. Dessa maneira, o aluno conseguirá perceber que a divisão por 7 possui
como restos possíveis o conjunto r(7) = {0, 1, 2, 3, 4, 5, 6}, a divisão por 11 terá
r(11) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} e por 19 o conjunto r(19) = {0, 1, 2, 3, 4, 5, 6, . . . ,
16, 17, 18}.
(iv) Os estudantes já poderão ter a consciência que se trata de um valor x2 , com
x ∈ Z, que ao ser dividido por m obteremos o resto a. No entanto, a será a classe
residual de m, ou seja, r(a) = {0, 1, 2, 3, 4, . . . , n − 1}.
(v) O aluno já sabe que r(13) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} e portanto
terá elevar ao quadrado cada resto e, em seguida efetuar a divisão por 13. Logo,
12 ≡ 1 (mod 13) 72 ≡ 10 (mod 13)

22 ≡ 4 (mod 13) 82 ≡ 12 (mod 13)
32 ≡ 9 (mod 13) 92 ≡ 3 (mod 13)
42 ≡ 3 (mod 13) 102 ≡ 9 (mod 13)
52 ≡ 12 (mod 13) 112 ≡ 4 (mod 13)
62 ≡ 10 (mod 13) 122 ≡ 1 (mod 13)
Ao colocar os quadrados dos números de 1 até 12 obtemos apenas 6 números

1,3,4,9,10, e 12. Estes serão todos resíduos quadráticos módulo 13 em que os números
na metade superior se repetem na metade inferior, se referindo ao Teorema 1.2.
(vi) O aluno deverá observar que 42 ≡ (13 − 4)2 = 92 ≡ 3 (mod 13). Dessa
maneira já terá condições de vericar a veracidade do Teorema 1.1 em que para n
um primo ímpar e a um inteiro não divisível por n, a congruência x2 ≡ a (mod n),
caso tenha solução, tem exatamente duas soluções incongruentes modulo n.
(vii) Com a congruência x2 ≡ a (mod n), em que (a, n) = 1 e x2 − a é divisível
por n, teremos consequentemente, pelo Pequeno Teorema de Fermat, (Anexo B),
que an−1 − 1 é divisível por n. Então, podemos armar que (a 2 )2 − 1 também será
n−1
divisível por n e como (a 2 )2 − 1 = (a 2 − 1)(a 2 + 1) temos que ou (a 2 − 1)

n−1 n−1 n−1 n−1
será divisível por n ou (a 2 + 1) será divisível por n. Essa descoberta permite

n−1
43
concluir que se ocorrer a primeira situação a será resíduo quadrático de n, enquanto

na segunda a não será resíduo quadrático de n.
Agora, para a congruência x2 ≡ a (mod 7) usaremos a consequência do Teorema
1.4, o Critério de Euler, como justicativa para vericar se há solução. Sendo n = 7
p−1
e = 3, poderemos admitir que
2
13 ≡ 1 (mod 7) 43 ≡ 1 (mod 7)
23 ≡ 1 (mod 7) 53 ≡ −1 (mod 7)
33 ≡ −1 (mod 7) 63 ≡ −1 (mod 7)
As congruências x2 ≡ 1 (mod 7), x2 ≡ 2 (mod 7) e x2 ≡ 4 (mod 7) possuem so-

lução por serem resíduos quadráticos à medida que x2 ≡ 3 (mod 7), x2 ≡ 5 (mod 7)
e x2 ≡ 6 (mod 7) não terão solução. Com essa abordagem, o aluno saberá o pro-
cedimento de como obter resíduos quadráticos sem se tornar um ensino voltado a
memorização de fórmulas em que o aluno será apenas reproduz o conhecimento e
passará a ser sujeito de sua própria aprendizagem podendo notar que uma metade
será resíduo quadrático já a outra não, Teorema 1.2. Por outro lado, empregaremos
o Símbolo de Legendre, Denição 1.3, de uma maneira mais simplicada, ou seja, es-
tamos adequando esta simbologia para alcançar uma aprendizagem mais expressiva
no Ensino Médio.
3.2 Atividade 2 − A Congruência x2 ≡ a (mod n) e

a Criptograa: Método de Rabin
Desde a antiguidade, os egípcios, gregos e romanos utilizavam técnicas tão inte-
ligentes quanto criativas para enviar mensagens. Neste envio, eles as protegiam com
códigos para prevenir que a informação possa ser interpretada por todos.
A evolução das tecnologias torna constante a preocupação de que o envio de
mensagens seja cercado de meios capazes de codicar o conteúdo a m de aumen-
tar a segurança dos usuários. Para manter a proteção das informações temos a
criptograa denida, segundo [13], como o estudo de técnicas matemáticas relacio-
nadas aos aspectos da segurança da informação, como condencialidade, integridade
e autenticação. Também pode ser visto como a transformação de um conjunto de
44
informações inteligíveis, como os e-mails, por exemplo, em um emaranhado de ca-

racteres impossíveis de ser compreendido, texto cifrado.
Assim, apenas quem tem a chave de decriptação é capaz de recuperar a mensagem
em formato legível mesmo que a pessoa não autorizada conheça todo o processo para
esconder e recuperar os dados não conseguirá descobrir a informação sem a chave
de decriptação. Enfatizaremos, a seguir, os processos de Criptograa e Decifração.
(i) Amanda deseja mandar uma mensagem M para Bernardo;
(ii) Bernardo acha dois números primos grandes (100 algarismos cada um) p e
q , em que a divisão deles por 4 apresenta 3 como resto;
(iii) Bernardo calcula n = pq e envia o inteiro n para Amanda;
(iv) Cássio, que consideraremos como o invasor, também conhece n, mas em
virtude do processo de fatoração ser custoso, nem Alice e nem Cássio conhecem os
fatores p e q ;
(v) Amanda forma o inteiro M convertendo e unindo suas palavras em represen-
tações numéricas pelo Método de Rabin;
(vi) Amanda calcula um valor a que compreende o resto da divisão de M 2 por
n, e o envia para Bernardo. Cássio também consegue ver a;
(vii) Para decriptograr, Bernardo calcula as quatro raízes quadradas de N no
intervalo [0, 1, . . . , n − 1];
(viii) O fato de Bernardo conhecer os fatores p e q de n permite calcular facil-
mente as raízes quadradas, gerando quatro raízes possíveis, em que apenas uma é a
mensagem M , enviada por Amanda.
(ix) Das quatro mensagens geradas, três delas não terão sentido, então Bernardo
terá que reconhecer a correta;
(x) Cássio não consegue decriptografar pelo motivo de não saber como descobrir
as raízes quadradas.
Agora, vamos apresentar uma atividade com a intenção de descrever um crip-
tossistema famoso que consagrou a história da criptograa, o método de Rabin,
que é um dos criptossistemas de chave pública de mais fácil compreensão. Este sis-
tema criptográco, denotado por E(M ) = M 2 (mod n), foi proposto pelo israelense
Michael Oser Rabin, em Janeiro de 1979, consiste em criptografar as mensagens
mediante a elevação ao quadrado e decodicadar através da extração de raízes qua-
45
dradas. Os cálculos presentes nesse processo se vericam em p e q , números primos

inteiros, em que a divisão por 4 deixa 3 como resto.
Atividade
Suponhamos que Amanda e Bernardo querem compartilhar uma mensagem sem
que Cássio a desvende para conseguir isto, faremos uso do Método de Rabin. Então,
Amanda deseja enviar a mensagem MATEMÁTICA É VIDA para ser cripto-
grafada (cifrada). Com isso, Bernardo deverá escolher os primos p = 179 e q = 43
de forma que n = p · q = 7697 e a envia para Amanda. Como n é a chave pública
e (179, 43) a chave privada, criptografe a letra M do vocábulo MATEMÁTICA,
com o auxílio da tabela abaixo.
Figura 3.1: Tabela de Conversão
Objetivo Geral
∗ Compreender a Criptograa, particularmente o Método de Rabin, como uma
estratégia capaz de transformar uma mensagem de sua forma original para outra
ilegível.
Objetivos Especícos
∗ Constatar que, na Criptograa, apenas o destinatário conhece a informação
enviada, mantendo a sua segurança;
∗ Criptografar uma mensagem pelo Método de Rabin;
∗ Vericar que quem calcula o valor a é o remetente e envia para o destinatário,
enquanto que o invasor também consegue ver a;
∗ Denir Sistema Binário e Sistema Decimal;
∗ Transformar um valor numérico em base binária para base decimal e vice−versa;
∗ Representar a congruência x2 ≡ a (mod n) como um x ∈ Z em que a será o
resto da divisão de x2 por n.
46
Público−Alvo e Materiais
Esta atividade contempla os números primos, as operações com números inteiros:
adição, multiplicação, divisão e potenciação, sistema base 2 e decimal. Também foi
desenvolvida para educando do Ensino Médio, envolvendo materiais como papel,
lápis, borracha, calculadora e computador.
Comentários
É possível que o alunado tenha alguma diculdade de identicar um número
primo e de operar com os números inteiros o que vai exigir do professor aperfeiçoar
estes conhecimentos matemáticos para, em seguida investir no sistema binário e
no decimal. Dessa maneira, deverá perceber, pela tabela 3.1, que M corresponde
ao m = 22. Ele ao escrever 22 na representação binário obterá 0· 20 + 1· 21 +
1· 22 + 0· 23 + 1· 24 , ou seja, (10110)2 . Como m = (10110)2 , deveremos repetir os
quatro últimos dígitos o que resultará em m = (101100110)2 e, consequentemente
m? será equivalente a 358 na forma decimal, ou seja, m = (358)10 pois 358 =
28 + 26 + 25 + 22 + 21 . Portanto, Amanda ao elevar ao quadrado m e dividir 128164
por n = 7697 descobre como resto 5012, isto é, a = 5012, que corresponde ao valor
enviado a Bernardo em que é conveniente ressaltar que Cássio, o invasor, conhece n
e a. O mesmo não podemos dizer dos primos p e q que são do conhecimento apenas
de Bernardo. De maneira análoga poderemos obter todas as letras do vocábulo em
questão.
47
Apêndice A
Coletânea: Provas da Lei de
Reciprocidade Quadrática
Trazemos aqui a coletânea de autores que contribuiram para a evolução da Lei

de Reciprocidade Quadrática contendo 221 demonstrações, o ano e o método
utilizado. A inspiração foi obtida por intermédio de [26].
AUTOR ANO MÉTODO

1. Legendre 1788 Formas Quadráticas; incompleto
2. Gauss 1 1801 Indução; 8 de Abril de 1796
3. Gauss 2 1801 Formas Quadráticas; 27 de Junho de 1796
4. Gauss 3 1808 Lema de Gauss; 6 de Maio de 1807
5. Gauss 4 1811 Ciclotomia; Maio de 1801
6. Gauss 5 1818 Lema de Gauss; 08/1807
7. Gauss 6 1818 Somas de Gauss; 08/1807
8. Cauchy 1829 Gauss 6
9. Jacobi 1830 Gauss 6
10. Dirichlet 1 1835 Gauss 4
11. Lebesgue 1 1838 N (x21 + . . . + x2q = 1 (mod p)
12. Schönemann 1839 Equação Períódica Quadrática
13. Cauchy 1840 Gauss 4
14. Eisenstein 1 1844 Generalização da Soma de Jacobi
48
Apêndice A Apêndice
15. Eisenstein 2 1844 Gauss 6

16. Eisenstein 3 1844 Lema de Gauss
17. Eisenstein 4 1845 Seno
18. Eisenstein 5 1845 Produtos Innitos
19. Liouville 1847 Ciclotomia
20. Lebesgue 2 1847 Lebesgue 1
21. Schaar 1847 Lema de Gauss
22. Plana 1 1852
23. Genocchi 1 1852 Lema de Gauss
24. Schaar 2 2 1854 Gauss 4
25. Dirichlet 2 1854 Gauss 1
26. Genocchi 2 1854 Liouville
27. Schaar 3 3 1860 Gauss 4
28. Lebesgue 3 1860 Gauss 7, 8
29. Kummer 1 1862 Formas Quadráticas
30. Kummer 2 1862 Formas Quadráticas
31. Dedekind 1 1863 Formas Quadráticas
32. Gauss 7 1863 Formas Quadráticas; Set. 1796
33. Gauss 8 1863 Formas Quadráticas; Set. 1796
34. Mathieu 1867 Ciclotomia
35. Von Staudt 1867 Ciclotomia
36. Bouniakowski 1869 Lema de Gauss
37. Stern 1870 Lema de Gauss
38. Zeller 1872 Lema de Gauss
39. Zolotarev 1872 Permutações
40. Kronecker 1 1872 Zeller
41. Schering 1 1875 Gauss 3
42. Kronecker 2 1876 Indução
43. Mansion 1 1876 Lema de Gauss
44. Dedekind 2 1877 Gaus 6
45. Dedekind 3 1877 Soma de Dedekind
46. Pellet 1 1878 Stickelberger-Voronoi
49
47. Pepin 1 1878 Ciclotomia

48. Sochocki 1878 Funções Theta
49. Schering 2 1879 Lema de Gauss
50. Petersen 1879 Lema de Gauss
51. Genocchi 2 1880 Lema de Gauss
52. Kronecker 3 1880 Gauss 4
53. Kronecker 4 1880 Períodos Quadráticos
54. Voigt 1881 Lema de Gauss
55. Pellet 2 1882 Mathieu 1867
56. Busche 1 1883 Lema de Gauss
57. Gegenbauer 1 1884 Lema de Gauss
58. Kronecker 5 1884 Lema de Gauss
59. Kronecker 6 1885 Gauss 3
61. Bock 1886 Lema de Gauss
62. Lerch 1 1887 Gauss 3
64. Hacks 1889 Schering
65. Hermes 1889 Indução
67. Tafelmacher 1 1889 Stern
68. Tafelmacher 2 1889 Stern/Schering
69. Tafelmacher 3 1889 Schering
71. Franklin 1890 Lema de Gauss
72. Lucas 1890 Lema de Gauss
73. Pepin 2 1890 Gauss 2
74. Fields 1891 Lema de Gauss
77. Schmidt 1 1893 Lema de Gauss
78. Schmidt 2 1893 Lema de Gauss
50
79. Schmidt 3 1893 Indução

81. Bang 1894 Indução
82. Mertens 1 1894 Lema de Gauss
83. Mertens 2 1894 Somas de Gauss
85. Lange 1 1896 Lema de Gauss
86. Mansion 2 1896 Gauss 2
87. De la Vallee Poussin 1896 Gaus 2
88. Lange 2 1897 Lema de Gauss
89. Hilbert 1897 Ciclotomia
90. Alexejewsky 1898 Schering
91. Pepin 3 1898 Legendre
93. Konig 1899 Indução
94. Fischer 1900 Resultantes
95. Takagi 1903 Zeller
96. Lerch 2 1903 Gauss 5
97. Mertens 3 1904 Eisenstein 4
98. Mirimano e Hensel 1905 Stickelberger-Voronoi
99. Cornacchia 5 1909
100. Busche 5 1909 Zeller
101. Busche 6 1909 Eisenstein
102. Aubry 1910 Eisenstein 3
103. Aubry 1910 Voigt
104. Aubry 1910 Kronecker
106. Petr 1 1911 Mertens 3
107. Pocklington 1911 Gauss 3
108. Dedekind 3 1912 Zeller
109. Heawood 1913 Geometria
110. Frobenius 1 1914 Zeller
51
111. Frobenius 2 1914 Geometria (Eisenstein)

112. Lasker 1916 Stickelberger-Voronoi
113. Cerone 1917 Eisenstein 4
114. Bartelds e Schuh 1918 Lema de Gauss
115. Stieltjes 1918 Pontos Reticulares
116. Teege 1 1920 Legendre
117. Teege 2 1921 Ciclotomia
118. Arwin 1924 Formas Quadráticas
119. Rédei 1 1925 Lema de Gauss
120. Rédei 2 1926 Lema de Gauss
121. Whitehead 1927 Teoria da Classe (Kummer)
122. Petr 2 1927 Funções Theta
123. Skolem 1 1928 Teoria da Classe
124. Petr 3 1934 Kronecker (sinais)
125. van Veen 1934 Geometria (Eisenstein)
126. Fueter 1935 Álgebras de Quatérnios
127. Whiteman 1935 Lema de Gauss
128. Dockeray 1938 Eisenstein 3
129. Dörge 1942 Lema de Gauss
130. Rédei 3 1944 Gauss 5
131. Lewy 1946 Ciclotomia
132. Petr 4 1946 Ciclotomia
133. Skolem 2 1948 Gauss 2
134. Barbilian 1950 Eisenstein 1
135. Rédei 4 1951 Gauss 3
136. Brandt 1 1951 Gauss 2
137. Brandt 2 1951 Somas de Gauss
138. Brewer 1951 Mathieu, Pellet
139. Furquim de Almeida 1951 Corpos Finitos
140. Zassenhaus 1952 Corpos Finitos
141. Riesz 1953 Permutações
142. Fröhlich 1954 Teoria do Campo de Classe
52
143. Ankeny 1955 Ciclotomia

144. D.H. Lehmer 1957 Lema de Gauss
145. C. Meyer 1957 Somas de Dedekind
146. Holzer 1958 Somas de Gauss
147. Rédei 5 1958 Ciclotomia Polinomial
148. Reichardt 1958 Gauss 3
149. Carlitz 1960 Gauss 1
150. Kubota 1 1961 Ciclotomia
151. Kubota 2 1961 Somas de Gauss (seno)
152. Skolem 3 1961 Ciclotomia
153. Skolem 4 1961 Corpos Finitos
154. Hausner 1961 Somas de Gauss
155. Swan 1 1962 Stickelberger-Voronoi
156. Gerstenhaber 1963 Eisenstein, seno
157. Koschmieder 1963 Eisenstein, seno
158. Rademacher 1964 Análise de Fourier Finita
159. Weil 1964 Funções Theta
160. Kloosterman 1965 Holzer
161. Chowla 1966 Corpos Finitos
162. Burde 1967 Lema de Gauss
163. Kaplan 1 1969 Eisenstein
164. Kaplan 2 1969 Congruências Quadráticas
165. Birch 1971 K-grupos (Tate)
166. Reshetukha 1971 Somas de Gauss
167. Agou 1972 Corpos Finitos
168. Brenner 1973 Zolotarev
169. Honda 1973 Somas de Gauss
170. Milnor e Husemöller 1973 Weil 1964
171. Allander 1974 Lema de Gauss
172. Berndt e Evans 1974 Lema de Gauss
173. Hirzebruch e Zagier 1974 Somas de Dedekind
174. Rogers 1974 Legendre
53
175. Castaldo 1976 Lema de Gauss

176. Springer 1976 Lema de Gauss
177. Frame 1978 Kronecker (sinais)
178. Hurrelbrink 1978 K-teoria
179. Auslander e Tolimieri 1979 Transformação de Fourier
180. Corro 1980 Somas de Gauss
181. Brown 1981 Gauss 1
182. Goldschmidt 1981 Ciclotomia
183. Kac 1981 Eisenstein, seno
184. Barcanescu 1981 Zolotarev
185. Zantema 1983 Grupos de Brauer
186. Ely 1984 Lebesgue 1
187. Eichler 1985 Funções Theta
188. Barrucand e Laubie 1987 Stickelberger-Voronoi
189. Peklar 1989 Lema de Gauss
190. Barnes 1990 Zolotarev
191. Swan 2 1990 Ciclotomia
192. Rousseau 1 1990 Álgebras Exterior
193. Rousseau 2 1991 Permutações
194. Keune 1991 Corpos Finitos
195. Kubota 3 1992 Geometria
196. Russino 1992 Lema de Gauss
197. Garrett 1992 Weil 1964
198. Motose 1993 Álgebras de Grupo
199. Rousseau 3 1994 Zolotarev
200. Young 1995 Somas de Gauss
201. Brylinski 1997 Açoes de Grupos
202. Merindol 1997 Eisenstein, seno
203. Watanabe 1997 Zolotarev
204. Ishii 1998 Gauss 4
205. Motose 1999 Álgebras de Grupo
206. Zahidi 2000 Stickelberger-Voronoi
54
207. Lemmermeyer 2000 Lebesgue 1, Ely

208. Meyer 2000 Somas de Dedekind
209. Tangedal 2000 Eisenstein, Geometria
210. Chapman 2001 Sequências Recorrentes
211. Hammick 2001 Rousseau 2
212. Girstmair 2001 Eichler
213. Murty 2001 Schur
214. Luo 2003 Rousseau
215. Motose 2 2003 Schur
216. Motose 3 2003 Schur
217. Sey Yoon Kim 2004 Rousseau 2
218. Sun 2004 Lema de Gauss
219. Duke e Spears 2005 Grupos
220. Murty e Pacelli 2005 Funções Theta
221. Szyjewski 2005 Zolotarev
55
Apêndice B
Pequeno Teorema de Fermat,
Teorema de Wilson e Teorema do
Resto Chinês
Apresentaremos a seguir demonstrações e exemplicações de teoremas bastante

úteis para o estudo das Congruências Quadráticas e para a Lei de Reciprocidade
Quadrática. Estas demonstrações foram inspiradas em [3],[5],[7], [21] e [22].
B.1 Pequeno Teorema de Fermat

Este teorema já era conhecido desde a antiguidade em que os chineses, por exem-
plo, sabiam que se p é primo então p divide 2p−1 − 1. [3] arma que foi Fermat quem
desvendou o resultado geral e o propagou na matemática européia do século XVII
aplicando a linguagem de congruências à maneira moderna de enunciar o teorema.
Teorema de Fermat: Seja p um número primo. Se p - a, então ap−1 ≡
1 (mod p).
Demonstração: Como o conjunto formado pelos p números 0, 1, 2, . . . , p − 1

compõe um sistema completo de resíduos módulo p teremos que qualquer conjunto
compreendendo no máximo p elementos incongruentes módulo p pode ser colocado
em correspondência biunívoca com um subconjuntos de {0, 1, 2, . . . , p − 1}. Vamos,
agora, considerar os p−1 números múltiplos de a, isto é, os inteiros a, 2a, 3a, . . . , (p−
56
Apêndice B Apêndice
1)a. Sabendo que, pelo fato de que p não divide a, (a, p) = 1 e, portanto nenhum
dos números deste conjunto é divisível por p. Além disso, dois quaisquer deles são
incongruentes módulo p, pois se fosse
ra ≡ sa (mod p), 1 ≤ r < s ≤ p − 1
poderemos cancelar o fator comum a e teríamos r ≡ s (mod p). Isto só é possível

se r = s, já que ambos r e s são positivos e menores do que p. Temos, portanto,
um conjunto de p − 1 incongruentes módulo p e não−divisíveis por p. Então, cada
um deles é congruente a exatamente um dentre os elementos 1, 2, . . . , p − 1, e por
conseguinte multiplicando ordenadamente todas essas p − 1 congruências, teremos
a· (2a)· (3a)· . . . · (p − 1)a ≡ 1· 2· 3· . . . · (p − 1) (mod p)
ou seja,
ap−1 (p − 1)! ≡ (p − 1)! (mod p).
Mas, como p é primo e p não divide (p − 1)!, ou seja, ((p − 1)!, p) = 1, podemos
cancelar o fator comum (p-1)!, o que resulta na congruência de Fermat:
ap−1 ≡ 1 (mod p).

Corolário: Se p é um primo e a é um inteiro positivo, então ap ≡ a (mod p).
Demontração: Temos que analisar dois casos, se p | a e p - a. Se p | a, então

a ≡ 0 (mod p) e ap ≡ 0 (mod p) o que implicará em ap ≡ a (mod p). Se, ao invés,
p - a então, pelo Teorema de Fermat, ap−1 ≡ 1 (mod p). Logo,
a· ap−1 ≡ a· 1 (mod p) ⇒ ap ≡ a (mod p).
Portanto, em ambos os casos, ap ≡ a (mod p).

Exemplo: Vericar o Teorema de Fermat com a = 3 e p = 17.
57
Solução: O inteiro 17 é primo e 17 não divide 3. Então, 317−1 = 316 em que não
é necessário calcular o número muito grande 316 , pois teremos
33 = 27 ≡ 10 (mod 17)
o que resultará em
36 ≡ 100 ≡ −2 (mod 17) e 312 ≡ 4 (mod 17).
Então,
317−1 = 316 = 312 · 33 · 3 ≡ 4· 10· 3 ≡ 120 ≡ 1 (mod 17).
O leitor pode encontrar em [22] outras provas distintas para o Pequeno Teorema
de Fermat.
B.2 Teorema de Wilson

Vamos provar um teorema atribuído a Wilson (1741−1793), mas que, na verdade,
foi provado, pela primeira vez, por Joseph Louis Lagrange (1736−1813).
Teorema (Wilson): Se p é primo, então (p − 1)! ≡ −1 (mod p).
Demonstração: O teorema é verdadeiro para p = 2 e p = 3, pois
(2 − 1)! = 1! = 1 ≡ −1 (mod 2)
(3 − 1)! = 2! = 2 ≡ −1 (mod 3).
Vamos, agora, supor para p ≥ 5. Consideremos que a congruência ax ≡ 1 (mod p)

apresenta uma única solução para todo a no conjunto {1, 2, 3, . . . , p − 1} e como,
destes elementos, somente 1 e p − 1 são seus próprios inversos módulo p, podemos
p−3
agrupar os números 2, 3, 4, . . . , p − 2 em pares cujo produto seja congruente
2
a 1 módulo p. Se multiplicarmos estas congruências, membro a membro, teremos
2· 3· 4· . . . · (p − 2) ≡ 1 (mod p). Multiplicando ambos os lados desta congruência
por p − 1 obtemos
58
2· 3· 4· . . . · (p − 2)(p − 1) ≡ (p − 1) (mod p).
Então, (p − 1)! ≡ −1 (mod p) já que p − 1 ≡ −1 (mod p).

O teorema a seguir nos fornece que se um número satisfaz a relação do teorema

de Wilson, ele deve ser primo.
Teorema: Se n é um inteiro tal que (n − 1)! ≡ −1 (mod n), então n é primo.
Demonstração: Suponhamos que o inteiro n é composto. Então, n apresenta
um divisor d de forma que 1 < d < n. Também, como d ≤ n − 1, segue−se que d é
um dos fatores de (n − 1)! = 1· 2· 3· . . . · (n − 1). Portanto, d | (n − 1)!. No entanto,
por hipótese, n | (n − 1)! + 1 de maneira que d | (n − 1)! + 1. Portanto, d | 1, o que
é um absurdo. Então, n é primo.

Exemplo: Reconhecer se o inteiro 11 é primo.
Solução:
(11 − 1)! + 1 = 10! + 1 = 1· 2· 3· . . . · 10 + 1 = 3628801 = 11329891
e, assim (11 − 1)! ≡ −1 (mod 11). Logo, 11 é primo.
B.3 Teorema do Resto Chinês

O Teorema do Resto Chinês é um algoritmo para solucionar sistemas de con-
gruências lineares. Este algoritmo é muito antigo e foi descoberto pelos chineses
e pelos gregos com o intuito de resolver problemas de astronomia. Também, [3]
arma que o algoritmo do resto chinês apresenta este nome porque apareceu inici-
almente no livro Manual de aritmética do mestre Sun, escrito entre 287 d.C. e 473
d.C e, posteriormente o mesmo resultado é mencionado na Aritmética de Nicômaco
de Gerasa.
Teorema do Resto Chinês: Se (ai , mi ) = 1, (mi , mj ) = 1 para i 6= j e ci
59
inteiro, então o sistema
a1 x ≡ c1 (mod m1 )
a2 x ≡ c2 (mod m2 )
a3 x ≡ c3 (mod m3 )
..
.
ar x ≡ cr (mod mr )
possui solução e a solução é única módulo m, onde m = m1 · m2 · . . . · mr .
Demonstração: O fato (ai , mi ) = 1 nos arma que a1 x ≡ c1 (mod m1 ) contém

m
uma única solução que denotamos por bi . Se estabelecermos yi = em que,
mi
m = m1 · m2 · . . . · mr , teremos (yi , mi ) = 1, pois (mi , mj ) = 1 para i 6= j .Assim,
cada uma das congruências ar x ≡ ci (mod mi ) apresenta uma única solução que
denotaremos por yi e, então yi yi ≡ 1 (mod mi ), i = 1, 2, . . . , r. Ao armarmos que o
número x dado por
x = b1 y1 y1 + b2 y2 y2 + · · · + br yr yr
é uma solução simultãnea para o nosso sistema de congruência. Consequentemente,

ai x = ai b1 y1 y1 + ai b2 y2 y2 + · · · + ai bi yi y1 + · · · + ai br yr yr
≡ ai bi yi yi (mod mi ) ≡ ai bi ≡ ci (mod mi )
já que yi é divisível por mi para i 6= j , yi yi ≡ 1(modmi ) e bi é solução de ai x ≡

ci (mod mi ).
Em seguida, vamos demonstrar que esta solução é única módulo m. Caso x é
uma outra solução para o sistema em questão, então ai x ≡ ci ≡ ai x (mod mi ) e,
como (ai , mi ) = 1 obtemos x ≡ x (mod mi ). Portanto mi | (x − x), i = 1, 2, . . . , r.
No entanto, como (mi , mj ) = 1 para i 6= j temos que
[m1 , m2 , . . . , mr ].
Assim, m1 , m2 , . . . , mr | (x − x), ou seja, x ≡ x (mod m).

Exemplo: Três satélites passarão sobre o Rio de Janeiro esta noite. O primeiro
à 1 hora da madrugada, o segundo às 4 horas e o terceiro às 8 horas da manhã.
60
Cada satélite tem um período diferente. 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 decorrerão, a partir da meia−noite, até que os três satélites passem
ao mesmo tempo sobre o Rio.
Solução: Vamos formular este problema de maneira matemática. Chamaremos

de x o número de horas, contadas a partir da meia−noite de hoje, quando os tês
passarão juntos sobre o Rio. O primeiro satélite passa sobre o Rio a cada 13 horas,
a contar da 1 da madrugada. Isto é equivalente a dizer x ≡ 1 (mod 13). Aplicando
para os outros satélites obtemos
x ≡ 4 (mod 15) e x ≡ 8 (mod 19).
Para saber qual o horário exato de passagem dos três satélites, devemos encontrar
o valor de x que satisfaça as três equações simultaneamente. Isto é, precisamos
resolver o sistema
x ≡ 1 (mod 13)
x ≡ 4 (mod 15)
x ≡ 8 (mod 19)
Os módulos 13,15 e 19 das congruências do sistema dado são primos entre si dois a
dois, de maneira que o sistema tem uma única solução módulo m = 13· 15· 19 = 3705.
Então,
m m m
M1 = = 285, M2 = = 247 , M3 = = 195.
13 115 19
As congruências lineares
285x ≡ 1 (mod 13) ⇒ 12x ≡ 1 (mod 13)
247x ≡ 1 (mod 15) ⇒ 7x ≡ 1 (mod 15)
195x ≡ 1 (mod 19) ⇒ 5x ≡ 1 (mod 19)
tem como soluções x1 = 12, x2 = 13, x3 = 4. Logo,

X = 1· 285· 12 + 4· 247· 13 + 8· 195· 4 = 22504.
Como 22504 ≡ 274 (mod 3705), segue−se que X ≡ 274 (mod 3705) é a única
solução do sistema de congruências lineares dado.
61
Referências Bibliográcas
[1] BIASE, Adriele Giareta and AGUSTINI, Edson.Criptograas El-

Gamal, Rabin e algumas técnicas de ciframento. Disponível em
http://www.portal.famat.ufu.br/sites/famat.ufu.br/les/Anexos/Bookpage/
famat.revista.13.artigo4.0.pdf. Acesso em 28 de Junho de 2013.
[2] BOYER, C. B. and MERZBACH U. C. A History of Mathematics. John Wiley

Sons, Inc., San Francisco, CA, 1991.
[3] COUTINHO, S.C. Números inteiros e Criptograa RSA. Coleção Matemática

e Aplicações. 2. ed. Rio de Janeiro: IMPA, 2005.
[4] ELVIDGE, Sean. The History of the Law of Quadratic Reciprocity.

The University of Birmingham School of Mathematics. Disponível em
http://seanelvidge.com/wp-content/uploads/2011/04/HistoryQR.pdf. Acesso
em 27 de Fevereiro de 2013.
[5] FILHO, Edgar de Alencar. Teoria Elementar dos Números. 3. ed. São Paulo:
Nobel, 1992.
[6] FLOSE, Vania Batista Schunck. Criptograa e Curvas Elípticas. Dissertação de

Mestrado. Universidade Estadual Paulista, Instituto de Geociências e Ciências
Exatas. Rio Claro: Novembro de 2011.
[7] HEFEZ, Abramo. Elementos de Aritmética. Textos Universitários. 2. ed. Rio

de Janeiro: IMPA, 2011.
[8] KIM, S.Y. An Elementary Proof of the Quadratic Reciprocity Law Amer. Math.
M onthly 1 11 (2004), no. 1, 48-50.
62
Referências Bibliográficas
[9] LEMMERMEYER, Franz. Reciprocity Laws: From Euler to Eisenstein, chapter

1, pages 1−27. Springer, Berlin, Germany, 2000.
[10] LINDAHL, Lars-Ake. Lectures on Number Theory. Disponível em

http://www2.math.uu.se/ lal/kompendier/Talteori.pdf. Acesso em 12 de
Março de 2013.
[11] MARTINEZ, Fabio Brochero Martinez; et al. Teoria dos Números: um passeio
com primos e outros números familiares pelo mundo inteiro. Rio de Janeiro:
IMPA, 2010.
[12] MELQUIADES, José A. Rodriguez NOLE, Teresa Bracamonte. Álgebra uni-

versal para la Ciencia de la Computación: Aplicación a la Criptofrafía. Uni-
versidad Nacional de La Libertad. Facultad de Ciencias Fisicas y Matemáticas.
Departamento de Informática. Trujillo, Peru: 2009.
[13] MENEZES, Alfred J.; et al. Handbook of Applied Cryptography.119.CRC Press,

1997.
[14] MOTA, Marcelo Lisboa. Lei da Reciprocidade Qua-

drática. Disponível emhttp://www.ime.unicamp.br/ ftor-
res/ENSINO/MONOGRAFIAS/LRQMM.pdf. Acesso em 04 de Março
de 2013.
[15] NETO, Afonso Comba de Araújo. Um algoritmo de Criptograa de Chave Pú-

blica semanticamente Seguro Baseado em Curvas Elípticas. Dissertação de Mes-
trado em Ciência da Computação. Universidade Federal do Rio Grande do Sul.
Instituto de Informática. Porto Alegre: Abril de 2006.
[16] POTTER, Harrison. The Historical Development of the Law of Quadra-

tic Reciprocity. History of Mathematics. April of 2007. Disponível em
http://people.duke.edu/ hdp2/MathHistory2.pdf. Acesso em 12 de Fevereiro
de 2013.
[17] RESENDE, Marilene Ribeiro. Buscando signicados para a Teoria dos Nú-
meros como saber a ensinar na Licenciatura em Matemática. Disponí-
63
Referências Bibliográficas
vel em www.sbem.com.br/les/ix-enem/...Cientica/.../CC16109783668T.doc.
Acesso em 20 de Maio de 2013.
[18] ROSEN, Kenneth H. Elementary Number Theory and lts Applications. 5. ed.
Estados Unidos da América: Addison Wesley, 1986.
[19] SAID, Sidki. Introdução à Teoria dos Números. Coloquio Brasileiro de Mate-
matica, IMPA, 1975.
[20] SANTOS, Jorge Manuel Lopes. O uso de cifragem para proteção de canais
abertos. Dissertação de Mestrado em Ensino da Matemática. Departamento
de Matemática Pura, Faculdade de Ciências da Universidade do Porto. Porto:
Setembro de 2002.
[21] SANTOS, José Plínio de Oliveira. Introdução à Teoria dos Números. Coleção
Matemática Universitária. 3. ed. Rio de Janeiro: IMPA, 2011.
[22] SCHEINERMAN, Edward R. Matemática Discreta: Uma Introdução. São

Paulo: Cengage Learning, 2011.
[23] SILVA, Otoniel Nogueira da CÂMARA, Marcos Antônio da. O Problema

de Waring e o Teorema de Lagrange. Famat em Revista. Faculdade de
Matemática−FAMAT. Universidade Federal de Uberlândia−UFU. v. 11. Uber-
lândia: Outubro de 2008.
[24] http://w3.math.uminho.pt/site/les/historicooutros/1597Capitulo4(congruencias
quadraticas).pdf?PHPSESSID=ec35bfc49dbcb46d7e1cde4f29ed73a7. Con-
gruências Quadráticas. Acesso em 16 de Março de 2013.
[25] http://www.ime.unicamp.br/ ftorres/ENSINO/MONOGRAFIAS/LRQRoberta.pdf.

Lei da Reciprocidade Quadrática. Acesso em 09 de Março de 2013.
[26] http://www.rzuser.uni-heidelberg.de/ hb3/rchrono.html. Proofs of the Quadra-

tic Reciprocity Law. Acesso em 20 de Fevereiro de 2013.
[27] http://www.witno.com/numbers/chap6.pdf. Quadratic Residues. Acesso em 10

de Março de 2013.
64

Congruências Quadráticas

Enviado por

Direitos autorais:

Formatos disponíveis

Congruências Quadráticas

Enviado por

Dados do documento

Descrição original:

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Congruências Quadráticas

Enviado por

Direitos autorais:

Formatos disponíveis

Universidade Federal da Paraíba

Centro de Ciências Exatas e da Natureza

Leonardo Rodrigues de Araújo

Prof. Dr. Bruno Henrique Carvalho Ribeiro

Trabalho de Conclusão de Curso apresen-

Pessoal de Nível Superior.

- Ao Prof. Dr. João Marcos Bezerra do Ó e à Profa. Me. Flávia Jerônimo

- À minha família, em particular aos meus pais José Marcelino de Araújo e

- À Eneida Rodrigues de Araújo Coêlho e a Breno Rodrigues de Araújo pelo

- A todos os colegas do curso de Mestrado, pela amizade e companheirismo

- Aos professores da Pós−Graduação, pelos conhecimentos matemáticos cons-

- À Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

A Deus, fonte de inesgotável inspira-

Neste estudo, vamos avaliar se a congruência x2 ≡ a (mod m), onde m é primo

Palavras−Chaves: Congruência − Resíduos Quadráticos − Lei de Reciproci-

In this study, we evaluate if the congruence x2 ≡ a (mod m), where m is prime

Keywords: Congruence − Quadratic Residues − Law of Quadratic Reciprocity.

2 Lei de Reciprocidade Quadrática 17

Muitos matemáticos desempenharam um papel de destaque no desenvolvimento

O primeiro matemático a estudar reciprocidade quadrática foi Fermat, que tinha

nos estudos de leis superiores de reciprocidade tendo o símbolo de Legendre como

aos Resíduos Quadráticos, Símbolo de Legendre, Critério de Euler, Lema de Gauss

Neste capítulo, vamos examinar se um inteiro é ou não um resíduo quadrático

1.1 Resíduos Quadráticos

ax2 + bx + c ≡ 0 (mod p) (1.1)

de modo que a, b, c ∈ Z, p é um primo ímpar e a 6≡ 0 (mod p). Podemos observar

y 2 ≡ d (mod p). (1.2)

pelo fato de se p | a obtemos a desinteressante equação x2 ≡ 0 (mod p), e por essa

Exemplo 1.1 Resolva a congruência 8x2 + 5x + 1 ≡ 0 (mod 23).

Teorema 1.1 Para p um primo ímpar e a um inteiro não divisível por p, a

Demonstração: Consideremos que a congruência (1.3) tenha x1 como solução,

(−x1 )2 = x21 ≡ 0 (mod p).

Agora, mostremos que estas soluções x1 e −x1 são incongruentes módulo p.

resultará em p | (x1 + y) ou p | (x1 − y), o que implicará em y ≡ −x1 (mod p) ou

Exemplo 1.2 Determine todas as soluções da congruência x2 ≡ 1 (mod 3).

(i) rt não for congruente a ru módulo p para t 6= u ;

(ii) para todo inteiro k , existe um rt , tal que k ≡ rt (mod p).

Denição 1.2 Sejam a e m inteiros com (a, m) = 1. Dizemos que a é um

12 ≡ 1 (mod 17) 92 ≡ 13 (mod 17)

Podemos observar que na coluna da esquerda das congruências acima temos os

(1) x2 ≡ 1 (mod p) , que tem soluções (1, p − 1);

Exemplo 1.3 Sendo o primo 7, encontre, dentre os números {1,2,3,4,5,6}, os

Demonstração: (⇒) Sendo p = 2, pode−se vericar que x = 1 é uma solução,

e como x2 2 ≡ x(p−1) (mod p) podemos escrever, pelo Pequeno Teorema de Fer-

mat, (Anexo B), que

xp−1 ≡ 1 (mod p) ⇒ (−1) ≡ 1 (mod p)

Como j(p − j) ≡ −j 2 (mod p), pois jp − j 2 ≡ − j 2 (mod p) obtemos:

que é uma solução de x2 ≡ −1 (mod p).

1.2 Símbolo de Legendre e o Critério de Euler

Denição 1.3 Seja p um inteiro primo ímpar. Para

Teorema 1.4 (Critério de Euler) Seja p > 2 um primo e a um inteiro. Então

Demonstração: Para a ≡ 0 (mod p) o resultado é evidente, de modo que deve-

Ao multiplicarmos as congruências acima obtemos

que representa um rearranjo de 1 · 2 · 3 · . . . · (p − 1) resultando em (p − 1)! ≡

Exemplo 1.4 Vericar que a = 3 é um resíduo não quadrático módulo 7, mas é

Solução: Pelo Critério de Euler é possível escrever que

Vamos introduzir algumas propriedades que permitem o cálculo do Símbolo de

Teorema 1.5 Seja p primo ímpar e a, b, c ∈ Z. Então, pelo Critério de Euler e

Demonstração: Para a propriedade 1 é suciente observar que

Denição 1.2 Sejam a e m inteiros com (a, m) = 1. Dizemos que a é um

Demonstração: (⇒) Sendo p = 2, pode−se vericar que x = 1 é uma solução,

Denição 1.3 Seja p um inteiro primo ímpar. Para

Exemplo 1.4 Vericar que a = 3 é um resíduo não quadrático módulo 7, mas é

Demonstração: Para a propriedade 1 é suciente observar que

Com isso, da congruência anterior resulta que (−1)r a 2 ≡

Desse modo, na demonstração do Lema de Gauss deveremos fazer o que foi

Demonstração: Usando o Critério de Euler, vamos vericar que 2 ≡ 1

Com o auxílio do Teorema 1.5 pode−se vericar que se p é um número primo

Demonstração: Fazendo uso

É possível vericar que o número de pontos de coordenadas naturais no interior

Primeira Demonstração: Inicialmente, consideremos a gura (2.2) em que

Terceira Demonstração: Consideremos o conjunto C denido por C = {a :

Demonstração: Quando zermos p = 2 e tomando a = b = 1 e c = 0 obtemos

o que permite armar que −d é um resíduo quadrático módulo p, ou seja, a congruên-

Denição 2.1 Seja n um número positivo com respectiva fatoração em compo-