Álgebra - Amílcar Pacheco

Prévia do material em texto

A´lgebra
Amı´lcar Pacheco
Universidade Federal do Rio de Janeiro (Universidade do Brasil),
Departamento de Matema´tica Pura
E-mail address: amilcar@im.ufrj.br
Suma´rio
Cap´ıtulo 1. Preliminares 1
1.1. Relac¸a˜o de equivaleˆncia 2
1.2. Lema de Zorn e aplicac¸o˜es 3
Parte 1. Nu´meros Inteiros 5
Cap´ıtulo 2. Algoritmos Euclideanos 7
2.1. O algoritmo euclideano para nu´meros inteiros 7
2.2. Ma´ximo divisor comum 8
2.3. Ane´is e ideais 9
Cap´ıtulo 3. Fatorac¸a˜o de inteiros 11
3.1. Existeˆncia 11
3.2. Unicidade 11
3.3. MDC e fatorac¸a˜o 12
3.4. Aplicac¸o˜es 13
3.5. Func¸o˜es aritme´ticas elementares 15
Cap´ıtulo 4. Induc¸a˜o finita 19
4.1. Enunciados 19
4.2. Exemplos da induc¸a˜o na sua primeira forma 19
4.3. Exemplos da induc¸a˜o finita na sua segunda forma 20
Cap´ıtulo 5. Nu´meros primos 23
5.1. Infinidade de primos 23
5.2. Primos em progresso˜es aritme´ticas 24
5.3. Infinidade de compostos por func¸o˜es polinomiais 26
5.4. Nu´meros de Fermat e Mersenne 27
5.5. Contando nu´meros primos 27
5.6. Func¸a˜o zeta 30
Cap´ıtulo 6. Aritme´tica modular 35
6.1. Aritme´tica modular 35
6.2. Crite´rios de divisibilidade 37
6.3. Contando elementos invers´ıveis 38
Cap´ıtulo 7. Sistemas de congrueˆncia 39
7.1. Equac¸o˜es diofantinas 39
7.2. Equac¸o˜es lineares 39
7.3. Sistemas de equac¸o˜es lineares 40
7.4. Teorema Chineˆs dos Restos 41
iii
iv SUMA´RIO
7.5. Aplicac¸a˜o 41
Cap´ıtulo 8. Aplicac¸o˜es da teoria de grupos a` teoria elementar dos nu´meros 43
8.1. Primalidade de nu´meros de Mersenne 43
8.2. Primalidade de nu´meros de Fermat 43
8.3. Nu´meros de Carmichael 44
8.4. Teorema da raiz primitiva 45
Parte 2. Grupos 47
Cap´ıtulo 9. Teoria de Grupos I 49
9.1. Definic¸a˜o e exemplos 49
9.2. Subgrupos 52
9.3. Classes Laterais e Teorema de Lagrange 54
9.4. Ordem de elemento e expoente de grupo abeliano 55
Cap´ıtulo 10. Teoria de grupos II 59
10.1. Subgrupos normais e grupos quocientes 59
10.2. Homomorfismo de grupos 61
10.3. Produtos de grupos 64
10.4. Grupos metac´ıclicos 68
10.5. Classificac¸a˜o de grupos de ordem ≤ 11 70
Cap´ıtulo 11. Teoremas de Sylow 73
11.1. Represesentac¸o˜es de grupos 73
11.2. Os teoremas de Sylow 75
11.3. Exemplos 77
Cap´ıtulo 12. Grupos solu´veis 79
12.1. Teorema de Jordan-Ho¨lder 79
12.2. Grupos solu´veis 81
Cap´ıtulo 13. Grupos abelianos finitamente gerados 85
13.1. Mo´dulos sobre ane´is 85
13.2. Diagonalizac¸a˜o de matrizes 86
13.3. Geradores e relac¸o˜es para mo´dulos 87
13.4. O teorema de estrutura 89
Parte 3. Ane´is 91
Cap´ıtulo 14. Ane´is de polinoˆmios 93
14.1. Algoritmo da divisa˜o 93
14.2. Ma´ximo divisor comum de polinoˆmios 95
14.3. Fatorac¸a˜o u´nica de polinoˆmios 97
Cap´ıtulo 15. Ane´is e domı´nios 101
15.1. Domı´nios euclideanos 101
15.2. Domı´nios fatoriais 106
15.3. Fatores mu´ltiplos e resultante 108
15.4. Ane´is quocientes e teorema chineˆs dos restos 110
15.5. Aplicac¸o˜es 115
SUMA´RIO v
Parte 4. Corpos 117
Cap´ıtulo 16. Extenso˜es finitas 119
Cap´ıtulo 17. Extenso˜es alge´bricas 123
17.1. Elementos alge´bricos e transcendentes 123
17.2. Extenso˜es alge´bricas 124
17.3. Adjunc¸a˜o de ra´ızes 126
17.4. Fechos alge´bricos 127
Cap´ıtulo 18. Extenso˜es separa´veis 133
18.1. Corpos Finitos 137
Cap´ıtulo 19. Extenso˜es puramente insepara´veis 139
Cap´ıtulo 20. Corpos de decomposic¸a˜o e extenso˜es normais 143
20.1. Exemplos 146
Cap´ıtulo 21. Teoria de Galois 149
21.1. Correspondeˆncia de Galois 149
21.2. Extenso˜es e subgrupos normais 152
21.3. Coeficientes e ra´ızes 153
Cap´ıtulo 22. Extenso˜es ciclotoˆmicas 155
Cap´ıtulo 23. Extenso˜es c´ıclicas 159
Cap´ıtulo 24. Solubilidade por radicais 165
Parte 5. To´picos adicionais 169
Cap´ıtulo 25. O problema inverso de Galois 171
25.1. Grupo Sn 171
25.2. Grupo An 175
25.3. Me´todo geral 175
Cap´ıtulo 26. Teoria de Galois infinita 177
26.1. Limite inverso 177
26.2. Completamento de um grupo 178
26.3. Teoria de Galois infinita 179
Cap´ıtulo 27. Teoria de transcendeˆncia 181
27.1. Bases de trasncendeˆncia 181
27.2. Transcendeˆncia de e 181
27.3. Transcendeˆncia de pi 181
27.4. Elementos de teoria de transcenceˆncia 181
Bibliografia - Livros 183
Bibliografia - Artigos 185
I´ndice Remissivo 187
CAP´ıTULO 1
Preliminares
Ao longo deste livro dentoraremos por N o conjunto dos nu´meros naturais, Z o
conjunto dos nu´meros inteiros, Q o conjunto dos nu´meros racionais, R o conjunto
dos nu´meros reais e C o conjunto dos nu´meros complexos. Para todo x ∈ C
denotamos por |x| seu valor absoluto usual, i.e., se x = a + bi com a, b ∈ R,
enta˜o |x| := √a2 + b2. Para todo x ∈ R denotamos seu valor absoluto usual por
|x| := x, se x ≥ 0, e |x| := −x, se x < 0.
Sejam S e T conjuntos. Uma func¸a˜o f : S → T e´ dita injetiva toda vez que
x 6= y implicar f(x) 6= f(y). Isto tambe´m equivale a dizer que se f(x) = f(y),
enta˜o x = y. A func¸a˜o f e´ dita sobrejetiva, se f(S) = T .
Lema 1.1. Sejam S′ e R conjuntos. Enta˜o existe um conjunto S′1 e bijec¸a˜o
ϕ0 : S′ → S′1 tal que S′1 ∩R = ∅.
Axioma 1.2 (axioma da boa ordenac¸a˜o). Todo subconjunto na˜o vazio de N
possui um menor elemento.
Seja n ≥ 1 inteiro. Sejam x, y varia´veis. Considere o produto nota´vel
xn − yn = (x− y)(xn−1 + xn−2y + . . .+ xyn−2 + yn−1.
Podemos obter dele a soma de n termos de uma progressa˜o geome´trica de raza˜o q.
Digamos que os termos sejam a, aq, · · · , aqn−1 . Assim,
a+ aq + . . .+ aqn−1 = a
qn − 1
q − 1 .
Basta na fo´rmula anterior tomar x = q e y = 1.
Para inteiros 1 ≤ m ≤ n definimos o nu´mero binomial(
n
m
)
:=
n!
m!(n−m)! ,
onde n! := n(n− 1) . . . 1.
Lembre-se [Sp, p. 632] das seguintes expanso˜es em se´ries
1
1− x = 1 + x
2 + x3 + . . .+ xn + . . . ;
log(1− x) = x+ x
2
2!
+
x3
3!
+ . . .+
xn
n!
+ . . . .
Dado um nu´mero real x denotamos por dxe a parte inteira de x, ou seja, o
maior nu´mero inteiro menor ou igual a x.
Para todo inteiro n ≥ 1 e nu´mero primo p, a ordem p-a´dica ordp(n) de n e´
definida por pordp(n) e´ a poteˆncia exata de p que divide n.
1
2 1. PRELIMINARES
1.1. Relac¸a˜o de equivaleˆncia
Seja X um conjunto. Uma relac¸a˜o bina´ria R e´ um subconjunto de X × X.
Dado um par (a, b) ∈ R dizemos que a e´ relacionado a b e denotamos por aRb. Por
exemplo, podemos tomar como X o conjunto de retas do plano e como R a relac¸a˜o
de ortogonalidade.
Uma relac¸a˜o de equivaleˆncia em um conjunto X e´ uma relac¸a˜o bina´ria ∼ satis-
fazendo a`s seguintes condic¸o˜es:
(1) x ∼ x (reflexividade).
(2) Se x ∼ y, enta˜o y ∼ x (simetria).
(3) Se x ∼ y e y ∼ z, enta˜o x ∼ z (transitividade).
Exemplo 1.3. Seja X = Z e ∼ a relac¸a˜o ≡ (mod n) definida por: dados
a, b ∈ Z, a ≡ b (mod n) se e somente se n | (a − b), i.e., existe k ∈ Z tal que
a− b = kn. Isto define uma relac¸a˜o de equivaleˆncia. De fato,
(1) a− a = 0 = 0.n.
(2) Se a ≡ b (mod n), enta˜o existe k ∈ Z tal que a−b = kn, logo b−a = (−k)n
e b ≡ a (mod n).
(3) Se a ≡ b (mod n) e b ≡ c (mod n), enta˜o existem k, l ∈ Z tais que a−b =
kn e b− c = ln. Somando estas duas igualdades obtemos a− c = (k+ l)n,
logo a ≡ c (mod n).
Exemplo 1.4. Seja X = Z × Z − {0}. Definimos dois pares (a, b), (c, d) ∈ X
como equivalentes, denotando (a, b) ∼ (c, d) se e somente se ad = bc. Isto define
uma relac¸a˜o de equivaleˆncia. De fato,
(1) ab = ba, logo (a, b) ∼ (a, b).
(2) Suponha que (a, b) ∼ (c, d), i.e., ad = bc. Logo cb = da, i.e., (c, d) ∼ (a, b).
(3) Suponha que (a, b) ∼ (c, d) e (c, d) ∼ (e, f), i.e., ad = bc e cf = de. Logo
af = bcd f =
bcf
d =
bde
d = be, i.e., (a, b) ∼ (e, f).
Seja X um conjunto e ∼ uma relac¸a˜o de equivaleˆncia em X. Definimos a classe
[a] de um elemento a ∈ X por [a] = {b ∈ X | b ∼ a}. Note que [a] e´ um conjunto.
Lema 1.5. Seja X um conjunto e ∼ uma relac¸a˜o de equivaleˆncia em X. Dados
a, b ∈ X, temos que a ∼ b se e somentese [a] = [b].
Demonstrac¸a˜o. Suponha que [a] = [b]. Observe que a ∈ [a], pois a ∼ a.
Logo a ∈ [b], i.e., b ∼ a, portanto a ∼ b.
Reciprocamente, suponha a ∼ b e c ∈ [a], i.e., c ∼ a. Por transitividade, c ∼ b,
i.e., c ∈ [b]. Suponha d ∈ [b], i.e., d ∼ b. Por simetria, b ∼ a, por transitividade,
d ∼ a, i.e., d ∈ [a]. �
Corola´rio 1.6. Seja X um conjunto e ∼ um relac¸a˜o de equivaleˆncia em X.
Enta˜o a � b se e somente se [a] ∩ [b] = ∅.
Demonstrac¸a˜o. Note que se a ∼ b, enta˜o [a] ∩ [b] = [a] = [b] 6= ∅. Por outro
lado, se existisse c ∈ [a] ∩ [b], enta˜o c ∼ a e c ∼ b. Por simetria, a ∼ c e por
transitividade a ∼ b, o que e´ uma contradic¸a˜o. �
Corola´rio 1.7. Seja X um conjunto e e ∼ um relac¸a˜o de equivaleˆncia em X.
Enta˜o X =
·⋃
a[a], onde
·⋃
a[a] denota a unia˜o disjunta das classes de equivaleˆncia
em X.
1.2. LEMA DE ZORN E APLICAC¸O˜ES 3
Demonstrac¸a˜o. Observe que o lado direito esta´ claramente contido no lado
esquerdo. Reciprocamente, pelo corola´rio anterior dado x ∈ X existe uma u´nica
classe de equivaleˆncia [a] tal que x ∈ [a]. �
Seja X um conjunto e e ∼ um relac¸a˜o de equivaleˆncia em X. Definimos X :=
X/ ∼:= {[a] | a ∈ X} como o conjunto das classes de equivaleˆncia de ∼ em X. No
caso particular em que X = Z e ∼ e´ ≡ (mod n), denotamos a classe [a] de a ∈ Z
por a. Neste caso, X e´ denotado por Z/nZ.
1.2. Lema de Zorn e aplicac¸o˜es
Definic¸a˜o 1.8. Um conjunto M e´ dito parcialmente ordenado, se existe uma
relac¸a˜o ≤ em M satisfazendo a`s seguintes condic¸o˜es
(1) (reflexividade) a ≤ a, para todo a ∈M.
(2) (Transitividade) Dados a, b, c ∈M, se a ≤ b e b ≤ c, enta˜o a ≤ c.
(3) (Anti-simetria) Dados a, b ∈M, se a ≤ b e b ≤ a, enta˜o a = b.
Esta ordem sera´ dita total, se para quaisquer a, b ∈M temos a ≤ b ou b ≤ a. Neste
caso dizemos que M e´ um conjunto totalmente ordenado.
Definic¸a˜o 1.9. Seja M um conjunto parcialmente ordenado. Um elemento
m ∈ M e´ dito um elemento maximal de M, se dado a ∈ M tal que a ≤ m, enta˜o
a = m. Um elemento c ∈ M e´ dito um limite superior para M, se para todo
a ∈M temos a ≤ c. O conjuntoM e´ dito indutivo, se todo subconjunto totalmente
ordenado L ⊂M possui limite superior. Neste caso, M 6= ∅.
Lema 1.10 (lema de Zorn). (ver [vWa, §69]) Todo conjunto parcialmente or-
denado indutivo possui elemento ma´ximo.
Lema 1.11 (lema de Krull). Seja R um anel comutativo com unidade. Todo
ideal na˜o nulo a de R esta´ contido em algum ideal maximal m de R.
Demonstrac¸a˜o. Considere o conjunto N de todos os ideais b ( R contendo
a. E´ imediato que este conjunto e´ parcialmente ordenado com respeito a` relac¸a˜o de
inclusa˜o de conjuntos. Seja L ⊂ N um subconjunto totalmente ordenado e
C :=
⋃
b∈L
b.
Segue de um exerc´ıcio do cap´ıulo de domı´nios euclideanos que C e´ um ideal de R.
Ale´m disto, este ideal e´ pro´prio, do contra´rio, existiria b ∈ L tal que 1 ∈ b, o que
contradiria b ( R. Por construc¸a˜o, o ideal C e´ um limite superior para L. Em
particular, pelo lema de Zorn, existe m elemento ma´ximo de N. Novamente por
construac¸a˜o m e´ maximal e conte´m a. �
Parte 1
Nu´meros Inteiros
CAP´ıTULO 2
Algoritmos Euclideanos
O objetivo deste cap´ıtulo e´ descrever o algoritmo euclideano que permite di-
vidir um nu´mero inteiro por outro, definir a noc¸a˜o de ma´ximo divisor comum de
nu´meros inteiros e provar o algoritmo euclideano estendido que da´ uma relac¸a˜o de
dependeˆncia linear entre o ma´ximo divisor comum e os nu´meros inteiros atrave´s da
noc¸a˜o de ideais.
2.1. O algoritmo euclideano para nu´meros inteiros
Definic¸a˜o 2.1. Sejam a, b ∈ Z. Dizemos que a divide b ou que b e´ divis´ıvel
por a e denotamos a | b se existe c ∈ Z tal que ac = b.
Proposic¸a˜o 2.2. A divisibilidade satisfaz as seguintes propriedades:
(1) (Cancelamento). Se c 6= 0 e ac | bc, enta˜o a | b.
(2) (Transitividade). Se a | b e b | c, enta˜o a | c.
Demonstrac¸a˜o. (1) Existe α ∈ Z tal que αac = bc, i.e., c(b− αa) = 0. Mas
o produto de dois inteiros e´ igual a zero implica em que um dos inteiros e´ nulo.
Observe que c 6= 0, assim b = ac, i.e., a | b.
(2) Existem α, β ∈ Z tais que b = αa e c = βb, substituindo a primeira
igualdade na segunda, obtemos c = βαa, i.e., a | c. �
Teorema 2.3 (algoritmo de Euclides). Sejam a, b ∈ Z com b 6= 0. Enta˜o
existem q, r ∈ Z tais que
a = bq + r, onde 0 ≤ |r| < |b|.
Se a, b ≥ 0, enta˜o q e r sa˜o unicamente determinados por a e b.
Demonstrac¸a˜o. Suponha inicialmente que a, b ≥ 0. Se a < b tome q = 0 e
r = a. Suponha que a ≥ b. Considere o conjunto S := {k ≥ 1 inteiro | kb > a}. Este
conjunto e´ um subconjunto na˜o vazio de N. Assim, pelo axioma da boa ordenac¸a˜o
(axioma 1.2) existe q + 1 ∈ S tal que q + 1 ≤ x para todo x ∈ S. Logo q /∈ S, i.e.,
a ≥ bq. Seja r := a− bq, portanto 0 ≤ r < (q + 1)b− b = b.
• Se a < 0 e b > 0, divida a′ := −a por b com quociente q′ e resto r′ e tome
q := −q′ e r := −r′.
• Se a < 0 e b < 0, divida a′ := −a por b′ := −b com quociente q′ e resto r′
e tome q := q′ e r := −r′.
• Se a > 0 e b < 0, divida a por b′ := −b com quociente q′ e resto r′ e tome
q := −q e r := r′.
Para provar a unicidade suponha que
a = bq1 + r1 = bq2 + r2, onde 0 ≤ r1, r2 < b.
7
8 2. ALGORITMOS EUCLIDEANOS
Basta provar que r1 = r2, pois neste caso bq1 = bq2 e como b 6= 0, pela propriedade
do cancelamento, q1 = q2. Suponha r1 < r2. Neste caso,
r2 − r1 = b(q1 − q2) ≥ b, mas r2 − r1 ≤ r2 < b.
Similarmente, na˜o podemos ter r1 > r2. �
2.2. Ma´ximo divisor comum
Definic¸a˜o 2.4. Sejam a, b ∈ Z. Dizemos que d ∈ Z e´ um ma´ximo divisor
comum de a e b, denotado por mdc(a, b) se
(1) d | a e d | b; (por isto d e´ dito um divisor comum de a e b.)
(2) Para todo d′ ∈ Z tal que d′ | a e d′ | b, d′ | d.
Observac¸a˜o 2.5. • A noc¸a˜o de mdc esta´ bem definida a menos de
sinal. De fato se e for um outro mdc de a e b, enta˜o por (2) e | d e d | e,
ou seja existem α, β ∈ Z tais que d = αe = αβd, portanto αβ = 1, i.e.,
α ∈ {±1}. Assim quando dizemos o mdc de a e b referimo-nos a` escolha
de d positiva.
• mdc(a, b) = mdc(−a,−b) (exerc´ıcio).
• Se b | a, enta˜o mdc(a, b) = b (idem).
• Denote por Da,b o conjunto dos divisores comuns positivos de a e b. Note
que para qualquer x ∈ Da,b temos que x ≤ min{a, b}. Assim, este con-
junto e´ finito. Fica novamente como exerc´ıcio verificar que mdc(a, b) e´
justamente o elemento ma´ximo de Da,b.
Lema 2.6. Sejam a, b ≥ 1 inteiros e a = bq + r onde 0 ≤ r < b a divisa˜o de a
por b. Enta˜o mdc(a, b) = mdc(b, r).
Demonstrac¸a˜o. Basta mostrar que os conjuntos Da,b e Db,r sa˜o coincidem.
De fato, neste caso seus elementos ma´ximos sa˜o iguais, o que prova o lema. Seja
e ∈ Da,b, digamos a = eα e b = eβ para α, β ∈ Z. Logo r = a − bq = e(α − βq),
i.e., e | r, i.e., e ∈ Db,r, i.e., Da,b ⊂ Db,r. Seja f ∈ Db,r, digamos b = fβ′ e r = fγ
para β′, γ ∈ Z. Enta˜o a = bq + r = f(β′q + γ), i.e., f | a, i.e., f ∈ Da,b, i.e.,
Db,r ⊂ Da,b. �
Teorema 2.7. Sejam a, b ≥ 1 inteiros. Consideremos a sequ¨eˆncia de diviso˜es
sucessivas:
(2.1)
a = bq1 + r1, 0 < r1 < b
b = r1q2 + r2, 0 < r2 < r1
...
...
rn−2 = rn−1qn + rn, 0 < rn < rn−1
rn−1 = rnqn+1,
onde rn e´ o u´ltimo resto na˜o nulo na sequ¨eˆncia de diviso˜es. Enta˜o mdc(a, b) = rn.
Demonstrac¸a˜o. Notemos inicialmente que em (2.1) ter´ıamos que ter um
primeiro resto nulo, rn+1, pois
b > r1 > r2 > · · · ≥ 1
e na˜o existe uma sequ¨eˆncia estritamente descendente infinita de nu´meros inteiros
positivos.
2.3. ANE´IS E IDEAIS 9
Pelo lema anterior aplicado a cada linha de (2.1) obtemos
mdc(a, b) = mdc(b, r1) = · · · = mdc(rn−1, rn).
Mas rn | rn−1, logo rn = mdc(rn, rn−1). A fortiori, rn = mdc(a, b). �
Teorema 2.8 (algoritmo euclideano estendido). Sejam a, b ≥ 1 inteiros e d =
mdc(a, b). Existem s, t ∈ Z tais que d = sa+ tb.
Demonstrac¸a˜o. Comec¸amos com a penu´ltima linha de (2.1),
rn = rn−2 + (−qn)rn−1,
tome A1 := −rn−1e B1 := 1. Da linha seguinte temos
rn−1 = rn−3 + (−qn−1)rn−2,
assim
rn = B1rn−2 +A1rn−1 = B1rn−2 +A1(rn−3 + (−qn−1)rn−2).
Tome A2 := B1 −A1qn−1 e B2 := A1. A linha seguinte nos da´
rn−2 = rn−4 + (−qn−2)rn−3.
Substituindo na fo´rmula anterior,
rn = B2rn−3 +A2rn−2 = B2rn−3 +A2(rn−4 + (−qn−2)rn−3)
Tome A3 := B2 −A2qn−2 e B3 := A2. Repetindo o mesmo argumento obtemos
rn = Bn−2r1 +An−2r2.
Mas r2 = b+ (−q2)r1, donde
rn = Bn−2r1 +An−2(b+ (−q2)r1),
tome An−1 := Bn−2 −An−2q2 e Bn−1 := An−2. Finalmente a primeira divisa˜o nos
da´, r1 = a+ (−q1)b e sustituindo na fo´rmula anterior obtemos
rn = Bn−1b+An−1(a+ (−q1)b).
Basta tomar s := An−1 e t := Bn−1 −An−1q1. �
2.3. Ane´is e ideais
Nesta sec¸a˜o daremos uma outra demonstrac¸a˜o (conceitual) do algoritmo eu-
clideano estendido. Para isto precisamos da noc¸a˜o de ideais no conjunto Z dos
nu´meros inteiros.
O conjunto Z dos nu´meros inteiros possui duas func¸o˜es. A soma + : Z×Z→ Z
de nu´meros inteiros (a, b) 7→ a + b que associa ao par (a, b) sua soma a + b. E o
produto de inteiros · : Z × Z → Z dada por (a, b) 7→ ab que associa ao par (a, b) o
seu produto ab. Dados inteiros a, b, c as seguintes propriedades sa˜o satisfeitas:
(1) (Associatividade da soma) a+ (b+ c) = (a+ b) + c.
(2) (Comutatividade da soma) a+ b = b+ a.
(3) (Elemento neutro da soma) a+ 0 = 0.
(4) (Inverso da soma) Dado a ∈ Z existe b ∈ Z tal que a+ b = 0 e denotamos
b = −a.
(5) (Associatividade do produto) a(bc) = (ab)c.
(6) (Comutatividade do produto) ab = ba.
(7) (Elemento neutro do produto) 1a = a.
10 2. ALGORITMOS EUCLIDEANOS
(8) (Distributividade do produto em relac¸a˜o a` soma) a(b+ c) = ab+ ac. Por
satisfazer estas propriedades Z e´ dito um anel comutativo com unidade.
Ale´m disto a seguinte propriedade e´ satisfeita:
(9) (Cancelamento) Se ab = 0, enta˜o a = 0 ou b = 0. Por satisfazer esta
propriedade Z e´ dito um domı´nio de integridade.
Observac¸a˜o 2.9. Poder´ıamos perguntar sobre a existeˆncia do inverso em Z
com relac¸a˜o ao produto. Ou seja, suponhamos que a, b ∈ Z sa˜o tais que ab =
1. Suponha a ≥ 1. Neste caso b = 1a ∈ Z tambe´m e´ um inteiro positivo, mas
a u´nica possibilidade destra frac¸a˜o ser um nu´mero inteiro e´ a = 1 e neste caso
necessariamente b = 1. Se a < 0, seja a′ = −a e b′ = −b, logo ab = a′b′ = 1 e pelo
caso anterior a′ = 1 e b′ = 1, i.e., a = b = −1. Assim os u´nicos nu´meros inteiros
que admitem inverso sa˜o ±1.
Definic¸a˜o 2.10. Um subconjunto I ⊂ Z de Z e´ dito um ideal de Z, se as
seguintes condic¸o˜es sa˜o satisfeitas:
(1) 0 ∈ I.
(2) (I e´ fechado com relac¸a˜o a` soma) Dados a, b ∈ I, a+ b ∈ I.
(3) (I e´ esta´vel com relac¸a˜o a` multiplicac¸a˜o de elementos de Z) Dado a ∈ I e
r ∈ Z, enta˜o ra ∈ I.
Fica como exerc´ıcio mostrar que os seguintes conjuntos sa˜o ideais de Z :
• I := 2Z = {2k | k ∈ Z} (o conjunto dos nu´meros pares).
• Seja n ≥ 1 inteiro e I := nZ = {nk | k ∈ Z} o conjunto dos mu´ltiplos de
n.
• Sejam n1, · · · , nk ≥ 1 inteiros. Seja I := n1Z+ . . .+ nkZ = {n1a1 + . . .+
nkak | a1, · · · , ak ∈ Z} o conjunto dos nu´meros que sa˜o somas de mu´ltiplos
de n1 com mu´ltiplos de n2, etc., com mu´ltiplos de nk.
Proposic¸a˜o 2.11. Todo ideal I 6= (0) de Z e´ da forma dZ para algum d ≥ 1.
Por isto dizemos que I e´ um ideal principal e que Z e´ um domı´nio principal.
Demonstrac¸a˜o. Observemos que I ∩ N 6= ∅. Dado a ∈ I, se a ≥ 1 nada ha´
a fazer. Sena˜o, ou seja, dado a < 0 em I, enta˜o −a = (−1)a ∈ I pela propriedade
(3) de ideais, mas −a ≥ 1. Pelo axioma da boa ordenac¸a˜o existe d ∈ I ∩ N tal que
d ≤ k para todo k ∈ I ∩ N. Afirmamos que I = dZ.
De um lado, como d ∈ I, pela propriedade (3) de ideais, para todo k ∈ Z,
dk ∈ I, i.e., dZ ⊂ I. De outro lado, dado a ∈ I, digamos a ≥ 1, pelo algoritmo
euclideano, existem q, r ∈ Z tais que a = qn + r, onde 0 ≤ r < n. Se r > 0, enta˜o
r = a + (−q)n ∈ I, pois a, (−q)n ∈ I, mas isto contradiz o fato de d ser o menor
inteiro positivo em I. Assim, r = 0 e n | a, portanto a ∈ nZ. Se a < 0, a mesma
prova mostra que se a′ = −a, d | a′, logo d | a, e assim I ⊂ nZ. �
CAP´ıTULO 3
Fatorac¸a˜o de inteiros
Neste cap´ıtulo mostramos que todo nu´mero inteiro fatora-se de forma u´nica
como produto de nu´meros primos
3.1. Existeˆncia
Definic¸a˜o 3.1. Seja p ≥ 2 inteiro. Dizemos que p e´ um nu´mero primo, se
para todo inteiro b ≥ 1 tal que b | p, enta˜o b = 1 ou b = p, i.e., os u´nicos divisores
positivos de p sa˜o 1 e p. Os nu´meros inteiros que na˜o primos sa˜o chamados de
nu´meros compostos, i.e., n ≥ 1 e´ composto se e somente se existem 1 < a, b < n
tais que n = ab.
Teorema 3.2 (teorema fundamental da aritme´tica - primeira versa˜o). Seja
n ≥ 1 inteiro, existem p1, · · · , pk nu´meros primos (na˜o necessariamente distintos)
tais que
n = p1 · · · pk.
Demonstrac¸a˜o. Se n e´ primo nada ha´ a fazer. Suponhamos que n seja com-
posto. Todo divisor d de n satisfaz d ≤ n, assim o conjunto dos divisores positivos
de n e´ finito. Seja p1 o menor divisor positivo de n. Afirmamos que p1 e´ primo.
Se p1 na˜o fosse primo, ter´ıamos que existem 1 < a, b < p1 tais que p1 = ab, em
particular a | n, mas isto contradiz a minimalidade de p1.
Seja n1 := np1 < n. Se n1 e´ igual a 1 ou primo, enta˜o n = n1p1 ja´ e´ a fatorac¸a˜o
procurada. Sena˜o, com o mesmo argumento anterior, o menor divisor positivo p2
de n1 e´ primo. Seja n2 := n1p2 =
n
p1p2
< n1. Se n2 e´ igual a 1 ou primo, enta˜o
n = n2p2p1 e´ a fatorac¸a˜o procurada. Sena˜o prosseguimos. Note que temos uma
sequ¨eˆncia estritamente decrescente n > n1 > n2 > · · · de inteiros positivos, assim
existe k ≥ 1 tal que nk = 1, i.e., n = p1 · · · pk. �
3.2. Unicidade
Lema 3.3. Seja p ≥ 2 um nu´mero primo e a, b ∈ Z \ {0}. Se p | ab, enta˜o p | a
ou p | b.
Demonstrac¸a˜o. Note que dado um nu´mero primo p, enta˜o mdc(a, p) = 1
equivale a p - a, pois os u´nicos divisores positivos de p sa˜o 1 e p. Suponha que
p - a, i.e., pelo algoritmo euclideano estendido, existem s, t ∈ Z tais que 1 = sa+ tp.
Multiplicando ambos os lados por b obtemos b = sab + tpb. Mas ab = αp, pois
p | ab, para algum α ∈ Z. Logo b = p(sα+ tb), i.e., p | b. �
Observac¸a˜o 3.4. O lema anterior pode ser estendido imediatamente para um
produto qualquer de inteiros, i.e., se p | a1 · · · an, enta˜o existe 1 ≤ i ≤ n tal que
p | ai.
11
12 3. FATORAC¸A˜O DE INTEIROS
Teorema 3.5 (teorema fundamental da aritme´tica - segunda versa˜o). Seja
n ≥ 1 inteiro, enta˜o existem u´nicos nu´meros primos
p1 < · · · < pr e inteiros e1, · · · , er ≥ 1
tais que
n = pe11 · · · perr .
Demonstrac¸a˜o. Ja´ provamos anteriormente a existeˆncia da fatorac¸a˜o, agru-
pando os primos e colocando-os em ordem temos a expressa˜o acima. Suponha que
existam outros primos
q1 < · · · < qs e inteiros f1, · · · , fs ≥ 1
tais que
n = pe11 · · · perr = qf11 · · · qfss .
Pela observac¸a˜o anterior temos que existe algum 1 ≤ j ≤ s tal que p1 | qj . Mas
ambos sa˜o primos, logo p1 = qj . O mesmo argumento acima mostra que existe
1 ≤ i ≤ r tal que q1 = pi. Afirmamos que j = 1. Caso contra´rio, ou seja j > 1,
q1 = pi ≥ p1 = qj , o que contradiz a ordenac¸a˜o dos nu´meros primos q’s. Logo
j = 1. Afirmamos tambe´m que e1 = f1. Suponha, por exemplo, que e1 > f1. Neste
caso, cancelando pf11 dos dois lados da equac¸a˜o acima obtemos
pe1−f11 p
e2
2 · · · perr = qf22 · · · qfss .
Repetindo a argumentac¸a˜o anterior obtemos que q2 = pi para algum 1 < i ≤ r.
Mas dessa forma, o fator primo p1 do lado esquerdo na˜o cancelara´ com nenhum
fator primo do lado direito. Portanto, e1 = f1.
Isto nos fornece a igualdade
pe22 · · · perr = qf22 · · · qfss .
Pelo mesmo argumento anterior, p2 = q2 e e2 = f2. Assim sucessivamente con-
cluimos que o nu´mero de fatores primos em ambos os lados e´ igual, i.e., r = s e
para cada 1 ≤ i ≤ r, pi = qi e ei = fi. �
3.3. MDC e fatorac¸a˜o
Proposic¸a˜o 3.6. Sejam a, b ≥ 1 inteiros,
a = pe11 · · · pekke b = pf11 · · · pfkk
suas fatorac¸o˜es, com ei, fi ≥ 0 para 0 ≤ i ≤ k. Seja gi = min{ei, fi} e
d = pg11 · · · pgkk .
Enta˜o d = mdc(a, b).
Demonstrac¸a˜o. Notemos que d e´ um divisor comum de a e b, pois
a = dpe1−g11 · · · pek−gkk e b = dpf1−g11 · · · pfk−gkk ,
uma vez que para cada i, fi − gi, ei − gi ≥ 0. Seja d′ ≥ 1 um divisor comum de a e
b, i.e.,
d = ph11 · · · phkk
para 0 ≤ hi ≤ ei, fi. Em particular, hi ≤ gi. Assim,
d = d′pg1−h11 · · · pgk−hkk .
�
3.4. APLICAC¸O˜ES 13
3.4. Aplicac¸o˜es
Proposic¸a˜o 3.7. Seja p ≥ 2 um nu´mero primo. Enta˜o √p /∈ Q.
Demonstrac¸a˜o. Seja x ∈ Q \ {0}. Enta˜o x = ab com a, b ∈ Z \ {0}. Note
que a = da′ e b = db′, onde d = mdc(a, b) e que mdc(a′, b′) = 1. Simplificando d
obtemos que x = a
′
b′ . Assim, dividindo pelo mdc, suporemos sempre que dado um
nu´mero x ∈ Q \ {0}, x e´ da forma ab com mdc(a, b) = 1.
Suponha que
√
p ∈ Q, i.e., existem a, b ∈ Z tais que √p = ab e mdc(a, b) = 1.
Logo a2 = pb2 e p | a2. Pelo lema 3.3 concluimos que p | a, digamos a = pα, para
algum α ∈ Z. Substituindo na igualdade anterior concluimos que p2α2 = pb2, i.e.,
pα2 = b2. Mas isto implica em p | b2. Novamente, pelo lema 3.3, obtemos que p | b,
mas isto e´ imposs´ıvel pois mdc(a, b) = 1. �
Definic¸a˜o 3.8. Seja n ≥ 1 inteiro. Dizemos que n e´ livre de quadrados se sua
fatorac¸a˜o e´ da forma
n = p1 · · · pk.
Lema 3.9. Seja n ≥ 1 inteiro, enta˜o existem Q, a ≥ 1 inteiros tais que n = a2Q,
onde Q e´ livre de quadrados.
Demonstrac¸a˜o. Fatoramos n como
n = pe11 · · · pekk .
Pelo algoritmo euclideano, para cada 1 ≤ i ≤ k, existem qi, ri ∈ Z tais que ei =
2qi + ri, onde 0 ≤ ri < 2. Assim
n = p2q11 p
r1
1 · · · p2qkk prkk
e tomando Q := pr11 · · · prkk , excluindo os primos com expoente zero, temos que Q e´
livre de quadrados. O que sobra e´ a2 com a := pq11 · · · pqkk , i.e., n = a2Q. �
Proposic¸a˜o 3.10. Seja n ≥ 1 inteiro livre de quadrados, enta˜o √n /∈ Q.
Demonstrac¸a˜o. Suponha que
√
n = ab com a, b ∈ Z e mdc(a, b) = 1. Seja
n = p1 · · · pk
a fatorac¸a˜o de n. Enta˜o
a2 = p1 · · · pkb2.
Logo para cada 1 ≤ i ≤ r temos que pi | a2. Pelo lema 3.3 concluimos que pi | a,
digamos a = piαi para αi ∈ Z. Substituindo na igualdade anterior obtemos
p2iα
2
i = p1 · · · pkb2.
Simplificando pi na igualdade acima, obtemos
piα
2
i = p1 · · · pi−1pi+1 · · · pkb2 = cb2,
onde c := p1 · · · pi−1pi+1 · · · pk. Como pi - c, pois pi na˜o pode dividir nenhum dos
fatores de c uma vez que p1 < · · · < pk, ou seja sa˜o todos distintos, concluimos que
pi | b2. Novamente pelo lema 3.3 temos que pi | b, o que contradiz mdc(a, b) = 1. �
Proposic¸a˜o 3.11. Seja f ≥ 2 inteiro e p ≥ 2 primo. Enta˜o f√p /∈ Q.
14 3. FATORAC¸A˜O DE INTEIROS
Demonstrac¸a˜o. Suponha que f
√
p = ab com a, b ∈ Z e mdc(a, b) = 1. Enta˜o
af = pbf
e p | af . Pela observac¸a˜o 3.4 concluimos que p | a, digamos a = pα. Substituindo
na igualdade anterior obtemos
pfαf = pbf ,
simplificando a igualdade anterior por p, concluimos que
pf−1αf = bf .
Como f ≥ 2 temos que p aparece na fatorac¸a˜o do lado esquerdo, em particular,
p | bf . Novamente, pela observac¸a˜o 3.4 concluimos que p | b, mas isto contradiz
mdc(a, b) = 1. �
Definic¸a˜o 3.12. Sejam n ≥ 1 e f ≥ 2 inteiros. Dizemos que n e´ livre de
f-poteˆncias se a fatorac¸a˜o de n e´ da forma
n = pe11 · · · pekk
com 1 ≤ ei < f para todo 1 ≤ i ≤ k.
Lema 3.13. Seja n ≥ 1 inteiro, enta˜o existem Q, a ≥ 1 inteiros tais que n =
afQ com Q livre de f-poteˆncias.
Demonstrac¸a˜o. Seja
n = pe11 · · · pekk
a fatorac¸a˜o de n. Pelo algoritmo euclideano, para cada 1 ≤ i ≤ k, existem qi, ri ∈ Z
tais que ei = fqi + ri, onde 1 ≤ ei < f . Assim escrevemos
n = pfq11 p
r1
1 · · · pfqkk prkk .
Como anteriormente Q := pr11 · · · prkk e´ livre de f -poteˆncias e tomando a :=
pq11 · · · pfkk concluimos que n = afQ. �
Proposic¸a˜o 3.14. Sejam n ≥ 1 e f ≥ 2 inteiros. Suponhamos que n seja livre
de f-poteˆncias. Enta˜o f
√
n /∈ Q.
Demonstrac¸a˜o. Seja
n = pe11 · · · pekk
a fatorac¸a˜o de n, onde 1 ≤ ei < f para todo i ≤ i ≤ k. Suponhamos que f
√
n = ab
com a, b ∈ Z e mdc(a, b) = 1. Enta˜o
af = pe11 · · · pekk bf .
Logo para cada 1 ≤ i ≤ k pi | af . Pela observac¸a˜o 3.4 concluimos que pi | a,
digamos a = piαi para αi ∈ Z. Substituindo na igualdade anterior obtemos
pfi α
f
i = p
e1
1 · · · pekk bf .
Cancelando peii em ambos os lados da igualdade acima e denotando
c := pe11 · · · pei−1i−1 pei+1i+1 · · · pekk ,
obtemos
pf−eii α
f
i = cb
f .
Como anteriormente pi - c uma vez que pi na˜o divide nenhum fator de c. Logo
pi | bf . Novamente pela observac¸a˜o 3.4 concluimos que pi | b, mas isto contradiz
mdc(a, b) = 1. �
3.5. FUNC¸O˜ES ARITME´TICAS ELEMENTARES 15
3.5. Func¸o˜es aritme´ticas elementares
Para todo nu´mero inteiro n ≥ 1 denotemos por ν(n) o nu´mero de divisores
inteiros positivos de n e por σ(n) a soma de todos estes divisores, i.e.,
ν(n) := #{d ≥ 1 | d | n} e σ(n) :=
∑
d≥1,d|n
d.
Utilizaremos a fatorac¸a˜o u´nica para obter fo´rmulas expl´ıcitas para estes dois nu´-
meros.
Proposic¸a˜o 3.15. Seja n = pa11 · · · parr a fatorac¸a˜o de n em nu´meros primos.
Enta˜o
ν(n) = (a1 + 1) · · · (ar + 1) e σ(n) = p
a1+1
1 − 1
p1 − 1 · · ·
par+1r − 1
pr − 1 .
Demonstrac¸a˜o. Note que d | n se e somente se d fatora-se como
d = pb11 · · · pbrr com 0 ≤ bi ≤ ai para todo 1 ≤ i ≤ r.
Assim, os divisores positivos de n correspondem bijetivamente as r-uplas (b1, · · · , br)
satisfazendo a 0 ≤ bi ≤ ai para todo 1 ≤ i ≤ r. A quantidade destas r-uplas e´
exatamente (a1 + 1) · · · (ar + 1).
Para a segunda igualdade observe que
σ(n) =
∑
(b1,··· ,br)
pb11 · · · pbrr =
(∑
b1
pb11
)
· · ·
(∑
br
pbrr
)
e que cada soma no segundo membro e´ a soma dos termos de uma progressa˜o
geome´trica, disto segue a fo´rmula para σ(n). �
3.5.1. Func¸a˜o de Mœbius. Definimos a func¸a˜o de Mœbius µ : N \ {0} → Z
por µ(1) := 1, µ(n) := 0, se n na˜o e´ livre de quadrados, caso contra´rio, i.e.,
n = p1 · · · pr, onde os pi’s sa˜o primos distintos definimos µ(n) := (−1)r.
Proposic¸a˜o 3.16. Se n > 1, enta˜o∑
d≥1,d|n
µ(d) = 0.
Demonstrac¸a˜o. Seja n = pa11 · · · parr a fatorac¸a˜o de n. Pela definic¸a˜o de µ
temos que ∑
d≥1,d|n
µ(d) =
∑
(�1,··· ,�r)
µ(p�11 . . . p
�r
r ),
onde os �i’s sa˜o 0 ou 1. Portanto,∑
d≥1,d|n
µ(d) = 1− r +
(
r
2
)
−
(
r
3
)
+ . . .+ (−1)r = (1− 1)r = 0.
�
Para entender melhor a func¸a˜o de Mœbius precisamos introduzir a multi-
plicac¸a˜o de Dirichlet. Sejam f, g : N \ {0} → C, definimos
f ◦ g(n) :=
∑
d1,d2≥1,d1d2=n
f(d1)g(d2).
16 3. FATORAC¸A˜O DE INTEIROS
Este produto e´ associativo. Isto segue do seguinte exerc´ıcio
f ◦ (g ◦ h)(n) = (f ◦ g) ◦ h(n) =
∑
d1,d2,d3≥1,d1d2d3=n
f(d1)g(d2)h(d3).
Definimos a func¸a˜o 1 : N \ {0} → Z por 1(1) := 1 e 1(n) := 0, se n > 1. Segue
da definic¸a˜o que para toda func¸a˜o f : N \ {0} → C temos f ◦ 1 = 1 ◦f = f . Defina
tambe´m a func¸a˜o I : N \ {0} → Z por I(n) := 1 para todo n. Novamente, por esta
definic¸a˜o obtemos f ◦ I(n) = I ◦ f(n) =∑d≥1,d|n f(d).
Lema 3.17. I ◦ µ = µ ◦ I = 1.
Demonstrac¸a˜o. E´ claro que µ ◦ I(1) = µ(1)I(1) = 1. Se n > 1, enta˜o
µ ◦ I(n) =∑d≥1,d|n µ(d) = 0. A prova para I ◦ µ e´ ideˆntica. �
Teorema 3.18 (teorema de inversa˜o de Mœbius). Seja
F (n) :=
∑
d≥1,dmin d
f(d).
Enta˜o
f(n) =
∑
d≥1,d|n
µ(d)F (n/d).
Demonstrac¸a˜o. Por definic¸a˜o F = f◦I. Logo, F ◦µ = (f◦I)◦µ = f◦(I◦µ) =
f ◦ 1 = f , i.e.,
f(n) = F ◦ µ(n) =
∑
d≥1,d|n
µ(d)F (n/d).
�
O teorema de inversa˜o de Mœbius tem diversas aplicac¸o˜es, dentre elas a func¸a˜o
φ de Euler definida da seguinte forma. Seja n ≥ 1 inteiro, φ(n) denota o nu´mero
de inteiros positivos d ≤ n tais que mdc(d, n) = 1. E´ claro que se p for um nu´mero
primo φ(p) = p− 1.
Proposic¸a˜o 3.19. ∑
d≥1,d|nφ(d) = n
Demonstrac¸a˜o. Consideremos as n frac¸o˜es 1/n, 2/n, · · · , (n−1)/n, n/n. Po-
demos reduzir cada uma delas a forma mı´nima cancelando os fatores primos comuns
do numerador e denominador. Assim, cada uma delas sera´ igual a uma frac¸a˜o a/b
com mdc(a, b) = 1. Os denominadores sera˜o sempre divisores de n. O nu´mero de
frac¸o˜es na forma mı´nima com denominador d, pela definic¸a˜o da func¸a˜o φ, e´ igual a
φ(d). Disto segue a proposic¸a˜o. �
Proposic¸a˜o 3.20. Se n = pa11 . . . p
ar
r , enta˜o
φ(n) = n
(
1− 1
p1
)
. . .
(
1− 1
pr − 1
)
.
Demonstrac¸a˜o. Como
n =
∑
d≥1,d|n
φ(d),
3.5. FUNC¸O˜ES ARITME´TICAS ELEMENTARES 17
pelo teorema de inversa˜o de Mœbius temos
φ(n) =
∑
d≥1,d|n
µ(d)n/d = n−
∑
i
n
pi
+
∑
i<j
n
pipj
+ . . .
= n
(
1− 1
p1
)
. . .
(
1− 1
pr − 1
)
�
CAP´ıTULO 4
Induc¸a˜o finita
Neste cap´ıtulo apresentamos o me´todo da induc¸a˜o finita. Este me´todo e´ uti-
lizado em diversas circunstaˆncias em matema´ticas para provar afirmativas que de-
pendem “indutivamente” dos nu´meros naturais.
4.1. Enunciados
Axioma 4.1 (princ´ıpio da induc¸a˜o finita na sua primeira forma). Seja A(n)
uma afirmativa sobre nu´meros naturais n ∈ N. Suponha que
(1) exista n0 ∈ N tal que A(n0) seja verdadeira.
(2) Dado k ≥ n0, toda vez que A(k) for verdade, enta˜o A(k + 1) tambe´m o
sera´.
Enta˜o para todo n ≥ n0 a afirmativa A(n) e´ verdadeira.
Axioma 4.2 (princ´ıpio da induc¸a˜o finita na sua segunda forma). Seja A(n)
uma afirmativa sobre nu´meros naturais n ∈ N. Suponha que
(1) exista n0 ∈ N tal que A(n0) seja verdadeira.
(2) Se A(k) e´ verdadeira para todo n0 ≤ k < n enta˜o A(n) tambe´m e´ ver-
dadeira.
Logo para todo n ≥ n0 a afirmativa A(n) e´ verdadeira.
4.2. Exemplos da induc¸a˜o na sua primeira forma
Exemplo 4.3. Para todo inteiro n ≥ 1 temos
n∑
i=1
i =
n(n+ 1)
2
.
Demonstrac¸a˜o. (1) Para n = 1 temos que 1 = 1.22 .
(2) Suponha que
∑n
i=1 i =
n(n+1)
2 . Enta˜o
n+1∑
i=1
i =
n∑
i=1
i+ (n+ 1) =
n(n+ 1)
2
+ (n+ 1) =
(n+ 1)(n+ 2)
2
.
�
Lema 4.4. Seja p um nu´mero primo e 1 ≤ i < p inteiro, enta˜o o binomial (pi)
e´ divis´ıvel por p.
Demonstrac¸a˜o. Por definic¸a˜o(
p
i
)
=
p(p− 1) · · · (p− i+ 1)
i(i− 1) · · · 1 ∈ Z.
19
20 4. INDUC¸A˜O FINITA
Note que p na˜o divide nenhum dos fatores do denominador, pois i < p. Logo
podemos colocar p para fora da frac¸a˜o e o que sobra
(p− 1) · · · (p− 1 + i)
i(i− 1) · · · 1
tambe´m e´ inteiro. �
Exemplo 4.5. Seja p um nu´mero primo. Para todo inteiro n ≥ 1 temos que p
divide np − n.
Demonstrac¸a˜o. (1) Para n = 1 temos que p divide 1p − 1 = 0.
(2) Suponha que p | (np − n). Enta˜o
(n+ 1)p − (n+ 1) =
p−1∑
i=1
(
p
i
)
ni + (np − n).
Pelo Lema 4.4 e pela hipo´tese de p | (np − n) concluimos que p | ((n +
1)p − (n+ 1)).
�
Teorema 4.6 (pequeno teorema de Fermat). Seja p um nu´mero primo e a ∈ Z.
Enta˜o p | (ap − a).
Demonstrac¸a˜o. O exemplo mostra o teorema para inteiros positivos. Seja
m < 0 inteiro, digamos m = −n para n ≥ 1. Suponha p > 2. Neste caso,
mp−m = (−n)p− (−n) = −(np−n) que e´ divis´ıvel por p. No caso de p = 2 temos
que se n2 − n = 2α, enta˜o m2 −m = n2 + n = n+ 2α+ n = 2(α+ 1). �
Observac¸a˜o 4.7. O teorema anterior e´ na verdade equivalente para um inteiro
a na˜o divis´ıvel por p a p | (ap−1−1). De fato, suponha que ap−a = a(ap−1−1) = αp
para α ∈ Z. Se p - a, enta˜o pelo Lema 3.3 concluimos que p | (ap−1 − 1).
4.3. Exemplos da induc¸a˜o finita na sua segunda forma
Ordenamos os nu´meros primos
p1 = 2 < p2 = 3 < p3 = 5 · · · < pn · · · ,
onde pn denota o n-e´simo nu´mero primo. Seja P o conjunto dos nu´meros primos.
Teorema 4.8 (Euclides). O conjunto P e´ infinito.
Demonstrac¸a˜o. Suponhamos que P seja finito, digamos com k elementos,
P = {p1 < · · · < pk}.
Seja
M := p1 · · · pk + 1.
Notemos que M > p1 · · · pk ≥ 2pk > pk, logo M tem que ser um nu´mero composto.
Pelo teorema fundamental da aritme´tica M e´ produto de nu´meros primos. Logo
os u´nicos primos que podem aparecer na sua fatorac¸a˜o sa˜o p1, · · · , pk, digamos que
pi | M , i.e., existe αi ≥ 1 inteiro tal que M = αipi. Retornando a` definic¸a˜o de M
obtemos
pi(αi − p1 · · · pi−1pi+1 · · · pk) = 1.
Os fatores do lado esquerdo sa˜o ambos inteiros, o primeiro e´ positivo e o produto e´
positivo. Logo a expressa˜o entre pareˆnteses e´ positiva. Por outro lado pi ≥ 2, logo
4.3. EXEMPLOS DA INDUC¸A˜O FINITA NA SUA SEGUNDA FORMA 21
o lado esquerdo e´ pelo menos 2, enquanto o lado direito e´ 1, o que e´ imposs´ıvel. A
contradic¸a˜o vem do fato de termos suposto P finito, portanto P e´ infinito. �
No pro´ximo cap´ıtulo daremos outras demonstrac¸o˜es deste teorema bem como
discutiremos em maior profundidade os nu´meros primos.
Exemplo 4.9. Para todo inteiro n ≥ 1 temos pn ≤ 22n .
Demonstrac¸a˜o. (1) Observe que p1 = 2 ≤ 22 = 4.
(2) Suponha que para todo 1 ≤ m < n tenhamos pm ≤ 22m . A demonstrac¸a˜o
do teorema de Euclides mostra que M := p1 · · · pn−1 + 1 na˜o pode ser di-
vis´ıvel por nenhum dos primos p1, · · · , pn−1. LogoM so´ pode ser divis´ıvel
por primos maiores que pn−1, em particular, pn ≤M . Assim,
pn ≤ p1 · · · pn−1 + 1 ≤ 222 + . . . 2n−1 + 1.
Mas 22 + . . . + 2n−1 = 2(1 + . . . + 2n−2) = 2 2
n−1−1
2−1 = 2
n − 2. Portanto,
pn ≤ 22n−2+1. Basta mostrar que 22n−2+1 ≤ 22n , i.e., 4 ≤ 22n+2−22n =
22
n
(4− 1), o que e´ verdade.
�
Exemplo 4.10 (algoritmo de Euclides). Seja b ≥ 1 inteiro. Para todo inteiro
n ≥ 1 existem q, r ∈ Z tais que n = bq + r para 0 ≤ r < n.
Demonstrac¸a˜o. (1) Se n < b tome q = 0 e r = n. Se n = b tome q = 1
e r = 0.
(2) Suponhamos que n > b. Enta˜o 1 ≤ n − b < n. Por hipo´tese de induc¸a˜o,
para todo 1 ≤ m < n existem qm, rm ∈ Z tais que m = bqm + rm, onde
0 ≤ rm < n. Em particular, existem q′, r′ ∈ Z tais que n − b = q′b + r′
onde 0 ≤ r′ < b. Logo n = (q′+1)b+ r′ e basta tomar q = q′+1 e r = r′.
�
CAP´ıTULO 5
Nu´meros primos
No cap´ıtulo anterior provamos que o conjunto dos nu´meros primos e´ infinito.
Daremos 3 outras demonstrac¸o˜es para este fato. Cada qual tem seu me´rito pro´prio.
A prova apresentada no cap´ıtulo sobre induc¸a˜o finita e´ a original de Euclides.
Provaremos tambe´m que existe uma infinidade de nu´meros primos em certas progre-
sso˜es aritme´ticas e que func¸o˜es polinomiais na˜o lineares produzem uma infinidade
de nu´meros compostos.
5.1. Infinidade de primos
Seja P o conjunto dos nu´meros primos.
Teorema 5.1 (Euclides). O conjunto P e´ infinito.
2a. Demonstrac¸a˜o. Suponhamos que P seja finito, digamos P = {p1, · · · ,
pk}. Seja n ≥ 1 inteiro. Pelo Lema 3.9, n = mQ2, com m,Q ≥ 1 inteiros e m
livre de quadrados. Por um lado a quantidade de nu´meros inteiros positivos ate´ n e´
exatamente n. Por outro, m = pe11 · · · pekk , onde ei ∈ {0, 1}, para 1 ≤ i ≤ k. Assim,
escolher m e´ equivalente a escolher os expoentes ei, e como tenho duas escolhas
para cada i, o nu´mero de escolhas poss´ıveis para m e´ no ma´ximo 2k. Observemos
tambe´m que Q ≤ √n, logo o nu´mero de escolhas para Q e´ no ma´ximo √n, portanto,
o nu´mero de escolhas para n e´ no ma´ximo 2k
√
n, i.e., n ≤ 2k√n, i.e., √n ≤ 2k,
i.e., n ≤ 22k. Mas k e´ fixo, e´ a cardinalidade do conjunto de nu´meros primos, e n e´
um inteiro qualquer, i.e., estamos mostrando que o conjunto dos inteiros positivos
e´ limitado, o que e´ imposs´ıvel. Portanto, P e´ infinito. �
3a. Demonstrac¸a˜o. Seja F (n) := 22
n
+ 1 o n-e´simo nu´mero de Fermat.
Mostramos anteriormente (exerc´ıcio do cap´ıtulo sobre algoritmo de Euclides) que
se n > m ≥ 1, enta˜o mdc(F (n), F (m)) = 1. Comec¸amos escolhendo um fator primo
q1 de F (1). Pelo resultado anterior, todo fator primo de F (2) e´ distinto de q1, escol-
hemos um destes fatores primos, digamos q2. Suponhamos que para todo 1 ≤ m < n
tenhamos escolhidopara cada F (m) um fator primo distinto. Novamente pelo re-
sultado anterior todo fator primo de F (n) e´ distinto de q1, · · · , qn−1, escolhemos um
destes fatores primos, digamos qn. Provamos assim (via a Induc¸a˜o na sua segunda
forma) que para todo n ≥ 1 temos um nu´mero primo qn fator de F (n) distinto de
q1, · · · , qn−1. Produzimos assim um subconjunto infinito {q1, · · · , qn, · · · } ⊂ P de
P. Em particular, P e´ infinito. �
Uma quarta demonstrac¸a˜o e´ consequ¨eˆncia do seguinte teorema.
Teorema 5.2 (*). A se´rie ∑
p∈P
1
p
23
24 5. NU´MEROS PRIMOS
diverge.
Para a noc¸a˜o de divergeˆncia de se´rie veja [Li, Cap´ıtulo IV].
Demonstrac¸a˜o. Sejam n ≥ 1 inteiro e p1, · · · , pl(n) os nu´meros primos me-
nores ou iguais a n. Seja
λ(n) :=
l(n)∏
i=1
1
1− pi .
Segue das Preliminares que
1
1− pi =
∑
ai≥0
1
paii
,
logo
λ(n) =
∑
(a1,··· ,al(n))
1
pa11 . . . p
al(n)
l(n)
,
onde a l(n)-upla (a1, · · · , al(n)) e´ formada de inteiros na˜o negativos. Em particular,
como
1 +
1
2
+ . . .+
1
n
< λ(n),
concluimos que λ(n) → ∞ quando n → ∞ (ver [Li, Cap´ıtulo IV, Exemplos 23]).
Em particular, P e´ um conjunto infinito.
Calculando o logartimo de λ(n) (ver Preliminares) obtemos
log(λ(n)) = −
l(n)∑
i=1
log(1− pi) =
l(n)∑
i=1
∑
m≥1
1
mpmi
=
1
p1
+ . . .+
1
pl(n)
+
l(n)∑
i=1
∑
m≥2
1
mpmi
.
Note que ∑
m≥2
1
mpmi
<
∑
m≥2
1
pmi
=
1
p2i
1
1− p−1i
≤ 2
p2i
.
Logo,
log(λ(n)) <
1
p1
+ . . .+
1
pl(n)
+ 2
(
1
p21
+ . . .+
1
p2l(n)
)
.
Segue de [Li, Cap´ıtulo IV, Exemplo 29] que
∑
n≥1 n
−2 converge, a fortiori o mesmo
vale para
∑
i≥1 p
−2
i . Dessa forma, se
∑
p∈P p
−1 convergisse, existiria uma constante
M tal que log(λ(n)) < M , i.e., λ(n) < eM , mas λ(n)→∞, quando n→∞. Assim,∑
p∈P p
−1 na˜o pode convergir. �
5.2. Primos em progresso˜es aritme´ticas
Nos pro´ximos 3 para´grafos procuramos estudar fo´rmulas “simples” que “car-
acterizem” os nu´meros primos. Na verdade procuramos func¸o˜es f : N → N cuja
imagem contenha “muitos” nu´meros primos. Comec¸aremos pela func¸a˜o linear, dig-
amos f(n) = an + b com a, b ≥ 1 inteiros. Note que f(N) e´ uma progressa˜o
aritme´tica com primeiro elemento a+ b e raza˜o b.
5.2. PRIMOS EM PROGRESSO˜ES ARITME´TICAS 25
Lema 5.3. Existem infinitos nu´meros primos da forma 4n + 3 com n ≥ 1
inteiro.
Demonstrac¸a˜o. Seja p > 2 um nu´mero primo. Comecemos analisando os
poss´ıveis restos da divisa˜o de p por 4. Pelo algoritmo da divisa˜o existem q, r ∈ Z
tais que p = 4q + r com 0 ≤ r < 4. Como p e´ primo as u´nicas possibilidades para
r sa˜o 1 e 3.
Seja P4,3 o conjunto dos nu´meros primos maiores ou iguais a 7 da forma 4n+3.
Suponha que P4,3 seja infinito, digamos P4,3 = {p1 < · · · < pk}. Seja
M := 4p1 · · · pk + 3.
Observe que M deixa resto 3 na divisa˜o por 4. Observe tambe´m que M >
4p1 · · · pk > 4pk > pk, logo (como pk e´ o maior nu´mero primo que deixa resto
3 na divisa˜o por 4) M e´ composto. Pelo teorema fundamental da aritme´tica M
fatora-se em um produto de primos.
Note que se a, b ≥ 1 sa˜o inteiros que deixam resto 1 na divisa˜o por 4, enta˜o o
mesmo ocorre para ab. De fato, se a = 4x+ 1, b = 4y + 1, enta˜o
ab = 4(4xy + x+ y) + 1.
Fica como exerc´ıcio verificar (utilizando a primeira forma da induc¸a˜o finita) que o
mesmo vale para um produto finito a1 · · · an de inteiros positivos cada qual deixando
resto 1 na divisa˜o por 4.
Assim, na˜o e´ poss´ıvel que todo fator de M deixe resto 1 na divisa˜o por 4,
i.e., existe algum 1 ≤ i ≤ k tal que pi | M , i.e., M = piαi para αi ≥ 1 inteiro.
Retornando a` definic¸a˜o de M obtemos
pi(αi − 4p1 · · · pi−1pi+1 · · · pk) = 3.
No lado esquerdo temos um produto de um nu´mero inteiro positivo por outro cujo
produto tambe´m e´ um inteiro positivo, logo o nu´mero inteiro entre parenteˆses e´ um
inteiro positivo. Como p1 ≥ 7, o lado esquerdo e´ pelo menos 7, o que e´ imposs´ıvel.
Portanto P4,3 e´ infinito. �
Lema 5.4. Existem infinitos nu´meros primos da forma 6n + 5 com n ≥ 1
inteiro.
Demonstrac¸a˜o. Seja p > 2 um nu´mero primo. Pelo algoritmo da divisa˜o
existem q, r ∈ Z tais que p = 6q+ r com 0 ≤ r < 6. Como p e´ primo, r so´ pode ser
1 ou 5.
Seja P6,5 o conjunto dos nu´meros primos maiores ou iguais a 11 da forma 6n+5
para n ≥ 1 inteiro. Suponha que P6,5 seja finito, digamos P6,5 = {p1 < · · · < pk}.
Seja
M := 6p1 · · · pk + 5.
Note que M deixa resto 5 na divisa˜o por 6. Note tambe´m que M > 6p1 · · · pk >
6pk > pk. Como pk e´ o maior nu´mero primo que deixa resto 5 na divisa˜o por 6
obtemos que M e´ composto.
Observe que se a, b ≥ 1 sa˜o inteiros que deixam resto 1 na divisa˜o por 6, enta˜o
o mesmo ocorre com ab. De fato, se a = 6x+ 1, b = 6y + 1, enta˜o
ab = 6(6xy + x+ y) + 1.
Fica como exerc´ıcio mostrar que o mesmo vale para um produto finito a1 · · · an de
inteiros positivos cada qual deixando resto 1 na divisa˜o por 6.
26 5. NU´MEROS PRIMOS
Assim na˜o e´ poss´ıvel que todo fator de M deixe resto 1 na divisa˜o por 6, i.e.,
existe 1 ≤ i ≤ k tal que pi | M , M = piαi para αi ≥ 1 inteiro. Retornando a`
definic¸a˜o de M obtemos
pi(αi − 6p1 · · · pi−1pi+1 · · · pk) = 5.
No lado esquerdo temos um produto de um nu´mero inteiro positivo por outro cujo
produto tambe´m e´ um inteiro positivo, logo o nu´mero inteiro entre parenteˆses e´ um
inteiro positivo. Como p1 ≥ 11, o lado esquerdo e´ pelo menos 11, o que e´ imposs´ıvel.
Portanto P6,5 e´ infinito. �
No para´grafo sobre func¸a˜o zeta a seguir enunciaremos um teorema devido a
Dirichlet que generaliza os dois lemas anteriores.
5.3. Infinidade de compostos por func¸o˜es polinomiais
Queremos agora analisar o que ocorre se a func¸a˜o considerada anteriormente
for polinomial. Veremos que em geral o fenoˆmeno se contrapo˜e ao caso linear, ou
seja, e´ poss´ıvel apenas garantir uma infinidade de nu´meros compostos na imagem
de f .
Teorema 5.5. Seja
f(n) := adn+ad−1nd−1 + . . .+ a1n+ a0,
onde ad, · · · , a0 ∈ Z com ad > 0. Enta˜o existem infinitos nu´meros compostos da
forma f(n).
Demonstrac¸a˜o. Se para todo n ≥ 1, f(n) for composto nada ha´ a fazer.
Caso contra´rio, seja n0 ∈ N tal que f(n0) = p nu´mero primo. Seja h ≥ 1 inteiro e
f(n0 + hp) = ad(n0 + hp)d + ad−1(n0 + hp)d−1 + . . .+ a1(n0 + hp) + a0.
Note que a soma dos termos constantes (considerando a expressa˜o acima como um
polinoˆmio em h) e´ igual a
adn
d
0 + ad−1n
d−1
0 + . . .+ a1n0 + a0 = p.
Logo,
f(n0 + hp) = p(1 + a1h+ a2(2n0h+ h2p) + . . .
+ ad−1((d− 1)nd−20 h+ . . .+ (d− 1)n0hd−2pd−3 + hd−1pd−2)
+ ad(dnd−10 h+ . . .+ dn0h
d−1pd−2 + hdpd−1)).
Observe que o termo l´ıder da expressa˜o acima como polinoˆmio em h e´ igual a
adp
d−1p > 0. Assim para um inteiro h ≥ 1 suficiente grande a expressa˜o entre
pareˆnteses do lado direito menos 1 e´ sempre positiva, portanto f(n0+hp) = p(1+α)
com α ≥ 1 inteiro. Em particular, f(n0 + hp) e´ sempre composto para todo h ≥ 1
suficientemente grande.
Para o caso d = 2 a cota para h e´ h > −(2an0 + b)/(ap) (fac¸a a conta neste
caso!). �
5.5. CONTANDO NU´MEROS PRIMOS 27
5.4. Nu´meros de Fermat e Mersenne
Nesta sec¸a˜o apresentamos os nu´meros de Fermat e Mersenne e comec¸amos a
discussa˜o de quando podem ser nu´meros primos. No cap´ıtulo subsequ¨ente sobre
aplicac¸o˜es da teoria de grupos a` aritme´tica elementar descreveremos de forma mais
precisa crite´rios para decidir quando estes nu´meros sa˜o primos.
Para todo n ≥ 1 inteiro seja F (n) := 22n + 1 o n-e´simo nu´mero de Fermat.
Fermat afirmava que todo nu´mero desta forma era primo. Na verdade o que deve
ter ocorrido e´ que ele calculou os quatro primeiros que realmente sa˜o. Entretanto,
Euler mostrou que 641 | F (5). Daremos uma demonstrac¸a˜o disto posteriormente.
Para todo n ≥ 1 inteiro seja M(n) := 2n − 1 o n-e´simo nu´merode Mersenne.
Lema 5.6. Se n e´ composto, enta˜o M(n) tambe´m e´ composto.
Demonstrac¸a˜o. Suponha que n = ab com 1 < a, b < n. Enta˜o
2n − 1 = (2a)b − 1 = (2a − 1)(2a(b−1) + 2a(b−2) + . . .+ 2a + 1)
o que mostra que M(a) |M(n). �
Observac¸a˜o 5.7. Se quisermos que um nu´mero de Mersenne seja primo, de-
vemos nos restringir a`queles nu´meros de Mersenne cujo ı´ndice n seja um nu´mero
primo. Mersenne produziu uma lista incompleta e incorreta deM(p)’s para p primo
tais que M(p) e´ primo. Novamente, produziremos a posteriori uma lista ocrreta, a
menos da complexidade computacional, utilizando teoria de grupos.
5.5. Contando nu´meros primos
Para todo nu´mero real x > 1 seja pi(x) := #{p | nu´mero primo com p ≤ x}.
O teorema de Euclides nos garante que limx→∞ pi(x) =∞ (para a noc¸a˜o de limite
veja [Li, cap´ıtulo IV]). Nosso objetivo e´ determinar uma estimativa elementar para
a func¸a˜o pi(x) que conta a quantidade de nu´meros primos menores ou iguais a um
dado nu´mero real maior que 1. Note que se 1 < x ≤ y, enta˜o pi(x) ≤ pi(y). Seja pn
o n-e´simo nu´mero primo. Enta˜o pi(pn) = n.
Proposic¸a˜o 5.8. Seja log(x) o logaritmo na base e. Enta˜o
pi(x) ≥ log(log(x)).
Demonstrac¸a˜o. Ja´ obtivemos anteriormente (via induc¸a˜o finita) que pn ≤
22
n
. Para todo x > 1 real fixado o conjunto {m ≥ 1 | inteiro, eem ≤ x} e´ finito.
Seja n− 1 seu maior elemento, i.e., een−1 ≤ x < een . Observe que
ee
n−1 ≥ 22n para n ≥ 4.
De fato, basta mostrar que
en−1 ≥ 2n log(2), ou seja , n− 1 ≥ n log(2) + log(log(2)),
o que e´ verdade pois log(2) < 1. Logo
pi(x) ≥ pi(een−1) ≥ pi(22n) ≥ pi(pn) = n ≥ log(log(x)).
�
Utilizaremos o me´todo da segunda demonstrac¸a˜o do teorema de Euclides para
refinar a` proposic¸a˜o anterior. Para todo inteiro n ≥ 1 seja γ(n) o conjunto dos
divisores primos de n.
28 5. NU´MEROS PRIMOS
Proposic¸a˜o 5.9.
pi(x) ≥ log(dxe)
2 log(2)
,
onde dxe denota a parte inteira de x (para a definic¸a˜o ver Preliminares).
Demonstrac¸a˜o. Para qualquer conjunto de nu´meros primos S denotamos
por fS(x) o nu´mero de inteiros positivos n ≤ x tais que γ(n) ⊂ S. Suponha que
S seja finito de cardinalidade t. Escrevemos n = m2s com s livre de quadrados.
Note que m ≤ √x. Ale´m disto temos no ma´ximo 2t escolhas para s. Portanto,
fS(x) ≤ 2t
√
x. Seja m := pi(x), assim pm+1 > x. Se S = {p1, · · · , pm}, enta˜o
fS(x) = dxe. Em particular, dxe ≤ 2pi(x)
√
x e disto segue a proposic¸a˜o. �
O me´todo acima nos da´ uma nova demonstrac¸a˜o do teorema 5.2. De fato, se∑
p∈P 1/p fosse convergente, enta˜o existiria n ≥ 1 tal que∑
j>n
1
pj
<
1
2
.
Seja S := {p1, · · · , pn} e x ≥ 1 inteiro. Enta˜o x−fS(x) e´ igual ao nu´mero de inteiros
positivos m ≤ x tais que γ(m) 6⊂ S. Em outras palavras, contamos o nu´mero de
inteiros 1 ≤ m ≤ x para os quais existe j > n tal que pj | m. Para cada primo pj
existem dx/pje mu´ltiplos de pj menores ou iguais a x. Portanto,
x− fS(x) ≤
∑
j>n
⌈
x
pj
⌉
≤
∑
j>n
x
pj
<
x
2
.
A fortiori, fS(x) ≥ x/2. Mas, fS(x) ≤ 2n
√
x. Logo, 2n ≥ √x/2, o que e´ imposs´ıvel
pois n e´ fixo e x e´ varia´vel.
Intimamente relacionada a` func¸a˜o pi(x) temos a seguinte func¸a˜o
θ(x) :=
∑
p∈P,p≤x
log(p).
Utilizaremos θ(x) para limitar pi(x). Seja θ(1) := 0.
Proposic¸a˜o 5.10.
θ(x) < (4 log(2))x.
Demonstrac¸a˜o. Considere o binomial(
2n
n
)
=
(n+ 1) . . . 2n
1.2 . . . n
.
Este nu´mero e´ um inteiro divis´ıvel por todo nu´mero primo n < p < 2n. Ale´m disto,
como
(1 + 1)2n =
2n∑
j=0
(
2n
j
)
, enta˜o 22n >
(
2n
n
)
.
Em consequ¨eˆncia,
22n >
(
2n
n
)
>
∏
n<p<2n
p.
Calculando o logartimo,
2n log(2) >
∑
n<p<2n
log(p) = θ(2n)− θ(n).
5.5. CONTANDO NU´MEROS PRIMOS 29
Somando esta relac¸a˜o para n = 1, 2, 4, · · · , 2m−1 obtemos
θ(2m) < log(2)(2m+1 − 2) < log(2)2m+1.
Como na demonstrac¸a˜o da proposic¸a˜o 5.8 existe m ≥ 1 tal que 2m−1 < x ≤ 2m,
donde
θ(x) ≤ θ(2m) < log(2)2m+1 = (4 log(2))2m−1 < (4 log(2))x.
�
Proposic¸a˜o 5.11. Existe um real c1 > 0 tal que
pi1(x) < c1
x
log(x)
, para x ≥ 2.
Demonstrac¸a˜o. Observe que
θ(x) ≥
∑
√
x<p≤x
log(p) ≥ log(√x)(pi(x)− pi(√x)) ≥ log(√x)pi(x)−√x log(√x).
Logo,
pi(x) ≤ 2θ(x)
log(x)
+
√
x ≤ (8 log(2)) x
log(x)
+
√
x,
onde a u´ltima desigualdade segue da proposic¸a˜o anterior. O resultado segue da
observac¸a˜o que
√
x < 2x/ log(x) para x ≥ 2. �
Corola´rio 5.12.
lim
x→∞
pi(x)
x
= 0.
Nosso objetivo agora e´ obter uma cota inferior para a func¸a˜o pi(x). Para isto
comecemos observando que(
2n
n
)
=
(
n+ 1
1
)(
n+ 2
2
)
. . .
(
n+ n
n
)
≥ 2n.
Por um exerc´ıcio deste cap´ıtulo temos
ordp
((
2n
n
))
= ordp
(
(2n)!
(n!)2
)
=
tp∑
j=1
(⌈
2n
pj
⌉
− 2
⌈
n
pj
⌉)
,
onde tp denota o maior inteiro tal que ptp ≤ 2n. Logo, tp = dlog(2n)/ log(p)e. Ale´m
disto, d2xe − 2dxe e´ sempre 0 ou 1, assim
ordp
((
2n
n
))
≤ log(2n)
log(p)
.
Proposic¸a˜o 5.13 (*). Existe real c2 > 0 tal que
pi(x) > c2
x
log(x)
.
Demonstrac¸a˜o. Pelo que foi feito anteriormente,
2n ≤
(
2n
n
)
≤
∏
p<2n
ptp .
Calculando o logaritmo obtemos,
n log(2) ≤
∑
p<2n
tp log(p) =
∑
p<2n
⌈
log(2n)
log(p)
⌉
log(p).
30 5. NU´MEROS PRIMOS
Se log(p) > (1/2) log(2n), i.e., p >
√
2n, enta˜o dlog(2n)/ log(p)e = 1. Assim,
n log(2) ≤
∑
p≤√2n
⌈
log(2n)
log(p)
⌉
log(p) +
∑
√
2n<p<2n
log(p) ≤
√
2n log(2n) + θ(2n)
Portanto, θ(2n) ≥ n log(2) − √2n log(2n). Mas, limn→∞(
√
2n log(2n))/n = 0.
Assim, existe uma constante real T > 0 tal que para n suficientemente grande
θ(2n) > Tn. Toamndo x suficientemente grande e tal que 2n ≤ x < 2n+1 obtemos
θ(x) ≥ θ(2n) > Tn > T x− 1
2
> Cx,
para algum real C > 0 conveniente. Portanto, existe real c2 > 0 tal que θ(x) > c2x
para todo x ≥ 2. Para completar a prova observamos que
θ(x) =
∑
p≤x
log(p) ≤ pi(x) log(x).
Portanto,
pi(x) ≥ θ(x)
log(x)
> c2
x
log(x)
.
�
5.5.1. Comenta´rios. As duas proposic¸o˜es anteriores sa˜o devidas a C˘ebychef
(1852). O seguinte teorema suplanta ambas (cf. [Ap, chapter 4], este resultado
depende de teoria anal´ıtica dos nu´meros).
Teorema 5.14 (teorema dos nu´meros primos).
lim
x→∞pi(x) =
x
log(x)
.
O teorema dos nu´meros primos foi conjecturado por Gauss na idade de 15 ou 16
anos. A prova correta surgiu apenas em 1896 por Hadamard e de la Valle´ Poussin
utilizando a func¸a˜o zeta de Riemann, que introduziremos no para´grafo seguinte.
Existem uma infinidade de problemas abertos sobre os nu´meros primos. Para
mencionar apenas dois :
• Existem infinitos nu´meros primos da forma n2 + 1?
• (Primos geˆmeos) Existem infinitos pares de nu´meros primos da forma
(p, p+ 2)?
Para mais problemas abertos veja [Si] e [Sh].
5.6. Func¸a˜o zeta
Nesta sec¸a˜o descreveremos sem prova diversos fatos a respeito da func¸a˜o zeta de
Riemann (para a prova destes fatos ver [IrRo, chapter 16]). Esta func¸a˜o e´ definida
por
ζ(s) :=
∑
n≥1
n−s, onde s ∈ C,<(s) > 1.
Esta se´rie converge em <(s) > 1 e converge uniformemente para <(s) ≥ 1 + δ
para todo δ > 0 (para a noc¸a˜o de convergeˆncia ver [Li, cap’ıtulo IV]). A primeira
propriedade e´ que ela admite uma expansa˜o em produto euleriano.
5.6. FUNC¸A˜O ZETA 31
Proposic¸a˜o 5.15. Para <(s) > 1 temos
ζ(s) =
∏
p∈P
1
1− p−s .
Particularmente importante e´ o comportamento assinto´tico desta func¸a˜o quan-
do s→ 1. Considerando que∑n≥1 1/n diverge suspeitamos que ζ(s)→∞ quando
s→ 1. Lembre que ζ(s) e´ uma func¸a˜o de uma varia´vel complexa.
Proposic¸a˜o 5.16. Suponha que <(s) > 1. Enta˜o
lim
s→1
(s− 1)ζ(s) = 1.
A proposic¸a˜o na verdade diz que ζ(s) e´ uma func¸a˜o meromorfa com um po´lo
simples em s = 1 (para mais detalhes ver [Ap, chapter 12]).
Corola´rio5.17. Quando s→ 1 temos
log(s)
(log(s− 1))−1 → 1.
Proposic¸a˜o 5.18.
ζ(s) =
∑
p∈P
1
ps
+R(s),
onde R(s) fica limitada quando s→ 1.
Dado um subconjunto S do conjunto dos nu´meros primos P, dizemos que S
tem densidade de Dirichlet se o limite
lim
s→1
∑
p∈S p
−s
(log(s− 1))−1
existe. Neste caso este limite e´ denotado por d(S) e e´ chamado a densidade de
Dirichlet de S. Esta densidade satisfaz as seguintes propriedades.
Proposic¸a˜o 5.19. Seja S um subconjunto do conjunto P dos nu´meros primos.
Enta˜o
(1) Se S e´ finito, enta˜o d(S) = 0.
(2) Se S conte´m todos os nu´meros primos, exceto um nu´mero finito deles,
enta˜o d(S) = 1.
(3) Se S = S1 ∪ S2 com S1 ∩ S2 = ∅, enta˜o d(S1 ∪ S2) = d(S1) + d(S2).
Teorema 5.20 (teorema das progresso˜es aritme´ticas de Dirichlet). Sejam a ∈
Z e m ≥ 1 inteiro tais que mdc(a,m) = 1. Seja P(a;m) o subconjunto do conjunto
P dos nu´meros primos que conte´m os primos p tais que p ≡ a (mod m). Enta˜o
d(P(a;m)) = 1/φ(m). A fortiori, P(a;m) e´ infinito.
5.6.1. Comenta´rios (*). Riemann propoˆs a seguinte conjectura (que per-
manece em aberto ate´ hoje).
Conjectura 5.21 (hipo´tese de Riemann). Todos os zeros da func¸a˜o zeta de
Riemann ζ(s) esta˜o contidos na reta <(s) = 1/2.
Sabe-se que na reta <(s) = 1/2 existe uma infinidade de zeros da func¸a˜o zeta
e que estes sa˜o sime´tricos em relac¸a˜o a` reta =(s) = 0. A veracidade da hipo´tese de
Riemann implica em maiores informac¸o˜es sobre a distribuic¸a˜o dos nu´meros primos
(para mais sobre isto ver [Ap, chapter13]).
32 5. NU´MEROS PRIMOS
O inteiro positivo n nada mais e´ que a cardinalidade do anel Z/nZ da arit-
me´tica modular (a ser introducido no pro´ximo cap´ıtulo). Esta analogia faz com
que Dedekind considere a seguinte extensa˜o da func¸a˜o zeta. Seja K uma extensa˜o
finita do corpo dos racionais Q (ver a parte referente a` teoria de corpos). Existe
um subconjunto OK de K que cumpre o mesmo papel de Z com relac¸a˜o a Q. Este
conjunto e´ chamado o anel de inteiros de K. Ele tem (entre outras propriedades
importantes) a caracter´ıstica que o anel quociente OK/I (onde I e´ um ideal de
OK , para mais sobre anel quocientes ver a parte de ane´is) e´ um conjunto finito cuja
cardinalidade e´ denotada por N(I). Assim, Dedekind define a func¸a˜o zeta de K
por
ζK(s) :=
∑
I
N(I)−s, onde <(s) > 1,
e I percorre todos os ideais de OK . Novamente conjectura-se que os zeros desta
func¸a˜o esta˜o na reta <(s) = 1/2, o que permanece em aberto. Note que ζQ nada
mais e´ que a func¸a˜o zeta de Riemann.
Nos anos 20 e 30 do se´culo XX, E. Artin, H. Hasse e A. Weil consideraram um
ana´logo “geome´trico” desta situac¸a˜o. Nele o papel de Q era ocupado pelo corpo de
func¸o˜es racionais em uma varia´vel Fq(τ) sobre um corpo finito Fq de q elementos
(ver parte de corpos). Neste contexto, L e´ uma extensa˜o finita de Fq(τ). O corpo
L possui tambe´m um subanel com propriedades similares a OK (quando K e´ uma
extensa˜o finita de Q). Isto permite a construc¸a˜o de uma func¸a˜o zeta associada a
L. Similarmente, pode-se formular como acima uma “hipo´tese de Riemann” para
L. Esta e´ chamada uma “hipo´tese de Riemann para curvas” porque L nada mais
e´ que o corpo de func¸o˜es racionais de uma curva sobre um corpo finito (para mais
sobre curvas sobre corpos finitos e a hipo´tese de Riemann neste contexto ver [Lo]).
Apo´s casos particulares da hipo´tese de Riemann para curvas terem sido tratados
por Artin e Hasse, Weil utilizando variedades abelianas e representac¸o˜es `-a´dicas
obte´m em 1948 a prova da “hipo´tese de Riemann para curvas” de forma geral.
No ano seguinte (1949) Weil propo˜e uma vasta generalizac¸a˜o deste resultado
substituindo Fq(τ) por um corpo de func¸o˜es κ em n varia´veis sobre Fq. Neste caso
a extensa˜o finita L de κ nada mais e´ que o corpo de func¸o˜es de uma variedade
alge´brica sobre Fq (para variedades alge´bricas ver [Ha]). De maneira visiona´ria
Weil percebe que uma prova da hipo´tese de Riemann neste contexto mais geral
seria consequ¨eˆncia de uma teoria de cohomologia suficientemente “rica” para re-
produzir as propriedades da cohomologia singular sobre os complexos. Segundo
muitos, as conjecturas de Weil foram sem sobra de du´vida o problema matema´tico
mais profundo apo´s a segunda guerra mundial. Na busca da cohomologia perdida,
os primeiros passos foram dados por J.-P. Serre introduzindo a cohomologia de feixes
de vetores de Witt. Mas foi A. Grothendieck que compreendeu que a func¸a˜o zeta
traz em si algo de novo que na˜o havia sido percebido pelos geˆometras alge´bricos,
desde de os italianos do se´culo XIX. Ela necessitava de uma base varia´vel, ou seja, a
variedade alge´brica era considerada simultaneamente sobre todos os corpos finitos
Fqn . Para isto introduziu o conceito que revoluciona completamente a geometria
alge´brica no se´culo XX, a teoria de esquemas. Com a contribuic¸a˜o de inu´meros
matema´ticos ale´m de Serre e Grothendieck, dentre eles M. Artin, J.-L. Verdier e
L. Illusie, as teoria de esquemas e de cohomologia evoluiram, permitindo que se
descobrisse que a “cohomologia apropriada”, a cohomologia e´tale (para mais so-
bre a cohomologia e´tale veja [Mi]), e que finalmente em 1973, um ex-aluno de
5.6. FUNC¸A˜O ZETA 33
Grothendieck, P. Deligne provasse finalmente as conjecturas de Weil (para os resul-
tados de Deligne veja [We1] e [We2]). Entretanto, o mestre na˜o ficou satisfeito. Na
verdade Grothendieck havia formulado um programa muito mais amplo, “as conjec-
turas standard”, das quais as conjecturas de Weil eram um corola´rio. Infelizmente,
este programa nunca foi atingido.
CAP´ıTULO 6
Aritme´tica modular
6.1. Aritme´tica modular
Definimos uma func¸a˜o soma de classes ⊕ : Z/nZ×Z/nZ→ Z/nZ por a⊕ b :=
a+ b.
Lema 6.1. Esta func¸a˜o esta´ bem definida, i.e., se a′ ≡ a (mod n) e b′ ≡ a
(mod n), enta˜o a′ + b′ = a+ b.
Demonstrac¸a˜o. Suponha a′ ≡ a (mod n) e b′ ≡ b (mod n), i.e., existem
k, l ∈ Z tais que a′ − a = kn e b′ − b = ln. Somando estas igualdades, (a′ + b′) −
(a+ b) = (k + l)n, i.e., a′ + b′ ≡ a+ b (mod n), i.e., a′ + b′ = a+ b. �
Definimos tambe´m um func¸a˜o produto de classes � : Z/nZ × Z/nZ → Z/nZ
por a� b := ab.
Lema 6.2. Esta func¸a˜o tambe´m esta´ bem definida, i.e., se a′ ≡ a (mod n) e
b′ ≡ b (mod n), enta˜o a′b′ = ab.
Demonstrac¸a˜o. Sejam k, l ∈ Z tais que a′ − a = kn e b′ − b = ln. Logo
a′b′ − ab = a′b′ − a′b+ a′b− ab = a′(b′ − b) + b(a′ − a) = (a′l+ bk)n, i.e., a′b′ ≡ ab
(mod n), i.e., a′b′ = ab. �
Proposic¸a˜o 6.3. O conjunto Z/nZ munido das operac¸o˜es ⊕ e � e´ um anel
comutativo com unidade.
Demonstrac¸a˜o. Precisamos provar que as 8 propriedades de 2.3 sa˜o satis-
feitas. Elas sa˜o herdadas das mesmas propriedades para inteiros como segue abaixo.
(1) a⊕ (b⊕c) = a⊕b+ c = a+ (b+ c) = (a+ b) + c = a+ b⊕c = (a⊕b)⊕c.
(2) a⊕ b = a+ b = b+ a = b⊕ a.
(3) Note que 0 = n = {kn | k ∈ Z} = nZ e´ o conjunto dos inteiros que sa˜o
mu´ltiplos de n. Observe que a⊕ 0 = a+ 0 = a.
(4) a⊕ n− a = a+ n− a = n = 0.
(5) a� (b� c) = a� bc = a(bc) = (ab)c = ab� c = (a� b)� c.
(6) a� b = ab = ba = b� a.
(7) a� 1 = a.1 = a.
(8) a� (b⊕ c) = a� b+ c = a(b+ c) = ab+ ac = ab⊕ ac = (a� b)⊕ (a� c).
�
A propriedade de cancelamento em um anel garante que este e´ um domı´nio de
integridade. Nem sempre Z/nZ e´ um domı´nio de integridade. Para simplificar a
notac¸a˜o escreveremos + no lugar de ⊕ e ab no lugar de a� b.
Proposic¸a˜o 6.4. Z/nZ e´ um domı´nio de integridade se e somente se n = p e´
um nu´mero primo.
35
36 6. ARITME´TICA MODULAR
Demonstrac¸a˜o. Suponha que Z/nZ seja um domı´nio de integridade. Supo-
nha que n = ab com 1 ≤ a, b ≤ n. Enta˜o n = 0 = ab = ab. Pela propriedade do
cancelamento, a = 0 ou b = 0. No primeiro caso existe α ≥ 1 inteiro tal que a = nα,
logo n = nαb, i.e., 1 = αb, i.e., b = 1 e a = n. No segundo caso existe β ≥ 1 inteiro
tal que b = nβ, logo n =anβ, i.e., 1 = aβ, i.e., a = 1 e b = n. Portanto, n e´ primo.
Suponha que n = p seja primo. Suponha ab = 0, i.e., ab = 0, i.e., p | ab.
Pelo Lema 3.3, p | a ou p | b, i.e., a = 0 ou b = 0, i.e., vale a propriedade de
cancelamento. �
Um elemento a ∈ Z/nZ e´ dito invers´ıvel, se existe b ∈ Z/nZ tal que ab = 1. De-
notamos por (Z/nZ)∗ o subconjunto de Z/nZ formado pelos elementos invers´ıveis.
Um domı´nio de integridadeD e´ dito um corpo, se para todo a ∈ D\{0} existe b ∈ D
tal que ab = 1. Assim, Z/nZ e´ um corpo se e somente se (Z/nZ)∗ = Z/nZ \ {0}.
Proposic¸a˜o 6.5. Z/nZ e´ um corpo se e somente se n = p e´ um nu´mero primo.
Demonstrac¸a˜o. Suponha que Z/nZ seja um corpo. Seja n = ab com 1 ≤
a, b ≤ n inteiros. Suponha que a < n. Neste caso, a 6= 0. Por hipo´tese, existe
c ∈ Z/nZ tal que ac = 1. Note que n = 0 = ab = ab. Multiplicando esta igualdade
por c dos dois lados obtemos 0 = b, i.e., b = n. Neste caso a = 1. Se a = n, enta˜o
necessariamente b = 1 e portanto n e´ primo.
Reciprocamente, suponha que n = p seja primo. Seja a ∈ Z/nZ\{0}, i.e., p - a.
Logo mdc(a, p) = 1. Pelo algoritmo euclideano estendido, existem r, s ∈ Z tais que
ra+ sp = 1, i.e., ra ≡ 1 (mod p), i.e., ra = ra = 1, i.e., a ∈ (Z/nZ)∗. �
A princ´ıpio Z/nZ e´ o conjunto de todas as classes a para a ∈ Z. Definido desta
forma Z/nZ poderia ser infinito. Isto na˜o ocorre.
Proposic¸a˜o 6.6. Z/nZ = {0, · · · , n− 1} e #Z/nZ = n.
Demonstrac¸a˜o. Por definic¸a˜o o conjunto do lado direito esta´ contido no con-
junto do lado esquerdo. O que temos que provar e´ a inclusa˜o oposta. Suponha que
a ∈ Z/nZ. Note que podemos sempre supor que a ≥ 0, basta tomar um mu´ltiplo
kn de n suficientemente grande tal que a′ = a+ kn ≥ 0, uma vez que a = a′. Pelo
algoritmo da divisa˜o, existem q, r ∈ Z tais que a = qn+r com 0 ≤ r < n, i.e., a ≡ r
(mod n), i.e., a = r ∈ {0, · · · , n− 1}.
Mostraremos agora que quaisquer duas classes no conjunto da direita sa˜o dis-
tintas. Sejam 0 ≤ a < b < n inteiros. Logo 0 ≤ b− a < b < n, i.e., b 6≡ a (mod n),
i.e., b 6= a. �
O conjunto (Z/nZ)∗ dos invers´ıveis em Z/nZ pode ser caracterizado tambe´m
da seguinte forma.
Proposic¸a˜o 6.7. (Z/nZ)∗ = {a ∈ Z/nZ | mdc(a, n) = 1}.
Demonstrac¸a˜o. Seja a ∈ (Z/nZ)∗, i.e., existe b ∈ Z/nZ tal que ab = ab = 1,
i.e., existe k ∈ Z tal que ab− kn = 1. Seja d = mdc(a, n) ≥ 1. Logo d | 1, mas isto
so´ e´ poss´ıvel se d = 1.
Seja a ∈ Z/nZ tal que mdc(a, n) = 1. Pelo algoritmo euclideano estendido,
existem r, s ∈ Z tais que ra+ sn = 1, i.e., ra ≡ 1 (mod n), i.e., ra = r a = 1, i.e.,
a ∈ (Z/nZ)∗. �
6.2. CRITE´RIOS DE DIVISIBILIDADE 37
6.2. Crite´rios de divisibilidade
Utilizaremos a aritme´tica modular para demonstrar crite´rios de divisibilidade.
6.2.1. Expansa˜o de um inteiro em uma dada base. Sejam a ≥ 0 e b ≥ 1
inteiros. Seja n ≥ 1 inteiro tal que bn seja a maior poteˆncia positiva de b menor ou
igual a a, i.e.,
bn ≤ a < bn+1.
Pelo algoritmo da divisa˜o existem qn, rn ∈ Z tais que
a = qnbn + rn, onde 0 ≤ rn < bn.
Observemos que
0 ≤ qn < b.
A primeira desigualdade e´ clara, porque qnbn e´ o maior mu´ltiplo positivo de bn que
e´ menor ou igual a a. Suponha que qn ≥ b. Logo
a ≥ bn+1 + rn ≥ bn+1,
o que na˜o e´ poss´ıvel. Em seguida, dividimos rn por qn−1, i.e., existem qn−1, rn−1 ∈
Z tais que
rn = qn−1bn−1 + rn−1, onde 0 ≤ rn−1 < bn−1.
Novamente,
0 ≤ qn−1 < b.
Na˜o precisamos repetir o argumento da primeira desigualdade, pois e´ o mesmo.
Para a segunda, se qn−1 ≥ b, ter´ıamos
rn ≥ bn + rn−1 ≥ bn,
o que na˜o e´ poss´ıvel. Substituindo na primeira igualdade obtemos
a = qnbn + qn−1bn−1 + rn−1.
Novamente, pelo algoritmo da divisa˜o existem qn−2, rn−2 ∈ Z tais que
rn−1 = qn−2bn−2 + rn−2, onde0 ≤ rn−2 < bn−2.
Se qn−2 ≥ b, enta˜o
rn−1 ≥ bn−1 + rn−2 ≥ bn−1,
o que e´ imposs´ıvel. Portanto, 0 ≤ qn−2 < b. Prosseguindo sucessivamente obtemos
(6.1) a = qnbn + qn−1bn−1 + . . .+ q1b+ q0,
onde 0 ≤ qi < b para todo 0 ≤ i ≤ n. A expressa˜o (6.1) e´ chamada a expansa˜o de
a na base b. Denotamos esta expansa˜o por ab := (qn · · · q0)b.
Seja a ≥ 0 inteiro e a = an.10n + . . .+ a1.10 + a0 sua expansa˜o na base 10. Os
elementos an, · · · , a0 sa˜o chamados os algarismos de a e a := (an · · · a0)10.
Exemplo 6.8. Um inteiro a ≥ 0 e´ divis´ıvel por 3 se e somente se ∑ni=0 ai ≡ 0
(mod 3). De fato, 10 ≡ 1 (mod 3), pois 10 − 1 = 9 = 3.3. Logo para todo n ≥ 0,
10n ≡ 1n = 1 (mod 3). Portanto, a ≡∑ni=0 ai (mod 3). Logo a ≡ 0 (mod 3) se e
somente se
∑n
i=0 ai ≡ 0 (mod 3).
Exemplo 6.9. Um inteiro a ≥ 0 e´ divis´ıvel por 11 se e somente se∑ni=0(−1)ai
≡ 0 (mod 11). De fato, 10 ≡ −1 (mod 11), pois 10 − (−1) = 11. Logo para todo
n ≥ 1, 10n ≡ (−1)n (mod 11) e portanto, a ≡ ∑ni=0(−1)ai (mod 11). Conse-
quentemente, a ≡ 0 (mod 11) se e somente se ∑ni=0(−1)ai ≡ 0 (mod 11).
38 6. ARITME´TICA MODULAR
Exemplo 6.10. O crite´rio de divisibilidade por 7 e´ um pouco mais intrincado.
A raza˜o e´ a seguinte: 10 ≡ 3 (mod 7), pois 10 − 3 = 7. Logo 102 ≡ 32 ≡ 2
(mod 7), pois 9 − 2 = 7; 103 ≡ 3.2 = 6 (mod 7); 104 ≡ 6.3 ≡ 4 (mod 7), pois
18− 4 = 14 = 2.7; 105 ≡ 4.3 ≡ 5 (mod 7), pois 12− 5 = 7; 106 ≡ 5.3 ≡ 1 (mod 7),
pois 15 − 1 = 14 = 2.7. Suponha para simplificar que n = 5, i.e., a tem apenas 6
algarismos. Aplicando o mesmo racioc´ınio acima obtemos que a ≡ 0 (mod 7) se e
somente se 5a5 + 4a4 + 6a3 + 2a2 + 3a1 + a0 ≡ 0 (mod 7).
6.3. Contando elementos invers´ıveis
No cap´ıtulo de fatorac¸a˜o de inteiros introduzimos a func¸a˜o φ de Euler. Pela
proposic¸a˜o 6.7 a definic¸a˜o dada anteriormente coincide com φ(n) := #(Z/nZ)∗.
Nesta sec¸a˜o vamos calcular no caso em que n e´ primo ou poteˆncia de primo. No
cap´ıtulo seguinte, usando o teorema chineˆs dos restos, faremos o ca´lculo geral.
Lema 6.11. Seja p um nu´mero primo. Enta˜o
φ(p) = p− 1.
Demonstrac¸a˜o. Provamos anteriormente que quando n = p e´ primo (Z/pZ)∗
= Z/pZ \ {0}, logo φ(p) = #(Z/pZ)− 1 = p− 1. �
Lema 6.12. Seja p um nu´mero primo e r ≥ 1 inteiro. Enta˜o
φ(pr) = pr−1(p− 1).
Demonstrac¸a˜o. Pela proposic¸a˜o 6.7, a ∈ (Z/prZ)∗ se e somente se mdc(a, pr)
= 1, i.e., p - a. Ao inve´s de contarmos estes elementos contaremos aqueles que sa˜o
divis´ıveis por p e subtairemos do total pr este nu´mero. Expandimos a na base p,
i.e.,
a = qr−1pr−1 + . . .+ q1p+ q0, onde 0 ≤ qi < p
e´ inteiro para todo 0 ≤ i ≤ r − 1. Assim, p | a se e somente se q0 = 0. Para cada
qi com 1 ≤ i ≤ r− 1 temos exatamente p escolhas. Logo o total de escolhas para a
tal que p | a e´ pr−1. Portanto, φ(pr) = pr − pr−1 = pr−1(p− 1). �
CAP´ıTULO 7
Sistemas de congrueˆncia
7.1. Equac¸o˜es diofantinas
Uma equac¸a˜o diofantina e´ uma equac¸a˜o polinomial em um nu´mero finito de
varia´veis cujos coeficientes sa˜o nu´meros inteiros e/ou racionais e procuramos solu-
c¸o˜es inteiras e/ou racionais. Nesta sec¸a˜o daremos um exemplo de como utilizar a
aritme´tica modular para provar que uma dada equac¸a˜o diofantina na˜o tem soluc¸o˜es
inteiras.
Exemplo 7.1. Seja f(x, y) = x3 − 711y3 = 5. Perguntamos se existem pares
(a, b) ∈ Z × Z tais que f(a, b) = 0. Mostraremos que na˜o pode existir um tal par
(a, b). De fato, suponha que exista. Logo a3 ≡ 5 (mod 9). Calculemos os cubos
de todos os elementos de Z/9Z. 13 = 1; 23 = 8, 33 = 0, 43 = 424 = 74 = 1;
53 = −43 = −43 = 8; 63 = −33 = −33 = 0; 73 = −23 = −23 = 1; 83 = −13 = 8.
Portanto, na˜o existe a ∈ Z tal que a3 ≡ 5 (mod 9), logo na˜o pode existir (a, b) ∈
Z× Z tal que f(a, b) = 0.
7.2. Equac¸o˜es lineares
Teorema 7.2. Sejam a, b ∈ Z, a 6= 0 e n ≥ 1 inteiro. A equac¸a˜o ax ≡ b
(mod n) tem soluc¸a˜o se e somente se d := mdc(a, n) | b.
Demonstrac¸a˜o. Suponha que x0 ∈ Z seja uma soluc¸a˜o da equac¸a˜o. Como d
divide a e n, denotamos a = a′d e n = n′d, onde n′, a′ ∈ Z. Logo existe k ∈ Z tal
que ax0 − b = kn, i.e., d(a′x0 − kn′) = b, assim d | b.
Reciprocamente, suponha que d | b, digamos b = db′. Pelo algoritmo euclideano
estendido, existem t, s ∈ Z taisque ta+ sn = d. Multiplicando ambos os lados por
b′ obtemos a(tb′) + snb′ = db′ = b, i.e., a(tb′) ≡ b (mod n), i.e., tb′ e´ uma soluc¸a˜o
da equac¸a˜o. �
Observac¸a˜o 7.3. Observe que se x0 ∈ Z e´ uma soluc¸a˜o de ax ≡ b (mod n),
enta˜o para todo y0 ≡ x0 (mod n), concluimos que y0 tambe´m e´ soluc¸a˜o da equac¸a˜o
(assim dizemos que a classe x0 de x0 e´ uma soluc¸a˜o para ax = b). De fato, y0 =
x0+kn para algum k ∈ Z e ax0 = b+ln para algum l ∈ Z. Logo ay0 = b+ln+akn =
b+ (l + ak)n, i.e., ay0 ≡ b (mod n).
Teorema 7.4. Suponha que a equac¸a˜o ax ≡ b (mod n) admita uma soluc¸a˜o
x0 ∈ Z. O nu´mero de soluc¸o˜es (mo´dulo n) de ax ≡ b (mod n) e´ d e elas sa˜o dadas
pelas classes cujos representantes sa˜o x0, x0 + n′, · · · , x0 + (d− 1)n′.
Demonstrac¸a˜o. Provemos inicialmente que cada um desses elementos e´ solu-
c¸a˜o. Escrevemos y0 = x0 + kn′ para algum 0 ≤ k ≤ d − 1 inteiro. Logo ay0 =
ax0 + akn′ = b+ ln+ akn′ = b+ ln+ a′dkn′ = b+ ln+ a′kn = b+ n(l+ a′k), i.e.,
ay0 ≡ b (mod n). Em seguida observemos que se 0 ≤ k < r ≤ d − 1 sa˜o nu´meros
39
40 7. SISTEMAS DE CONGRUEˆNCIA
inteiros, enta˜o x0+ kn′ 6≡ x0+ rn′ (mod n). De fato, 0 < (x0+ rn′)− (x0+ kn′) =
n′(r − k) < n′d = n, logo n - ((x0 + rn′)− (x0 + kn′) = n′(r − k)). �
7.3. Sistemas de equac¸o˜es lineares
Teorema 7.5. Sejam m,n ≥ 1 inteiros tais que mdc(m,n) = 1 e a, b ∈ Z.
Existe x ∈ Z tal que o sistema {
x ≡ a (mod m)
x ≡ b (mod n)
tenha soluc¸a˜o.
Demonstrac¸a˜o. Pelo algoritmo euclideano estendido existem t, s ∈ Z tais
que tm+ sn = 1. Logo
tm ≡ 1 (mod n) e sn ≡ 1 (mod m).
Seja x0 := asn+ btm. Observe que
x0 ≡ asn (mod m) ≡ a (mod m) e x0 ≡ btm (mod n) ≡ b (mod n).
�
Teorema 7.6. Sejam m1, · · · ,mr ≥ 1 inteiros tais que para todo 1 ≤ i 6= j ≤ r,
mdc(mi,mj) = 1. Sejam a1, · · · , ar ∈ Z. Existe x ∈ Z tal que o sistema
(7.1)

x ≡ a1 (mod m1)
· · ·
x ≡ ar (mod mr)
tenha soluc¸a˜o.
Demonstrac¸a˜o. Seja
m := m1 · · ·mr
e para todo 1 ≤ i ≤ r, seja
ni :=
m
mi
= m1 · · ·mi−1mi+1 · · ·mr.
Como para cada j 6= i, mdc(mj ,mi) = 1, temos que mdc(ni,mi) = 1. Pelo
algoritmo euclideano estendido existem ti, si ∈ Z tais que tini + simi = 1, i.e.,
tini ≡ 1 (mod mi)
e para todo j 6= i, como ni ≡ 0 (mod mj), enta˜o
tini ≡ 0 (mod mj).
Tome
x0 := a1t1n1 + . . .+ artrnr.
De fato, para todo 1 ≤ i ≤ r, temos
x0 ≡ aitini (mod mi) ≡ ai (mod mi),
uma vez que
ajtjnj ≡ 0 (mod mi) para i 6= j.
�
7.5. APLICAC¸A˜O 41
7.4. Teorema Chineˆs dos Restos
Notac¸a˜o. Dado n ≥ 1 inteiro e a ∈ Z denotaremos nesta sec¸a˜o a classe de a
mo´dulo n por a + nZ. Isto e´ motivado pelo fato que um elemento e´ equivalente a
a mo´dulo n se e somente se ele difere de a por um mu´ltiplo de n.
Teorema 7.7. Sejam m1, · · · ,mr ≥ 1 inteiros tais que para todo 1 ≤ i 6= j ≤ r,
mdc(mi,mj) = 1. Seja m := m1 · · ·mr. Existe uma bijec¸a˜o
ϕ :
Z
mZ
→ Z
m1Z
× . . .× Z
mrZ
definida por
ϕ(a+mZ) = (a+m1Z, · · · , a+mrZ).
Seja ψ a restric¸a˜o de ϕ a (Z/mZ)∗, enta˜o
ψ :
(
Z
mZ
)∗
→
(
Z
m1Z
)∗
× . . .×
(
Z
mrZ
)∗
tambe´m e´ uma bijec¸a˜o.
Demonstrac¸a˜o. Provemos inicialmente que ϕ esta´ bem definida. De fato, se
b ≡ a (mod m), enta˜o para todo 1 ≤ i ≤ r, mi | m | (b− a), logo b ≡ a (mod mi),
i.e., b+miZ = a+miZ.
Provemos agora que ϕ e´ injetiva. Suponha que ϕ(a +mZ) = ϕ(b +mZ), i.e.,
para todo 1 ≤ i ≤ r, a ≡ b (mod mi). Como para i 6= j, mdc(mi,mj) = 1,
concluimos que m | (a− b), i.e., a+mZ = b+mZ.
Provar que ϕ e´ sobrejetiva equivale a dizer que para todo (a1 +m1Z, · · · , ar +
mrZ) ∈ Z/m1Z× . . .× Z/mrZ e´ da forma ϕ(x+mZ) para algum x ∈ Z, i.e., que
o sistema (7.1) tema soluc¸a˜o, o que ja´ foi provado.
Provemos agora que um elemento invers´ıvel mo´dulo m tem imagem cujas
componentes sa˜o invers´ıveis com respeito aos respectivos mo´dulos. Suponha que
a + mZ ∈ (Z/mZ)∗, i.e., mdc(a,m) = 1. Como m = m1 · · ·mr, concluimos que
para cada 1 ≤ i ≤ r, mdc(a,mi) = 1, i.e., a+miZ ∈ (Z/miZ)∗. Como ψ e´ obtida
restringindo ϕ a um subconjunto do domı´nio, concluimos que ψ tambe´m e´ injetiva.
Quanto a sobrejetividade, seja (a1 +m1Z, · · · , ar +mrZ) ∈ (Z/m1Z)∗ × . . .×
(Z/mrZ)∗. Pela parte anterior sabemos que existe x ∈ Z tal que ϕ(x+mZ) = (a1+
m1Z, · · · , ar+mrZ). Observemos que na verdade x+mZ ∈ (Z/mZ)∗. De fato, para
cada 1 ≤ i ≤ r, x+miZ = ai +miZ, i.e., x ≡ ai (mod mi), mas mdc(ai,mi) = 1,
logo mdc(x,mi) = 1 para todo 1 ≤ i ≤ r. Como m = m1 · · ·mr e mdc(mi,mj) = 1
para i 6= j obtemos que mdc(x,m) = 1, i.e., x+mZ ∈ (Z/mZ)∗. �
Corola´rio 7.8. Para todo n ≥ 1 inteiro seja φ(n) = #(Z/nZ)∗. Enta˜o
φ(m) = φ(m1) · · ·φ(mr).
7.5. Aplicac¸a˜o
Seja n = pe11 · · · perr a fatorac¸a˜o do inteiro n ≥ 1. Pelo corola´rio 7.8 e pelo lema
6.12,
(7.2) φ(n) = φ(pe11 ) · · ·φ(perr ) = pe1−11 (p1 − 1) · · · per−1r (pr − 1)
= pe11
(
1− 1
p1
)
· · · perr
(
1− 1
pr
)
= n
∏
p|n
(
1− 1
p
)
.
42 7. SISTEMAS DE CONGRUEˆNCIA
Vamos utilizar a fo´rmula (7.2) para uma aplicac¸a˜o.
Proposic¸a˜o 7.9. Suponha que φ(n) = p seja um nu´mero primo. Enta˜o n = 3,
4 ou 6.
Demonstrac¸a˜o. Se r > 2, enta˜o ei = 1 para todo 1 ≤ i ≤ r. Logo φ(n) =∏r
i=1(pi − 1). Como r > 2 existem pelo menos dois primos ı´mpares na fatorac¸a˜o,
logo 4 | φ(n), o que na˜o e´ poss´ıvel. Logo r ≤ 2. Suponhamos inicialmente r = 2,
i.e., φ(n) = pe1−11 (p1 − 1)pe2−12 (p2 − 1). Se p1, p2 > 2 enta˜o (novamente) 4 | φ(n).
Logo p1 = 2 e φ(n) = 2e1−1pe2−12 (p2 − 1). Se e1 > 1, como p2 > 2, enta˜o 4 | φ(n).
Assim, e1 = 1 e φ(n) = pe2−12 (p2 − 1). Se e2 > 1, enta˜o φ(n) tem 2 e p2 como
fatores primos. Assim, e2 = 1 e φ(n) = pe2−12 . Novamente, como este nu´mero e´
primo, e2 = 1 e φ(n) = p2−1. Mas este nu´mero e´ par e primo, logo p2 = 3 e n = 6.
Suponhamos que r = 1, i.e., φ(n) = pe1−11 (p1 − 1). Se p1 = 2, enta˜o φ(n) =
2e1−1. A u´nica forma deste nu´mero ser primo e´ e1 = 2, logo n = 4. Suponha
p1 > 2. Se e1 > 1, enta˜o φ(n) tem 2 fatores primos p1 e 2 (pois p1 − 1 e´ par),
imposs´ıvel. Assim, e1 = 1 e φ(n) = p1 − 1. Isto ja´ foi feito anteriormente, i.e.,
p1 = 3 e n = 3. �
CAP´ıTULO 8
Aplicac¸o˜es da teoria de grupos a` teoria elementar
dos nu´meros
Neste cap´ıtulo desenvolveremos aplicac¸o˜es da teoria de grupos a` aritme´tica
elementar. Utilizaremos os resultados do cap´ıtulo 9.
8.1. Primalidade de nu´meros de Mersenne
Para todo inteiro n ≥ 1, seja Mn := 2n − 1 o n-e´simo nu´mero de Mersenne.
Nosso objetivo e´ utilizar a teoria de grupos para determinar seMn e´ primo ou obter
seu menor fator primo. Ja´ provamos anteriormente que se n e´ composto, enta˜o Mn
tambe´m o e´. Assim, consideraremos apenas Mp para p primo.
Seja q um fator primo deMp, i.e., 2p ≡ 1 (mod q). Portanto em (Z/qZ)∗ temos
2p = 1, i.e., o(2) | p. Como p e´ primo temos que o(2) = 1 ou p. O primeiro caso
na˜o pode ocorrer, pois 2 6= 1. Logo o(2) = p. Pelo teorema de Lagrange,
o(2) = p | #(Z/qZ)∗ = φ(q) = q − 1,
i.e., existe k ≥ 1 inteiro tal que q = 1 + kp.
Proposic¸a˜o 8.1. Todo fator primo deMp e´ da forma 1+kp para algum inteiro
k ≥ 1.
Provamos anteriormente que o menor fator primo de um nu´mero inteiro n ≥ 1
e´ no ma´ximo
√
n. Logo
q ≤ √2p − 1 < 2p/2, i.e. , k < 2
p/2 − 1
p
.
Dessa forma para determinar um fator primo de Mp testamos para cada inteiro k
tal que
1 ≤ k < 2
p/2 − 1
p
se 1 + kp e´ primo e se divide Mp. Se para cada k pelo menos um desses fatos na˜o
ocorrer enta˜o Mp e´ um nu´mero primo.
8.2. Primalidade de nu´meros de Fermat
Para todo inteiro n ≥ 1, seja Fn := 22n + 1 o n-e´simo nu´mero de Fermat. Seja
q um fator primo de Fn. Enta˜o 22
n ≡ −1 (mod q), logo 22n+1 ≡ 1 (mod q), i.e.,
22
n+1
= 1 em (Z/qZ)∗. Neste caso
o(2) | (2n+1), i.e. , o(2) = 2d para 1 ≤ d ≤ n+ 1.
Afirmamos que d = n+ 1. De fato, se d < n+ 1, enta˜o
22
n
= (22
d
)2
n−d
= 1,
43
44 8. APLICAC¸O˜ES DA TEORIA DE GRUPOS
o que e´