Apontamentos Teóricos

Prévia do material em texto

Introduc¸a˜o a` Teoria dos Nu´meros
Carlos A. M. Andre´
(DM/FCUL)
2013/14 (3o ano, 2o semestre)
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 1 / 31
Programa
Revisa˜o sobre factorizac¸a˜o de nu´meros inteiros e congrueˆncias.
! Nu´meros primos e teorema fundamental da aritme´tica.
! Aritme´tica modular; teorema chineˆs dos restos.
! Pequeno teorema de Fermat e sua generalizac¸a˜o (teorema de Euler).
! Aplicac¸o˜es a` criptografia: o criptosistema RSA.
Reciprocidade quadra´tica e formas quadra´ticas.
! Res´ıduos quadra´ticos e s´ımbolo de Legendre; crite´rio de Euler.
! Demonstrac¸a˜o da lei da reciprocidade quadra´tica.
! Formas quadra´ticas bina´rias; soma de dois quadrados.
! Aplicac¸a˜o a` factorizac¸a˜o em ane´is de inteiros quadra´ticos.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 2 / 31
Fracc¸o˜es continuadas.
! Fracc¸o˜es continuadas simples.
! Irracionais quadra´ticos.
! Func¸o˜es continuadas perio´dicas.
! A equac¸a˜o de Pell.
Curvas el´ıpticas.
! Pontos racionais de uma curva.
! Estrutura de grupo sobre uma curva el´ıptica.
! Curvas el´ıpticas sobre os racionais.
! Factorizac¸a˜o de inteiros usando curvas el´ıpticas.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 3 / 31
Teoria aditiva dos nu´meros.
! Soma de subconjuntos; teoremas de Cauchy-Davenport e de Kneser.
! Soma de sequeˆncias de inteiros; constante de Davenport.
! O me´todo polinomial de Dias da Silva e Hamidoune.
! Teoremas de Vosper, de Olson e de Pollard.
! (Somas de conjuntos e conectividade de grafos sime´tricos.)
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 4 / 31
Alguma bibliografia
R. Crandall and C. Pomerance. Prime Numbers. Springer-Verlag, New
York, 2001.
H. Davenport. The Higher Arithmetic: An Introduction to the Theory
of Numbers. 7th ed. Cambridge University Press, 1999. ISBN:
978-0-521-63446-6.
I. Niven, H. S. Zuckerman & H. L. Montgomery. An Introduction to
the Theory of Numbers. 5th ed. Wiley Text Books, 1991. ISBN:
978-0-471-62546-9.
W. Stein. Elementary Number Theory: Primes, Congruences, and
Secrets. 1st ed. Springer-Verlag, 2008. ISBN: 978-0-387-85525-7.
(Dispon´ıvel em http://modular.math.washington.edu/ent/.)
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 5 / 31
Ao longo do curso,
N = {1, 2, 3, 4, ...} = conjunto dos nu´meros naturais;
Z = {...,−2,−1, 0, 1, 2, ...} = conjunto dos nu´meros inteiros.
Temos
Z = −N ∪ {0} ∪N.
Outras notac¸o˜es sa˜o como usualmente:
N0 = N ∪ {0} = {0, 1, 2, 3, 4, ...};
Q = conjunto dos nu´meros racionais,
R = conjunto dos nu´meros reais,
C = conjunto dos nu´meros complexos.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 6 / 31
Divisibilidade
Definic¸a˜o 1.1 (Divide)
Se a, b ∈ Z, definimos
a | b ⇐⇒ ∃c ∈ Z : b = ac .
Quando a | b, dizemos que a divide b, a e´ divisor de b, ou que b e´
divis´ıvel por a.
Quando a na˜o divide b, escrevemos a ! b.
Por exemplo,
2 | 6, −3 | 15, 7 | −21, −7 | −14, . . .;
a | 0 para todo a ∈ Z;
0 | a ⇐⇒ a = 0;
3 ! 7.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 8 / 31
Divisibilidade
Teorema 1.2
Para quaisquer a, b, c ∈ Z:
1 Se a | b, enta˜o a | rb para qualquer r ∈ Z;
2 Se a | b e b | c, enta˜o a | c;
3 Se a | b e a | c, enta˜o a | (rb + sc) para quaisquer r , s ∈ Z;
4 Se a | b e b | a, enta˜o a = ±b;
5 Se a | b e a, b > 0, enta˜o a ≤ b;
6 Se n ∈ Z, n ̸= 0, enta˜o a | b se e so´ se na | nb.
Demonstrac¸a˜o.
Exerc´ıcio: por exemplo, para (3),
b = ak ∧ c = ak ′ =⇒ rb + sc = a(rk + sk ′).
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 9 / 31
Algoritmo da divisa˜o
Teorema 1.3 (Algoritmo da divisa˜o)
Para quaisquer a, b ∈ Z com b ̸= 0, existem u´nicos q, r ∈ Z tais que
a = bq + r e 0 ≤ r < |b|;
ale´m disso, se a ! b, enta˜o r ̸= 0.
Demonstrac¸a˜o (b > 0).
Existeˆncia: Seja
r = min
{
a + kb : k ∈ Z, a + kb ≥ 0
}
,
de modo que r = a − qb para algum q ∈ Z. Ora,
r ≥ b =⇒ a − (q + 1)b = a − qb − b = r − b ≥ 0,
o que e´ imposs´ıvel.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 11 / 31
Algoritmo da divisa˜o
Unicidade: Sejam q, q′, r , r ′ ∈ Z tais que
a = bq + r = bq′ + r ′ e 0 ≤ r , r ′ < b.
Enta˜o,
0 = a − a = b(q − q′) + (r − r ′) =⇒ r ′ − r = b(q − q′) =⇒ b | r ′ − r .
Ora,
0 ≤ r , r ′ < b =⇒ 0 ≤ |r ′ − r | < b.
Pelo Teorema 1.2-(5), tem de ser
r ′ − r = 0 =⇒ q − q′ = 0
(porque b ̸= 0). !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 12 / 31
Ma´ximo divisor comum
Definic¸a˜o 1.4 (Ma´ximo divisor comum)
Se a, b ∈ Z, dizemos que
d ∈ Z e´ um divisor comum de a e b quando d | a e d | b.
Quando a, b ̸= 0, definimos
mdc(a, b) = max
{
d ∈ Z : d | a e d | b
}
;
dizemos que d = mdc(a, b) e´ o ma´ximo divisor comum de a e b.
Por convenc¸a˜o, mdc(0, 0) = 0.
Por exemplo,
mdc(1, 2) = 1, mdc(−6, 27) = 3, . . .;
mdc(0, a) = mdc(a, 0) = a para qualquer a ∈ Z.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 14 / 31
Ma´ximo divisor comum
Observac¸a˜o
Para quaisquer a, b ∈ Z,
1 e´ divisor comum de a e b;
o conjunto
{
c ∈ Z : c | a, c | b
}
e´ finito e majorado por min{|a|, |b|}.
Por conseguinte, existe o ma´ximo divisor comum de a e b.
Teorema 1.5
Para quaisquer a, b ∈ Z com a, b ̸= 0,
mdc(a, b) = min
(
(aZ+ bZ) ∩N
)
onde aZ+ bZ =
{
ra + sb : r , s ∈ Z
}
.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 15 / 31
Ma´ximo divisor comum
Demonstrac¸a˜o.
A intersecc¸a˜o (aZ+ bZ) ∩N e´ na˜o-vazia, logo tem elemento m´ınimo:
d = r0a + s0b, r0, s0 ∈ Z.
Pelo algoritmo da divisa˜o, existem q, r ∈ Z tais que
a = dq + r e 0 ≤ r < d .
Como
r = a− dq = a − (r0a + s0b)q = (1− r0q)a + s0qb ∈ aZ+ bZ,
tem de ser r = 0, logo d | a. De modo ana´logo, d | b.
Como d | a e d | b, temos d ≤ mdc(a, b) = c . Por outro lado, escolhendo
a′, b′ ∈ Z tais que a = ca′ e b = cb′, vem
d = r0ca
′ + s0cb
′ = c(r0a
′ + s0b
′) =⇒ c | d =⇒ c ≤ d .
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 16 / 31
Ma´ximo divisor comum
Teorema 1.6
Para quaisquer a, b ∈ Z com a, b ̸= 0, mdc(a, b) e´ o u´nico d ∈ N que
satisfaz:
1 d | a e d | b;
2 Para qualquer c ∈ Z, se c | a e c | b, enta˜o c | d.
Demonstrac¸a˜o.
Seja c ∈ Z tal que c | a e c | b e sejam a′, b′ ∈ Z tais que a = ca′ e
b = cb′. Pelo teorema anterior, existem r , s ∈ Z tais que
mdc(a, b) = ra + sb = c(ra′ + sb′) =⇒ c | d .
Para a unicidade, basta notar que
c ̸= mdc(a, b) =⇒ c < mdc(a, b) =⇒ mdc(a, b) ! c .
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 17 / 31
Ma´ximo divisor comum
Corola´rio 1.7
Para quaisquer a, b ∈ Z e qualquer n ∈ N, tem-se
mdc(na, nb) = n ·mdc(a, b).
Demonstrac¸a˜o.
Basta observar que
(na)Z+ (nb)Z = n(aZ+ bZ)
e aplicar o Teorema 1.5. !
Corola´rio 1.8
Se a, b ∈ Z e n ∈ N for tal que n | a e n | b, enta˜o
mdc
(
a/n, b/n
)
= 1/n ·mdc(a, b).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 18 / 31
Ma´ximo divisor comum
Proposic¸a˜o 1.9
Se a, b ∈ Z e n ∈ N forem tais que mdc(a, n) = mdc(b, n) = 1, enta˜o
mdc(ab, n) = 1.
Demonstrac¸a˜o.
Sejam r , s, r ′, s ′ ∈ Z tais que
ar + ns = 1 = br ′ + ns ′.
Enta˜o,
(ar)(br ′) = (1− ns)(1− ns ′) = 1− n(s + s ′) + n2(ss ′)
e, portanto,
1 = (ab)(rr ′) + n(s + s ′ − nss ′),
o que prova que 1 = mdc(ab, n). !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 19 / 31
Ma´ximo divisor comum
Corola´rio 1.10
Se a ∈ Z e n ∈ N forem tais que mdc(a, n) = 1, enta˜o
mdc(ab, n) = mdc(b, n)
para qualquer b ∈ Z.
Demonstrac¸a˜o.
Pondo d = mdc(b, n), temos
mdc
(
b/d, n/d)
= 1/d ·mdc(b, n) = 1 =⇒ mdc
(
a · b/d, n/d
)
= 1
(pela proposic¸a˜o anterior uma vez que mdc(a, n/d) = 1) e, portanto,
mdc(ab, n) = d ·mdc
(
ab/d, n/d
)
= d .
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 20 / 31
Ma´ximo divisor comum
Definic¸a˜o 1.11
Dizemos que a, b ∈ Z sa˜o primos entre si (ou coprimos) se
mdc(a, b) = 1.
Proposic¸a˜o 1.12
Se a, b, c ∈ Z forem tais que a | bc e mdc(a, b) = 1, enta˜o a | c.
Demonstrac¸a˜o.
Temos
mdc(ac , bc) = c ·mdc(a, b) = c ,
logo
a | ac , a | bc =⇒ a | mdc(ac , bc) = c .
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 21 / 31
Ma´ximo divisor comum
Proposic¸a˜o 1.13
Para quaisquer a, b, k ∈ Z,
mdc(a, b) = mdc(b, a) = mdc(a,−b) = mdc(a, b + ka).
Demonstrac¸a˜o.
Basta notar que
aZ+ bZ = bZ+ aZ = aZ+ (−b)Z = aZ+ (b + ka)Z
e aplicar o Teorema 1.5. !
Exemplo 1.14
mdc(15, 6) = mdc(6 · 2 + 3, 6) = mdc(3, 6)
= mdc(3, 2 · 3) = 3 ·mdc(1, 2) = 3.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 22 / 31
Algoritmo de Euclides
Exemplo 1.15
Calculamos mdc(7472, 2464):
7472 = 3 · 2464 + 80 =⇒ mdc(7472, 2464) = mdc(80, 2464),
2464 = 30 · 80 + 64 =⇒ mdc(80, 2464) = mdc(80, 64),
80 = 64+16 =⇒ mdc(80, 64) = mdc(16, 64) = mdc(16, 4 ·16) = 16.
Por outro lado, invertendo o processo,
16 = 80 − 64
= 80 − (2464 − 30 · 80)
= −2464 + 31 · 80
= −2464 + 31 · (7472 − 3 · 2464)
= 31 · 7472 + (−94) · 2464.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 24 / 31
Algoritmo de Euclides
Teorema 1.16 (Algoritmo de Euclides)
Dados a, b ∈ Z, sejam q1, . . . , qt+1, r1, . . . , rt ∈ Z, com t ∈ N, tais que:
a = bq1 + r1, 0 < r1 < b,
b = r1q2 + r2, 0 < r2 < r1,
r1 = r2q3 + r3, 0 < r3 < r2,
. . . ,
rt−2 = rt−1qt + rt , 0 < rt < rt−1,
rt−1 = rtqt+1.
Enta˜o,
rt = mdc(a, b).
Ale´m disso, e´ poss´ıvel determinar r , s ∈ Z tais que
rt = ra + sb
“invertendo” sucessivamente as equac¸o˜es acima.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 25 / 31
Algoritmo de Euclides
Demonstrac¸a˜o.
Como r1 > r2 > r3 > . . . ≥ 0, tem de existir t ∈ N tal que rt+1 = 0 — e,
portanto, o algoritmo termina.
Provamos que rt = mdc(a, b) fazendo induc¸a˜o em t (= nu´mero de passos
necessa´rios para terminar o algoritmo.)
Se t = 0, enta˜o r1 = 0, logo
a = bq1 e mdc(a, b) = b = r0.
Admitamos que o teorema e´ verdadeiro sempre que o algoritmo termina
em ≤ t − 1 passos.
Comec¸ando com b e r1, o algoritmo termina em t − 1 passos, logo
rt = mdc(b, r1) = mdc(b, a − bq1) = mdc(b, a).
Deste modo, o teorema vale quando o algoritmo termina em t passos. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 26 / 31
M´ınimo mu´ltiplo comum
Definic¸a˜o 1.17 (Mı´nimo mu´ltiplo comum)
Se a, b ∈ Z, dizemos que
m ∈ Z e´ um mu´ltiplo comum de a e b quando a | c e b | c .
Definimos
mmc(a, b) = min
{
n ∈ N : a | n e b | n
}
;
dizemos que m = mmc(a, b) e´ o m´ınimo mu´ltiplo comum de a e
b.
Por exemplo,
mmc(1, 2) = 2 e mmc(−6, 27) = 54.
Teorema 1.18
Para quaisquer a, b ∈ Z e qualquer n ∈ N,
mmc(na, nb) = n ·mmc(a, b).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 28 / 31
M´ınimo mu´ltiplo comum
Demonstrac¸a˜o.
Pondo
m′ = mmc(na, nb) e m = mmc(a, b),
provamos que nm ≤ m′ e m′ ≤ nm.
Sejam r , s ∈ Z tais que m = ra = sb. Enta˜o
nm = rna = snb =⇒
{
na | nm
nb | nm
=⇒ m′ ≤ nm.
Por outro lado, se r , s ∈ Z forem tais que m′ = rna = snb, enta˜o
m′/n = ra = sb =⇒ a | m′/n e b | m′/n
=⇒ m ≤ m′/n
=⇒ nm ≤ m′.
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 29 / 31
M´ınimo mu´ltiplo comum
Teorema 1.19
Para quaisquer a, b ∈ Z,
mmc(a, b) ·mdc(a, b) = |ab|.
Demonstrac¸a˜o.
Primeiro, reduzimos ao caso em que mdc(a, b) = 1: neste caso, pondo
d = mdc(a, b), vem mdc
(
a/d, b/d
)
= 1, logo
mmc(a, b) = d ·mmc
(
a/d, b/d
)
= d ·
∣∣a/d · b/d∣∣
mdc
(
a/d, b/d
)
=
|ab|
d
=
|ab|
mdc(a, b)
.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 30 / 31
M´ınimo mu´ltiplo comum
Admitindo que mdc(a, b) = 1, ha´ que provar que
mmc(a, b) = |ab|.
Escolhendo c ∈ N tal que
mmc(a, b) = |a| · c ,
vem
b | ac =⇒ b | c =⇒ |b| ≤ c =⇒ |ab| ≤ |a|c = mmc(a, b).
Por outro lado, {
a | |ab|
b | |ab|
=⇒ mmc(a, b) ≤ |ab|
e, portanto, mmc(a, b) = |ab|. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 31 / 31
Nu´meros primos e Teorema Fundamental da Aritme´tica
Definic¸a˜o 2.1 (Nu´meros primos and nu´meros compostos)
Dizemos que:
n ∈ N e´ um nu´mero primo se n ̸= 1 e se os u´nicos divisores
positivos de n forem 1 e n.
Dizemos que n ∈ N e´ um nu´mero composto se n ̸= 1 e se n na˜o
for primo.
Denotamos por P o conjunto dos nu´meros primos.
Observac¸a˜o
O nu´mero 1 na˜o e´ primo, nem e´ composto.
Os primeiros nu´meros primos sa˜o:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, . . .
Os primeiros nu´meros compostos sa˜o:
4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, . . .
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 33 / 71
Nu´meros primos e Teorema Fundamental da Aritme´tica
Proposic¸a˜o 2.2
Qualquer nu´mero natural e´ produto de nu´meros primos.
Demonstrac¸a˜o.
Seja n ∈ N.
Se n = 1, enta˜o n e´ o produto vazio (isto e´, sem factores) de primos.
Se n for primo, na˜o ha´ nada a provar.
Se n for composto, enta˜o n = ab em que a, b < n. Por induc¸a˜o, a and b
sa˜o produtos de primos, logo n tambe´m e´ produto de primos. !
O objectivo e´ provar provar que esta factorizac¸a˜o e´ “u´nica”.
Teorema 2.3 (Lema de Euclides)
Se p ∈ P e a, b ∈ Z forem tais que p | ab, enta˜o p | a ou p | b.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 34 / 71
Nu´meros primos e Teorema Fundamental da Aritme´tica
Demonstrac¸a˜o.
Se p | a, na˜o nada para provar.
Se p ! a, enta˜o mdc(p, a) = 1 e, portanto, basta aplicar a
Proposic¸a˜o 1.12. !
Teorema 2.4 (Teorema Fundamental da Aritme´tica)
Qualquer nu´mero natural pode ser escrito de maneira u´nica (a menos da
ordem dos factores) como produto de nu´meros primos.
Demonstrac¸a˜o.
Se n = 1, enta˜o a u´nica factorizac¸a˜o poss´ıvel e´ o produto vazio de
nu´meros primos.
Assim, supomos que n > 1 e escolhemos p1, . . . , pr ∈ P tais que
n = p1p2 · · · pr .
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 35 / 71
Nu´meros primos e Teorema Fundamental da Aritme´tica
Seja
n = q1q2 · · · qs
“outra” factorizac¸a˜o de n como produto de nu´meros primos.
Pelo Lema de Euclides,
p1 | n = q1(q2 · · · qs) =⇒ p1 = q1 ou p1 | q2 · · · qs .
Usando induc¸a˜o, conclu´ımos que
p1 = qi para algum 1 ≤ i ≤ s.
Cancelando p1 e qi e repetindo o argumento (um nu´mero finito de vezes),
chegamos a` conclusa˜o que, a menos da ordem dos factores, as duas
factorizac¸o˜es sa˜o a mesma. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 36 / 71
Nu´meros primos e Teorema Fundamental da Aritme´tica
Observac¸a˜o
Usando o Teorema Fundamental da Aritme´tica, podemos escrever
qualquer m ∈ N na forma
m =
∏
p∈P
pα(p)
onde α(p) ∈ N0 e α(p) = 0 ⇐⇒ p ! m.
Se m, n ∈ N tiverem factorizac¸o˜es
m =
∏
p∈P
pα(p) e n =
∏
p∈P
pβ(p),
enta˜o
mn =
∏
p∈P
pα(p)+β(p).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 37 / 71
Nu´meros primos e Teorema Fundamental da Aritme´tica
Observac¸a˜o (cont.)
Como consequeˆncia, obtemos
m | n ⇐⇒ α(p) ≤ β(p) para qualquer p ∈ P,
de onde resulta que
mdc(m, n) =
∏
p∈P
pmin{α(p),β(p)};
mmc(m, n) =
∏
p∈P
pmax{α(p),β(p)}.
Por exemplo, como 108 = 22 · 33 · 50 e 225 = 20 · 32 · 52, vem
mdc(108, 225) = 20 · 32 · 50 = 9;
mmc(108,225) = 22 · 33 · 52 = 2700.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 38 / 71
Infinitude dos nu´meros primos
Cada nu´mero da tabela que segue e´ um nu´mero primo:
3 = 2 + 1,
7 = 2 · 3 + 1,
31 = 2 · 3 · 5 + 1,
211 = 2 · 3 · 5 · 7 + 1,
2311 = 2 · 3 · 5 · 7 · 11 + 1.
No entanto,
2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509
— se multiplicarmos os primeiros seis nu´meros primos e somarmos 1, na˜o
obtemos um nu´mero primo, mas sim um nu´mero natural que e´ divis´ıvel
por um novo nu´mero primo! Isto acontece em geral:
Teorema 2.5 (Euclides)
Existe uma infinidade de nu´meros primos.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 40 / 71
Infinitude dos nu´meros primos
Demonstrac¸a˜o.
Dados p1, . . . , pn ∈ P distintos dois-a-dois, constru´ımos um nu´mero primo
pn+1 /∈ {p1, . . . , pn}.
Seja
m = p1p2 · · · pn + 1
e sejam q1, . . . , qt ∈ P tais que
m = q1q2 · · · qt .
Se q1 = pi para algum 1 ≤ i ≤ n, enta˜o pi | m e, portanto,
pi | m − p1p2 · · · pn = m − (m − 1) = 1,
o que na˜o pode acontecer.
Deste modo, pn+1 = q1 ∈ P na˜o ocorre na lista p1, . . . , pn. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 41 / 71
Primos em progressa˜o aritme´tica
O argumento da demonstrac¸a˜o do Teorema de Euclides pode ser adaptado,
por exemplo, a progresso˜es aritme´ticas de nu´meros primos:
. . . ,−3a + b,−2a + b,−a + b, b, a + b, 2a + b, 3a + b, . . .
onde a, b ∈ Z sa˜o fixos com a ≥ 2 e mdc(a, b) = 1 — caso contra´rio, na˜o
pode existir uma infinidade de nu´meros primos com aquela forma: por
exemplo,
3k − 6 = 3(k − 2) ∈ P ⇐⇒ x = 3.
Proposic¸a˜o 2.6
Existe uma infinidade de nu´meros primos com a forma 4k − 1 para k ∈ N.
Demonstrac¸a˜o.
Suponhamos que p1, . . . , pn sa˜o primos distintos com a forma 4k − 1 e
consideremos o nu´mero
m = 4p1p2 · · · pn − 1.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 43 / 71
Primos em progressa˜o aritme´tica
Temos pi ! m para qualquer 1 ≤ i ≤ n.
Ale´m disso, se todo o divisor primo de m fosse da forma 4ℓ+ 1, m
tambe´m seria desta forma.
Como m e´ ı´mpar, todos os seus divisores primos teˆm de ser ı´mpares e,
portanto, existe p ∈ P tal que
p | m e p = 4k − 1 para algum k ∈ N.
Como p /∈ {p1, . . . , pn}, conclu´ımos que
{
p ∈ P : p = 4k − 1, k ∈ N}
e´ um conjunto infinito. !
[A demonstrac¸a˜o na˜o funciona quando 4k − 1 e´ substitu´ıdo por 4k + 1:
um produto de primos da forma 4k − 1 pode ser da forma 4k + 1.]
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 44 / 71
Primos em progressa˜o aritme´tica
Exemplo 2.7
m = 4 · 3 · 7− 1 = 83 e´ um primo com a forma 4k − 1.
m′ = 4 · 3 · 7 · 83− 1 = 6971 tambe´m e´ um primo com a forma 4k − 1.
No entanto,
m′′ = 4 · 3 · 7 · 83 · 6971 − 1 = 48601811 = 61 · 796751
na˜o e´ primo, mas
! 61 = 4 · 15 + 1 e´ primo com a forma 4k + 1,
! 796751 = 4 · 199188 − 1 e´ primo com a forma 4k − 1.
O processo continua indefinidamente:
m′′′ = 4 · 3 · 7 · 83 · 6971 · 796751 − 1 = 5591 · 6926049421
onde
! 5591 e´ primo com a forma 4k − 1;
! 6926049421 e´ primo com a forma 4k + 1.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 45 / 71
Primos em progressa˜o aritme´tica
Proposic¸a˜o 2.8
Existe uma infinidade de nu´meros primos com a forma 4k + 1 para k ∈ N.
Demonstrac¸a˜o.
Seja n ∈ N, n ≥ 2, e consideremos o nu´mero
m = (n!)2 + 1.
Seja p ∈ P o menor divisor primo de m e notemos que p > n — nenhum
dos nu´meros 2, 3, . . . , n e´ divisor de m.
Se m = pr para r ∈ N, vem (n!)2 = pr − 1, logo
(n!)p−1 = ((n!)2
)p−1/2
= (pr − 1)p−1/2
= (−1)p−1/2 +
∑
1≤k≤p−1/2
±
(
p−1/2
k
)
(pr)k .
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 46 / 71
Primos em progressa˜o aritme´tica
Segue-se que
p | (n!)p−1 − (−1)p−1/2.
Um resultado que provaremos adiante (Teorema de Euler-Fermat) garante
que
p ! n =⇒ p | (n!)p−1 − 1,
de modo que
p | ((n!)p−1 − (−1)p−1/2)− ((n!)p−1 − 1) = 1− (−1)p−1/2.
Isto so´ e´ poss´ıvel quando
1− (−1)p−1/2 = 0 ⇐⇒ (−1)p−1/2 = 1
⇐⇒ p−1/2 e´ par. ⇐⇒ 4 | p − 1.
Concluindo: qualquer nu´mero natural n ≥ 2 tem pelo menos um divisor
primo com a forma 4k + 1, o que termina a demonstrac¸a˜o. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 47 / 71
Primos em progressa˜o aritme´tica
Em geral, temos o seguinte resultado (na˜o-elementar!):
Teorema 2.9 (Dirichlet)
Se a, b ∈ Z forem tais que mdc(a, b) = 1, enta˜o existe uma infinidade de
nu´meros primos com a forma ak + b com k ∈ N.
Os primos distribuem-se muito irregularmente: alguns esta˜o “muito
pro´ximos” e outros, embora consecutivos, esta˜o “muito distantes”:
Teorema 2.10
Para qualquer n ∈ N, existem n nu´meros compostos consecutivos.
Demonstrac¸a˜o.
Os nu´meros
(n + 1)! + 2, (n + 1)! + 3, . . . , (n + 1)! + n, (n + 1)! + n + 1
sa˜o compostos. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 48 / 71
A distribuic¸a˜o dos nu´meros primos
Por causa do teorema anterior, na˜o e´ de esperar que a func¸a˜o
π(x) = #
{
p ∈ P : p ≤ x} (x ∈ R)
possa ser dada por uma fo´rmula simples.
No entanto, e´ poss´ıvel estimar a raza˜o de crescimento de π(x). A resposta
e´ dada pelo Teorema dos Nu´meros Primos que relaciona esta questa˜o com
a famosa Hipo´tese de Riemann.
De facto, a Hipo´tese de Riemann e´ equivalente a provar que a
func¸a˜o
Li(x) =
∫ x
2
1
log t dt
e´ uma “boa” aproximac¸a˜o de π(x): para qualquer x ≥ 2.01 (!?),
|π(x)− Li(x)| ≤ √x log x .
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 50 / 71
A distribuic¸a˜o dos nu´meros primos
Ha´ algumas perguntas de resposta quase imediata:
Que percentagem de nu´meros naturais sa˜o pares? Resposta: 50%.
Que percentagem de nu´meros naturais teˆm a forma 4k − 1?
Resposta: 25%.
Que percentagem de nu´meros naturais sa˜o quadrados perfeitos?
Resposta: 0%.
Para a u´ltima resposta, entenda-se que o limite da porporc¸a˜o de quadrados
perfeitos com respeito a todos os nu´meros naturais e´ igual a zero:
lim
x→+∞
#
{
n ∈ N : n ≤ x e n e´ um quadrado perfeito}
x
= 0;
de facto,
#
{
n ∈ N : n ≤ x e n e´ um quadrado perfeito} ≈ √x .
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 51 / 71
A distribuic¸a˜o dos nu´meros primos
Que percentagem de nu´meros naturais sa˜o primos?
A resposta e´ dada pelo Teorema dos Nu´meros Primos: 0% de todos os
nu´meros naturais sa˜o primos.
A pergunta crucial e´:
Dado x ∈ R, x ≥ 2, qual e´ o valor de π(x)?
Por exemplo,
x 100 200 300 400 500 600 700 800 900 1000
π(x) 25 46 62 78 95 109 125 139 154 168
A fo´rmula assimpto´tica para π(x) foi conjecturada por Gauss (com base
em ca´lculos feitos manualmente!) e foi provada independentemente por
Hadamard e por Valle´e Poussin em 1896.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 52 / 71
A distribuic¸a˜o dos nu´meros primos
Teorema 2.11 (Teorema dos Nu´meros Primos)
lim
x→+∞
π(x)
x/log x
= 1.
x π(x) x/log(x) π(x)/(x/log(x))
10 4 4.3 0.93
102 25 21.7 1.15
103 168 144.8 1.16
104 1 229 1 086 1.13
105 9 592 8 686 1.10
106 78 498 72 382 1.08
107 664 579 620 420 1.07
108 5 761 455 5 428 681 1.06
109 50 847 534 48 254 942 1.05
1010 455 052 511 434 294 482 1.048
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 53 / 71
Congrueˆncias.
Definic¸a˜o 2.12 (Congrueˆncia mo´dulo n)
Para n ∈ N, n ≥ 2, e a, b ∈ Z, definimos
a ≡ b (mod n) ⇐⇒ n | a − b.
Quando a ≡ b (mod n), dizemos que a e´ congruente a b mo´dulo n
ou que a e b sa˜o congruentes mo´dulo n.
Quando a e b na˜o sa˜o congruentes mo´dulo n, escrevemos a ̸≡ b (mod n).
Por exemplo,
6 ≡ 0 (mod 3), 7 ≡ −1 (mod 4), −1 ≡ 1 (mod 2), . . .;
3 ̸≡ 7 (mod 5).
De agora em diante, fixamos n ∈ N, n ≥ 2.C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 55 / 71
Congrueˆncias.
Teorema 2.13
Para quaisquer a, b, c , d ∈ Z:
1 a ≡ b (mod n) se e so´ se b ≡ a (mod n) se e so´ se a− b ≡ 0
(mod n);
2 Se a ≡ b (mod n) e b ≡ c (mod n), enta˜o a ≡ c (mod n);
3 Se a ≡ b (mod n) e c ≡ d (mod n), enta˜o a + c ≡ b + d (mod n) e
ac ≡ bd (mod n);
4 Se a ≡ b (mod n) e d | n, d ≥ 2, enta˜o a ≡ b (mod d);
5 Se a ≡ b (mod n), enta˜o ar ≡ br (mod nr) para todo r ∈ N.
Demonstrac¸a˜o.
Exerc´ıcio. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 56 / 71
Congrueˆncias.
Teorema 2.14
Se f (x) for um polino´mio de coeficientes inteiros e a, b ∈ Z, enta˜o
a ≡ b (mod n) =⇒ f (a) ≡ f (b) (mod n).
Demonstrac¸a˜o.
Pomos
f (x) = c0 + c1x + c2x
2 + · · ·+ cmxm (c0, c1, . . . , cm ∈ Z).
Pelo teorema anterior,
a ≡ b (mod n) =⇒ ak ≡ bk (mod n) para todo 0 ≤ k ≤ m
=⇒ ckak ≡ ckbk (mod n) para todo 0 ≤ k ≤ m
=⇒ c0 + c1a+ c2a2 + · · ·+ cmam
≡ c0 + c1b + c2b2 + · · ·+ cmbm (mod n).
Como se queria. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 57 / 71
Congrueˆncias.
A aritme´tica modular pode ser usada para obter testes de divisibilidade.
Por exemplo:
Proposic¸a˜o 2.15
Um nu´mero m ∈ Z e´ divis´ıvel por 3 se e so´ se a soma dos seus digitos for
divis´ıvel by 3.
Demonstrac¸a˜o.
Pomos
m = c0 + c1 · 10 + c2 · 102 + · · · + ct · 10t (0 ≤ ck ≤ 9).
Como 10 ≡ 1 (mod 3), vem
m ≡ c0 + c1 + c2 + · · ·+ ck (mod 3).
Assim, m ≡ 0 (mod 3) ⇐⇒ c0 + c1 + c2 + · · ·+ ck (mod 3). !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 58 / 71
Congrueˆncias.
Teorema 2.16 (Lei do corte)
Para quaisquer a, b, c ∈ Z,
ab ≡ ac (mod n) =⇒ b ≡ c (mod n/d)
onde d = mdc(a, n). Em particular,
mdc(a, n) = 1 ∧ ab ≡ ac (mod n) =⇒ b ≡ c (mod n).
Demonstrac¸a˜o.
Temos
ab ≡ ac (mod n) =⇒ n | ab − ac = a(b − c)
=⇒ n/d | a/d · (b − c)
=⇒ n/d | b − c
=⇒ b ≡ c (mod n/d).
Para a terceira implicac¸a˜o, note que mdc(n/d, a/d) = 1. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 59 / 71
Sistemas completos de res´ıduos
Definic¸a˜o 3.1 (Sistema completo de res´ıduos)
Dizemos que r ∈ Z e´ um res´ıduo mo´dulo n de a ∈ Z se a ≡ r
(mod n).
Um conjunto {r1, . . . , rn} diz-se um sistema completo de
res´ıduos mo´dulo n se:
! para qualquer a ∈ Z, existir um e um so´ 1 ≤ i ≤ n tal que
a ≡ ri (mod n).
Por exemplo,
R = {0, 1, 2, . . . , n− 1} e´ um sistema completo de res´ıduos mo´dulo n.
{−2,−1, 0, 1, 2} e´ um sistema completo de res´ıduos mo´dulo 5.
Definic¸a˜o 3.2 (Classe residual)
Para qualquer a ∈ Z, a classe residual de a e´ o conjunto
a+ nZ =
{
a + nb : b ∈ Z} = {. . . , a − 2n, a − n, a, a+ n, a + 2n, . . .}.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 61 / 83
Sistemas completos de res´ıduos
Observac¸a˜o
Existem exactamente n classes residuais mo´dulo n.
Escolher um sistema completo de res´ıduos e´ o mesmo que escolher
um representante em cada classe residual mo´dulo n.
Lema 3.3
Para quaisquer a, b ∈ Z,
a ≡ b (mod n) =⇒ mdc(a, n) = mdc(b, n).
Demonstrac¸a˜o.
Se a ≡ b (mod n), enta˜o a = b + nk para algum k ∈ Z, logo
mdc(a, n) = mdc(b + nk , n) = mdc(b, n).
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 62 / 83
Sistemas completos de res´ıduos
Definic¸a˜o 3.4 (Sistema reduzido de res´ıduos)
Um conjunto {r1, . . . , rt} diz-se um sistema reduzido de res´ıduos
mo´dulo n se:
para qualquer a ∈ Z tal que mdc(a, n) = 1, existir um e um so´
1 ≤ i ≤ t tal que a ≡ ri (mod n).
[Note que tem de ser t ≤ n.]
Proposic¸a˜o 3.5
Se R = {r1, . . . , rt} for um sistema completo (resp., reduzido) de res´ıduos
mo´dulo n e a ∈ Z for tal que mdc(a, n) = 1, enta˜o
aR =
{
ar : r ∈ R} = {ar1, . . . , art}
tambe´m e´ um sistema completo (resp., reduzido) de res´ıduos mo´dulo n.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 63 / 83
Sistemas completos de res´ıduos
Demonstrac¸a˜o.
Sejam r , s ∈ R . Como mdc(a, n) = 1, temos
ar ≡ as (mod n) =⇒ r ≡ s (mod n).
Por definic¸a˜o de R , tem de ser r = s, de modo que ar = as. O resultado
segue-se porque #(aR) = #R . !
Corola´rio 3.6
Se a, b ∈ Z e mdc(a, n) = 1, enta˜o a equac¸a˜o ax ≡ b (mod n) tem uma
soluc¸a˜o e esta soluc¸a˜o e´ u´nica mo´dulo n.
Demonstrac¸a˜o.
Se R for um sistema completo de res´ıduos mo´dulo n, o lema anterior
garante que aR tambe´m o e´. Por conseguinte, existe um e um so´ elemento
r ∈ R tal que
b ≡ ar (mod n).
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 64 / 83
Equac¸o˜es lineares mo´dulo n
Exemplo 3.7
Consideremos a equac¸a˜o 2x ≡ 3 (mod 7) e o sistema completo de
res´ıduos R = {0, 1, 2, 3, 4, 5, 6}. Temos
2R = {0, 2, 4, 6, 8, 10, 12} ≡ {0, 2, 4, 6, 1, 3, 5} (mod 7),
logo
2 · 5 ≡ 3 (mod 7).
Quando mdc(a, n) ̸= 1, a equac¸a˜o ax ≡ b (mod n) pode ter ou na˜o ter
soluc¸o˜es. Por exemplo,
2x ≡ 1 (mod 4)
na˜o tem soluc¸o˜es; no entanto,
2x ≡ 2 (mod 4)
tem (mais do que uma) soluc¸a˜o: x = 1 e x = 3.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 66 / 83
Equac¸o˜es lineares mo´dulo n
Teorema 3.8
Para quaisquer a, b ∈ Z, a equac¸a˜o ax ≡ b (mod n) tem soluc¸a˜o se e so´
se mdc(a, n) | b.
Demonstrac¸a˜o.
Seja d = mdc(a, n).
Ora,
ax ≡ b (mod n) ⇐⇒ n | ax − b,
de modo que, se ax ≡ b (mod n) tem soluc¸a˜o, enta˜o d | b (porque d | a e
d | n).
Reciprocamente, suponhamos que d | b. Enta˜o,
n | ax − b ⇐⇒ n/d | (a/d)x − (b/d),
logo ax ≡ b (mod n) tem soluc¸a˜o se e so´ se (a/d)x ≡ b/d (mod n/d) tem
soluc¸a˜o. O resultado segue-se porque mdc(a/d, n/d) = 1. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 67 / 83
Teorema de Euler-Fermat
Definic¸a˜o 3.9 (A func¸a˜o-φ de Euler)
Para n ∈ N, definimos
φ(n) = #
{
a ∈ N : a ≤ n, mdc(a, n) = 1}.
φ(n) e´ a cardinalidade de qualquer sistema reduzido de res´ıduos
mo´dulo n.
Exemplo 3.10
φ(1) = 1, φ(2) = 1, φ(5) = 4 e φ(12) = 4.
Se p ∈ P, enta˜o φ(p) = p − 1.
Teorema 3.11 (Euler-Fermat)
Para qualquer a ∈ Z,
mdc(a, n) = 1 =⇒ aφ(n) ≡ 1 (mod n).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 69 / 83
Teorema de Euler-Fermat
Demonstrac¸a˜o.
Seja
R =
{
k ∈ N : k ≤ n, mdc(k , n) = 1} = {r1, . . . , rφ(n)}
— de modo que R e´ um sistema reduzido de res´ıduos.
Como aR = {ar1, . . . , arφ(n)} tambe´m e´ um sistema reduzido de res´ıduos,
temos #aR = #R = φ(n) e
{r1, . . . , rφ(n)} ≡ {ar1, . . . , arφ(n)} (mod n).
Sendo assim,
r1 · · · rφ(n) ≡ (ar1) · · · (arφ(n)) = aφ(n)(r1 · · · rφ(n)) (mod n).
Cancelando r1 · · · rφ(n) (que e´ coprimo com n), conclu´ımos que
aφ(n) ≡ 1 (mod n).
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 70 / 83
Teorema de Euler-Fermat
Corola´rio 3.12 (Pequeno Teorema de Fermat)
Para qualquer a ∈ Z e qualquer p ∈ P com p ! a, tem-se
ap−1 ≡ 1 (mod p).
Exemplo 3.13
Qual e´ o resto da divisa˜o de 798 por 13?
Como φ(13) = 12 (porque 13 ∈ P) e mdc(7, 13) = 1, vem
712 ≡ 1 (mod 13)
(pelo teorema anterior). Sendo assim,
798 = 78·12+2 = (712)8 · 72 ≡ 49 = 3 · 13 + 10 ≡ 10 (mod 13).
A resposta e´ 10.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 71 / 83
Teorema de Wilson
Teorema 3.14 (Wilson)
Um nu´mero natural p ≥ 2 e´ primo se e so´ se (p − 1)! ≡ 1 (mod p).
Demonstrac¸a˜o.
O´bvio quando p = 2. Assim, supomos que p ≥ 3.
=⇒: Admitindo que p ∈ P, provamos que (p − 1)! ≡ 1 (mod p).
Se 1 ≤ a < p, enta˜o a equac¸a˜o
ax ≡ 1 (mod p)
tem uma e uma so´ soluc¸a˜o 1 ≤ a′ < p.
Se for a′ = a, enta˜o
a2 ≡ 1 (mod p) =⇒ p | a2 − 1 = (a − 1)(a + 1)
=⇒ p | a − 1 ou p | a + 1
=⇒ a = 1 ou a = p − 1.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 73 / 83
Teorema de Wilson
Por conseguinte,podemos particionar {2, 3, . . . , p − 2} em pares {a, a′} de
elementos mutuamente “inversos” mo´dulo p, de modo que
2 · 3 · · · (p − 2) ≡ 1 (mod p) =⇒ (p − 1)! ≡ p − 1 ≡ −1 (mod p).
⇐=: Admitindo que (p − 1)! ≡ 1 (mod p), provamos que p ∈ P.
Se tal na˜o acontecer, seja ℓ um divisor primo de p. Enta˜o,
ℓ < p =⇒ ℓ | (p − 1)!.
Como
(p − 1)! ≡ −1 (mod p) ⇐⇒ p | (p − 1)! + 1,
conclu´ımos que
ℓ | (p − 1)!− ((p − 1)! + 1) = −1,
uma contradic¸a˜o. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 74 / 83
Teorema de Wilson
Exemplo 3.15
Se p = 3, enta˜o
(p − 1)! = 2 ≡ −1 (mod 3).
Se p = 17, enta˜o
(p − 1)! = 20922789888000 ≡ −1 (mod 17).
Mas, se p = 15, enta˜o
(p − 1)! = 87178291200 ≡ 0 (mod 15) =⇒ 15 /∈ P.
Ilustramos a passagem principal da demonstrac¸a˜o: para p = 17,
16! = (2 · 9) (3 · 6) (4 · 13) (5 · 7) (8 · 15) (10 · 12) (14 · 11) 16
≡ 16 ≡ −1 (mod 17).
onde agrupamos os pares (a, a′) tais que aa′ ≡ 1 (mod 17).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 75 / 83
Teorema de Wilson
Teorema 3.16
Se p ∈ P, enta˜o a equac¸a˜o x2 ≡ −1 (mod p) tem soluc¸o˜es se e so´ se
p = 2 ou p ≡ 1 (mod 4).
Demonstrac¸a˜o.
O resultado e´ o´bvio quando p = 2. Assim supomos que p ≥ 3.
⇐=: Supomos p ≡ 1 (mod 4) e escrevemos
(p − 1)! = (1 · 2 · · · (p−1/2))((p+1/2) · · · (p − 2)(p − 1)).
Como p − k ≡ −k (mod p), o Teorema de Wilson implica que
−1 ≡ (p − 1)! ≡ (−1)p−1/2(1 · 2 · · · (p−1/2))2 (mod p).
Como p ≡ 1 (mod 4), p−1/2 e´ par, logo a = (p−1/2)! e´ uma soluc¸a˜o de
x2 ≡ −1 (mod p).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 76 / 83
Teorema de Wilson
=⇒: Supomos que x2 ≡ −1 (mod p) tem uma soluc¸a˜o a ∈ Z.
Enta˜o,
ap−1 = (a2)
p−1/2 ≡ (−1)p−1/2 (mod p).
Como p ! a (caso contra´rio, −1 ≡ a2 ≡ 0 (mod p)), o Teorema de
Euler-Fermat garante que
ap−1 ≡ 1 (mod p)
e, portanto,
(−1)p−1/2 ≡ 1 (mod p).
Como p ≥ 3, na˜o pode ser −1 ≡ 1 (mod p), logo
(−1)p−1/2 = 1 ⇐⇒ p ≡ 1 (mod 4).
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 77 / 83
Somas de 2 quadrados
Teorema 3.17
Se p ∈ P for tal que p ≡ 1 (mod 4), enta˜o existem a, b ∈ Z tais que
p = a2 + b2.
Demonstrac¸a˜o.
Pelo teorema anterior, existe k ∈ Z tal que
k2 ≡ −1 (mod p).
Definamos
f (r , s) = r + ks e ℓ = ⌊√p⌋.
Como
√
p /∈ N, tem-se
ℓ <
√
p < ℓ+ 1.
Consideremos o “quadrado”
Q =
{
(r , s) ∈ Z2 : 0 ≤ r , s ≤ ℓ}.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 79 / 83
Somas de 2 quadrados
Temos
#Q = (ℓ+ 1)2 > (
√
p)2 = p.
Como existem p classes residuais mo´dulo p, teˆm de existir pelo menos dois
pares (r , s), (r ′, s ′) ∈ Q tais que
(r , s) ̸= (r ′, s ′) e f (r , s) ≡ f (r ′, s ′) (mod p).
Assim,
r + ks ≡ r ′ + ks ′ (mod p) ⇐⇒ r − r ′ ≡ −k(s − s ′) (mod p).
Pondo
a = r − r ′ e b = s − s ′,
vem
a ≡ −kb (mod p) =⇒ a2 ≡ (−kb)2 ≡ k2b2 ≡ −b2 (mod p).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 80 / 83
Somas de 2 quadrados
Sendo assim,
p | a2 + b2.
Ora,
(r , s) ̸= (r ′, s ′) =⇒ a ̸= 0 ou b ̸= 0 =⇒ a2 + b2 > 0.
Ale´m disso,
0 ≤ r , r ′ ≤ ℓ < √p =⇒ −√p < a < √p,
0 ≤ s, s ′ ≤ ℓ < √p =⇒ −√p < b < √p
e, portanto,
|a|, |b| < √p =⇒ a2, b2 < p =⇒ a2 + b2 < 2p.
Finalmente,
p | a2 + b2 < 2p =⇒ a2 + b2 = p.
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 81 / 83
Somas de 2 quadrados
Teorema 3.18
Se p ∈ P for tal que p ≡ 3 (mod 4), enta˜o, para quaisquer a, b ∈ Z,
p | a2 + b2 =⇒ p | a e p | b.
Demonstrac¸a˜o.
Suponhamos que p ! a e seja c ∈ Z tal que
ac ≡ 1 (mod p).
Enta˜o,
p | a2 + b2 =⇒ a2 ≡ −b2 (mod p)
=⇒ 1 ≡ (ac)2 ≡ −(ba)2 (mod p),
de modo que ba e´ soluc¸a˜o da equac¸a˜o x2 ≡ −1 (mod p).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 82 / 83
Somas de 2 quadrados
Pelo Teorema 3.16, tem de ser p = 2 ou p ≡ 1 (mod 4), contra a hipo´tese.
Segue-se que p | a e, analogamente, p | b. !
Teorema 3.19 (Fermat)
Seja n ∈ N e seja
n = 2t
∏
p∈P
p≡1 (mod 4)
pα(p)
∏
p∈P
p≡3 (mod 4)
pβ(p)
a factorizac¸a˜o de n em nu´meros primos. Enta˜o, n e´ uma soma de dois
quadrados se e so´ se todos os expoentes β(p) forem pares.
Demonstrac¸a˜o.
Exerc´ıcio: note que
(a2 + b2)(c2 + d2) = (ac − bd)2 + (ad − bc)2.
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 83 / 83
Teorema Chineˆs dos Restos
Teorema 4.1 (Teorema Chineˆs dos Restos)
Se m1, . . . ,mr ∈ N forem coprimos dois-a-dois, enta˜o, para quaisquer
a1, . . . , ar ∈ Z, o sistema de congrueˆncias⎧⎪⎪⎪⎪⎨
⎪⎪⎪⎪⎩
x1 ≡ a1 (mod m1)
x2 ≡ a2 (mod m2)
. . . . . . . . .
xr ≡ ar (mod mr )
tem soluc¸a˜o e, ale´m disso, esta soluc¸a˜o e´ u´nica mo´dulo m = m1m2 · · ·mr .
Demonstrac¸a˜o.
Pondo m = m1m2 · · ·mr , temos mdc(m/mi ,mi ) = 1 e, portanto, para cada
1 ≤ i ≤ r , existe bi tal que
(m/mi)bi ≡ 1 (mod mi ).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 85 / 111
Teorema Chineˆs dos Restos
E´ claro que
(m/mi)bi ≡ 0 (mod mj) (j ̸= i).
Pondo
x0 =
r∑
i=1
(m/mi)biai ,
vemos que
x0 ≡ (m/mi)biai ≡ ai (mod mi) (1 ≤ i ≤ r)
e, portanto, x0 e´ soluc¸a˜o do sistema.
Se x1 for outra soluc¸a˜o, temos
x0 ≡ x1 (mod mi ) (1 ≤ i ≤ r)
e, portanto,
x0 ≡ x1 (mod m)
porque m1, . . . ,mr sa˜o coprimos dois-a-dois. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 86 / 111
Multiplicatividade da func¸a˜o de Euler
Teorema 4.2
A func¸a˜o-φ de Euler e´ multiplicativa, isto e´: se m, n ∈ N forem
coprimos, enta˜o φ(mn) = φ(m)φ(n).
Demonstrac¸a˜o.
Sejam R(mn), R(m) e R(n) sistema reduzidos de res´ıduos mo´dulo mn, m
e n, respectivamente.
Definimos f : R(mn)→ R(m) da seguinte forma: dado r ∈ R(mn),
escolhemos o u´nico res´ıduo f (r) ∈ R(m) tal que
r ≡ f (r) (mod m)
— notemos que mdc(r ,m) = 1 porque mdc(r ,mn) = 1.
Analogamente, definimos g : R(mn)→ R(n) declarando que, para
qualquer r ∈ R(mn), a imagem g(r) e´ o u´nico res´ıduo em R(n) tal que
r ≡ g(r) (mod n).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 88 / 111
Multiplicatividade da func¸a˜o de Euler
Finalmente, definimos
h : R(mn)→ R(m)× R(n)
por
h(r) =
(
f (r), g(r)
)
, r ∈ R(mn)
e provamos que h e´ bijectiva.
h e´ injectiva: Sejam r , s ∈ R(mn) tais que
(
f (r), g(r)
)
=
(
f (s), g(s)
)
.
Deste modo, {
r ≡ f (r) = f (s) ≡ s (mod m),
r ≡ g(r) = g(s) ≡ s (mod n)
e, portanto, r e s sa˜o soluc¸o˜es do sistema{
x ≡ a (mod m),
x ≡ b (mod n),
onde a = f (r) = f (s) e b = g(r) = g(s).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 89 / 111
Multiplicatividade da func¸a˜o de Euler
Pelo Teorema Chineˆs dos Restos, conclu´ımos que
r ≡ s (mod mn)
de onde resulta que r = s (porque R(mn) e´ sistema reduzido de res´ıduos).
h e´ sobrejectiva: dados quaisquer a ∈ R(m) e b ∈ R(n), consideramos o
sistema {
x ≡ a (mod m),
x ≡ b (mod n).
Como mdc(m, n) = 1, o Teorema Chineˆs dos Restos garante que este
sistema tem soluc¸a˜o, isto e´, existe c ∈ Z tal que{
c ≡ a (mod m),
c ≡ b (mod n).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 90 / 111
Multiplicatividade da func¸a˜o de Euler
Pelo Lema 3.3, conclu´ımos que{
mdc(c ,m) = mdc(a,m) = 1,
mdc(c , n) = mdc(b,m) = 1,
=⇒ mdc(c ,mn) = 1.
Sendo assim, existe r ∈ R(mn) tal que c ≡ r (mod mn). Como
r ≡ c (mod mn) =⇒
{
r ≡ c ≡ a (mod m),
r ≡ c ≡ b (mod n),
segue-se que f (r) = a e g(r) = b, logo
h(r) =
(
f (r), g(r)
)
= (a, b).
Para terminar, a bijectividade de h implica que
φ(mn) = #R(mn) =
(
#R(m)
)
·
(
#R(n)
)
= φ(m) · φ(n).
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 91 / 111
Ca´lculo da func¸a˜o-φ de Euler
Teorema 4.3
Para quaisquer p ∈ P e e ∈ N,tem-se φ(pe) = pe−1(p − 1).
Demonstrac¸a˜o.
Para qualquer a ∈ {1, 2, . . . , pe}, temos
mdc(a, pe) ̸= 1 ⇐⇒ a ∈ {p, 2p, . . . pe−1p}.
Sendo assim,
φ(pe) = pe − pe−1 = pe−1(p − 1).
!
Exemplo 4.4
φ(2453112) = φ(24)φ(53)φ(112)
= 23(2− 1) · 52(5− 1) · 11(11 − 1)
= 265311.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 93 / 111
O criptosistema RSA
Na de´cada 1970-80, comec¸aram a usar-se te´cnicas de Teoria dos Nu´meros
que permitem a duas pessoas (Alice e Bob) comunicar mensagens secretas
num ambiente hostil, em que qualquer mensagem pode ser interceptada e
lida por intrusos. Estas te´cnicas sa˜o usadas no dia-a-dia (em compras
“online”, em caixas de Multibanco, etc.) e essencialmente baseiam-se na
aritme´tica mo´dulo n.
O criptosistema RSA foi introduzido por Rivest, Shamir e Adleman
[1978].
A ideia fundamental e´ construir um “alc¸apa˜o” (ou, uma func¸a˜o de sentido
u´nico) E : X → X num conjunto X — por definic¸a˜o, E tem de ser
bijectiva e tal que Alice possa calcular facilmente a inversa E−1, mas que
este ca´lculo seja extremamente dif´ıcil para qualquer outra pessoa. Alice
define esta func¸a˜o como se segue:
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 95 / 111
O criptosistema RSA
Escolhe dois nu´meros primos “grandes” p e q, e faz n = pq.
Calcula a func¸a˜o de Euler:
φ(n) = φ(p)φ(q) = (p − 1)(q − 1).
Escolhe aleatoriamente e ∈ N tal que
1 < e < φ(n) e mdc(e,φ(n)) = 1.
Determina 1 < d < φ(n) tal que
ed ≡ 1 (mod φ(n)).
Define E : {0, 1, 2, . . . , n − 1}→ {0, 1, 2, . . . , n − 1} por
E (x) ≡ xe (mod n) (0 ≤ x < n).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 96 / 111
O criptosistema RSA
A chave pu´blica de Alice e´ o par (n, e) que conte´m a informac¸a˜o
suficiente para que qualquer um possa calcular E (x) eficientemente.
A chave secreta de Alice e´ o nu´mero d que lhe permite calcular
facilmente a inversa E−1 (uma vez que d e´ dif´ıcil de determinar
usando apenas a chave pu´blica — porque depende de φ(n) e a
factorizac¸a˜o n = pq so´ e´ conhecida por Alice!).
Teorema 4.5
Se p, q ∈ P com p ̸= q, n = pq e e, d ∈ N forem tais que ed ≡ 1
(mod φ(n)), enta˜o aed ≡ a (mod n) para todo a ∈ Z.
Demonstrac¸a˜o.
Se p | a, temos a ≡ 0 (mod p), logo aed ≡ 0 ≡ a (mod p).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 97 / 111
O criptosistema RSA
Demonstrac¸a˜o.
Se p ! a, temos ap−1 ≡ 1 (mod p) (pelo Pequeno Teorema de Fermat).
Como p − 1 | φ(n),
ed ≡ 1 (mod φ(n)) =⇒ ed ≡ 1 (mod p − 1)
e, portanto,
ed = (p − 1)k + 1, k ∈ N.
Segue-se que
aed = (ap−1)ka ≡ a (mod p).
Analogamente se prova que
aed ≡ a (mod q).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 98 / 111
O criptosistema RSA
Como p ̸= q e n = pq, conclu´ımos que
aed ≡ a (mod n).
!
Exemplo 4.6
Escolhemos p = 17 e q = 19, de modo que n = pq = 323.
φ(323) = φ(17)φ(19) = 16 · 18 = 288.
Escolhemos e = 95 (< 288).
Usando o Algoritmo de Euclides, encontramos d = 191: de facto,
95 · 191 ≡ 1 (mod 288).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 99 / 111
O criptosistema RSA
Neste exemplo, a chave pu´blica e´ (323, 95), de modo que a func¸a˜o (de
codificac¸a˜o) e´ dada por
E (x) ≡ x95 (mod 323) (0 ≤ x < 323).
A func¸a˜o-inversa (de descodificac¸a˜o) e´ dada por
D(x) ≡ x191 (mod 323) (0 ≤ x < 323).
Se a letra “X” for codificada como o nu´mero 24, temos
E (24) = 2495 ≡ 294 (mod 323).
Para decifrar, calculamos a inversa:
D(294) = 294191 ≡ 24 (mod 323).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 100 / 111
Res´ıduos quadra´ticos
Ja´ considera´mos equac¸o˜es lineares
ax − b ≡ 0 (mod n);
uma equac¸a˜o destas tem uma soluc¸a˜o se e so´ se mdc(a, n) | b.
Questa˜o
Procuramos crite´rios para que uma equac¸a˜o quadra´tica
ax2 + bx + c ≡ 0 (mod n)
tenha soluc¸o˜es.
Em particular: quando e´ que um dado nu´mero inteiro a ∈ Z e´ um
quadrado mo´dulo n?
Para o caso em que n = p ∈ P, veremos que a resposta depende da
reduc¸a˜o de p mo´dulo 4a — um facto surpreendente!).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 102 / 111
Res´ıduos quadra´ticos
Definic¸a˜o 4.7 (Res´ıduo quadra´tico)
Dados p ∈ P e a ∈ Z tal que p ! a, dizemos que a e´ um res´ıduo
quadra´tico mo´dulo p se existir b ∈ Z tal que a ≡ b2 (mod p).
Por exemplo,
1 e 4 sa˜o res´ıduos quadra´ticos mo´dulo 5.
2 e 3 na˜o sa˜o res´ıduos quadra´ticos mo´dulo 5.
Definic¸a˜o 4.8 (S´ımbolo de Legendre)
Para p ∈ P, p ≥ 3, e a ∈ Z, definimos o s´ımbolo de Legendre
(
a
p
)
=
⎧⎪⎨
⎪⎩
0, se p | a,
1, se a for um res´ıduo quadra´tico mo´dulo p,
−1, se a na˜o for um res´ıduo quadra´tico mo´dulo p.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 103 / 111
Res´ıduos quadra´ticos
Por exemplo,(
1
5
)
=
(
4
5
)
= 1,
(
2
5
)
=
(
3
5
)
= −1 e
(
5
5
)
= 0.
Proposic¸a˜o 4.9
Para qualquer p ∈ P, p ≥ 3, tem-se(
1
p
)
= 1 e
(
−1
p
)
= (−1)
p−1/2.
Demonstrac¸a˜o.
E´ claro que
(
1
p
)
= 1.
Para
(
−1
p
)
basta usar o Teorema 3.16. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 104 / 111
Crite´rio de Euler
A proposic¸a˜o anterior e´ consequeˆncia do seguinte resultado mais
geral.
Teorema 4.10 (Crite´rio de Euler)
Para qualquer p ∈ P, p ≥ 3, e qualquer a ∈ Z, tem-se(
a
p
)
≡ a
p−1/2 (mod p).
Demonstrac¸a˜o.
Se
(
a
p
)
= 1, existe b ∈ Z tal que a ≡ b2 (mod p) e, portanto,
a
p−1/2 ≡ bp−1 ≡ 1 =
(
a
p
)
(mod p).
por outro lado, suponhamos que
(
a
p
)
= −1, de modo que a equac¸a˜o
x2 ≡ a (mod p) na˜o tem soluc¸o˜es.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 106 / 111
Crite´rio de Euler
Demonstrac¸a˜o.
Para cada 1 ≤ b < p, escolhemos 1 ≤ b′ < p tal que
bb′ ≡ a (mod p).
Na˜o pode ser b′ = b, caso contra´rio b2 ≡ a (mod p).
Deste modo, decompomos {1, 2, . . . , p − 1} como unia˜o disjunta de p−1/2
subconjuntos da forma {b, b′}, que corresponde a decompor (p− 1)! como
produto de p−1/2 factores da forma bb′.
Segue-se que
(p − 1)! ≡ a
p−1/2 (mod p),
logo
a
p−1/2 ≡ −1 =
(
a
p
)
(mod p)
(usando o Teorema de Wilson). !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 107 / 111
Crite´rio de Euler
Corola´rio 4.11
Para qualquer p ∈ P, p ≥ 3, e quaisquer a, b ∈ Z, tem-se:
1
(
ab
p
)
=
(
a
p
)(
b
p
)
;
2 a ≡ b (mod p) =⇒
(
a
p
)
=
(
b
p
)
.
Demonstrac¸a˜o.
Para (1),(
ab
p
)
≡ (ab)
p−1/2 = a
p−1/2b
p−1/2 ≡
(
a
p
)(
b
p
)
(mod p),
a igualdade segue-se porque o s´ımbolo de Legendre toma os valores 0,±1
e p ̸= 2.
(2) e´ ana´logo, escrevendo a = b + kp para k ∈ Z. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 108 / 111
Lema de Gauss
Teorema 5.1 (Lema de Gauss)
Sejam p ∈ P, p ≥ 3, e a ∈ Z tal que p ! a. Consideremos o conjunto
{a, 2a, . . . , (p−1/2)a} e, para cada 1 ≤ k ≤ p−1/2, seja 1 ≤ rk < p tal que
ka ≡ rk (mod p). Enta˜o,(
a
p
)
= (−1)n, para n = #
{
rk : 1 ≤ k ≤ p−1/2, p/2 < rk
}
.
Demonstrac¸a˜o.
Sejam r ′1, . . . , r
′
n ∈ {r1, . . . , rp−1/2} os res´ıduos que excedem p/2 e r
′′
1 , . . . , r
′′
m
os restantes — de modo que n +m = p−1/2.
Temos
0 < p − r ′i < p/2, i = 1, 2, . . . , n.
Ale´m disso,
{p − r ′1, . . . , p − r
′
p/2} ∩ {r
′′
1 , . . . , r
′′
m} ̸= ∅.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 110 / 136
Lema de Gauss
De facto, suponhamos que p − r ′i = r
′′
j para alguns 1 ≤ i , j ≤ p−1/2. Sejam
1 ≤ k , ℓ ≤ p−1/2 tais que
r ′i ≡ ka (mod p) e r
′′
j ≡ ℓa (mod p).
Enta˜o,ℓa ≡ r ′′j = p − r
′
i ≡ −r
′
i ≡ −ka (mod p) =⇒ ℓ ≡ −k (mod p)
(porque p ! a). Isto significa que p | (ℓ+ k) o que na˜o pode acontecer
porque
ℓ + k ≤ p−1/2 + p−1/2 = p − 1.
Deste modo, temos n+m = p−1/2 nu´meros distintos
1 ≤ p − r ′1, . . . , p − r
′
n, r
′′
1 , . . . , r
′′
m ≤ p−1/2,
de maneira que
{p − r ′1, . . . , p − r
′
p/2} ∪ {r
′′
1 , . . . , r
′′
m} = {1, 2, . . . , p−1/2}.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 111 / 136
Lema de Gauss
Segue-se que (
p−1/2
)
! = (p − r ′1) · · · (p − r
′
n)r
′′
1 · · · r
′′
m
≡ (−r ′1) · · · (−r
′
n)r
′′
1 · · · r
′′
m
≡ (−1)n
(
r ′1 · · · r
′
nr
′′
1 · · · r
′′
m
)
≡ (−1)n
(
a · 2a · · · (p−1/2)a
)
= (−1)nap−1/2
(
p−1/2
)
! (mod p).
Cancelando
(
p−1/2
)
!, obtemos
(−1)nap−1/2 ≡ 1 (mod p) ⇐⇒ ap−1/2 ≡ (−1)n (mod p),
o que da´ o resultado (pelo Crite´rio de Euler). !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 112 / 136
Lema de Gauss
Teorema 5.2
Se p ∈ P, p ≥ 3, e a ∈ Z for tal que 2p ! a, enta˜o:
1
(
a
p
)
= (−1)t onde t =
p−1/2∑
k=1
⌊
ka
p
⌋
.
2
(
2
p
)
= (−1)
p2−1/8.
Demonstrac¸a˜o.
Mantemos a notac¸a˜o de demonstrac¸a˜o anterior.
Notemos que
{r1, . . . , rp−1/2} = {r
′
1, . . . , r
′
n, r
′′
1 , . . . , r
′′
m}
sa˜o os restos da divisa˜o por p dos inteiros a, 2a, . . . ,
(
p−1/2
)
a e que
ka = p ·
⌊
ka
p
⌋
+ rk , 1 ≤ k ≤ p−1/2.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 113 / 136
Lema de Gauss
Assim,
a ·
p−1/2∑
k=1
k =
p−1/2∑
k=1
ka = p ·
p−1/2∑
k=1
⌊
ka
p
⌋
+
p−1/2∑
k=1
rk
= p ·
p−1/2∑
k=1
⌊
ka
p
⌋
+
n∑
i=1
r ′i +
m∑
j=1
r ′′j .
Por outro lado,
p−1/2∑
k=1
k =
n∑
i=1
(p − r ′i ) +
m∑
j=1
r ′′j = np −
n∑
i=1
r ′i +
m∑
j=1
r ′′j .
Subtraindo, obtemos
(a − 1) ·
p−1/2∑
k=1
k = p ·
⎛
⎝p−1/2∑
k=1
⌊
ka
p
⌋
− n
⎞
⎠+ 2 · n∑
i=1
ri .
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 114 / 136
Lema de Gauss
Como p−1/2∑
k=1
k =
p2 − 1
8
,
conclu´ımos que
(a − 1) ·
p2 − 1
8
≡
p−1/2∑
k=1
⌊
ka
p
⌋
− n (mod 2).
Se a for ı´mpar, obtemos
n ≡
p−1/2∑
k=1
⌊
ka
p
⌋
(mod 2).
Se a = 2, vem
n ≡
p2 − 1
8
(mod 2)
uma vez que
⌊
2k/p
⌋
= 0 para qualquer 1 ≤ k ≤ p−1/2.
Para terminar a demonstrac¸a˜o, basta aplicar o Lema de Gauss. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 115 / 136
Reciprocidade quadra´tica
Teorema 5.3 (Lei da reciprocidade quadra´tica)
Se p, q ∈ P forem ı´mpares, enta˜o(
q
p
)
= (−1)(p−1)(q−1)/4
(
p
q
)
.
Observac¸a˜o
Uma forma equivalente de formular este teorema e´:
Se os nu´meros primos p e q forem ambos da forma 4k + 3, enta˜o
uma das equac¸o˜es
x2 ≡ p (mod q) e x2 ≡ q (mod p)
tem soluc¸a˜o e a outra na˜o.
Se pelo menos um dos nu´meros primos p e q for da forma 4k + 1,
enta˜o, ou as duas equac¸o˜es teˆm soluc¸a˜o, ou nenhuma tem.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 117 / 136
Reciprocidade quadra´tica
Demonstrac¸a˜o.
Consideramos o “quadrado”
Q =
{
(k , ℓ) ∈ Z2 : 1 ≤ k , ℓ ≤ (p−1)/2
}
que tem (p−1)(q−1)/4 elementos.
Particionamos Q como a unia˜o disjunta Q = Q1 unionsq Q2 onde
Q1 =
{
(k , ℓ) ∈ Q : qk > pℓ
}
e Q2 =
{
(k , ℓ) ∈ Q : qk < pℓ
}
— na˜o pode acontecer qk = pℓ: caso contra´rio, seria p | k (e q | ℓ).
Temos
Q1 =
{
(k , ℓ) ∈ Z2 : 1 ≤ k ≤ (p−1)/2, 1 ≤ ℓ < qk/p
}
,
∣∣Q1∣∣ =
(p−1)/2∑
k=1
⌊
qk
p
⌋
.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 118 / 136
Reciprocidade quadra´tica
Analogamente,
Q2 =
{
(k , ℓ) ∈ Z2 : 1 ≤ ℓ ≤ (p−1)/2, 1 ≤ k < pℓ/q
}
,
∣∣Q2∣∣ =
(p−1)/2∑
ℓ=1
⌊
pℓ
q
⌋
.
Deste modo,
(p − 1)(q − 1)
4
=
∣∣Q∣∣ = ∣∣Q1∣∣+ ∣∣Q2∣∣ =
(p−1)/2∑
k=1
⌊
qk
p
⌋
+
(p−1)/2∑
ℓ=1
⌊
pℓ
q
⌋
.
Pelo Teorema 5.2, conclu´ımos que(
p
q
)(
q
p
)
= (−1)(p−1)(q−1)/4.
!
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 119 / 136
Reciprocidade quadra´tica
Exemplo 5.4
Calculamos
(
−42
61
)
:
(
−42
61
)
=
(
−1
61
)(
2
61
)(
3
61
)(
7
61
)
.(
−1
61
)
= (−1)60/2 = 1.(
2
61
)
= (−1)(61
2
−1)/8 = −1.(
3
61
)
= (−1)2/2·60/2
(
61
3
)
=
(
1
3
)
= 1.(
7
61
)
= (−1)6/2·
60/2
(
61
3
)
=
(
5
7
)
= (−1)4/2·
6/2
(
7
5
)
=
(
2
5
)
= (−1)24/8 = −1.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 120 / 136
Reciprocidade quadra´tica
Assim (
−42
61
)
= 1
— e, portanto, −42 e´ um quadrado mo´dulo 61.
Ha´ processos de ca´lculo mais ra´pidos:(
−42
61
)
=
(
19
61
)
= (−1)18/2·60/2
(
61
19
)
=
(
61
19
)
=
(
4
19
)
=
(
2
19
)2
= 1.
Exemplo 5.5
Determinamos os nu´meros primos ı´mpares p ∈ P para os quais 3 e´ um
quadrado mo´dulo p.
Temos (
3
p
)
= (−1)(p−1)/2
(p
3
)
.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 121 / 136
Reciprocidade quadra´tica
Como
(p
3
)
=
⎧⎪⎪⎪⎨
⎪⎪⎪⎩
(
1
3
)
= 1, se p ≡ 1 (mod 3),(
2
3
)
= −1, se p ≡ 2 (mod 3),
(−1)
(p−1)/2 =
{
1, se p ≡ 1 (mod 4),
−1, se p ≡ 3 (mod 4),
conclu´ımos que
(
3
p
)
= 1 ⇐⇒
{
p ≡ 1 (mod 3),
p ≡ 1 (mod 4)
ou
{
p ≡ 2 (mod 3),
p ≡ 3 (mod 4)
⇐⇒ p ≡ 1 (mod 12) ou p ≡ 11 (mod 12).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 122 / 136
Formas bina´rias quadra´ticas
Nesta secc¸a˜o, consideramos formas quadra´ticas bina´rias, isto e´, polino´mios
f (x , y) = ax2 + bxy + cy2
em que a, b, c ∈ Z e procuramos condic¸o˜es para que um nu´mero natural
n ∈ N possa ser representado por uma forma deste tipo.
Definic¸a˜o 5.6 (Discriminante)
Chamamos discriminante de uma forma quadra´tica
f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] ao nu´mero inteiro d = b2 − 4ac .
Teorema 5.7
Seja f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] uma forma quadra´tica com
discriminante d. Se d ̸= 0 e d na˜o for um quadrado perfeito, enta˜o:
a ̸= 0 e c ̸= 0;
(0, 0) e´ a u´nica soluc¸a˜o inteira da equac¸a˜o f (x , y) = 0.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 124 / 136
Formas bina´rias quadra´ticas
Demonstrac¸a˜o.
Se fosse a = 0 ou c = 0, enta˜o d = b2 o que na˜o acontece — assim,
temos a ̸= 0 e c ̸= 0.
Sejam u, v ∈ Z tais que f (u, v) = 0.
Se for v = 0, enta˜o au2 = 0, logo u = 0 (porque a ̸= 0).
Analogamente, u = 0 =⇒ v = 0.
Suponhamos que u ̸= 0 e v ̸= 0. Como
4af (x , y) = (2ax + by)2 − dy2,
obtemos
dv2 = (2au + bv)2.
Como dv2 ̸= 0, o Teorema Fundamental da Aritme´tica implica que d e´ um
quadrado perfeito, o que na˜o acontece. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 125 / 136
Formas bina´rias quadra´ticas
Definic¸a˜o 5.8 (Formas semidefinidas, definidas e indefinidas)
Dizemos que uma forma quadra´tica f (x , y) ∈ Z[x , y ] e´:
semidefinida positiva (resp., negativa) se f (u, v) ≥ 0 (resp.,
f (u, v) ≤ 0) para quaisquer u, v ∈ Z;
definida positiva (resp., negativa) se f (u, v) > 0 (resp.,
f (u, v) < 0);
indefinida em qualquer outro caso.
Exemplo 5.9
f (x , y) = x2 − 2y2 e´ indefinida porque f (1, 0) = 1 e f (0, 1) = −2.
f (x , y) = x2 − 2xy + y2 = (x − y)2 e´ semidefinida positiva, mas na˜o
e´ definida positiva porque f (1, 1) = 0.
f (x , y) = x2 + y2 e´ definida positiva.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 126 / 136Formas bina´rias quadra´ticas
Teorema 5.10
Seja f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] uma forma quadra´tica com
discriminante d.
1 Se d > 0, enta˜o f (x , y) e´ indefinida;
2 Se d = 0, enta˜o f (x , y) e´ semidefinida, mas na˜o e´ definida.
3 Se d < 0, enta˜o a e c teˆm o mesmo sinal e:
1 Se a > 0, enta˜o f (x , y) e´ definida positiva;
2 Se a < 0, enta˜o f (x , y) e´ definida negativa.
Demonstrac¸a˜o.
Suponhamos que d > 0.
Temos
f (1, 0) = a e f (b,−2a) = −ad ;
estes nu´meros teˆm sinais contra´rios, excepto quando a = 0.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 127 / 136
Formas bina´rias quadra´ticas
Analogamente,
f (0, 1) = c e f (−2c , b) = −cd ;
estes nu´meros teˆm sinais contra´rios, excepto quando a = 0.
Quando a = c = 0, temos d = b2 > 0, logo b ̸= 0 e, neste caso,
f (1, 1) = b e f (1,−1) = −b.
Em conclusa˜o, f (x , y) e´ indefinida.
Agora, suponhamos que d = 0 e que a ̸= 0.
Como 4af (x , y) = (2ax + by)2 − dy2, os valores de f (x , y) teˆm todos o
mesmo sinal que a e, portanto, f (x , y) e´ semidefinida.
Ale´m disso,
f (b,−2a) = −ad = 0,
logo f (x , y) na˜o e´ definida (porque a ̸= 0).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 128 / 136
Formas bina´rias quadra´ticas
Se for a = 0, enta˜o d = b2 e, portanto, b = 0. Neste caso,
f (x , y) = cy2
e, portanto, os valores de f (x , y) teˆm todos o mesmo sinal que c , logo
f (x , y) e´ semidefinida. Como f (1, 0) = 0, f (x , y) na˜o e´ definida.
Finalmente, suponhamos que d < 0.
Como 4af (x , y) = (2ax + by)2 − dy2, o Teorema 5.7 implica que
4af (u, v) ≥ 0, ∀ u, v ∈ Z \ {0}.
Assim, f (x , y) e´ positiva.
Como
f (1, 0) = a e f (0, 1) = c ,
conclu´ımos que a e c teˆm o mesmo sinal.
As restantes asserc¸o˜es seguem-se imediatamente. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 129 / 136
Formas bina´rias quadra´ticas
Teorema 5.11
Seja d ∈ Z. Enta˜o, existe pelo menos uma forma quadra´tica
f (x , y) ∈ Z[x , y ] com discriminante d se e so´ se d ≡ 0, 1 (mod 4).
Demonstrac¸a˜o.
=⇒: Se a, b, c ∈ Z forem os coeficientes de f (x , y), temos
d = b2 − 4ac ≡ 0, 1 (mod 4).
⇐=: Se d ≡ 0 (mod 4),
f (x , y) = x2 −
(
d/4
)
y2
tem discriminante d .
Se d ≡ 1 (mod 4),
f (x , y) = x2 + xy −
(
(d−1)/4
)
y2
tem discriminante d . !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 130 / 136
Representac¸a˜o de inteiros por formas quadra´ticas bina´rias
Definic¸a˜o 5.12
Dizemos que n ∈ Z e´ representado por uma forma quadra´tica
f (x , y) ∈ Z[x , y ] se existirem u, v ∈ Z tais que n = f (u, v) — e dizemos
que n = f (u, v) e´ uma representac¸a˜o de n.
Quando isto acontece, dizemos que n = f (u, v) e´ uma representac¸a˜o
pro´pria se mdc(u, v) = 1; no caso contra´rio, dizemos que a
representac¸a˜o e´ impro´pria.
Observac¸a˜o
Se n ∈ Z for representado por uma forma quadra´tica f (x , y) ∈ Z[x , y ],
n = f (u, v) for uma representac¸a˜o de n (de modo que u, v ∈ Z) e
d = mdc(u, v), enta˜o
d2 | n e n/d2 = f
(
u/d, v/d
)
.
Deste modo, as representac¸o˜es de n podem ser determinadas a partir das
representac¸o˜es pro´prias de n/d2 para qualquer d ∈ Z tal que d2 | n.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 132 / 136
Representac¸a˜o de inteiros por formas quadra´ticas bina´rias
Teorema 5.13
Sejam n, d ∈ Z com n ̸= 0. Enta˜o, existe uma forma quadra´tica
f (x , y) ∈ Z[x , y ] com discriminante d que representa n propriamente se e
so´ se a equac¸a˜o x2 ≡ d (mod 4|n|) tem uma soluc¸a˜o.
Demonstrac¸a˜o.
=⇒: Se b ∈ Z for tal que b2 ≡ d (mod 4|n|), enta˜o b2 − d = 4nc para
algum c ∈ Z.
A forma
f (x , y) = nx2 + bxy + cy2 ∈ Z[x , y ]
tem discriminante d e n = f (1, 0) e´ uma representac¸a˜o pro´pria de n.
⇐=: Seja f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] uma forma quadra´tica tal
que n = f (u, v) e´ uma representac¸a˜o pro´pria de n — assim, u, v ∈ Z e
mdc(u, v) = 1.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 133 / 136
Representac¸a˜o de inteiros por formas quadra´ticas bina´rias
Como mdc(u, v) = 1, existem m1,m2 ∈ N tais que
m1m2 = 4|n| e mdc(m1,m2) = mdc(m1, v) = mdc(m2, u) = 1.
Como 4af (x , y) = (2ax + by)2 − dy2, obtemos
4an = (2au + bv)2 − dv2 =⇒ (2au + bv)2 ≡ dv2 (mod m1).
Como mdc(m1, v) = 1, existe v ′ ∈ Z tal que
vv ′ ≡ 1 (mod m1).
Pondo r = (2au + bv)v ′, obtemos
r2 =
[
(2au + bv)v ′
]2
≡ d(vv ′)2 ≡ d (mod m1).
De modo ana´logo, usando 4cf (x , y) = (bx + 2cy)2 − dx2, provamos que
existe s ∈ Z tal que
s2 ≡ d (mod m2).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 134 / 136
Representac¸a˜o de inteiros por formas quadra´ticas bina´rias
Pelo Teorema Chineˆs dos Restos (uma vez que mdc(m1,m2) = 1), o
sistema {
x ≡ r (mod m1)
x ≡ s (mod m2)
tem soluc¸a˜o, isto e´, existe t ∈ Z tal que
t ≡ r (mod m1) e t ≡ s (mod m2).
Daqui, resulta que
t2 ≡ r2 ≡ d (mod m1) e t
2 ≡ s2 ≡ d (mod m2).
Como mdc(m1,m2) = 1, conclu´ımos que
t2 ≡ d (mod m1m2).
O resultado segue-se porque m1m2 = 4|n|. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 135 / 136
Representac¸a˜o de inteiros por formas quadra´ticas bina´rias
Corola´rio 5.14
Sejam d ∈ Z tal que d ≡ 0, 1 (mod 4) e p ∈ P um nu´mero primo ı´mpar.
Enta˜o, existe uma forma quadra´tica f (x , y) ∈ Z[x , y ] com discriminante d
que representa p se e so´ se p | d ou
(
d
p
)
= 1.
Demonstrac¸a˜o.
E´ claro que qualquer representac¸a˜o de p tem de ser pro´pria.
=⇒: Pelo teorema, d tem de ser um quadrado mo´dulo 4p, logo d e´
quadrado mo´dulo p e, portanto,
(
d
p
)
̸= −1.
=⇒: Se
(
d
p
)
̸= −1, enta˜o d e´ quadrado mo´dulo p.
Por definic¸a˜o, d e´ quadrado mo´dulo 4, logo d e´ quadrado mo´dulo 4p (pelo
Teorema Chineˆs dos Restos).
Agora, basta aplicar o teorema anterior. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 136 / 136
Formas bina´rias quadra´ticas
Nesta secc¸a˜o, consideramos formas quadra´ticas bina´rias, isto e´, polino´mios
f (x , y) = ax2 + bxy + cy2
em que a, b, c ∈ Z e procuramos condic¸o˜es para que um nu´mero natural
n ∈ N possa ser representado por uma forma deste tipo.
Definic¸a˜o 6.1 (Discriminante)
Chamamos discriminante de uma forma quadra´tica
f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] ao nu´mero inteiro d = b2 − 4ac .
Teorema 6.2
Seja f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] uma forma quadra´tica com
discriminante d. Se d ̸= 0 e d na˜o for um quadrado perfeito, enta˜o:
a ̸= 0 e c ̸= 0;
(0, 0) e´ a u´nica soluc¸a˜o inteira da equac¸a˜o f (x , y) = 0.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 138 / 194
Formas bina´rias quadra´ticas
Demonstrac¸a˜o.
Se fosse a = 0 ou c = 0, enta˜o d = b2 o que na˜o acontece — assim,
temos a ̸= 0 e c ̸= 0.
Sejam u, v ∈ Z tais que f (u, v) = 0.
Se for v = 0, enta˜o au2 = 0, logo u = 0 (porque a ̸= 0).
Analogamente, u = 0 =⇒ v = 0.
Suponhamos que u ̸= 0 e v ̸= 0. Como
4af (x , y) = (2ax + by)2 − dy2,
obtemos
dv2 = (2au + bv)2.
Como dv2 ̸= 0, o Teorema Fundamental da Aritme´tica implica que d e´ um
quadrado perfeito, o que na˜o acontece. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 139 / 194
Formas bina´rias quadra´ticas
Definic¸a˜o 6.3 (Formas semidefinidas, definidas e indefinidas)
Dizemos que uma forma quadra´tica f (x , y) ∈ Z[x , y ] e´:
semidefinida positiva (resp., negativa) se f (u, v) ≥ 0 (resp.,
f (u, v) ≤ 0) para quaisquer u, v ∈ Z;
definida positiva (resp., negativa) se f (u, v) > 0 (resp.,
f (u, v) < 0);
indefinida em qualquer outro caso.
Exemplo 6.4
f (x , y) = x2 − 2y2 e´ indefinida porque f (1, 0) = 1 e f (0, 1) = −2.
f (x , y) = x2 − 2xy + y2 = (x − y)2 e´ semidefinida positiva, mas na˜o
e´ definida positivaporque f (1, 1) = 0.
f (x , y) = x2 + y2 e´ definida positiva.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 140 / 194
Formas bina´rias quadra´ticas
Teorema 6.5
Seja f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] uma forma quadra´tica com
discriminante d.
1 Se d > 0, enta˜o f (x , y) e´ indefinida;
2 Se d = 0, enta˜o f (x , y) e´ semidefinida, mas na˜o e´ definida.
3 Se d < 0, enta˜o a e c teˆm o mesmo sinal e:
1 Se a > 0, enta˜o f (x , y) e´ definida positiva;
2 Se a < 0, enta˜o f (x , y) e´ definida negativa.
Demonstrac¸a˜o.
Suponhamos que d > 0.
Temos
f (1, 0) = a e f (b,−2a) = −ad ;
estes nu´meros teˆm sinais contra´rios, excepto quando a = 0.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 141 / 194
Formas bina´rias quadra´ticas
Analogamente,
f (0, 1) = c e f (−2c , b) = −cd ;
estes nu´meros teˆm sinais contra´rios, excepto quando a = 0.
Quando a = c = 0, temos d = b2 > 0, logo b ̸= 0 e, neste caso,
f (1, 1) = b e f (1,−1) = −b.
Em conclusa˜o, f (x , y) e´ indefinida.
Agora, suponhamos que d = 0 e que a ̸= 0.
Como 4af (x , y) = (2ax + by)2 − dy2, os valores de f (x , y) teˆm todos o
mesmo sinal que a e, portanto, f (x , y) e´ semidefinida.
Ale´m disso,
f (b,−2a) = −ad = 0,
logo f (x , y) na˜o e´ definida (porque a ̸= 0).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 142 / 194
Formas bina´rias quadra´ticas
Se for a = 0, enta˜o d = b2 e, portanto, b = 0. Neste caso,
f (x , y) = cy2
e, portanto, os valores de f (x , y) teˆm todos o mesmo sinal que c , logo
f (x , y) e´ semidefinida. Como f (1, 0) = 0, f (x , y) na˜o e´ definida.
Finalmente, suponhamos que d < 0.
Como 4af (x , y) = (2ax + by)2 − dy2, o Teorema 6.2 implica que
4af (u, v) ≥ 0, ∀ u, v ∈ Z \ {0}.
Assim, f (x , y) e´ positiva.
Como
f (1, 0) = a e f (0, 1) = c ,
conclu´ımos que a e c teˆm o mesmo sinal.
As restantes asserc¸o˜es seguem-se imediatamente. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 143 / 194
Formas bina´rias quadra´ticas
Teorema 6.6
Seja d ∈ Z. Enta˜o, existe pelo menos uma forma quadra´tica
f (x , y) ∈ Z[x , y ] com discriminante d se e so´ se d ≡ 0, 1 (mod 4).
Demonstrac¸a˜o.
=⇒: Se a, b, c ∈ Z forem os coeficientes de f (x , y), temos
d = b2 − 4ac ≡ 0, 1 (mod 4).
⇐=: Se d ≡ 0 (mod 4),
f (x , y) = x2 −
(
d/4
)
y2
tem discriminante d .
Se d ≡ 1 (mod 4),
f (x , y) = x2 + xy −
(
(d−1)/4
)
y2
tem discriminante d . !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 144 / 194
Representac¸a˜o de inteiros por formas quadra´ticas bina´rias
Definic¸a˜o 6.7
Dizemos que n ∈ Z e´ representado por uma forma quadra´tica
f (x , y) ∈ Z[x , y ] se existirem u, v ∈ Z tais que n = f (u, v) — e dizemos
que n = f (u, v) e´ uma representac¸a˜o de n.
Quando isto acontece, dizemos que n = f (u, v) e´ uma representac¸a˜o
pro´pria se mdc(u, v) = 1; no caso contra´rio, dizemos que a
representac¸a˜o e´ impro´pria.
Observac¸a˜o
Se n ∈ Z for representado por uma forma quadra´tica f (x , y) ∈ Z[x , y ],
n = f (u, v) for uma representac¸a˜o de n (de modo que u, v ∈ Z) e
d = mdc(u, v), enta˜o
d2 | n e n/d2 = f
(
u/d, v/d
)
.
Deste modo, as representac¸o˜es de n podem ser determinadas a partir das
representac¸o˜es pro´prias de n/d2 para qualquer d ∈ Z tal que d2 | n.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 146 / 194
Representac¸a˜o de inteiros por formas quadra´ticas bina´rias
Teorema 6.8
Sejam n, d ∈ Z com n ̸= 0. Enta˜o, existe uma forma quadra´tica
f (x , y) ∈ Z[x , y ] com discriminante d que representa n propriamente se e
so´ se a equac¸a˜o x2 ≡ d (mod 4|n|) tem uma soluc¸a˜o.
Demonstrac¸a˜o.
=⇒: Se b ∈ Z for tal que b2 ≡ d (mod 4|n|), enta˜o b2 − d = 4nc para
algum c ∈ Z.
A forma
f (x , y) = nx2 + bxy + cy2 ∈ Z[x , y ]
tem discriminante d e n = f (1, 0) e´ uma representac¸a˜o pro´pria de n.
⇐=: Seja f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] uma forma quadra´tica tal
que n = f (u, v) e´ uma representac¸a˜o pro´pria de n — assim, u, v ∈ Z e
mdc(u, v) = 1.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 147 / 194
Representac¸a˜o de inteiros por formas quadra´ticas bina´rias
Como mdc(u, v) = 1, existem m1,m2 ∈ N tais que
m1m2 = 4|n| e mdc(m1,m2) = mdc(m1, v) = mdc(m2, u) = 1.
Como 4af (x , y) = (2ax + by)2 − dy2, obtemos
4an = (2au + bv)2 − dv2 =⇒ (2au + bv)2 ≡ dv2 (mod m1).
Como mdc(m1, v) = 1, existe v ′ ∈ Z tal que
vv ′ ≡ 1 (mod m1).
Pondo r = (2au + bv)v ′, obtemos
r2 =
[
(2au + bv)v ′
]2
≡ d(vv ′)2 ≡ d (mod m1).
De modo ana´logo, usando 4cf (x , y) = (bx + 2cy)2 − dx2, provamos que
existe s ∈ Z tal que
s2 ≡ d (mod m2).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 148 / 194
Representac¸a˜o de inteiros por formas quadra´ticas bina´rias
Pelo Teorema Chineˆs dos Restos (uma vez que mdc(m1,m2) = 1), o
sistema {
x ≡ r (mod m1)
x ≡ s (mod m2)
tem soluc¸a˜o, isto e´, existe t ∈ Z tal que
t ≡ r (mod m1) e t ≡ s (mod m2).
Daqui, resulta que
t2 ≡ r2 ≡ d (mod m1) e t
2 ≡ s2 ≡ d (mod m2).
Como mdc(m1,m2) = 1, conclu´ımos que
t2 ≡ d (mod m1m2).
O resultado segue-se porque m1m2 = 4|n|. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 149 / 194
Representac¸a˜o de inteiros por formas quadra´ticas bina´rias
Corola´rio 6.9
Sejam d ∈ Z tal que d ≡ 0, 1 (mod 4) e p ∈ P um nu´mero primo ı´mpar.
Enta˜o, existe uma forma quadra´tica f (x , y) ∈ Z[x , y ] com discriminante d
que representa p se e so´ se p | d ou
(
d
p
)
= 1.
Demonstrac¸a˜o.
E´ claro que qualquer representac¸a˜o de p tem de ser pro´pria.
=⇒: Pelo teorema, d tem de ser um quadrado mo´dulo 4p, logo d e´
quadrado mo´dulo p e, portanto,
(
d
p
)
̸= −1.
=⇒: Se
(
d
p
)
̸= −1, enta˜o d e´ quadrado mo´dulo p.
Por definic¸a˜o, d e´ quadrado mo´dulo 4, logo d e´ quadrado mo´dulo 4p (pelo
Teorema Chineˆs dos Restos).
Agora, basta aplicar o teorema anterior. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 150 / 194
Equivaleˆncia de formas quadra´ticas bina´rias
Definic¸a˜o 6.10 (Grupo modular)
Chamamos grupo modular ao grupo Γ constitu´ıdo por todas as
matrizes de tipo 2× 2 com coeficientes em Z e determinante 1, isto e´,
Γ =
{[
m11 m12
m21 m22
]
: mij ∈ Z, det(M) = 1
}
.
Observac¸a˜o
1 Γ e´ de facto um grupo — exerc´ıcio.
2 Γ na˜o e´ comutativo: por exemplo, para
M =
[
0 1
−1 0
]
e N =
[
1 0
1 1
]
,
temos
MN =
[
1 1
−1 0
]
e NM =
[
0 1
−1 1
]
.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 152 / 194
Equivaleˆncia de formas quadra´ticas bina´rias
Definic¸a˜o 6.11 (Formas quadra´ticas bina´rias equivalentes)
Duas formas quadra´ticas f (x , y), f ′(x , y) ∈ Z[x , y ] dizem-se
equivalentes se exitir uma matriz M = [mij ] ∈ Γ tal que
g(x , y) = f (m11x +m12y ,m21x +m22y).
Nesta situac¸a˜o, escrevemos f ∼ g e dizemos que M leva f para g .
Exemplo 6.12
As formas
f (x , y) = x2 + y2 e g(x , y) = x2 + 2xy + 2y2
sa˜o equivalentes:
g(x , y) = f (x + y , y);
a matriz
[
1 1
0 1
]
∈ Γ leva f para g .
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 153 / 194
Equivaleˆncia de formas quadra´ticas bina´rias
Lema 6.13
∼ e´ uma relac¸a˜o de equivaleˆncia.
Uma forma quadra´tica f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] pode ser
representada matricialmente por uma matriz sime´trica (isto e´, igual a` sua
transposta): de facto, identificando f (x , y) com
[
f (x , y)
]
, temos
f (x , y) =
[
x y
] [ a 1/2b
1/2b c
] [
x
y
]
.
De agora em diante, escreveremos
f (x , y) = XTFX onde F =
[
a 1/2b
1/2b c
]
e X =
[
x
y
]
.
Lema 6.14
Se f (x , y) = XTFX ∈ Z[x , y ] foruma forma quadra´tica, enta˜o o
discriminante de f (x , y) e´ dado por d = −4 det(F ).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 154 / 194
Equivaleˆncia de formas quadra´ticas bina´rias
Lema 6.15
Se f (x , y) = XTFX ∈ Z[x , y ] e g(x , y) = XTGX ∈ Z[x , y ] forem formas
quadra´ticas equivalentes (em que F e G sa˜o matrizes sime´tricas) e M ∈ Γ
for uma matriz que leva f para g, enta˜o G = MTFM; em particular, f e g
teˆm o mesmo discriminante.
Demonstrac¸a˜o.
Pondo M = [mij ], temos
g(x , y) = f (m11x +m12y ,m21x +m22y)
=
[
m11x +m12y m21x +m22y
]
F
[
m11x +m12y
m21x +m22y
]
=
[
x y
] [m11 m21
m12 m22
]
F
[
m11 m12
m21 m22
] [
x
y
]
= XT (MTFM)X
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 155 / 194
Equivaleˆncia de formas quadra´ticas bina´rias
Sendo assim
XTGX = XT (MTFM)X ,
de onde resulta que G = MTFM — basta escolher matrizes X ∈M2×1(Z)
convenientes.
Sejam d e d ′ os discriminantes de f e g , respectivamente. Pelo
Lema 6.14, temos
d ′ = −4 det(MTFM) = −4 det(M)2 det(F ) = −4 det(F ) = d
(uma vez que det(M) = 1). !
Definic¸a˜o 6.16 (Forma quadra´tica bina´ria reduzida)
Seja f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] uma forma quadra´tica cujo
discriminante na˜o e´ um quadrado. Dizemos e´ f reduzida se
−|a| < b ≤ |a| < |c | ou 0 ≤ b ≤ |a| = |c |.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 156 / 194
Formas quadra´ticas bina´rias reduzidas
Definic¸a˜o 7.1 (Forma quadra´tica bina´ria reduzida)
Seja f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] uma forma quadra´tica cujo
discriminante na˜o e´ um quadrado. Dizemos e´ f reduzida se acontecer
uma (e so´ uma) das situac¸o˜es seguintes:
−|a| < b ≤ |a| < |c |;
0 ≤ b ≤ |a| = |c |.
Teorema 7.2
Seja f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] uma forma quadra´tica com
discriminante d e suponhamos que d na˜o e´ um quadrado. Enta˜o, existe
pelo menos uma forma quadra´tica reduzida g(x , y) ∈ Z[x , y ] que e´
equivalente a f .
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 158 / 194
Formas quadra´ticas bina´rias reduzidas
Demonstrac¸a˜o.
Como d na˜o e´ um quadrado, temos a ̸= 0 e c ̸= 0.
Se |c | < |a| ou |a| = |c | e −|a| ≤ b < 0, consideramos
M =
[
0 1
−1 0
]
∈ Γ.
Esta matriz leva f para a forma quadra´tica
g(x , y) = cx2 − bxy + ay2.
Esta forma so´ na˜o e´ reduzida quando |c | < |a| e −b /∈ (− |c |, |c |); se
isto acontecer procedemos como se segue.
Se |a| < |c | e b /∈ (− |a|, |a|), consideramos
M =
[
1 m
0 1
]
∈ Γ
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 159 / 194
Formas quadra´ticas bina´rias reduzidas
onde m ∈ Z e´ o u´nico inteiro tal que −|a| < 2am + b ≤ |a|. Esta
matriz leva f para a forma quadra´tica
g(x , y) = ax2 + (2am + b)xy + (am2 + bm + c)y2.
Esta forma pode na˜o ser reduzida porque pode acontecer
|am2 + bm + c | < |a|; se isto acontecer, usamos o processo acima.
Fica como exerc´ıcio, justificar que uma aplicac¸a˜o sucessiva destas duas
transformac¸o˜es leva f para uma forma quadra´tica reduzida que lhe e´
equivalente. !
Exemplo 7.3
Determinamos uma forma quadra´tica reduzida que e´ equivalente a
f (x , y) = 133x2 + 108xy + 22y2.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 160 / 194
Formas quadra´ticas bina´rias reduzidas
Como 22 < 133, transformamos f na forma
f1(x , y) = f (−y , x) = 133y2 − 108xy + 22x2
= 22x2 − 108xy + 133y2
(uma transformac¸a˜o do 1o tipo).
Temos 22 < 133 mas −108 /∈ (− 22, 22). Escolhendo m = 2 e efectuando
uma transformac¸a˜o do 2o tipo, passamos para a forma
f2(x , y) = f1(x + 2y , y) = 22(x + 2y)
2 − 108(x + 2y)y + 133y2
= 22x2 − 20xy + 5y2.
Esta forma na˜o e´ reduzida porque 5 < 22. Fazendo novamente uma
transformac¸a˜o do 1o tipo, obtemos
f3(x , y) = f2(−y , x) = 5x2 + 20xy + 22y2.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 161 / 194
Formas quadra´ticas bina´rias reduzidas
Finalmente, uma transformac¸a˜o do 2o tipo com m = −2, da´-nos
f4(x , y) = f3(x − 2y , y) = 5x2 + 2y2
e uma transformac¸a˜o do 1o tipo, da´-nos
f5(x , y) = f4(−y , x) = 2x2 + 5y2,
que e´ reduzida e equivalente a f .
Teorema 7.4
Seja f (x , y) = ax2 + bxy + cy2 ∈ Z[x , y ] uma forma quadra´tica reduzida
cujo discriminante d na˜o e´ um quadrado.
1 Se f for indefinida, enta˜o 0 < |a| ≤ √d/2.
2 Se f for definida positiva, enta˜o 0 < a ≤√−d/3.
Em qualquer dos casos, existe um nu´mero finito de formas quadra´ticas
reduzidas com discriminante d.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 162 / 194
Formas quadra´ticas bina´rias reduzidas
Demonstrac¸a˜o.
Se a e c tiverem o mesmo sinal, enta˜o
d = b2 − 4ac = b2 − 4|ac | ≤ a2 − 4a2 < 0.
Deste modo, se d > 0, enta˜o a e c teˆm sinais opostos e
d = b2 − 4ac = b2 + 4|ac | ≥ 4ac ≥ 4a2,
provando (1).
Se d > 0, enta˜o a, c > 0 e
d = b2 − 4ac ≤ a2 − 4a2 = −3a2,
provando (2).
Em qualquer dos casos, a e b so´ podem tomar um nu´mero finito de
valores, enquanto que c e´ univocamente determinado por a e b. !
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 163 / 194
Formas quadra´ticas bina´rias reduzidas
Definic¸a˜o 7.5 (Nu´mero de classe)
Se d ∈ Z na˜o for um quadrado, definimos o nu´mero de classe H(d)
de d como sendo o nu´mero de classes de equivaleˆncia das formas
quadra´ticas bina´rias reduzidas com discriminante d .
Proposic¸a˜o 7.6
Se p ∈ P, p ≥ 3, enta˜o p pode ser escrito na forma p = x2 − 2y2 se e so´
se p ≡ ±1 (mod 8).
Demonstrac¸a˜o.
A forma quadra´tica f (x , y) = x2 − 2y2 tem discriminante d = 8.
Pelo Corola´rio 6.9, se p for representado por f , enta˜o
1 =
(
8
p
)
=
(
2
p
)
= (−1)(p2−1)/8 ⇐⇒ p ≡ ±1 (mod 8).
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 164 / 194
Formas quadra´ticas bina´rias reduzidas
Para a rec´ıproca, se p ≡ ±1 (mod 8), enta˜o ( 8p ) = 1 e, portanto, pelo
Corola´rio 6.9, existe uma forma quadra´tica com discriminante 8 que
representa p; esta forma e´ equivalente a uma forma quadra´tica reduzida
que tambe´m representa p.
Determinemos todas as formas reduzidas
ax2 + bxy + cy2 ∈ Z[x , y ]
que teˆm discriminante 8.
Pelo teorema anterior, tem de ser |a| ≤ √2, logo a = ±1.
Por definic¸a˜o de forma reduzida, vem b = 0 ou b = 1.
Como b e d teˆm a mesma paridade, tem de ser b = 0.
Por conseguinte, existem exactamente duas formas reduzidas com
discriminante 8:
f (x , y) = x2 − 2y2 e − f (x , y) = −x2 + 2y2.
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 165 / 194
Formas quadra´ticas bina´rias reduzidas
Agora, consideremos a matriz
M =
[
1 −2
1 −1
]
∈M2×2(Z).
Como det(M) = −1 + 2 = 1, temos M ∈ Γ.
Ale´m disso,
f (x − 2y , x − y) = (x − 2y)2 − 2(x − y)2 = −x2 + 4y2 = −f (x , y),
logo M leva f para −f e, portanto, f ∼ −f .
Em conclusa˜o, existe apenas uma classe de equivaleˆncia de formas
quadra´ticas reduzidas com discriminante 8 – isto e´, temos H(8) = 1.
Em conclusa˜o, p tem de ser representado por f (x , y) = x2 − 2y2. !
Encontrar inteiros u, v ∈ Z tais que p = u2 − 2v2 e´ outro problema...
C. Andre´ (DM/FCUL) Introduc¸a˜o a` Teoria dos Nu´meros 2013/14 166 / 194
Somas de dois quadrados
O objectivo e´ apresentar um demonstrac¸a˜o alternativa a` do Teorema 3.19
que caracteriza os nu´meros n ∈ N que sa˜o representados pela forma
quadra´tica
f (x , y) = x2 + y2.
Esta forma tem discriminante d = −4, de modo que comec¸amos por listar
todas as formas quadra´ticas reduzidas que teˆm este discriminante.
Consideramos apenas formas definidas positivas: seja
f (x , y) = ax2 + bxy + y2 ∈ Z[x , y ]
uma forma reduzida, definida positiva e com discriminante −4.
Pelo Teorema 6.5, temos a, c > 0.
Pelo Teorema 7.4, tem de ser 0