UNIVERSIDADE FEDERAL DE MINAS GERAIS
INSTITUTO DE CIÊNCIAS EXATAS
DEPARTAMENTO DE MATEMÁTICA
SÁVIO RIBAS
ORIENTADOR:
FABIO ENRIQUE BROCHERO MARTINEZ
INFINITOS NÚMEROS DE CARMICHAEL
APOIO: CAPES
BELO HORIZONTE - MG
ABRIL - 2013
UNIVERSIDADE FEDERAL DE MINAS GERAIS
INSTITUTO DE CIÊNCIAS EXATAS
DEPARTAMENTO DE MATEMÁTICA
SÁVIO RIBAS
INFINITOS NÚMEROS DE CARMICHAEL
Dissertação de mestrado apresentada como
parte dos requisitos para obtenção do título
de Mestre pelo Departamento de Matemática
do Instituto de Ciências Exatas da Universi-
dade Federal de Minas Gerais.
Orientador: Fabio E. Brochero Martinez.
BELO HORIZONTE - MG
ABRIL - 2013
Agradecimentos
• Agradeço primeiramente a Deus.
• Aos meus pais, Antonio e Rovia, pelo oportunidade que me deram de vir estudar em
Belo Horizonte, por sempre me incentivar e ensinar o que era melhor para mim.
• Ao meu irmão e à minha cunhada, Sabir e Tiene, pelo incentivo que sempre me deram.
• À minha namorada, Karine, pela força, companheirismo e compreensão.
• À minha tia Lili, por todos os ensinamentos e por me fazer gostar de Matemática.
• Ao meu avô, Vicente, aos meus tios, primos e demais membros familiares.
• Ao meu orientador, Fabio, por todos os ensinamentos, pela paciência e pela enorme
boa vontade. Está sendo muito proveitoso trabalhar contigo.
• À toda equipe do PICME pela oportunidade. Em especial, à Sylvie, Mário Jorge e
Remy, pela força e pelas dicas.
• Aos demais professores e funcionários do Departamento de Matemática.
• Aos meus amigos de Ouro Preto, Mariana e Belo Horizonte: Flávia, Michele, Marcus,
Vitor, Lucas Assis, Saulo, Tulio, Luana, Vladimir, Alice, Daniel, Paim, Remer, Natália,
Dani, Jéssica, Vinícius, Luis Felipe, Danilo, Carol, Pedros (Daldegan e Franklin), Li-
lian, Letícia, Pablo, Luccas, a todos os outros moradores e ex-moradores da minha
república, entre outros.
iii
Resumo
O objetivo desse trabalho é mostrar que existem infinitos números de Carmichael. Com
isso, os números de Carmichael são de certa forma os piores números para se testar a pri-
malidade utilizando o Pequeno Teorema de Fermat. Assim, o Pequeno Teorema de Fermat
pode ser (e é) usado como um bom teste de não primalidade, mas nunca pode ser usado
como um teste de primalidade. Nossa principal referência foi o artigo There are infinitely
many Carmichael numbers ([1], de W. R. Alford, A. Granville e C. Pomerance) e para cumprir
nosso objetivo foram estudados diversos tópicos em várias áreas da Matemática, como as
estimativas assintóticas de Mertens, teoria de grupos e caráteres, a função de Carmichael, a
constante de Davenport, a desigualdade de Brun-Titchmarsh (que nos levou a estudar a teo-
ria de Fourier e o grande crivo), o Teorema dos Números Primos em Progressão Aritmética
em hipóteses mais gerais e algumas estimativas acerca dos zeros das L-séries de Dirichlet.
iv
Abstract
The goal of this work is to show that there are infinitely many Carmichael numbers.
Hence, the Carmichael numbers are in some way the worst numbers for testing primality
using Fermat’s Little Theorem. Thus, Fermat’s Little Theorem can be (and is) used as a good
test of non-primality, but it never can be used as a primality test. Our main reference was
the paper There are infinitely many Carmichael numbers ([1], W. R. Alford, A. Granville and C.
Pomerance) and to fulfill our goal we studied many topics in various areas of Mathematics,
such as Mertens’ asymptotic estimates, group theory and characters, Carmichael’s function,
Davenport’s constant, Brun-Titchmarsh inequality (which led us to study the Fourier’s the-
ory and the large sieve), Prime Number Theorem in Arithmetic Progression in more general
hypotheses and some estimates about the zeros of Dirichlet L-series.
v
vi
Sumário
Introdução ix
1 As estimativas assintóticas de Mertens 1
1.1 A 1a fórmula de Mertens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 A 2a fórmula de Mertens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 A constante de Euler-Mascheroni e a 3a fórmula de Mertens . . . . . . . . . . 5
2 Resultados algébricos 9
2.1 Caráteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 A função de Carmichael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Subsequências com produto 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 O Grande Crivo e a desigualdade de Brun-Titchmarsh 17
3.1 O Grande Crivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 A desigualdade de Brun-Titchmarsh . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Infinitos números de Carmichael 29
4.1 Grandes números, pequenos fatores primos . . . . . . . . . . . . . . . . . . . . 29
4.2 Relacionando pequenos fatores primos com primos em P.A. . . . . . . . . . . 32
4.3 A cota inferior para a quantidade de números de Carmichael . . . . . . . . . . 35
4.4 Transferindo o trabalho para os zeros das L-séries . . . . . . . . . . . . . . . . 38
A A teoria de Fourier 45
A.1 Uma integral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
A.2 A transformada de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.3 O somatório de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
B Riemann, Dirichlet e os teoremas dos números primos 53
B.1 A função ζ de Riemann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
B.2 O Teorema dos Números Primos . . . . . . . . . . . . . . . . . . . . . . . . . . 55
B.3 As L-séries de Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
B.4 O Teorema dos Números Primos em Progressão Aritmética . . . . . . . . . . . 58
C Sobre os zeros das L-séries 61
C.1 Uma cota para os zeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Referências Bibliográficas 65
vii
viii
Introdução
No final do século XX, a necessidade de determinar se um número n ∈ N é primo de forma
computacionalmente eficiente se tornou um problema prático fundamental. Tal necessidade
surgiu a partir da invenção dos sistemas criptográficos assimétricos baseados no fato de que
não é conhecido no momento nenhum algoritmo eficiente e genérico para fatorar números
que tenham apenas fatores primos grandes.
O sistema criptográfico desse tipo mais conhecido e usado é o RSA, que é um sistema
inventado pelos professores Ronald Rivest, Adi Shamir e Leonar Adleman, do MIT. Esse
método consiste em uma chave pública (n, a) e uma chave privada (p, q, b), onde n = pq com
p e q primos gigantes, a é um inteiro tal que 1 < a < n escolhido de forma a ser relativamente
primo com ϕ(n) = (p − 1)(q − 1) (onde ϕ é a função de Euler) e b ≡ a−1 (mod ϕ(n)). É
claro que se conhecemos algum dos três números da chave privada então os outros dois são
facilmente calculáveis computacionalmente, isto é, tal cálculo é de complexidade polinomial
com respeito ao tamanho da entrada.
Dada uma mensagem M com 1 < M < n, a mensagem criptografada será um número
C tal que 1 < C < n e C ≡ Ma (mod n). Para decodificar a mensagem basta observar que
existe k1 tal que:
Cb ≡Mab ≡Mk1ϕ(n)+1 ≡M (mod n),
onde a igualdade anterior é verdadeira para quase todo valor de M . De fato, ela pode ser
falsa no caso que mdc(M,n) 6= 1, mas isso acontece com probabilidade 1
p
+ 1
q
− 1
pq
. Porém, no
caso em que mdc(M,n) > 1 ainda podemos decodificar a mensagem. Sobraram os seguintes
casos: mdc(M,n) = p, q ou n. O último implica que n divide M , o que é um absurdo pois
1 < M < n. Os outros dois são completamente análogos entre si, de forma que podemos
supor sem perda de generalidade que p divide M e mdc(M, q) = 1. Sabemos que b ≡ a−1
(mod ϕ(n)) e C ≡ Ma (mod n) implicam b ≡ a−1 (mod q − 1) e C ≡ Ma (mod q), respecti-
vamente. Logo, existe k2 tal que:
Cb ≡Mab ≡Mk2(q−1)+1 ≡M (mod q),
ix
assim o Teorema Chinês dos Restos nos diz que M é o único inteiro tal que:
M ≡ 0 (mod p)
M ≡ Cb (mod q)
1 < M < n
.
Observemos que o método tradicional para determinar se um número n é primo consiste
em dividir n por todos os primos menores ou iguais a
√
n. Este método também nos permite
determinar seus fatores primos menores ou iguais a
√
n, mas tal método é computacional-
mente ruim. De fato, se n tem k algarismos binários, então o tamanho da entrada é k, isto
é, n = O(2k). Por esse método realizaríamos O(
√
n) = O(2k/2) divisões, ou seja, o algoritmo
tem tempo exponencial com respeito ao tamanho da entrada.
Podemos usar vários teoremas de Teoria dos Números para testar a não primalidade
de um número inteiro positivo grande. Atualmente, a melhor ideia é a de usar o Pequeno
Teorema de Fermat.
Teorema 0.0.1 (Pequeno Teorema de Fermat). Para todo p primo e a ∈ Z temos ap ≡ a (mod p).
Esse mesmo teorema pode ser reescrito da seguinte forma:
Teorema 0.0.2. Seja n um inteiro positivo. Se existe a inteiro tal que n não divide an − a então n
não é primo.
Esta segunda versão do teorema de Fermat apresenta um método para mostrar que um
dado n não é primo. O número a é dito testemunha da não primalidade de n.
Exemplo 0.0.1. O número n = 227 + 1 não é primo, pois:
3n ≡ 1425349925083243041548732252780780755616976 6≡ 3 (mod n),
assim 3 é uma testemunha da não primalidade de n.
Ressaltamos que para calcular a potência anterior módulo n não precisamos multiplicar
a×a×· · ·×a, n vezes (o que dariaO(n) operações). Existe um algoritmo linear com respeito
ao tamanho da entrada, isto é, fixando 1 < a < n, para o cálculo de an (mod n) pode-
mos fazer no máximo 4 log2 n operações. No exemplo anterior, a quantidade de operações é
menor que 1000. De fato, começando do 1, podemos multiplicar por a, elevar ao quadrado,
(possivelmente) tomar o resto da divisão por n, (possivelmente) multiplicar por a e nova-
mente tomar o resto da divisão por n. Dessa forma, o número de operações é no máximo 4
vezes o número de dígitos binários de n.
Definição 0.0.1. Dizemos que n composto é um pseudoprimo na base a > 1 se an−1 ≡ 1 (mod n).
Exemplo 0.0.2. O menor pseudoprimo na base 2 é 341 = 11 × 31. De fato, temos 210 ≡ 1
(mod 11) =⇒ 2340 ≡ 1 (mod 11) e 25 ≡ 1 (mod 31) =⇒ 2340 ≡ 1 (mod 31). Comomdc(11, 31) =
1 segue que 2340 ≡ 1 (mod 341).
x
Fixado a > 1, existem infinitos pseudoprimos na base a. De fato, não é difícil mostrar
que se p é primo ímpar tal que p não divide a2 − 1 então:
n =
a2p − 1
a2 − 1 =
ap − 1
a− 1
ap + 1
a+ 1
é um pseudoprimo na base a.
A noção de pseudoprimo pode ser otimizada da seguinte forma: seja n − 1 = 2kb, com
b ímpar. Observemos, pelo Pequeno Teorema de Fermat, que se n é primo ímpar então
(ab)2
k ≡ 1 (mod n), logo deve existir um menor j tal que (ab)2j ≡ 1 (mod n). No caso que
j ≥ 1 e n é primo temos, pela minimalidade de j, que (ab)2j−1 ≡ −1 (mod n). A partir da
observação anterior, dizemos que n é pseudoprimo forte na base a se ab ≡ 1 (mod n) ou se
existe m < k tal que (ab)2m ≡ −1 (mod n). É claro que todo pseudoprimo forte na base a é
um pseudoprimo na base a.
Fixado a > 1, foi provado por Pomerance que existem infinitos pseudoprimos fortes
na base a. Especificamente, ele provou que o número de pseudoprimos fortes na base a
menores ou iguais a x é maior ou igual a e(log x)5/14 para todo x suficientemente grande.
Definimos α(n) como a probabilidade de, ao escolher um número arbitrário a menor que
n com mdc(a, n) = 1, n ser pseudoprimo forte na base a, isto é:
α(n) :=
1
ϕ(n)
#{a ∈ N; 0 < a < n, n é pseudoprimo forte na base a}.
O valor dessa probabilidade pode ser limitado superiormente, como enunciamos a seguir:
Teorema 0.0.3. Para todo número composto ímpar n > 9 temos α(n) ≤ 1/4.
A demonstração do teorema acima pode ser encontrada em [8] e a igualdade ocorre se e
somente se n é de alguma das formas:n = p1p2; pi’s primos, p1 ≡ 3 (mod 4), p2 = 2p1 − 1 oun = p1p2p3; pi’s primos, pi ≡ 3 (mod 4), e pi − 1 divide n− 1 para todo i = 1, 2, 3.
Uma ideia natural é testar vários valores de a, pois ao testarmos t bases distintas e primas
entre si, a probabilidade de n não ser primo, mas ser pseudoprimo forte em cada uma dessas
bases (assumindo que os eventos são independentes) é menor ou igual a 1/4t. O teste de não-
primalidade (ou teste de primalidade probabilístico) de Miller-Rabin é baseado nessa ideia
natural.
Por outro lado, existem números compostos que validam o teorema de Fermat para toda
base. Esses números são o ponto central desse trabalho.
Definição 0.0.2. Um número composto n é dito número de Carmichael se an ≡ a (mod n) para
todo inteiro a, ou equivalentemente, se n é pseudoprimo na base a para todo a.
O teorema 0.0.3 nos mostra, além da eficiência do teste de Miller-Rabin, que não existem
"números de Carmichael fortes". De fato, para todo número composto ímpar n existe 0 <
xi
xii SUMÁRIO
a < n primo com n que não é pseudoprimo forte na base a. Miller mostrou em sua tese de
doutorado que se a Hipótese Estendida de Riemann for verdadeira então é suficiente testar
os O(log4+ε n) primeiros primos como bases no teste de Miller-Rabin para garantir que n é
primo.
O seguinte critério facilita verificar se um número é de Carmichael dada sua fatoração.
Teorema 0.0.4 (Critério de Korselt). Seja n um número composto. Temos que n é número de
Carmichael se e somente se n é livre de quadrados e p− 1 divide n− 1 para todo p primo dividindo n.
Demonstração. (=⇒): Suponhamos que existe p primo tal que p2 divide n. Como n é número
de Carmichael temos que an ≡ a (mod n) para todo a inteiro, logo an ≡ a (mod p2) para
todo a. Tomando a = p segue 0 ≡ pn ≡ p (mod p2), um absurdo. Logo, n é livre de quadra-
dos. Sejam p divisor primo de n e g uma raiz primitiva módulo p. Como mdc(g, p) = 1,
ordpg = p− 1 e gp−1 ≡ 1 (mod p) segue que p− 1 divide n− 1.
(⇐=): Seja n = p1p2 . . . pk. Temos api ≡ a (mod pi) para todos a, i, logo a(api−1 − 1) ≡ 0
(mod pi). Multiplicando ambos os lados por 1+a+a2 + · · ·+a(n−1)/(pi−1) segue a(an−1−1) =
an − a ≡ 0 (mod pi) para todos a, i. Portanto, an ≡ a (mod n), ou seja, n é número de
Carmichael.
Exemplo 0.0.3. Exemplos de números de Carmichael:
• O menor número de Carmichael é o 561. De fato, pelo critério acima basta notar que 561 =
3× 11× 17 é livre de quadrados, 2|560, 10|560 e 16|560.
• Os próximos números de Carmichael menores que 105 são 1.105, 1.729, 2.465, 2.821, 6.601,
8.911, 10.585, 15.841, 29.341, 41.041, 46.657, 52.633, 62.745, 63.973 e 75.361. Existem 8.241
números de Carmichael menores que 1012, 19.279 menores que 1013, 44.706 menores que 1014
e 105.212 menores que 1015.
• Em 1939, Chernick mostrou que se p = 6m+ 1, q = 12m+ 1 e r = 18m+ 1 são primos então
pqr é um número de Carmichael, mas não se sabe se existem infinitas triplas de primos dessa
forma.
Nesse texto, vamos provar que existem infinitos números de Carmichael, como foi feito
no artigo [1]. Com isso, existem infinitos números inteiros positivos que satisfazem o Pe-
queno Teorema de Fermat para toda base mas não são primos. Assim, o Pequeno Teorema
de Fermat pode muito bem indicar que alguns números não são primos, mas mesmo se
testarmos todas as possíveis bases podemos ficar em dúvida se o número é primo ou não.
A ideia da demonstração de que existem infinitos números de Carmichael é usar o critério
de Korselt. Vamos construir um inteiro L = q1q2 . . . qs que é produto de primos distintos, es-
colhidos de forma que qj − 1 possui somente fatores primos "pequenos (mas não muito)".
Consideramos um subconjunto P de números primos p < L tais que p−1 divide kL para al-
gum k inteiro positivo fixo primo com L (por exemplo, escolhemos P como primos da forma
dk + 1 onde d é um divisor de L). Esses primos serão vistos como elementos do grupo mul-
tiplicativo (Z/kLZ)∗. Se a quantidade de elementos de P for "grande", podemos escolher
um subconjunto {p1, p2, . . . , pr} desses primos tal que C := p1p2 . . . pr ≡ 1 (mod L). Além
disso, vale que pj ≡ 1 (mod k) para 1 ≤ j ≤ r e portanto C ≡ 1 (mod k). Como pj − 1
divide kL e kL divide C − 1 segue que C é número de Carmichael. Fixado L, vamos estimar
inferiormente a quantidade de números de Carmichael obtidos por esse processo.
Algumas perguntas naturais a serem respondidas ao longo do texto são: como construir
esses inteiros L? Quão pequenos devem ser os fatores primos dos qj − 1? Por que eles não
podem ser tão pequenos? Como escolher k? Como podemos garantir que existem muitos
primos da forma dk + 1? Como podemos garantir que existem alguns desses primos com
produto 1 (mod L)? Quantas subsequências com produto 1 (mod L) existem?
Tentamos ao máximo provar todos os resultados, mas infelizmente alguns teoremas
ficaram para trás, por fugirem do tema ou por serem bastante conhecidos. Nesses casos,
vamos enunciá-los e exibir uma referência para o leitor contemplar suas demonstrações. Em
todo o texto vamos usar principalmente o primeiro dos dois teoremas enunciados a seguir.
Eles dizem respeito ao comportamento assintótico das funções:
pi(x) := #{p primo; p ≤ x} e
pi(x; q, a) := #{p primo; p ≤ x e p ≡ a (mod q)},
e as ideias para suas demonstrações encontram-se no apêndice B.
Teorema 0.0.5 (dos Números Primos). Temos lim
x→∞
pi(x)
x/ log x
= 1.
Teorema 0.0.6 (Dirichlet). Sejam a, q ∈ Z∗+ com mdc(q, a) = 1. Temos lim
x→∞
pi(x; q, a)
pi(x)
=
1
ϕ(q)
.
A tese do teorema acima é válida em ocasiões mais gerais. De fato, se f : R+ → R+ é
uma função não decrescente então dizemos que vale a Propriedade dos Números Primos em
Progressão Aritmética com parâmetro f se dado ε > 0 existe x0 tal que para todo x ≥ x0 e a, d
inteiros positivos primos entre si com d ≤ f(x) então:∣∣∣∣pi(x; q, a)pi(x) − 1ϕ(q)
∣∣∣∣ < εϕ(q) .
Ao longo de todo o texto, vamos considerar p como um número primo e vamos denotar:
C(x) := #{n ≤ x;n é número de Carmichael}.
xiii
xiv SUMÁRIO
Capítulo 1
As estimativas assintóticas de Mertens
Existem inúmeras provas elementares da existência de infinitos números primos. Uma delas
consiste em mostrar que a soma dos inversos dos primos é divergente. Uma pergunta na-
tural é: qual é o comportamento assintótico dessa soma? Nesse capítulo, mostraremos uma
prova elementar devida a Mertens do comportamento assintótico da soma dos inversos dos
primos, que será amplamente usado ao longo do texto. Para isso, precisamos da 1a fórmula
de Mertens, que será usado apenas para mostrar a 2a fórmula. Introduziremos a constante
de Euler-Mascheroni e demonstraremos também a 3a fórmula.
1.1 A 1a fórmula de Mertens
Teorema 1.1.1 (1a fórmula de Mertens). Para todo x ≥ 2 temos
∑
p≤x
log p
p
= log x+O(1).
Antes de demonstrar isso, necessitamos de alguns lemas.
Lema 1.1.2. A maior potência de p dividindo n! é vp(n!) =
∑
k≥1
⌊
n
pk
⌋
.
Demonstração. Na fatoração de n! aparecem bn/pcmúltiplos de p. Desses, bn/p2c contribuem
com dois fatores p. Desses, bn/p3c contribuem com três fatores p, e assim por diante. É claro
que essa soma é finita, pois pk > n para todo k grande.
Lema 1.1.3. Para todo n ∈ N temos n
p
− 1 < vp(n!) < n
p
+
n
p(p− 1) .
Demonstração. Por um lado, temos:
n
p
− 1 <
⌊
n
p
⌋
≤
∑
k≥1
⌊
n
pk
⌋
= vp(n!).
Por outro lado, temos:
∑
k≥1
⌊
n
pk
⌋
<
n
p
+
∑
k≥2
n
pk
=
n
p
+
n
p
∑
k≥1
1
pk
=
n
p
+
n
p(p− 1) .
1
2 CAPÍTULO 1. AS ESTIMATIVAS ASSINTÓTICAS DE MERTENS
Lema 1.1.4. Para todo n ≥ 2 temos
∏
p≤n
p < 4n.
Demonstração. Vamos mostrar por indução sobre n. Para n = 1, 2, 3, 4 o lema é claramente
verdadeiro. Suponhamos que n > 2 é par. Temos que n não é primo. Logo:∏
p≤n
p =
∏
p≤n−1
p ≤ 4n−1 < 4n.
Assim, basta provar para n ímpar, digamos n = 2m+ 1. Como
(
2m+1
m
)
= (2m+1)!
m!(m+1)!
temos:
∏
m+1<p≤2m+1
p
∣∣∣∣(2m+ 1m
)
≤ 1
2
22m+1 = 4m,
pois os fatores p com m + 1 < p ≤ 2m + 1 estão no numerador do binomial e não são
cancelados com nenhum termo do denominador e a desigualdade segue do fato de que, na
expansão de (1 + 1)2m+1 pelo Binômio de Newton, aparecem
(
2m+1
m
)
e
(
2m+1
m+1
)
e esses termos
são iguais. Logo, por hipótese, temos:∏
p≤n
p =
∏
p≤m+1
p
∏
m+1<p≤2m+1
p ≤ 4m+14m = 4n.
É interessante ressaltar que esse lema pode ser melhorado. Denis Hanson mostrou que a
desigualdade anterior continua válida para todo n se a base 4 for trocada por 3. Existe ainda
outro resultado cotando superiormente o produto de primos. Dado ε > 0 a constante 3 pode
ainda ser trocada por e1+ε usando o Teorema dos Números Primos. Ganhamos por um lado
mas perdemos por outro: nesse caso o teorema pode não valer para todo n ∈ N e sim para
todo n grande. De fato, o Teorema dos Números Primos nos garante que existe n0(ε) tal que
n ≥ n0(ε) implica pi(n) < (1 + ε) nlogn . Assim, para n ≥ n0(ε) temos:∏
p≤n
p ≤ npi(n) < n(1+ε)n/ logn = e[(1+ε)n/ logn] logn = e(1+ε)n.
O próximo lema é uma versão fraca da aproximação de Stirling, que diz que:
n! =
(n
e
)n√
2pin
(
1 +O
(
1
n
))
.
Lema 1.1.5. Existe θn ∈ [0, 1] tal que log(n!) = n log n− n+ 1 + θn log n.
Demonstração. Usando a integral de Riemann-Stieltjes e integrando por partes temos:
n∑
i=1
log i−
∫ n
1
log tdt =
∫ n
1−
log tdbtc −
∫ n
1
log tdt = −
∫ n
1−
log td{t}
= [− log t{t}]n1 +
∫ n
1−
{t}d log t =
∫ n
1−
{t}d log t = θn(log n− log 1).
1.1. A 1a FÓRMULA DE MERTENS 3
Logo, log n! = n log n− n+ 1 + θn log n.
Alternativamente, poderíamos usar a aproximação de Stirling no lugar do lema acima
para demonstrar a 1a fórmula de Mertens.
Demonstração. (da 1a fórmula de Mertens) Seja n = bxc. Temos:
log n! =
∑
p≤n
vp(n!) log p,
logo, pelo lema 1.1.3, obtemos:
n
∑
p≤n
log p
p
−
∑
p≤n
log p < log n! < n
∑
p≤n
log p
p
+ n
∑
p≤n
log p
p(p− 1) . (1.1)
Usando os lemas 1.1.4 e 1.1.5 na primeira desigualdade acima segue que:
n
∑
p≤n
log p
p
− n log 4 < n log n− n+ (1 + log n) < n log n
∑
p≤x
log p
p
=
∑
p≤n
log p
p
< log n+ log 4 ≤ log x+ log 4.
Por outro lado, temos:
∑
p≤n
log p
p(p− 1) <
∑
m≥2
logm
m(m− 1) ≤
∑
r≥1
∑
2r−1<m≤2r
r log 2
m(m− 1)
=
∑
r≥1
∑
2r−1<m≤2r
(
r log 2
m− 1 −
r log 2
m
)
= log 2
∑
r≥1
( r
2r−1
− r
2r
)
= log 2
∑
r≥1
r
2r
= log 2
[(
1
2
+
1
4
+
1
8
+ . . .
)
+
(
1
4
+
1
8
+ . . .
)
+
(
1
8
+ . . .
)
+ . . .
]
= log 4.
Assim, da segunda desigualdade de (1.1), temos:
∑
p≤x
log p
p
> log n+
1
n
− (1 + log 4) ≥ log x− (1 + log 4)
uma vez que
log x− log n =
∫ x
n
1
t
dt ≤ 1
n
(x− n) ≤ 1
n
=⇒ log n+ 1
n
≥ log x.
4 CAPÍTULO 1. AS ESTIMATIVAS ASSINTÓTICAS DE MERTENS
1.2 A 2a fórmula de Mertens
Como veremos adiante, a segunda fórmula de Mertens determina o comportamento assin-
tótico da soma dos inversos dos primos. Para a prova dessa fórmula precisaremos da 1a
fórmula de Mertens e dos seguintes lemas:
Lema 1.2.1. A soma
∑
p
[
log
(
1
1− 1/p
)
− 1
p
]
é convergente.
Demonstração. Pela série de Taylor do logaritmo temos:
log
(
1
1− 1/p
)
− 1
p
= − log
(
1− 1
p
)
− 1
p
=
= −
(
−
∑
k≥1
1
kpk
)
− 1
p
=
∑
k≥2
1
kpk
<
∑
k≥2
1
2pk
=
1
2p(p− 1) ,
assim cada um dos termos é positivo e limitado por 1
2p(p−1) , portanto:
∑
p
[
log
(
1
1− 1/p
)
− 1
p
]
<
∑
p
1
2p(p− 1) <
∑
n≥2
1
2n(n− 1) =
1
2
,
isto é, o somatório é uma série crescente e limitada superiormente, logo é convergente.
Lema 1.2.2. Seja c0 =
∑
p
[
log
(
1
1− 1/p
)
− 1
p
]
. Para todo x ≥ 2 e algum θx ∈ (0, 1) temos:
∑
p≤x
1
p
= log
[
1∏
p≤x(1− 1/p)
]
− c0 + θx
2(x− 1) .
Demonstração. Definindo θx tal que satisfaça a equação anterior, basta mostrar que θx ∈ (0, 1).
Para isso notemos que:
0 < θx = 2(x− 1)
∑
p>x
[
log
(
1
1− 1/p
)
− 1
p
]
= 2(x− 1)
∑
p>x
∑
k≥2
1
kpk
< 2(x− 1)
∑
p>x
∑
k≥2
1
2pk
= (x− 1)
∑
p>x
1
p(p− 1) = (x− 1)
∑
p>x
(
1
p− 1 −
1
p
)
< (x− 1)
∑
n>x
(
1
n− 1 −
1
n
)
<
x− 1
N − 1 < 1, (1.2)
onde N = bxc+ 1.
Teorema 1.2.3 (2a fórmula de Mertens). Existe c1 ∈ R tal que se x ≥ 2 então:
∑
p≤x
1
p
= log log x+ c1 +O
(
1
log x
)
.
1.3. A CONSTANTE DE EULER-MASCHERONI E A 3a FÓRMULA DE MERTENS 5
Demonstração. Definimos R(t) :=
∑
p≤t
log p
p
− log t. Pela 1a fórmula de Mertens sabemos que
R(t) = O(1). Utilizando integral de Riemann-Stieltjes temos que:
∑
p≤x
1
p
=
∫ x
2−
1
log t
d
(∑
p≤t
log p
p
)
=
∫ x
2−
1
log t
d(R(t) + log t).
Fazendo u = 1
log t
⇒ du = − 1
t log2 t
dt, dv = dR(t)⇒ v = R(t) e integrando por partes:
∑
p≤x
1
p
=
∫ x
2
1
t log t
dt+
∫ x
2−
1
log t
dR(t) = [log log t]x2 +
[
R(t)
log t
]x
2−
+
∫ x
2−
R(t)
t log2 t
dt
= log log x− log log 2 + R(x)
log x
− R(2
−)
log 2
+
∫ x
2−
R(t)
t log2 t
dt.
Seja R := supt≥2− |R(t)|. Pela limitação da 1a fórmula temos:∣∣∣∣R(x)log x −
∫ ∞
x
R(t)
t log2 t
dt
∣∣∣∣ ≤ ∣∣∣∣ Rlog x
∣∣∣∣+ ∣∣∣∣∫ ∞
x
R
t log2 t
dt
∣∣∣∣ = 2Rlog x < 2(1 + log 4)log x .
Logo, o teorema segue com c1 = − log log 2 + 1 +
∫ ∞
2
R(t)
t log2 t
dt.
1.3 A constante de Euler-Mascheroni e a 3a fórmula de Mertens
Olhemos para a sequência an =
∑n
i=1 1/i− log n. Mostremos que {an} é convergente. Temos:
1
k + 1
≤
∫ k+1
k
1
t
dt = log(k + 1)− log k ≤ 1
k
para todo k ≥ 2. Assim, como log n = ∑nk=2[log k − log(k − 1)] para n ≥ 2 segue que:
|an| =
∣∣∣∣∣
n∑
k=2
1
k
− log n
∣∣∣∣∣ =
∣∣∣∣∣
n∑
k=2
(
1
k
−
∫ k
k−1
1
t
dt
)∣∣∣∣∣ ≤
n∑
k=2
(
1
k − 1 −
1
k
)
= 1− 1
n
< 1, (1.3)
logo an é soma de termos positivos e an < 1 para todo n, assim an converge. Definimos
γ = lim an. Essa constante γ é chamada constante de Euler-Mascheroni. Numericamente
podemos mostrar que γ = 0, 577215663 . . . . Concluímos também que para todo n temos:
n∑
k=1
1
k
≥ log n, (1.4)
logo a série harmônica (lado esquerdo acima com n→∞) diverge.
As constantes c0 e c1 definidas no lema 1.2.2 e na 2a fórmula de Mertens, respectivamente,
são unidas pelo seguinte teorema.
Teorema 1.3.1. Temos c0 + c1 = γ.
6 CAPÍTULO 1. AS ESTIMATIVAS ASSINTÓTICAS DE MERTENS
Antes de demonstrá-lo precisamos de algumas propriedades acerca da função Zeta.
Definição 1.3.1. Definimos a função Zeta de Riemann como a única extensão meromorfa de:
ζ(s) =
∑
n≥1
1
ns
(1.5)
para o plano complexo.
Notemos que se s = σ + iθ então essa soma faz sentido sempre que σ > 1, uma vez que:
|ζ(s)| =
∣∣∣∣∣∑
n≥1
1
ns
∣∣∣∣∣ ≤∑
n≥1
∣∣∣∣ 1ns
∣∣∣∣ = ∑
n≥1
1
nσ
<∞.
Teorema 1.3.2 (Euler). A função Zeta satisfaz:
ζ(s) =
∏
p
(
1− 1
ps
)−1
.
Sabemos que a soma definida em 1.5 só faz sentido se σ > 1. Integrando por partes a
integral de Riemann-Stieltjes obtemos:
∑
n≥1
1
ns
=
∫ ∞
1−
1
ts
dbtc = s
s− 1 − s
∫ ∞
1−
{t}
ts+1
dt
Como essa última integral converge sempre que σ > 0, obtemos a primeira parte da
nossa extensão:
ζ(s) =
s
s− 1 − s
∫ ∞
1−
{t}
ts+1
dt.
A expressão do lado direito acima tem um polo simples em s = 1, o que poderia ser
previsto antes, já que a série harmônica diverge (e então só faltaria obter a ordem desse
polo). Notemos também que ζ(1 + σ) = 1/σ +O(1) para σ > 0.
Demonstração. (do Teorema 1.3.1) Seja f : (0,∞)→ R dada por f(σ) = log ζ(1+σ)−
∑
p
p−1−σ.
Pela Fórmula de Euler temos:
f(σ) =
∑
p
[
log
(
1
1− p−1−σ
)
− p−1−σ
]
.
Pelas desigualdades em (1.2), cada termo da soma acima é menor que 1
2p(p−1) . Logo, f
converge uniformemente em σ ≥ 0, o que implica que 0 é um ponto de continuidade de f ,
ou seja, limσ→0 f(σ) = f(0) = c0.
1.3. A CONSTANTE DE EULER-MASCHERONI E A 3a FÓRMULA DE MERTENS 7
Por um lado, temos:
log ζ(1 + σ) = log(1/σ +O(1)) = log(1/σ) +O(σ) = − log(σ) +O(σ)
= − log(σ +O(σ2)) = − log[1− (1− σ +O(σ2))]
= − log(1− e−σ) +O(σ) =
∑
n≥1
e−σn
n
+O(σ) =
∫ ∞
0
e−σtdH(t) +O(σ),
onde H(t) :=
∑
1≤n≤t 1/n. Integrando por partes obtemos:
log ζ(1 + σ) = σ
∫ ∞
1
e−σtH(t)dt+O(σ).
Por outro lado, seja P (t) :=
∑
p≤u 1/p. Integrando por partes e fazendo u = e
t, temos:
∑
p
p−1−σ =
∫ ∞
1
u−σdP (u) = σ
∫ ∞
1
u−1−σP (u)du = σ
∫ ∞
0
e−σtP (et)dt.
Juntando as duas partes e a definição de f obtemos:
f(σ) = σ
∫ ∞
0
e−σt[H(t)− P (et)]dt+O(σ). (1.6)
Pelos lema 1.3 e 2a fórmula de Mertens sabemos que para todo t ≥ 1 vale:
H(t) = log t+ γ +O(1/t)
P (et) = log t+ c1 +O(1/t)
Assim, substituindo em (1.6) obtemos:
f(σ) = σ
∫ ∞
0
[
γ − c1 +O
(
1
t+ 1
)]
e−σtdt+O(σ)
= σ(γ − c1)
∫ ∞
0
e−σtdt+ σ
∫ ∞
0
e−σtO
(
1
t+ 1
)
dt+O(σ)
= γ − c1 +O
(
σ + σ
∫ ∞
0
e−σt
dt
t+ 1
)
= γ − c1 +O
(
σ log
(
1
σ
))
.
Portanto, fazendo σ → 0 obtemos c0 = f(0) = γ − c1.
8 CAPÍTULO 1. AS ESTIMATIVAS ASSINTÓTICAS DE MERTENS
Sabemos, pelo lema 1.2.2 e pela 2a fórmula de Mertens, que:
c0 = −
∑
p≤x
[
log
(
1− 1
p
)
+
1
p
]
+
∑
p>x
[
log
(
1
1− 1/p
)
− 1
p
]
= −
∑
p≤x
log
(
1− 1
p
)
− log log x− c1 +O
(
1
log x
)
+
∑
p>x
[
log
(
1
1− 1/p
)
− 1
p
]
=⇒ c0 + c1 + log log x+
∑
p≤x
log
(
1− 1
p
)
=
∑
p>x
[
log
(
1
1− 1/p
)
− 1
p
]
.
Pelas desigualdades em (1.2) temos
∑
p>x
[
log
(
1
1−1/p
)
− 1
p
]
< 1
2bxc . Tomando a exponen-
cial de ambos lados e usando a série de Taylor temos:
ec0+c1 log x
∏
p≤x
(
1− 1
p
)
= exp
{∑
p>x
[
log
(
1
1− 1/p
)
− 1
p
]
+O
(
1
log x
)}
= exp
[
O
(
1
log x
)]
= 1 +O
(
1
log x
)
.
Portanto, pelo teorema anterior obtemos para x ≥ 2 que:
∏
p≤x
(
1− 1
p
)
=
e−γ
log x
{
1 +O
(
1
log x
)}
.
A equação acima é a chamada Terceira Fórmula de Mertens. Ao longo do texto, usaremos
apenas a segunda fórmula, que fornece uma relação assintótica da soma dos inversos dos
primos.
Capítulo 2
Resultados algébricos
2.1 Caráteres
Definição 2.1.1. Dado um corpo K e um grupo abeliano finito G definimos um caráter como um
homomorfismo χ : G→ K∗. Indicaremos por χ1 o caráter trivial (χ1 = 1 ∀x ∈ G).
No caso em que K = C temos que a imagem de cada caráter está contida em S1 pois as
imagens são raízes da unidade. Denotaremos por Ĝ = ĜK o conjunto de caráteres de G com
respeito ao corpo K. Quando não restar dúvida sobre quem é K vamos omitir tal índice.
Lema 2.1.1. Se |G| = n e χ é caráter de G então:
∑
x∈G
χ(x) =
n, se χ = χ1,0, caso contrário. (2.1)
Demonstração. Se χ = χ1 então o lema é óbvio. Caso exista y ∈ G com χ(y) 6= 1 obtemos:
χ(y)
∑
x∈G
χ(x) =
∑
x∈G
χ(xy) =
∑
x∈G
χ(x) =⇒
∑
x∈G
χ(x) = 0.
Se χ e χ′ são caráteres de G então podemos definir o produto
(χ.χ′)(x) = χ(x).χ′(x),
e isso fornece uma estrutura de grupo abeliano ao conjunto Ĝ := {χ;χ é caráter de G}.
Lema 2.1.2. Seja K um corpo que contém uma raiz |G|-ésima da unidade. Então o grupo Ĝ é finito
e da mesma ordem de G.
Demonstração. Se G é cíclico de ordem g, digamos que G = (σ), então para todo χ ∈ Ĝ temos
[χ(σ)]g = χ(σg) = 1, ou seja, χ(g) é raiz g-ésima da unidade. Por outro lado, se w ∈ K com
wg = 1 temos que a aplicação gn → wn é um caráter. Concluímos daí que |Ĝ| = g.
9
10 CAPÍTULO 2. RESULTADOS ALGÉBRICOS
Se G não é cíclico o teorema da representação de grupos abelianos finitos diz que G '
G1 ⊕ G2 ⊕ · · · ⊕ Gn, onde cada Gi é cíclico de ordem gi e gerador σi. Para aplicar o que
concluímos no caso cíclico devemos mostrar que Ĝ ' Ĝ1 ⊕ Ĝ2 ⊕ · · · ⊕ Ĝn. Basta provar que
Ĝ1 ⊕G2 ' Ĝ1 ⊕ Ĝ2 (G1 e G2 não necessariamente cíclicos). O resto segue por indução.
Se χi é caráter de Gi, i = 1, 2 então (x1, x2) → χ1(x1)χ2(x2) é um caráter de G1 ⊕ G2,
onde xi ∈ Gi, i = 1, 2. Por outro lado, se χ é caráter de G1 ⊕ G2 então x1 → χ(x1, e2)
é caráter de G1 e x2 → χ(e1, x2) é caráter de G2, onde ei ∈ Gi é a identidade do grupo
Gi, i = 1, 2. Como os mapas do tipo (x1, x2) → χ1(x1)χ2(x2) são inversos aos mapas do tipo
x1 → χ(x1, e2);x2 → χ(e1, x2), segue-se o resultado.
Definição 2.1.2. Dado um grupo G, definimos o expoente de G como o mínimo inteiro positivo t
tal que gt = 1 para todo g ∈ G.
Exemplo 2.1.1. No grupoG = (Z4×Z8,+) com 32 elementos, o expoente é 8. É fácil mostrar que no
grupo G = (Zn1 ×Zn2 ×· · ·×Znk ,+) com n1n2 . . . nk elementos, o expoente é mmc(n1, n2, . . . , nk)
pois o expoente tem que ser múltiplo de nj para todo j (já que (0, . . . , 0, 1, 0, . . . , 0) com 1 na j-ésima
posição tem ordem nj) e tem que ser o mínimo.
Lema 2.1.3. Se |G| = n, K contém uma raiz m-ésima primitiva da unidade onde m é o expoente de
G então para todo x ∈ G temos:
∑
χ∈Ĝ
χ(x) =
n, se x = eG0, caso contrário. (2.2)
Demonstração. A aplicação x : Ĝ → K∗, χ 7→ χ(x) define um caráter de Ĝ, isto é, um ele-
mento de ̂̂G. Esse lema segue, portanto, dos dois lemas anteriores.
As equações (2.1) e (2.2) são chamadas de "Relações de Ortogonalidade".
Dado um grupo G e Fq um corpo com q elementos definimos a álgebra de grupos Fq[G]
como o conjunto de somas formais finitas da forma:∑
g∈G
agg.
Dotamos esse conjunto com duas operações +, · definidas por:∑
g∈G
agg +
∑
g∈G
bgg :=
∑
g∈G
(ag + bg)g(∑
g∈G
agg
)
·
(∑
g∈G
bgg
)
:=
∑
g∈G
cgg, onde cg :=
∑
h1,h2∈G
h1h2=g
ah1bh2 .
Com essas operações, Fq[G] é uma Fq-álgebra com base G. Em geral, omitiremos o sinal
de multiplicação.
2.1. CARÁTERES 11
Dado um caráter χ : G→ F∗q , definimos χ : Fq[G]→ Fq[F∗q] ∼ Fq estendendo linearmente:
χ
(∑
g∈G
agg
)
:=
∑
g∈G
agχ(g) ∈ Fq,
assim χ é uma transformação linear. De fato, χ é um homomorfismo de Fq-álgebras pois:
χ
((∑
g∈G
agg
)(∑
g∈G
bgg
))
= χ
(∑
g∈G
cgg
)
=
∑
g∈G
cgχ(g) =
∑
g∈G
∑
h1,h2∈G
h1h2=g
ah1bh2χ(h1h2)
=
∑
h1∈G
∑
h2∈G
ah1χ(h1)bh2χ(h2) = χ
(∑
h1∈G
ah1h1
)
χ
(∑
h2∈G
bh2h2
)
.
Lema 2.1.4. Sejam Fq um corpo com q elementos e G um grupo abeliano com m elementos, tal que
q ≡ 1 (mod m). Seja b ∈ Fq[G]. Então b = 0 se e somente se χ(b) = 0 para todo caráter χ ∈ Ĝ.
Demonstração. Como q ≡ 1 (mod m) então Fq possui uma raizm-ésima primitiva da unidade.
Sejam b =
∑
g∈G ag.g e h ∈ G. Pelas relações de ortogonalidade segue que:
∑
χ∈Ĝ
χ(h−1b) =
∑
χ∈Ĝ
χ
(∑
g∈G
agh
−1g
)
=
∑
g∈G
ag
∑
χ∈Ĝ
χ(h−1g)
 = ah|G|.
Logo, b = 0 se e somente se ah = 0 para todo h ∈ G.
Seja q ≥ 1 um inteiro. Vejamos o caso em que G = (Z/qZ)∗ (ou seja, G é o grupo dos
elementos inversíveis módulo q). Denotamos ̂(Z/qZ)∗ como o grupo de caráteres módulo q.
Além disso, podemos estender a definição de caráter para uma função χ˜ : Z → C de forma
que se χ ∈ ̂(Z/qZ)∗ então:
χ˜(n) =
χ(n(mod q)), se mdc(n, q) = 10, caso contrário.
Ao longo do texto vamos nos referir aos caráteres módulo q como sendo essas extensões,
que também são chamadas de Caráteres de Dirichlet.
As relações de ortogonalidade implicam facilmente que:
ϕ(q)−1
∑
χ
χ(n)χ(m) =
1, se n ≡ m (mod q), 1 ≤ m ≤ q,mdc(n, q) = 10, se mdc(n, q) > 1 (2.3)
e se χ, χ′ ∈ Ĝ então:
ϕ(q)−1
∑
1≤n≤q
χ(n)χ′(n) =
1, se χ = χ10, caso contrário. (2.4)
12 CAPÍTULO 2. RESULTADOS ALGÉBRICOS
2.2 A função de Carmichael
Vejamos o que acontece com o expoente do grupo G = Z∗n ' Z∗pα11 × Z
∗
p
α2
2
× · · · × Z∗
p
αk
k
onde
n = pα11 p
α2
2 . . . p
αk
k . Para isso, vamos definir a função λ de Carmichael.
Definição 2.2.1. Definimos a função λ(n) de Carmichael como o expoente do grupo Z∗n. Em outras
palavras, λ(n) := min{k ∈ N; ak ≡ 1 (mod n) ∀a;mdc(a, n) = 1}.
Observemos que λ(n) está definido para todo n pois se a e n são primos entre si então
aϕ(n) ≡ 1 (mod n). Se ordna denota a ordem de a módulo n então temos que ordna divide
λ(n) para todo a com mdc(a, n) = 1. Logo, λ(n) é um múltiplo de mmc({ordna;mdc(a, n) =
1}) e pela minimalidade de λ temos que:
λ(n) = mmc({ordna;mdc(a, n) = 1}).
Por outro lado, ϕ(n) é múltiplo de ordna para todo a primo com n, logo λ(n) divide ϕ(n).
Teorema 2.2.1. Sejam p um primo ímpar e k um inteiro positivo. Os únicos números que possuem
raiz primitiva são 2, 4, pk e 2pk.
Demonstração. A demonstração pode ser encontrada em [8].
Vamos agora obter um algoritmo para calcular λ(n) para todo n.
Teorema 2.2.2. Se mdc(m,n) = 1 então λ(mn) = mmc(λ(m), λ(n)).
Demonstração. Notemos primeiramente que se a, m e n são dois a dois primos entre si
então ammc(λ(m),λ(n)) ≡ 1 (mod m) e ammc(λ(m),λ(n)) ≡ 1 (mod n), pois λ(m), λ(n) dividem
mmc(λ(m), λ(n)), logo ammc(λ(m),λ(n)) ≡ 1 (mod mn) e portanto λ(mn) dividemmc(λ(m), λ(n)).
Por outro lado, existem a1 e a2 tais que ordma1 = λ(m) e ordna2 = λ(n). Pelo Teo-
rema Chinês do Resto existe a inteiro tal que a ≡ a1 (mod m) e a ≡ a2 (mod n) o que
implica ordma = λ(m) e ordna = λ(n), logo ammc(λ(m),λ(n)) ≡ 1 (mod mn). Assim, segue que
mmc(λ(m), λ(n)) divide λ(mn).
Dessa forma fica provado que λ(mn) = mmc(λ(m), λ(n)).
Sendo assim, basta calcular a função nas potências de primo. De fato, no caso de n =
2, 4 ou pα (onde p é primo ímpar e α ∈ N) então de acordo como teorema 2.2.1 existe raiz
primitiva módulo n, logo existe g ∈ Zn tal que Z∗n = (g) e portanto λ(n) = ϕ(n). Portanto, só
faltam as potências de 2 a partir de 23. Provaremos o seguinte:
Teorema 2.2.3. Seja α ≥ 3 um inteiro. Temos λ(2α) = 2α−2.
Demonstração. Indutivamente, para α = 3 e n ímpar (de modo que mdc(n, 2) = 1), digamos,
n = 2k + 1, temos n2 = 4k(k + 1) + 1 ≡ 1 (mod 23) pois k(k + 1) é par. Suponhamos que
n2
α−2 ≡ 1 (mod 2α) para todo n ímpar e para algum α ≥ 3. Temos duas opções:
n2
α−2 ≡ 1 (mod 2α+1) ou n2α−2 ≡ 1 + 2α (mod 2α+1).
2.3. SUBSEQUÊNCIAS COM PRODUTO 1 13
Elevando ambas as opções ao quadrado segue que n2α−1 ≡ 1 (mod 2α+1), portanto λ(2α+1)
divide 2α−1.
Seja agora n ≡ 3 (mod 23). Temos ord23(n) = 2 e ord24(n) = 4. Novamente por indução,
suponha que ord2α(n) = 2α−2 e ord2α+1(n) = 2α−1 para algum α ≥ 3. Então, n2α−2 ≡ 1
(mod 2α) mas n2α−2 6≡ 1 (mod 2α+1), o que implica n2α−2 ≡ 1 + 2α (mod 2α+1). Temos duas
opções:
n2
α−2 ≡ 1 + 2α (mod 2α+2) ou n2α−2 ≡ 1 + 2α + 2α+1 (mod 2α+2).
Elevando ambas as opções ao quadrado segue que n2α−1 ≡ 1 + 2α+1 6≡ 1 (mod 2α+2).
Portanto, ord2α+2(n) > 2α−1. Logo, só podemos ter ord2α+2(n) = 2α ou ord2α+2(n) = 2α+1,
uma vez que ord2α+2(n) divide ϕ(2α+2) = 2α+1. Mas sabemos que ord2α+2(n) ≤ λ(2α+2) ≤ 2α,
assim só podemos ter λ(2α+2) = 2α.
Dessa forma, a função λ fica completamente determinada e será usada no teorema 4.3.1.
2.3 Subsequências com produto 1
Observemos que para toda sequência de elementos de um grupoG de comprimento |G|+1 é
possível escolher uma subsequência cujo produto é 1, pois dada a sequência g1, g2, . . . , g|G|+1
e definindo hj = g1g2 . . . gj com j = 1, 2, . . . , |G|+ 1 obtemos uma lista com |G|+ 1 elementos
de G. Logo, existem j1 < j2 tais que hj1 = hj2 e portanto gj1+1gj1+2 . . . gj2 = hj2h
−1
j1
= 1.
Assim, uma pergunta natural é: qual é o máximo valor de n ∈ N tal que existe uma sequência
de n elementos de G que não possui subsequência não vazia com produto 1?
Definição 2.3.1. Dado um grupo G definimos sua constante de Davenport, n(G), como o com-
primento da maior sequência de elementos de G (não necessariamente distintos) tal que nenhuma
subsequência não-vazia tem o produto dos termos igual a 1.
Pelo que demonstramos acima, a constante de Davenport de qualquer grupo existe e vale
no máximo a ordem do grupo. Dado um grupo G, em geral não sabemos determinar sua
constante de Davenport, mas o seguinte teorema limita n(G) em função do seu expoente se
G é um grupo abeliano finito.
Teorema 2.3.1 (van Emde Boas & Kruyswijk). Se G é um grupo abeliano finito e m é o expoente
de G então:
n(G) < m
(
1 + log
|G|
m
)
.
Demonstração. Sejam g1, g2, . . . , gn ∈ G uma sequência que não possui subsequências com
produto 1 e suponha por absurdo que n ≥ m
(
1 + log |G|
m
)
. Escolha um número primo q tal
que q ≡ 1 (mod m). Consideremos o elemento da álgebra de grupo Fq[G]:
(a1 − g1)(a2 − g2) . . . (an − gn) =
∑
g∈G
kgg.
14 CAPÍTULO 2. RESULTADOS ALGÉBRICOS
Como nenhuma subsequência de g1, g2, . . . , gn tem produto 1 segue que k1 = a1a2 . . . an.
Observemos que basta encontrar a1, . . . , an ∈ F∗q tais que
n∏
i=1
(ai − gi) = 0 (2.5)
pois isso implica que k1 = 0, o que gera um absurdo e logo existirá uma subsequência com
produto 1.
Pelo lema 2.1.4, qualquer caráter χ : G → F∗q em Ĝ pode ser extendido a um homomor-
fismo de aneis χ : Fq[G]→ Fq. Como:
χ
(
n∏
i=1
(ai − gi)
)
=
n∏
i=1
(ai − χ(gi))
vemos que (2.5) vale se existe j ∈ {1, 2, . . . , n} tal que χ(gj) = aj . Assim, o problema é
equivalente a mostrar que é possível escolher a1, a2, . . . , an ∈ F∗q tal que para todo caráter χ
existe j tal que χ(gj) = aj . A estratégia para a escolha dos aj é a seguinte: escolhemos a1
tal que χ(g1) = a1 vale para o máximo possível de χ ∈ Ĝ. Do restante, escolhemos a2 da
mesma forma, e assim sucessivamente. Cada χ(gi) é raiz m-ésima da unidade em F∗q , então
temos m valores diferentes para χ(gi). Se S é qualquer subconjunto de Ĝ e g ∈ G então
existe algum a ∈ F∗q tal que χ(g) = a é verdadeiro para pelo menos |S|/m caráteres X ∈ S.
Logo, χ(g) 6= a vale para no máximo |S|(1− 1/m) caráteres χ ∈ S. Aplicando esse algoritmo
para g1, g2, . . . , gk podemos escolher a1, . . . , ak ∈ F∗q tais que o resto dos caráteres χ ∈ Ĝ com
χ(gj) 6= aj para todo j = 1, 2, 3, . . . , k estão em quantidade máxima de:
|Ĝ|
(
1− 1
m
)k
= |G|
(
1− 1
m
)k
< |G|e−k/m.
Escolhemos k como o menor inteiro tal que |G|.e−k/m < m, isto é, k = bm log (|G|/m)c+1.
Sejam χ1, χ2, . . . , χr os únicos caráteres tais que χi(gj) 6= aj para todo j = 1, 2, . . . , k e gj ∈ G.
Como r ≤ m− 1 e por hipótese sabemos que n ≥ m
(
1 + log |G|
m
)
, segue que n ≥ m+ k− 1 ≥
k + r. Portanto, definindo χj(gk+j) = ak+j para todo j com 1 ≤ k ≤ r teremos que:
χ
(
n∏
i=1
(ai − gi)
)
= 0 ∀χ ∈ Ĝ,
o que é contraditório. Logo, n < m
(
1 + log
|G|
m
)
.
Teorema 2.3.2. Sejam G um grupo abeliano finito, r > t > n = n(G) inteiros positivos. Qualquer
sequência de r elementos em G contém ao menos
(
r
t
)
/
(
r
n
)
sequências distintas de comprimento entre
t− n e t cujo produto é a identidade.
Demonstração. Seja R uma sequência de r elementos em G. Pelo teorema 2.3.1 existe subse-
quência em R com produto 1. Seja S ⊂ R a maior dessas subsequências, com |S| = s. Caso
2.3. SUBSEQUÊNCIAS COM PRODUTO 1 15
n < r − s teríamos que no conjunto R − S existiria uma subsequência com produto 1 que
pode ser adicionada a S, o que contradiz a maximalidade de S. Assim, n ≥ r − s. Seja T
qualquer subsequência de S, com |T | = t− n. Se:∏
x∈T
x = g
então: ∏
x∈S−T
x = g−1.
Seja U a menor subsequência de S − T com produto g−1 (possivelmente, U = ∅). Temos
|U | ≤ n (caso contrário poderíamos retirar uma subsequência de U com produto 1).
Seja V a subsequência obtida da sequência original contendo os elementos de U e T .
Observemos que: ∏
x∈V
x =
(∏
x∈U
x
)(∏
x∈T
x
)
= gg−1 = 1
e t − n = |U | ≤ |U | + |T | = |V | ≤ t. Portanto, B é uma subsequência cujo produto é a
identidade e de comprimento entre t− n e t. Basta então contar a quantidade de sequências
distintas.
Notemos também que para cada escolha da subsequência T obtemos uma subsequência
V , mas sequências T ’s distintas podem gerar a mesma sequência V . O número de escolhas
de subsequências T é ao menos
(
s
t−n
) ≥ (r−n
t−n
)
e o número de repetições é no máximo
( |V |
t−n
) ≤(
t
t−n
)
=
(
t
n
)
, logo o número de V ’s distintos é maior ou igual a:(
s
t− n
)
(
t
n
) ≥
(
r − n
t− n
)
(
t
n
) =
(
r
t
)
(
r
n
) .
16 CAPÍTULO 2. RESULTADOS ALGÉBRICOS
Capítulo 3
O Grande Crivo e a desigualdade de
Brun-Titchmarsh
Todo esse capítulo é dedicado à demonstração da desigualdade de Brun-Titchmarsh, que
será usada nas demonstrações de alguns teoremas no capítulo 4. Por ser bastante profundo,
necessitamos de uma ferramenta pesada para a sua demonstração: o Teorema do Grande
Crivo. Para a prova do Teorema do Grande Crivo necessitamos da Teoria de Fourier, que se
encontra no Apêndice A.
3.1 O Grande Crivo
Sejam {an}, an ∈ C uma sequência e M,N ∈ Z e N > 0. Definimos a soma:
S(α) :=
∑
M<n≤M+N
ane
2piiαn. (3.1)
Além disso, definimos ‖u‖ = min{u − buc, buc + 1 − u} (ou seja, ‖u‖ é a distância de u
para o inteiro mais próximo).
Seja α1, α2, . . . , αR uma sequência finita de números reais. Dizemos que tal sequência é
δ-espaçada se ‖αi − αj‖ ≥ δ para todo i, j ∈ {1, 2, . . . , R}, i 6= j.
Teorema 3.1.1 (do Grande Crivo). Sejam α1, α2, . . . , αR uma sequência δ-espaçada e S a função
definida pela equação (3.1). Então existe ∆(N, δ) > 0 tal que:
R∑
j=1
|S(αj)|2 ≤ ∆(N, δ)
∑
M<n≤M+N
|an|2.
Nos anos 60 e 70 foram feitas inúmeras tentativas para calcular o valor ótimo para ∆(N, δ).
Finalmente, tal valor foi encontrado em 1973 por Montgomery e Vaughan.
Teorema 3.1.2 (Montgomery-Vaughan). ∆(N, δ) ≤ N − 1 + δ−1.
É fácil comprovar que a cota dada por Mongomery-Vaughan é a melhor, pois tomando
αj = j/R temos δ = 1/R. Tomando também:
17
18 CAPÍTULO 3. O GRANDE CRIVO E A DESIGUALDADE DE BRUN-TITCHMARSH
an =
1, se R|n0, caso contrário,
segue para M = −1 e N ≡ 1 (mod R) que S(αj) = #{múltiplos de R em [0, N − 1]}. Logo:
R∑
j=1
|S(αj)|2 =
(⌊
N − 1
R
+ 1
⌋)2
R =
(N − 1 +R)2
R
.
Por outro lado,
∑
0≤n≤N−1
|an|2 = #{múltiplos de R em [0, N − 1]} = N − 1 +R
R
.
Logo, nesse caso ocorre a igualdade:
R∑
j=1
|S(αj)|2 = (N − 1 +R)
2
R
= ∆(N, δ)
∑
M<n≤M+N
|an|2.
Ao invés de demonstrar o Grande Crivo com a cota de Montgomery-Vaughan, provare-
mos um resultado mais fraco, mas que será suficiente para demonstrar uma versão mais
simples da desigualdade de Brun-Titchmarsh. De fato, vamos mostrar que:
R∑
j=1
|S(αj)|2 ≤ pi
2
2
(N − 1 + δ−1)
∑
M<n≤M+N
|an|2.
Os seguintes lemas sobre sequências nos permitirão demonstrar a desigualdade acima.
Lema 3.1.3. Sejam D um real positivo e [cn,r] uma matriz complexa N ×R. São equivalentes:
A)
∑
r
∣∣∣∣∣∑
n
cn,rxn
∣∣∣∣∣
2
≤ D
∑
n
|xn|2, para todo xn ∈ C.
B)
∣∣∣∣∣∑
n,r
cn,ryrxn
∣∣∣∣∣
2
≤ D
∑
n
|xn|2
∑
r
|yr|2, para todo xn, yr ∈ C.
C)
∑
n
∣∣∣∣∣∑
r
cn,ryr
∣∣∣∣∣
2
≤ D
∑
r
|yr|2, para todo yr ∈ C.
Demonstração. (A⇒ B) Por Cauchy-Schwarz e por hipótese, temos:∣∣∣∣∣∑
n,r
cn,ryrxn
∣∣∣∣∣
2
=
∣∣∣∣∣∑
r
yr
∑
n
cn,rxn
∣∣∣∣∣
2
≤
∑
r
|yr|2
∑
r
∣∣∣∣∣∑
n
cn,rxn
∣∣∣∣∣
2
≤ D
∑
r
|yr|2
∑
n
|xn|2.
(B⇒ A) Sejam Lr :=
∑
n
cn,rxn e yr = Lr. Temos por hipótese:
∣∣∣∣∣∑
r
|Lr|2
∣∣∣∣∣
2
=
∣∣∣∣∣∑
r
∑
n
cn,rxn
∑
m
cm,rxm
∣∣∣∣∣
2
=
∣∣∣∣∣∑
n,r
cn,ryrxn
∣∣∣∣∣
2
≤ D
∑
n
|xn|2
∑
r
|Lr|2
3.1. O GRANDE CRIVO 19
=⇒
∑
r
∣∣∣∣∣∑
n
cn,rxn
∣∣∣∣∣
2
=
∑
r
|Lr|2 ≤ D
∑
n
|xn|2.
A equivalência entre B e C é completamente análoga.
O que realmente precisamos do lema acima é a equivalência entre A e C, que usaremos
no lema a seguir. O item B foi usado apenas como intermediador entre A e C.
Lema 3.1.4. Sejam α1, α2, . . . , αR números reais fixos, M e N inteiros positivos e S(α) a função
definida pela equação (3.1). Se são dados B > 0 constante e {bi}i∈Z com bi ≥ 0 e bi > 0 para
M < i ≤M +N então são equivalentes:
I)
∑
1≤r≤R
|S(αr)|2 ≤ B
∑
M<n≤M+N
|an|2
bn
para todo an ∈ C.
II)
∑
M<n≤M+N
bn
∣∣∣∣∣ ∑
1≤r≤R
yre
2piinαr
∣∣∣∣∣
2
≤ B
∑
1≤r≤R
|yr|2 para todo yr ∈ C.
Demonstração. Sejam xn =
an√
bn
e cn,r = e2piiαrn
√
bn. Pelos itens A e C do lema anterior temos:
∑
1≤r≤R
∣∣∣∣∣ ∑
M<n≤M+N
ane
2piiαrn
∣∣∣∣∣
2
≤ B
∑
M<n≤M+N
|an|2
bn
se e somente se: ∑
M<n≤M+N
∣∣∣∣∣ ∑
1≤r≤R
yre
2piiαrn
√
bn
∣∣∣∣∣
2
≤ B
∑
1≤r≤R
|yr|2.
Corolário 3.1.5. Seja B(α) :=
∑
n∈Z
bne
2piiαn uma série de Fourier convergente, com bn ≥ 0 e bn > 0
para M < n ≤M +N . Se: ∑
1≤r,s≤R
yrysB(αr − αs) ≤ B
∑
1≤r≤R
|yr|2 (3.2)
para algum B > 0 e yr ∈ C com 1 ≤ r ≤ R arbitrários então
∑
1≤r≤R
|S(αr)|2 ≤ B
∑
M<n≤M+N
|an|2
bn
para todo an ∈ C.
Demonstração. Substituindo B(αr − αs) na hipótese, temos:
∑
1≤r,s≤R
yrysB(αr − αs) =
∑
n∈Z
bn
∑
1≤r,s≤R
yryse
2piiαrne2piiαsn =
∑
n∈Z
bn
∣∣∣∣∣∑
r
yre
2piiαrn
∣∣∣∣∣
2
,
logo pela equivalência do lema anterior o corolário segue.
20 CAPÍTULO 3. O GRANDE CRIVO E A DESIGUALDADE DE BRUN-TITCHMARSH
Observemos que se escolhermos a sequência bn no corolário anterior de tal forma que:
bn ≥ 0, se n ∈ Z
bn ≥ 1, se M < n ≤M +N
B(α) = 0, se ‖α‖ ≥ δ
(3.3)
então a validade da desigualdade (3.2) para algum B > 0 implica que:
∑
1≤r≤R
|S(αr)|2 ≤ B
∑
M<n≤M+N
|an|2
bn
≤ B
∑
M<n≤M+N
|an|2,
que corresponde exatamente à desigualdade do Grande Crivo. Nesse ponto, basta escolher
{bn} cumprindo (3.3) e B adequados tais que a desigualdade (3.2) é válida e depois verificar
a dependência de B com a sequência {αr} e com N .
Podemos supor δ < 1/2, pois o caso δ = 1/2 é possível somente se R = 2, que é trivial.
Observemos que se {bn} é uma sequência satisfazendo (3.3) de tal forma que a série de
Fourier B(α) =
∑
n∈Z bne
2piiαn tem suporte contido em ‖α‖ ≤ δ então a desigualdade do
Grande Crivo é verdadeira tomando ∆(N, δ) = B(0). De fato, como os αi’s são δ-espaçados
segue que B(αr − αs) = 0 sempre que r 6= s. Assim, temos:∑
1≤r,s≤R
yrysB(αr − αs) =
∑
1≤r≤R
yryrB(0) = B(0)
∑
1≤r≤R
|yr|2.
Sejam {bn} os coeficientes de Fourier da função B(α). É natural tentar escrever bn como
o valor em n da função b ∈ L1(R), para os quais a transformada de Fourier:
b̂(θ) :=
∫ ∞
−∞
b(t)e−2piiθtdt
tem suporte contido em [−δ, δ]. Assim, o somatório de Poisson (teoremaA.3.1) garantirá que
B(α) = 0 sempre que ‖α‖ ≥ δ, pois:
B(α) :=
∑
n∈Z
b(n)e2piiαn =
∑
k∈Z
b̂(k − α). (3.4)
Para verificar se o somatório de Poisson é efetivamente aplicável, primeiramente vamos
observar que b̂ ∈ L1(R), pois b ∈ L1(R). Pelo teorema A.2.5, notando que B(α) = 0 quando
‖α‖ ≥ δ, temos:
b(t) =
∫
R
b̂(θ)e2piiθtdθ =
∫ δ
−δ
b̂(θ)e2piiθtdθ. (3.5)
Seja β(α) :=
∑
k∈Z b̂(k − α). Temos que os b(n)’s são os coeficientes de Fourier da função
periódica β. Assim, paraN ≥ 1 e |α| ≤ 1/2, da equação (3.5), fazendo a mudança de variável
3.1. O GRANDE CRIVO 21
θ → θ − α, obtemos que:
b(t)e2piiαt =
∫ δ+α
−δ+α
b̂(θ − α)e2piiθtdθ. (3.6)
Somando de −N a N a última equação, obtemos:
N∑
n=−N
b(n)e2piiαn =
N∑
n=−N
∫ δ+α
−δ+α
b̂(θ − α)e2piiθndθ =
∫ δ+α
−δ+α
b̂(θ − α)
(
N∑
n=−N
e2piiθn
)
dθ
=
∫ δ+α
−δ+α
b̂(θ − α)
(
e2piiθ(N+1/2) − e−2piiθ(N+1/2)
epiiθ − e−piiθ
)
dθ
=
∫ δ+α
−δ+α
b̂(θ − α)sen[(2N + 1)piθ]
sen(piθ)
dθ.
Integrando a equação (3.6) de −N − 1/2 até N + 1/2, temos:
∫ N+1/2
−N−1/2
b(n)e2piiαt =
∫ N+1/2
−N−1/2
∫ δ+α
−δ+α
b̂(θ − α)e2piiθtdθdt =
∫ δ+α
−δ+α
b̂(θ − α)
(∫ N+1/2
−N−1/2
e2piiθtdt
)
dθ
=
∫ δ+α
−δ+α
b̂(θ − α)
([
e2piiθt
2piiθ
]N+1/2
−N−1/2
)
dθ =
∫ δ+α
−δ+α
b̂(θ − α)sen[(2N + 1)piθ]
piθ
dθ.
Juntando as duas equações obtidas acima segue que:
N∑
n=−N
b(n)e2piiαn −
∫ N+1/2
−N−1/2
b(t)e2piiαtdt =
∫ δ+α
−δ+α
λα sen[(2N + 1)piθ]dθ, (3.7)
onde λα(θ) := b̂(θ − α)
[
1
sen(piθ)
− 1
piθ
]
.
Como | ± δ + α| < 1 temos λα ∈ L1([−δ + α, δ + α]). O teorema A.2.1 assegura que o
lado direito da equação (3.7) tende a 0 quando N →∞. Assim, como b ∈ L1(R), segue pelas
equações (3.4) e (3.7) e pela definição de β que
∑
|n|≤N b(n)e
2piiαn converge para b̂(−α) = β(α)
quando N →∞.
Com isso, confirmamos que poderíamos ter aplicado o somatório de Poisson, ou seja,
isso estabelece a equação (3.4) para |α| ≤ 1/2 e, consequentemente, estabelece para todo α
por periodicidade.
Queremos obter b ∈ L1(R) sujeito às condições:
b(t) ≥ 0, se t ∈ R
b(t) ≥ 1, se M + 1 ≤ t ≤M +N
b̂(θ) = 0, se |θ| ≥ δ.
(3.8)
e tal que B(0) = b̂(0) =
∫∞
−∞ b(t)dt seja pequeno.
Vejamos uma função bastante simples que, após algumas mudanças de variáveis, satisfaz
a terceira condição. Tomemos, por exemplo, a função f tal que f̂(θ) := max{0, 1− |θ|}, cujo
22 CAPÍTULO 3. O GRANDE CRIVO E A DESIGUALDADE DE BRUN-TITCHMARSH
gráfico é o seguinte:
Figura 3.1.1. Função f̂(θ) = max{0, 1− |θ|}.
Vamos calcular f a partir da f̂ . Temos:
f(t) =
∫
R
f̂(θ)e2piiθtdθ =
∫ 0
−1
(θ + 1)e2piiθtdθ +
∫ 1
0
(1− θ)e2piiθtdθ
=
∫ 0
−1
θe2piiθtdθ −
∫ 1
0
θe2piiθtdθ +
[
e2piiθt
2piit
]1
−1
=
[
θe2piiθt
2piit
]0
−1
− 1
2piit
∫ 0
−1
e2piiθtdθ −
[
θe2piiθt
2piit
]1
0
+
1
2piit
∫ 1
0
e2piiθtdθ +
e2piit − e−2piit
2piit
=
e−2piit
2piit
−
[
1
(2piit)2
− e
−2piit
(2piit)2
]
− e
2piit
2piit
+
[
e2piit
(2piit)2
− 1
(2piit)2
]
+
sen(2pit)
pit
=
e2piit + e−2piit − 2
(2piit)2
=
(
epiit − e−piit
2piit
)2
=
(
sen(pit)
pit
)2
.
Para a mudança de variáveis, definimos fn,δ(t) := f
(
n−δt
2
)
. Sua transformada vale:
f̂n,δ(θ) =
∫ ∞
−∞
(
sen[pi
2
(n− δt)]
pi
2
(n− δt)
)2
e−2piiθtdt
=
∫ −∞
∞
(
sen(pi
2
u)
pi
2
u
)2
e−2piiθ(n−u)/δ
du
−δ =
e−2piinθ/δ
δ
∫ ∞
−∞
(
sen(pi
2
u)
pi
2
u
)2
e−2piiu(−θ/δ)du
=
2e−2piinθ/δ
δ
f̂(−θ/δ) = 2e
−2piinθ/δ
δ
max{0, 1− |θ/δ|}.
Para cumprir a terceira condição de (3.8), sendo C > 0, é suficiente definir:
b̂(θ) := 2Cδ−1 max {1− |θ/δ|, 0}
∑
δ(M+1)≤n≤δ(M+N)
e−2piinθ/δ,
e assim teremos:
b(t) = C
∑
δ(M+1)≤n≤δ(M+N)
{
sen
[
pi
2
(n− δt)]
pi
2
(n− δt)
}2
.
3.1. O GRANDE CRIVO 23
Da última equação segue a primeira condição de (3.8). Só falta a segunda condição.
Notemos que |n− δt| ≤ 1/2, logo ∣∣pi
2
(n− δt)∣∣ ≤ pi/4. Assim:
{
sen[pi(n− δt)/2]
pi(n− δt)/2
}2
≥
{
sen(pi/4)
pi/4
}2
=
8
pi2
,
portanto é suficiente tomar C =
pi2
4
. Dessa forma, como o comprimento do intervalo da
soma na definição de b̂ é δ(N − 1), existem no máximo δ(N − 1) + 1 inteiros nesse intervalo.
Com isso, obtemos:
b̂(0) =
pi2
2δ
[δ(N − 1) + 1] = pi
2
2
(N − 1 + δ−1),
o que mostra uma cota mais simples que a dada por Montgomery e Vaughan do Teorema
do Grande Crivo.
O Teorema do Grande Crivo acima é dito estar na forma analítica. Vejamos agora sua
forma aritmética. Seja, como antes, {an} uma sequência de números complexos. No caso
onde α = a/q com mdc(a, q) = 1 e q ≤ Q temos, para r 6= s:
‖αr − αs‖ =
∥∥∥∥aq − a′q′
∥∥∥∥ = ∥∥∥∥aq′ − a′qqq′
∥∥∥∥ ≥ 1Q2 ,
o que mostra que os α’s são Q−2-espaçados.
Portanto, podemos escrever:
∑
q≤Q
∑
1≤a≤q
mdc(a,q)=1
|S(a/q)|2 ≤ pi
2
2
(N − 1 +Q2)
∑
M<n≤M+N
|an|2. (3.9)
Para cada p primo, definimos w(p) := #{0 ≤ h < p;n ≡ h (mod p)⇒ an = 0}. Sendo µ a
função de Möbius, definimos também:
g(q) = [µ(q)]2
∏
p|q
w(p)
p− w(p) .
Podemos assumir w(p) < p pois caso contrário an = 0 para todo n. Além disso, a função
g é claramente multiplicativa.
Lema 3.1.6. Para todo p primo temos que
w(p)
p− w(p) |S(0)|
2 ≤
p−1∑
a=1
|S(a/p)|2.
Demonstração. Observemos que:
δp(t) :=
1
q
p−1∑
h=0
e2piith/p =
1, se p|t0, caso contrário.
24 CAPÍTULO 3. O GRANDE CRIVO E A DESIGUALDADE DE BRUN-TITCHMARSH
Assim:
p−1∑
a=0
|S(a/p)|2 =
p−1∑
a,a′=0
S(a/p)S(a′/p)δp(a− a′) =
p−1∑
a,a′=0
S(a/p)S(a′/p)
1
p
p−1∑
h=0
e2piit(a−a
′)/p
=
1
p
p−1∑
h=0
∣∣∣∣∣
p−1∑
a=0
e−2piiah/pS(a/p)
∣∣∣∣∣
2
=
1
p
p−1∑
h=0
∣∣∣∣∣ ∑
M<n≤M+N
an
p−1∑
a=0
e2piia(n−h)/p
∣∣∣∣∣
2
=
1
p
p−1∑
h=0
∣∣∣∣∣ ∑
M<n≤M+N
anpδp(n− h)
∣∣∣∣∣
2
= p
p−1∑
h=0
|S(p, h)|2,
onde S(q, h) :=
∑
M<n≤M+N
n≡h (mod q)
an.
Portanto, como S(p, h) = 0 para pelo menos w(p) valores de h módulo p, temos pela
desigualdade de Cauchy-Schwarz que:
|S(0)|2 +
p−1∑
a=1
|S(a/p)|2 =
p−1∑
a=0
|S(a/p)|2 = p
p−1∑
h=0
|S(p, h)|2 ≥ p |S(0)|
2
p− w(p) .
Logo,
w(p)
p− w(p) |S(0)|
2 ≤
p−1∑
a=1
|S(a/p)|2.
Teorema 3.1.7. Para todo q ≥ 1 temos
∣∣∣∣∣ ∑
M<n≤M+N
an
∣∣∣∣∣
2
g(q) ≤
∑
1≤a≤q
mdc(a,q)=1
|S(a/q)|2.
Demonstração. Pela definição de S devemos mostrar que para toda sequência {an} temos:
|S(0)|2g(q) ≤
∑
1≤a≤q
mdc(a,q)=1
|S(a/q)|2. (3.10)
Como a definição de w(p) é invariante quando trocamos an por ane2piinβ (β ∈ R), a relação
anterior é equivalente a:
|S(β)|2g(q) ≤
∑
1≤a≤q
mdc(a,q)=1
|S(a/q + β)|2. (3.11)
Temos que g é multiplicativa e g(n) = 0 se n não é livre de quadrados. Logo, basta
provar esse teorema para produto de primos distintos. Pelo lema anterior, esse teorema é
válido para os primos. Suponhamos então que a desigualdade (3.11) é satisfeita para q e q′
3.2. A DESIGUALDADE DE BRUN-TITCHMARSH 25
com mdc(q, q′) = 1. Pelo Teorema Chinês dos Restos podemos escrever:∑
1≤c≤qq′
mdc(c,qq′)=1
|S(c/qq′)|2 =
∑
1≤a≤q
mdc(a,q)=1
∑
1≤b≤q′
mdc(b,q′)=1
|S(a/q + b/q′)|2
≥
∑
1≤a≤q
mdc(a,q)=1
|S(a/q)|2g(q′) ≥ |S(0)|2g(q)g(q′) = |S(0)g(qq′)|.
Logo, as desigualdades (3.10) e (3.11) são válidas para qq′. Por indução, segue que o
teorema é válido para todo q ≥ 1.
Corolário 3.1.8 (Forma Aritmética do Grande Crivo). Para qualquer sequência de números com-
plexos {an} temos: ∣∣∣∣∣ ∑
M<n≤M+N
an
∣∣∣∣∣
2
≤ pi
2
2
(
N − 1 +Q2
L
) ∑
M<n≤M+N
|an|2,
onde L :=
∑
q≤Q
g(q).
Demonstração. Basta usar o teorema anterior e a equação (3.9):
∑
q≤Q
∣∣∣∣∣ ∑
M<n≤M+N
an
∣∣∣∣∣
2
g(q) ≤
∑
q≤Q
∑
1≤a≤Q
mdc(a,q)=1
|S(a/q)|2 ≤ pi
2
2
(N − 1 +Q2)
∑
M<n≤M+N
|an|2,
de onde segue o resultado.
A parte surpreendente desse corolário é que temos a liberdade de escolher Q como qui-
sermos. Vamos, portanto, escolher um Q adequado e usar esse corolário para demonstrar a
desigualdade de Brun-Titchmarsh.
3.2 A desigualdade de Brun-Titchmarsh
Dados k e l com mdc(k, l) = 1, o Teorema de Dirichlet afirma que o comportamento assin-
tótico de pi(y; k, l) é y
ϕ(k) log y
quando y → ∞, isto é, limx→∞ pi(y;k,l)y/ log y = 1ϕ(k) . Observemos que
nesse teorema o y cresce, enquanto k é fixo. O seguinte teorema, cuja primeira versão é
devida a Brun e posteriormente melhorado por Titchmarsh limita superiormente a função
pi(y; k, l) quando k, y → ∞ desde que y/k → ∞. De fato, o teorema de Brun-Titchmarsh
limita o número de primos em progressão aritmética dentro de um intervalo. Como vere-
mos, sua prova independe do Teorema dos Números Primos e é uma aplicação do Grande
Crivo Aritmético.
Definição 3.2.1. Sejam P+(n) e P−(n) o maior e o menor fator primo de n, respectivamente.
26 CAPÍTULO 3. O GRANDE CRIVO E A DESIGUALDADE DE BRUN-TITCHMARSH
Teorema 3.2.1 (Brun-Titchmarsh). Seja x ∈ R+. Para todo ε > 0 existe y0 = y0(ε) tal que, se
y ≥ y0 e k, l são inteiros positivos primos entre si com k < y1−ε, então:
pi(x+ y; k, l)− pi(x; k, l) ≤ (pi2 + o(1)) y
ϕ(k) log(y/k)
.
Demonstração. Definimos:
an =
1, se x < l + nk ≤ x+ y e P−(l + nk) >
√
y/k
0, caso contrário.
Observemos que se kn+ l é um número primo no intevalo [x, x+ y] com kn+ l >
√
y/k
então an = 1, logo o número de primos iguais a l módulo k no intervalo [x, x+y]∩ [
√
y/k,∞)
é menor ou igual a
∑∞
n=1 an. Portanto:
pi(x+ y; k, l)− pi(x; k, l) ≤
∞∑
n=1
an + pi(
√
y/k) ≤
∞∑
n=1
an +
√
y/k.
Assim, basta limitar a soma
∑∞
i=1 an. De fato, essa soma é finita pois an = 0 para todo
n > x+y−l
k
e todo n ≤ x−l
k
. Assim, temos:
∞∑
n=1
an =
∑
M<n≤M+N
an,
com M = b(x− l)/kc e N = dy/ke ≤ y/k + 1. Pelo Grande Crivo Aritmético sabemos que:∣∣∣∣∣ ∑
M<n≤M+N
an
∣∣∣∣∣
2
≤ pi
2
2
(
N − 1 +Q2
L
) ∑
M<n≤M+N
|an|2
=⇒
∑
M<n≤M+N
an ≤ pi
2
2
(
N − 1 +Q2
L
)
,
onde L :=
∑
q≤Q
mdc(q,k)=1
[µ(q)]2
∏
p|q
w(p)
p− w(p) , Q pode ser selecionado de modo arbitrário e w(p) =
#{0 ≤ h ≤ p− 1;n ≡ h (mod p)⇒ an = 0}, como foi definido na seção anterior.
Notemos que an = 0 sempre que l + kn tem um fator primo p menor que
√
y/k, ou seja,
an = 0 sempre que p divide l+kn. Se h é tal que h ≡ −lk−1 (mod p) com p primo fixo menor
que
√
y/k e se n = pt+ h então l+ kn = l+ k(pt+ h) ≡ l+ kh ≡ 0 (mod p), portanto an = 0,
logo w(p) ≥ 1. Seja Q ≤√y/k. Como an = |an|2, o Teorema do Grande Crivo implica que:
∑
M<n≤M+N
an ≤ pi
2
2
(
y/k +Q2
L
)
,
3.2. A DESIGUALDADE DE BRUN-TITCHMARSH 27
com:
L =
∑
q≤Q
mdc(q,k)=1
[µ(q)]2
∏
p|q
w(p)
p− w(p) ≥
∑
q≤Q
mdc(q,k)=1
[µ(q)]2
∏
p|q
1
p− 1 =
∑
q≤Q
mdc(q,k)=1
[µ(q)]2
ϕ(q)
,
onde na última igualdade usamos o fato de que µ(q) = 0 quando q não é livre de quadrados.
Denotamos por β|α∞ se todo fator primo de β divide α. Cadam ≤ Q é fatorado de forma
única como m = qdt, onde mdc(q, k) = 1, q livre de quadrados, d|q∞ e t|k∞. De fato, se:
m = p
α1
1 . . . p
αr
r q
β1
1 . . . q
βs
s
k = pγ11 . . . p
γr
r q
βs+1
s+1 . . . q
βu
u
onde os pi’s e qi’s são primos distintos com αi, βi, γi > 0 então:
q = q1 . . . qs
d = qβ1−11 . . . q
βs−1
s
t = pα11 . . . p
αr
r
.
Usando tal representação (única) m = qdt temos que:
∑
q≤Q
1
m
=
∑
qdt≤Q
d|q∞,t|k∞
mdc(q,d)=1
[µ(q)]2
qdt
=
∑
q≤Q
[µ(q)]2
q
 ∑
d|q∞
d<Q/q
1
d
 ∑
t|k∞
t<Q/(qd)
1
t


≤
∑
q<Q
[µ(q)]2
q
∑
d|q∞
1
d
∑
t|k∞
1
t

Dado α ∈ N, queremos obter a soma dos inversos de todos os β tais que β|α∞. Seja
α = αγ11 α
γ2
2 . . . α
γt
t a fatoração de α em primos. Temos:
∑
β|α∞
1
β
=
t∏
i=1
(
1 +
1
αi
+
1
α2i
+ . . .
)
=
t∏
i=1
1
1− 1/αi =
t∏
i=1
αγii
(αi − 1)αγi−1i
=
α
ϕ(α)
.
Portanto, obtemos:
∑
m≤Q
1
m
≤
∑
m≤Q
mdc(q,k)=1
[µ(q)]2
q
q
ϕ(q)
k
ϕ(k)
=
k
ϕ(k)
∑
m≤Q
mdc(q,k)=1
[µ(q)]2
ϕ(q)
.
Dessa forma, podemos limitar L inferiormente, pois:
L ≥
∑
m≤Q
mdc(q,k)=1
[µ(q)]2
ϕ(q)
≥ ϕ(k)
k
∑
m≤Q
1
m
≥ ϕ(k)
k
logQ,
28 CAPÍTULO 3. O GRANDE CRIVO E A DESIGUALDADE DE BRUN-TITCHMARSH
onde na última desigualdade usamos a equação (1.4). Logo, basta escolher Q de modo que:
y/k +Q2
logQ.ϕ(k)/k
+
√
y
k
≤ (2 + o(1)) y
ϕ(k) log(y/k)
.
Escolhemos, portanto, Q =
√
y/k
log(y/k)
. Para esse valor de Q temos:
y/k +Q2
logQ.ϕ(k)/k
+
√
y
k
=
y + k y/k
log(y/k)
ϕ(k)[log(y/k)− log log(y/k)]/2 +
√
y
k
=
2y
ϕ(k)
1 + 1
log(y/k)
log(y/k)− log log(y/k) +
√
y
k
=
2y
ϕ(k) log(y/k)
(1 + o(1)).
Logo, o teorema está provado.
Usando a cota de Montgomery-Vaughan, o mesmo argumento nos leva a melhorar as
constantes da Forma Aritmética do Grande Crivo e da Desigualdade de Brun-Titchmarsh.
De fato, são válidas as desigualdades:∣∣∣∣∣ ∑
M<n≤M+N
an
∣∣∣∣∣
2
≤ N − 1 +Q
2
L
∑
M<n≤M+N
|an|2
pi(x+ y; k, l)− pi(x; k, l) ≤ (2 + o(1)) y
ϕ(k) log(y/k)
,
onde L foi definido no enunciado da Forma Aritmética do Grande Crivo.
Corolário 3.2.2. Para todo ε > 0 existe y0 = y0(ε) tal que, se y ≥ y0 e k, l são inteiros positivos
primos entre si com k < y1−ε, então:
pi(y; k, l) ≤ 10y
ϕ(k) log(y/k)
.
Na verdade, a melhor cota para a desigualdade de Brun-Titchmarsh é:
pi(y; k, l) ≤ 2y
ϕ(k) log(y/k)
para todo y > 0, mas não vamos demonstrar essa versão.
Capítulo 4
Infinitos números de Carmichael
4.1 Grandes números, pequenos fatores primos
Pelo Teorema dos Números Primos sabemos que ao escolher aleatoriamente um número
inteiro no intervalo [0, y], com y arbitrariamente grande, temos que a probabilidade dele ser
primo está próxima de 1
log y
. Em geral, pelo Teorema de Dirichlet, quando escolhemos um
número inteiro positivo aleatório que não excede y, a probabilidade desse número ser um
primo da forma dk + a, com mdc(d, a) = 1 e k ∈ N, é aproximadamente 1
ϕ(d) log y
∼ pi(y)
yϕ(d)
.
Em particular, a probabilidade de um primo menor que y ser congruente a a módulo d fica
próximo de 1
ϕ(d)
. Observemos que na afirmação anterior os números d e a são fixados e y é
considerado muito grande. Assim, uma pergunta natural é: o que acontece quando d cresce,
mas limitado por uma função que depende de y? Isto é, é possível que a probabilidade de ao
escolher um primo menor que y e congruente a a módulo d seja maior que C
ϕ(d)
onde C > 0
é uma constante adequada? Formalmente, temos a seguinte definição:
Definição 4.1.1. Seja B ⊂ (0, 1) o conjunto dos númerosB para os quais existem x2(B) eDB inteiro
positivo tais que se x > x2(B),mdc(a, d) = 1 e 1 ≤ d ≤ min
{
xB, y
x1−B
}
então:
pi(y, d, a) ≥ pi(y)
2ϕ(d)
quando d não é divisível por nenhum elemento de DB(x), que é um conjunto formado por no máximo
DB inteiros, todos maiores que log x.
Lembrando da definição 3.2.1, é claro que P+(p) = P−(p) = p se p é primo. Mas P+(p−1)
pode assumir valores extremos. De fato, se p−1 = 2q onde q é um primo de Sophie Germain
temos que P+(p−1) = q. Conjectura-se que existem infinitos primos de Sophie Germain. Se
p = 22
k
+1 é um primo de Fermat temos P+(p−1) = 2 e nesse caso existem várias conjecturas
conflitantes acerca de sua infinitude. Assim, uma pergunta natural é: qual é a proporção de
primos p ≤ x com x grande tal que P+(p− 1) seja também grande? Formalmente, temos:
Definição 4.1.2. Definimos pi(x, y) = #{p primo; p ≤ x e p− 1 livre de fatores primos > y}.
29
30 CAPÍTULO 4. INFINITOS NÚMEROS DE CARMICHAEL
Definição 4.1.3. Seja E ⊂ (0, 1) o conjunto dos números E tais que existem x1(E) > 0 e γ1(E) > 0
tais que pi(x, x1−E) ≥ γ1(E)pi(x) para todo x ≥ x1(E).
Observemos que calcular pi(x, y) equivale a calcular o número de elementos do conjunto:
D(x, L) = {d|L; d+ 1 é primo e d+ 1 ≤ x},
com L =
∏
p≤y p
αp onde αp é a maior potência de p tal que pαp ≤ x. De fato, para cada
d ∈ D(x, L) geramos um primo p = d + 1 menor ou igual a x tal que os divisores primos
de p − 1 são menores que y e, por outro lado, dado p ≤ x tal que p − 1 possui unicamente
divisores menores ou iguais a y segue que p− 1 divide L.
Podemos generalizar o conjunto anterior da seguinte forma: para cada inteiro positivo k
definimos:
Dk(x, L) = {d|L; dk + 1 é primo e d+ 1 ≤ x}.
Claramente, D1(x, L) = D(x, L). O seguinte teorema, devido a Prachar, limita sob algu-
mas condições o número de elementos de Dk(x, L) e no caso k = 1 relaciona B e pi(x, y). No
que segue, usaremos a desigualdade de Brun-Titchmarsh (na verdade, o corolário 3.2.2).
Teorema 4.1.1 (Prachar). Suponhamos B ∈ B e 0 < δ′ < 1/2. Existe x3(B) tal que se x ≥ x3(B) e
L é um inteiro livre de quadrados não divisível por nenhum primo maior que x(1−B)/2 e para os quais:
∑
q|L
q primo
1
q
≤ (1−B)(1− 2δ
′)
160
,
então existe k ∈ Z∗+, com k ≤ x1−B e mdc(k, L) = 1, tal que
#{d|L; dk + 1 ≤ x é primo } ≤ 2
−DB−2
log x
#{d|L; 1 ≤ d ≤ xB}.
Demonstração. Para cada d ∈ DB(x) que divide L escolhemos um divisor primo pd de d e
definimos L′ como o número obtido depois de retirar os pd’s da fatoração prima de L. Dessa
forma, nenhum elemento de DB(x) divide L′, isto é, L = L′m onde todo divisor primo de m
divide algum elemento de DB(x).
Observemos que para cada d′ divisor de L′ podemos construir dividores d de L com
mdc(d, L′) = d′ multiplicando por um divisor de m. Logo, para cada divisor d′ de L′ pode-
mos construir no máximo 2ω(m) divisores de d distintos (onde ω(n) denota o número de
divisores primos de n). Além disso, todos esses divisores cumprem que d ≥ d′. Assim:
#{d|L; 1 ≤ d ≤ y} ≤ 2ω(m)#{d′|L′; 1 ≤ d′ ≤ y}
para todo y ≥ 2. Como ω(m) ≤ DB segue que:
#{d|L′; 1 ≤ d ≤ y} ≤ 2−DB#{d|L; 1 ≤ d ≤ y}. (4.1)
4.1. GRANDES NÚMEROS, PEQUENOS FATORES PRIMOS 31
Para cada d divisor de L′ segue, da definição de B, que:
pi(dx1−B; d, 1) ≥ pi(dx
1−B)
2ϕ(d)
para todo x ≥ x2(B). Além disso, para 1 < d ≤ xB e 0 < δ′ < 1/2 segue pelo Teorema dos
Números Primos que todo x suficientemente grande satisfaz:
pi(dx1−B; d, 1) ≥ (1− δ
′)dx1−B
2ϕ(d) log x
. (4.2)
Por outro lado, sendo q um fator primo de L, temos por hipótese que q ≤ x(1−B)/2. Como
ϕ(dq) ≥ ϕ(d)ϕ(q) segue pela desigualdade de Brun-Titchmarsh que:
pi(dx1−B; dq, 1) ≤ 10dx
1−B
ϕ(dq) log(x1−B/q)
≤ 20
ϕ(q)(1−B)
dx1−B
ϕ(d) log x
≤ 40
q(1−B)
dx1−B
ϕ(d) log x
. (4.3)
Com isso, usando as desigualdades (4.2) e (4.3) segue que a quantidade de primos p ≤
dx1−B com p ≡ 1 (mod d) e mdc (p−1
d
, L
)
= 1 é no mínimo:
pi(dx1−B; d, 1)−
∑
q|L
q primo
pi(dx1−B; dq, 1) ≥ (1− δ
′)dx1−B
2ϕ(d) log x
−
∑
q|L
q primo
40dx1−B
q(1−B)ϕ(d) log x
≥ dx
1−B
ϕ(d) log x
1− δ′
2
− 40
1−B
∑
q|L
q primo
1
q
 .
Assim, como ϕ(d) ≤ d segue, por hipótese, que essa quantidade de primos q é no mínimo:
dx1−B
ϕ(d) log x
(
1− δ′
2
− 1− 2δ
′
4
)
≥ x
1−B
4 log x
.
Logo, o número de pares (p, d) com p ≤ dx1−B, p ≡ 1 (mod d),mdc (p−1
d
, L
)
= 1, p primo,
d|L′ e 1 ≤ d ≤ xB é no mínimo x1−B
4 log x
#{d|L′; 1 ≤ d ≤ xB}.
Cada par (p, d) corresponde a um inteiro p−1
d
≤ x1−B que é coprimo com L, e então pelo
Princípio da Casa dos Pombos existe k ∈ Z∗+, k ≤ x1−B com mdc(k, L) = 1 tal que k tem ao
menos 1
4 log x
#{d|L′; 1 ≤ d ≤ xB} representações como p−1
d
, sendo o par (p, d) como acima.
Logo, para esse k vale #{d|L; dk + 1 ≤ x e dk + 1 primo } ≥ 1
4 log x
#{d|L′; 1 ≤ d ≤ xB}.
Portanto, da equação (4.1) e da linha acima segue que:
#{d|L; dk + 1 ≤ x e dk + 1 primo} ≥ 2
−DB−2
log x
#{d|L; 1 ≤ d ≤ xB}.
Teorema 4.1.2. Se E 6= ∅ então E ⊂ (0, 1) é um intervalo aberto.
Demonstração. Se E ∈ E então é claro que (0, E] ⊂ E pois os mesmos x1(E) e γ1(E) servem
32 CAPÍTULO 4. INFINITOS NÚMEROS DE CARMICHAEL
para os elementos em (0, E). Basta mostrar que se E ∈ E então existe E ′ ∈ E com E ′ > E.
Sejam E ∈ E , E < E ′ < 1 e 0 < δ′ < 1/2. Denotemos I = [x1−E′ , x1−E]. Para x grande, como
E ∈ E , temos pela desigualdade de Brun-Titchmarsh e Teorema dos Números Primos que:
pi(x, x1−E
′
) ≥ pi(x, x1−E)−
∑
p∈I
pi(x; p, 1) ≥ γ1(E)pi(x)−
∑
p∈I
10x
ϕ(p) log(x/p)
.
Usando o fato que xE < x/p < xE′ temos:
pi(x, x1−E
′
) ≥ γ1(E)x(1− δ
′)
log x
−
∑
p∈I
10x
E(p− 1) log x
≥ x
log x
(
γ1(E)(1− δ′)− 10
E
∑
p∈I
1
p− 1
)
. (4.4)
Como 1
p
= 1
p−1 +O
(
1
p2
)
segue pela 2a fórmula de Mertens que:
∑
p∈I
1
p
=
∑
p≤x1−E
1
p
−
∑
p<x1−E′
1
p
= log log x1−E − log log x1−E′ +O
(
1
(1− E ′) log x
)
=⇒
∑
p∈I
1
p− 1 = log
(
1− E
1− E ′
)
+O
(
1
(1− E ′) log x
)
. (4.5)
Portanto, se E ′ está próximo de E então temos pelas equações (4.4) e (4.5) que todo x
suficientemente grande satisfaz:
γ1(E)(1− δ′)− 10
E
log
(
1− E
1− E ′
)
>
1
2
γ1(E) =⇒ pi(x, x1−E′) > 1
3
γ1(E)
x
log x
.
Logo, aplicando novamente o Teorema dos Números Primos (e supondo x grande) temos
que pi(x, x1−E′) > 1
4
γ1(E)pi(x). Assim E ′ ∈ E .
4.2 Relacionando pequenos fatores primos com primos em
P.A.
Essa seção é dedicada a mostrar a existência de uma importante relação de inclusão entre os
conjuntos B e E que foram definidos na seção anterior.
Lema 4.2.1. Sejam 0 < ε < 1, 0 < δ < ε/2 e P o conjunto dos primos no intervalo [xε/2, xε/2+δ].
Salvo por um número finito fixo D de primos, temos para todo x suficientemente grande que:
∑
p∈P
1
p
≥ δ
ε
.
Demonstração. Temos que P contém quase todos os primos desse intervalo, exceto D deles.
4.2. RELACIONANDO PEQUENOS FATORES PRIMOS COM PRIMOS EM P.A. 33
Pela 2a fórmula de Mertens temos:∑
p∈P
1
p
=
∑
p≤xε/2+δ
1
p
−
∑
p<xε/2
1
p
−
∑
xε/2≤p≤xε/2+δ
p/∈P
1
p
= log log xε/2+δ − log log xε/2 +O
(
1
log xε/2
)
+O
(
DB
xε/2
)
= log
(
ε/2 + δ
ε/2
)
+O
(
1
ε log x
)
= log
(
1 +
2δ
ε
)
+O
(
1
ε log x
)
.
Basta, portanto, limitarmos o logaritmo. De fato, temos que o gráfico de g(y) = log(1 +y)
está acima do gráfico de f(y) = y/2 em um intervalo que contém (0, 5/2).
Figura 4.2.1. Desigualdade log(1 + y) > y/2.
Logo, como o erro tende a 0 quando x→∞, o teorema segue.
Teorema 4.2.2. Para cada B ∈ B temos (0, B) ⊂ E
Demonstração. Suponhamos B ∈ B, x ≥ x2(B) e seja 0 < ε < B. Queremos mostrar que
B−ε ∈ E , ou seja, queremos mostrar que existe constante γ3(B, ε) > 0 tal que pi(x, x1−(B−ε)) >
γ3(B, ε)pi(x) para todo x suficientemente grande.
Para cada d ∈ DB(x) tomamos um primo pd que divide d. Seja 0 < δ < ε/2 e P o conjunto
de primos no intervalo [xε/2, xε/2+δ] diferentes dos primos pd escolhidos anteriormente.
Observemos que se q é um primo tal que:
q ≤ x,
q ≡ 1 (mod n),
os fatores primos de n pertencem a P ,
xB−ε ≤ n ≤ xB
(4.6)
34 CAPÍTULO 4. INFINITOS NÚMEROS DE CARMICHAEL
então todos os fatores primos de q − 1 são menores que x1−(B−ε) pois q − 1 = n q−1
n
. Pela
escolha de n temos que seus fatores primos são menores ou iguais a xε/2+δ ≤ x1−(B−ε) e
q−1
n
< x
n
≤ x
xB−ε = x
1−(B−ε). Assim, q é contado no número pi(x, x1−(B−ε)).
Para cada q fixo podem existir vários valores de n que satisfazem (4.6), mas tal quanti-
dade de n’s pode ser limitado contando o número de fatores primos de q− 1 que pertencem
a P . Suponhamos que k é essa quantidade. Assim:
x > q − 1 ≥
∏
p|q−1
p∈P
p ≥
∏
p|q−1
p∈P
xε/2 = xkε/2,
logo k ≤ b2/εc. Portanto, se n = pα11 pα22 . . . pαll com pj ∈ P então para cada q temos no
máximo
(b2/εc
l
) ≤ 2ε/2 possíveis valores de n. Logo:
pi(x, x1−(B−ε)) ≥ 2−ε/2
∑
n∈C(P,B,ε,x)
pi(x;n, 1),
onde C(P , B, ε, x) := {n ∈ N;xB−ε ≤ n ≤ xB e para todo p|n temos p ∈ P}.
Por outro lado, como B ∈ B temos que pi(x, n, 1) ≥ pi(x)
2ϕ(n)
para todo x ≥ x2(B) e para todo
n ≤ xB. Usando essas duas últimas desigualdades temos para todo x > x2(B) que:
pi(x, x1−(B−ε)) ≥ 2−1−ε/2pi(x)
∑
n∈C(P,B,ε,x)
1
ϕ(n)
. (4.7)
Logo, a prova do teorema se reduz a limitar inferiormente a soma acima por um valor
que independa de x. Vamos usar que 1/ϕ(n) ≥ 1/n. Observemos que se n ∈ C(P , B, ε, x)
então (xε/2)α1+···+αl ≤ pα11 . . . pαll = n ≤ xB, logo α1 + · · · + αl ≤
2B
ε
. Analogamente, xB−ε ≤
n = pα11 . . . p
αl
l ≤ (xε/2+δ)α1+···+αl , logo α1 + · · ·+ αl ≥
B − ε
ε/2 + δ
.
Notemos que sempre existe um inteiro positivo u tal que
B − ε
ε/2 + δ
≤ u ≤ 2B
ε
pois:
2B
ε
− B − ε
ε/2 + δ
>
2B
ε
− B − ε
ε/2
= 1.
Seja u = α1 + · · · + αl o menor inteiro tal que u ≥ B−εε/2 . Então B − ε ≥ uε/2 e como u é o
menor temos u ≥ 2B
ε
− 2 o que implica u− 1 < 2B/ε− 2 ≤ u < 2B/ε− 1. Portanto:
u
(ε
2
+ δ
)
<
(
2B
ε
− 1
)(ε
2
+ δ
)
= B +
(
2Bδ
ε
− ε
2
− δ
)
.
Queremos escolher um 0 < δ < ε/2 tal que o número acima fique menor que B, ou seja,
queremos que 2Bδ
ε
− ε
2
− δ < 0. Escolhemos, portanto, δ = ε2
4B
.
Como n é o produto de u primos (não necessariamente distintos) segue que:
xB−ε ≤ xuε/2 ≤ n ≤ xu(ε/2+δ) ≤ xB,
4.3. A COTA INFERIOR PARA A QUANTIDADE DE NÚMEROS DE CARMICHAEL 35
o que implica:
∑
n∈C(P,B,ε,x)
1
n
≥
∑
p
α1
1 ...p
αl
l
∈C(P,B,ε,x)
α1+···+αl=u
1
pα11 . . . p
αl
l
≥ 1
u!
(∑
p∈P
1
p
)u
.
Pelo lema 4.2.1 e pela escolha de δ segue que:
∑
n∈C(P,B,ε,x)
1
n
≥ 1
u!
( ε
4B
)u
.
Definimos γ3(B, ε) := 2−1−2/ε 1u!
(
ε
4B
)u (notemos que u depende apenas de B e ε). Pela
equação (4.7) segue, para todo x suficientemente grande, que pi(x, x1−(B−ε)) ≥ γ3(B, ε)pi(x),
logo B − ε ∈ E .
Corolário 4.2.3. Se B 6= ∅ então E 6= ∅.
4.3 A cota inferior para a quantidade de números de Carmichael
Esse é o principal teorema do texto, uma vez que ele mostra que C(x) é cotado inferiormente
por uma função do tipo xt com t > 0 sempre que x é grande. Como xt →∞ quando x→∞
segue que C(x)→∞, ou seja, existem infinitos números de Carmichael.
Uma hipótese essencial que usaremos é que B e E são não-vazios. Pelo corolário 4.2.3
basta mostrar que B 6= ∅, mas isso não é simples. A seção 4.4 e o apêndice C são dedicados
às ideias da demonstração de que isso de fato ocorre. Hoje, os melhores resultados conheci-
dos são E = 0, 7076 ∈ E e B = 0, 472 ∈ B, e isso implica que C(x) ≥ x1/3 para todo x grande.
Vários autores tentaram exibir limitações para C(x). Conjectura-se que E = B = (0, 1), e isso
implica que dado ε > 0 existe x0(ε) > 0 tal que C(x) > x1−ε sempre que x > x0(ε). Como
resultado desse capítulo, se a Hipótese Generalizada de Riemann for verdadeira então dado
ε > 0 temos C(x) > x1/2−ε para todo x grande. Por outro lado, o melhor resultado até
hoje, derivado do trabalho de vários matemáticos, diz que C(x) ≤ x1−(1+o(1)) log log log x/ log log x
(alguns desconfiam que a anterior desigualdade é na verdade uma igualdade). Apesar de
existirem infinitos números de Carmichael, essa desigualdade significa que os números de
Carmichael têm densidade nula, e mais: eles são mais escassos que os primos, pois sua
densidade com relação aos números primos também é nula.
Teorema 4.3.1. Para cada E ∈ E , B ∈ B e ε > 0 existe x4(E,B, ε) > 0 tal que para todo x ≥
x4(E,B, ε) temos C(x) ≥ xEB−ε.
Demonstração. Sejam E ∈ E , B ∈ B, 0 < ε < EB (para ε ≥ EB o teorema é óbvio), y ≥ 2 e
θ = 1
1−E . Observemos que para essa escolha de θ e pela definição de E temos que pi(yθ, y) ≥
36 CAPÍTULO 4. INFINITOS NÚMEROS DE CARMICHAEL
γ1(E)pi(y
θ) para y suficientemente grande. Definimos:
Q :=
{
q ∈
(
yθ
log y
, yθ
]
; q é primo tal que q − 1 não tem fatores primos maiores que y
}
.
Podemos limitar inferiormente o número de elementos de Q. De fato, pelo Teorema dos
Números Primos, se 0 < δ1 < 1/2 e y é suficientemente grande então:
|Q| ≥ pi(yθ, y)− pi
(
yθ
log y
)
≥ γ1(E).pi(yθ)− pi
(
yθ
log y
)
≥ γ1(E).(1− δ1) y
θ
log yθ
− (1 + δ1) y
θ/log y
log (yθ/log y)
≥ y
θ
log yθ
[
γ1(E).(1− δ1)− (1 + δ1).θ
θ log y − log log y
]
≥ 1
2
γ1(E)
yθ
log yθ
.
Seja L :=
∏
q∈Q q. Notemos queQ está contido no conjunto de primos menores ou iguais
a yθ. Fixado 0 < δ2 < 1 segue pelo Teorema dos Números Primos que se y é suficientemente
grande então:
logL ≤ |Q| log yθ ≤ pi(yθ) log yθ ≤ (1 + δ2)y
θ
log yθ
log yθ ≤ 2yθ.
Pelo teorema 2.2.2 segue que λ(L) = mmc{q−1; q ∈ Q}, onde λ é a função de Carmichael,
que foi vista na seção 2.2.
Como cada q − 1 é livre de fatores primos maiores que y, sabemos que se pα divide λ(L)
então p ≤ y e pα divide q − 1 < q ≤ yθ, o que implica pα < yθ. Seja αp o maior natural tal que
pαp < yθ. Fixado 0 < δ3 < 1 segue novamente pelo Teorema dos Números Primos que se y é
suficientemente grande então:
λ(L) ≤
∏
p<y
pαp ≤
∏
p<y
yθ = yθ.pi(y) ≤ eθ.(1+δ3) ylog y log y ≤ e2θy.
Sejam G = (Z/LZ)∗ e n(G) como definidos na seção 2.3. Podemos limitar a constante de
Davenport de G pelo teorema 2.3.1. De fato, temos para todo y grande que:
n(G) < λ(L)
[
1 + log
(
ϕ(L)
λ(L)
)]
≤ λ(L)(1 + logL) ≤ e2θy(1 + 2yθ) ≤ e3θy − 1.
Pela 2a fórmula de Mertens e pela série de Taylor do logaritmo, temos:
∑
q|L
q primo
1
q
≤
∑
yθ/ log y<q≤yθ
q primo
1
q
= log log yθ − log log
(
yθ
log y
)
+O
(
1
log(yθ/ log y)
)
≤ − log
(
log yθ − log log y
log yθ
)
+O
(
1
log(yθ/ log y)
)
.
4.3. A COTA INFERIOR PARA A QUANTIDADE DE NÚMEROS DE CARMICHAEL 37
Como log
(
1− log log y
log yθ
)
→ 0 e 1
log(yθ/ log y)
→ 0 quando y → ∞ segue que ∑q|L 1q é
arbitrariamente pequeno. Em particular, para todo y suficientemente grande temos:
∑
q|L
1
q
≤ (1−B)(1− 2δ
′)
160
.
Assim, podemos aplicar o teorema de Prachar com parâmetros B, x = ey1+δ e L, onde
δ > 0 será escolhido posteriormente. Logo, para y grande existe k ∈ Z∗+ coprimo com L tal
que o conjunto P dos primos menores ou iguais a x com p = dk + 1 para algum d divisor de
L satisfaz:
|P| ≥ 2
−DB−2
log x
#{d|L; 1 ≤ d ≤ xB}. (4.8)
Seja u um inteiro positivo. Podemos escolher o valor de u de forma que o produto de
quaisquer u fatores primos distintos de L é um divisor d de L com d ≤ xB. De fato, queremos
d ≤ (yθ)u ≤ xB, logo podemos tomar u :=
⌊
log xB
log yθ
⌋
. Assim, #{d|L; 1 ≤ d ≤ xB} ≥ (ω(L)
u
)
,
onde ω(n) denota o número de divisores primos de n.
Temos então:(
ω(L)
u
)
≥
(
ω(L)
u
)u
≥
(
1
2
γ1(E)y
θ
log yθ
1
u
)u
≥
(
γ1(E)y
θ
2B log x
)u
=
(
γ1(E)y
θ−1−δ
2B
)u
.
Pela desigualdade (4.8) e pela desigualdade acima, temos:
|P| ≥ 2
−DB−2
log x
#{d|L; 1 ≤ d ≤ xB} ≥ 2
−DB−2
log x
(
γ1(E)y
θ−1−δ
2B
)u
.
Escolhemos δ > 0 de tal forma que θ − 1 − δ = (EB − ε/4)θ/B. Como θ = 1
1−E basta
tomar δ = εθ
4B
. Assim:
(
yθ−1−δ
)u
q ≥
(
y(EB−ε/4)
θ
B
)B log x
θ log y
−1
≥ y(EB−ε/4) log xlog y− θB = xEB−ε/4y− θB .
Logo, se C1 = γ1(E)/2B e C2 = 2−DB−2 então:
|P| ≥ C2
log x
Cu1 x
EB−ε/4y−
θ
B ≥ C2
C1
C
B log x
θ log y
1
1
y1+δ
y−
θ
BxEB−ε/4 =
C2
C1
C
B
θ
y1+δ
log y
1
1
y1+δ+
θ
B
xEB−ε/4
=
C2
C1
exp
[
B
θ
y1+δ
log y
logC1 −
(
1 + δ +
θ
B
)
log y
]
xEB−ε/4 ≥ e−εy1+δ/12xEB−ε/4 = xEB−ε/3
Seja P ′ = P −Q. Como |Q| ≤ yθ temos:
|P ′| ≥ |P| − |Q| ≥ xEB−ε/3 − yθ ≥ xEB−ε/2
pois yθ = (log x)
θ
1+δ ≤ xEB−ε/3 − xEB−ε/2 para y grande.
Podemos ver P ′ como subconjunto de G = (Z/LZ)∗ considerando os resíduos de cada
38 CAPÍTULO 4. INFINITOS NÚMEROS DE CARMICHAEL
p ∈ P ′ módulo L. Se S é um subconjunto de P ′ que contém mais que um elemento e se
Π(S) :=
∏
p∈S p ≡ 1 (mod L) então afirmamos que Π(S) é um número de Carmichael.
De fato, todo elemento de P ′ é 1 módulo k, logo Π(S) ≡ 1 (mod k) e assim Π(S) ≡ 1
(mod kL) pois (k, L) = 1. Mas se p ∈ P ′ então p ∈ P , logo p − 1 divide kL e assim p − 1
divide Π(S)− 1. Portanto, Π(S) satisfaz o critério de Korselt (teorema 0.0.4).
Vamos então invocar o teorema 2.3.2 para contar a quantidade de subsequências de S
com produto 1 (que é o que precisamos). A quantidade de números de Carmichael da forma
Π(S), com |S| ≤ t, é pelo menos:
(|P ′|
btc
)
( |P ′|
n(G)
) ≥
( |P ′|
btc
)btc
|P ′|n(G) ≥
(
xEB−ε/2
)btc−n(G)
btcbtc ≥
x(EB−ε/2)(t−e
3θy)
tt
,
e queremos que essa última expressão majore x(EB−ε)t pois cada Π(S) assim formado satisfaz
Π(S) ≤ xt, uma vez que |S| ≤ t e p|Π(S), logo p ∈ P e assim p ≤ x.
Podemos tomar t = exp(y1+δ/2). Assim, x = exp(y1+δ/2yδ/2) = tyδ/2 , isto é, t = x−yδ/2 .
Temos:
x(EB−ε/2)(t−e
3θy)
tt
= (xEB−ε/2)t−e
3θy
(x−y
δ/2
)−t = x(EB−ε/2)(t−e
3θy)−ty−δ/2 .
Para esse t escolhido segue que para o expoente da última expressão vale:(
EB − ε
2
)
t− e3θy
(
EB − ε
2
)
− y−δ/2t ≥ (EB − ε)t ⇐⇒
(ε
2
− y−δ/2
)
t ≥ e3θy
(
EB − ε
2
)
,
o que é verdade pois (ε/2− y−δ/2) > 0 para y grande e limy→∞ t/(e3θy) =∞.
Logo, se X = xt então C(X) ≥ XEB−ε para todo y suficientemente grande. Mas X =
exp(y1+δey
1+δ/2
) pois logX = t log x = ey1+δ/2y1+δ, assim X é determinado unicamente por y,
o que implica C(X) ≥ XEB−ε para todo X grande.
Corolário 4.3.2. Para cada E ∈ E e B ∈ B existe x5(E,B) > 0 tal que para todo x > x5(E,B)
temos C(x) > xEB.
Demonstração. Pelo teorema 4.1.2, dado E ∈ E existe E ′ > E tal que E ′ ∈ E . Logo, tomando
ε = (E ′ − E)B > 0 no teorema anterior obtemos C(x) > xE′B−(E′−E)B = xEB para todo x
grande.
4.4 Transferindo o trabalho para os zeros das L-séries
As L-séries de Dirichlet são, de certa forma, generalizações da função Zeta de Riemann. Sua
definição encontram-se no apêndice B (definição B.3.1). Nessa seção, usaremos o principal
resultado da seção B.4, que é o teorema B.4.2.
Para cada caráter de Dirichlet χ e números reais 1/2 ≤ σ ≤ 1 e T ≥ 0 seja N(σ, T, χ) o
número de zeros s = β+iθ das L-séries de Dirichlet dentro do retângulo σ ≤ β ≤ 1 e |θ| ≤ T .
4.4. TRANSFERINDO O TRABALHO PARA OS ZEROS DAS L-SÉRIES 39
Definição 4.4.1. DefinimosA como o conjunto de números reais A > 2 para os quais existe γ(A) ≥
1 tal que para todo σ ≥ 1− 1/A e T ≥ 1,
N(σ, T, d) :=
∑
χ (mod d)
N(σ, T, χ) ≤ γ(A)(Td)A(1−σ), (4.9)
para todo inteiro positivo d.
É claro que se A ∈ A então (A,∞) ⊂ A, pois o mesmo γ(A) serve. Atualmente, o melhor
resultado é que se A > 12/5 então A ∈ A. Conjectura-se que todo A > 2 pertence a A.
Notemos, pela equação (B.10), que (4.9) pode não valer para todo A ≤ 2 (com σ = 1/2),
uma vez que o número de zeros de L(s, χ) até uma altura T na faixa crítica é da ordem de
T log(Td). Em particular, existe c ≥ 1 tal que:
N(1/2, T, d) ≤ cTd log(Td) (4.10)
para todo d inteiro positivo e T ≥ 1.
Teorema 4.4.1. Dados A ∈ A, ε, δ > 0, existem ηε,δ e Dε,δ tal que se x é suficientemente grande
então existe um conjunto Dε,δ(x) de no máximo Dε,δ inteiros para os quais:∣∣∣∣∣∣∣
∑
p≤y
p≡a (mod d)
log p− y
ϕ(d)
∣∣∣∣∣∣∣ ≤ ε
y
ϕ(d)
(4.11)
quando d não é divisivel por nenhum elemento de Dε,δ com mdc(a, d) = 1 e d no intervalo 1 ≤ d ≤
min{x1/A−δ, y/x1−1/A+δ, y1/A−δ}. Além disso, todos os elementos de Dε,δ(x) são maiores que log x e
no máximo um deles não é maior que xηε,δ .
Demonstração. Se 1 ≤ d ≤ log y então esse teorema é uma consequência direta do Teorema
dos Números Primos em Progressão Aritmética (teorema B.4.2), uma vez que:
log y ≤ eC(log y)1/2 ⇐⇒ log log y ≤ C(log y)1/2,
que é verdade para todo y grande. Suponha então que:
log y ≤ d ≤ min{x, y}1/A−δ. (4.12)
Para x grande, temos:
(log x)4/δ < x1/2 < dx1−1/A+δ ≤ y ≤ ex. (4.13)
40 CAPÍTULO 4. INFINITOS NÚMEROS DE CARMICHAEL
Seja a inteiro primo com d. Notemos que:
ψ(y; d, a) =
∑
p≤y
p≡a (mod d)
log p+
∑
p≤√y
p≡a (mod d)
log p+
∑
p≤ 3√y
p≡a (mod d)
log p+ . . .
=
∑
p≤y
p≡a (mod d)
log p+O(y1/2 log y), (4.14)
pois, exceto a primeira, cada uma das somas acima é O(y1/2) e existem no máximo O(log y)
parcelas. Podemos então deduzir, pelas equações (4.14), (B.11) e (B.13), que:
∑
p≤y
p≡a (mod d)
log p =
y
ϕ(d)
− 1
ϕ(d)
∑
χ (mod d)
χ(a)
∑
L(β+iθ,χ)=0
β≥1/2,|θ|≤T
yβ+iθ
β + iθ
+O
(
y1/2 log2(Td) +
y log2(Tdy)
T
)
.
(4.15)
Vamos reduzir a equação acima. Seja T = x3. Notemos que |χ(a)| = 1, |yβ+iθ| = yβ e
|β + iθ| ≥√1/4 + θ2 ≥ (1 + |θ|)/3.
Para compactar a primeira parcela do erro, podemos ver pela hipótese e pelas desigual-
dades (4.12) e (4.13), aumentando x e y se necessário, que temos y ≥ dx1−1/A+δ ≥ d2x1−2/A+2δ
≥ d2x2δ log4 x, portanto y1/2 log2(Td) ≤ y log2(x3d)
dxδ log2 x
= O(y/dxδ).
Para segundo termo, podemos notar que T = x3 > x3/A > xδd3 e que log(Tdy) ≤
log(x3+1/A−δy) = O(log y) = O(d), logo y log2(Tdy)/T = O(yd2/(d3xδ)) = O(y/dxδ). Subs-
tituindo esses erros e usando a desigualdade triangular, temos:∣∣∣∣∣∣∣
∑
p≤y
p≡a (mod d)
log p− y
ϕ(d)
∣∣∣∣∣∣∣ ≤
3
ϕ(d)
∑
χ (mod d)
∑
L(β+iθ,χ)=0
β≥1/2,|θ|≤x3
yβ
1 + |θ| +O
( y
dxδ
)
. (4.16)
Denotemos por
∑α
σ como a soma sobre todos os zeros β + iθ de L(s, χ) de todos os
caráteres χ (mod d), onde σ ≤ β < α e |θ| ≤ x3 (cada β + iθ é contado com multiplicidade
igual à quantidade de L-séries nas quais ele é um zero). Seja τ ∼ 1, por exemplo, τ :=
1 − ρ/ log x, onde escolheremos o valor de ρ > 0 mais tarde. Para estimar a soma dupla
acima, vamos usar as limitações:
• β ≤ 1− 1/A =⇒ yβ ≤ y1−1/A;
• 1− 1/A < β < τ =⇒ yβ = y1−1/A + log y ∫ β
1−1/A y
σdσ.
• β ≥ τ =⇒ yβ ≤ y;
4.4. TRANSFERINDO O TRABALHO PARA OS ZEROS DAS L-SÉRIES 41
Portanto, a soma dupla acima é no máximo:
1−1/A∑
1/2
y1−1/A
1 + |θ| +
τ∑
1−1/A
y1−1/A + log y
∫ β
1−1/A y
σdσ
1 + |θ| +
1∑
τ
y
1 + |θ|
=
τ∑
1/2
y1−1/A
1 + |θ| + log y
τ∑
1−1/A
1
1 + |θ|
∫ β
1−1/A
yσdσ +
1∑
τ
y
1 + |θ|
≤
1∑
1/2
y1−1/A
1 + |θ| + log y
∫ τ
1−1/A
yσ
(
1∑
σ
1
1 + |θ|
)
dσ +
1∑
τ
y
1 + |θ| . (4.17)
Para qualquer σ ≥ 1/2, integrando por partes a integral de Riemann-Stieltjes, temos:
1∑
σ
1
1 + |θ| ≤
1∑
σ
1
|θ| =
∫ x3
1
1
θ
d(N(σ, θ, d)) =
[
N(σ, t, d)
t
]x3
1
+
∫ x3
1
N(σ, t, d)
t2
dt
≤ N(σ, 1, d) + N(σ, x
3, d)
x3
+
∫ x3
1
N(σ, t, d)
t2
dt, (4.18)
e, além disso, para qualquer θ ∈ [1, x3] a desigualdade (4.10) nos diz que N(1/2, θ, d)/θ ≤
4cd log x. Com essas estimativas, podemos limitar cada termo da soma (4.17) como segue:
• Primeiro termo: Como d ≤ y1/A−δ e yδ > log4 x, o primeiro termo é no máximo:
1∑
1/2
y1−1/A
1 + |θ| ≤ 4cdy
1−1/A log x
(
2 +
∫ x3
1
dt
t
)
≤ 16cy1−δ log2 x ≤ y
log x
.
• Segundo termo: Se σ ≥ 1 − 1/A então A(1 − σ) ≤ 1, assim para qualquer θ ∈ [1, x3],
como A ∈ A, temos N(σ, θ, d)/θ ≤ γ(A)dA(1−σ). Logo:
1∑
σ
1
1 + |θ| ≤ γ(A)d
A(1−σ)
(
2 +
∫ x3
1
dt
t
)
≤ 4γ(A)dA(1−σ) log x.
Mas se σ ≥ 1−1/2A entãoA(1−σ) ≤ 1/2, assim para qualquer θ ∈ [1, x3], comoA ∈ A,
temos N(σ, θ, d) ≤ γ(A)(θd)A(1−σ) ≤ γ(A)dA(1−σ)θ1/2. Logo:
1∑
σ
1
1 + |θ| ≤ γ(A)d
A(1−σ)
(
2 +
∫ x3
1
dt
t3/2
)
≤ 4γ(A)dA(1−σ).
Usando as duas limitações acima e usando que y ≥ x1/2 e yAδ ≤ y/dA pelas desigual-
42 CAPÍTULO 4. INFINITOS NÚMEROS DE CARMICHAEL
dades (4.13), concluímos que o segundo termo é menor ou igual a:
4γ(A)dA log y
{
log x
∫ 1−1/2A
1−1/A
( y
dA
)σ
dσ +
∫ τ
1−1/2A
( y
dA
)σ
dσ
}
≤4γ(A)dA log y
log(y/dA)
y
dA
{( y
dA
)−1/2A
log x+
( y
dA
)−(1−τ)}
≤4γ(A)y
δA
{
y−δ/2 log x+ e−δAρ/2
}
.
Queremos que a expressão acima fique pequena, por exemplo, menor que ε/9. A
primeira parcela dentro das chaves tende a 0 quando y →∞. Para a segunda parcela,
se tomarmos ρ := (1/δ) log(1/εδ) então e−δAρ/2 = eA log(εδ)/2, que fica tão pequena
quanto quisermos ao supor ε e δ muito pequenos. Assim, o segundo termo da soma
(4.17) fica menor que (ε/9)y.
• Terceiro termo: definimos Dε,δ(x) como o conjunto de inteiros d′, onde 1 ≤ d′ ≤ x1/A−δ,
para os quais existe um caráter primitivo χ (mod d)′ com um zero β + iθ de L(s, χ)
satisfazendo β ≥ τ e |θ| ≤ ν para algum ν > 0 que será escolhido mais tarde. Por
hipótese, d não é divisível por nenhum elemento de Dε,δ(x), portanto o terceiro termo
só envolve zeros na região β ≥ τ e ν < |θ| ≤ x3. Assim, como A ∈ A e d ≤ x, o terceiro
termo é no máximo:
1∑
τ
y
1 + |θ| ≤ y
1∑
τ
1
|θ| ≤
y
ν
1∑
τ
1 ≤ yN(τ, x
3, d)
ν
≤ γ(A)yx
4A(1−τ)
ν
= γ(A)y
e4Aρ
ν
.
Nesse momento, tomamos ν := e4Aρ/ε2. Como ε é pequeno, o terceiro termo é menor
ou igual a (ε/9)y.
Juntando as três cotas acima na equação (4.16) obtemos:∣∣∣∣∣∣∣
∑
p≤y
p≡a (mod d)
log p− y
ϕ(d)
∣∣∣∣∣∣∣ ≤ ε
y
ϕ(d)
.
O teorema 14 de [2] afirma que existem constantes c2, c3 > 0 tais que:∑
d≤T
∑
χ (mod d)
χ primitivo
N(σ, T, χ) ≤ c2T c3(1−σ)
para todos T ≥ 2 e σ ≥ 1/2. Por definição, o conjunto Dε,δ(x) possui cardinalidade menor
ou igual ao lado esquerdo da desigualdade acima com T = x1/A−δ e σ = τ , logo #Dε,δ(x) ≤
c2e
ρc3/A =: Dε,δ.
Vamos aplicar o teorema B.3.2 com T = xη, onde η > 0. Existe c4 > 0 tal que para todo
T ≥ 2 existe no máximo um caráter primitivo χ1 módulo d1 ≤ T para os quais L(s, χ1) tem
4.4. TRANSFERINDO O TRABALHO PARA OS ZEROS DAS L-SÉRIES 43
um zero β1 + iθ1 satisfazendo β1 ≥ 1− c4/ log T e |θ| ≤ T . No caso de existência de tal zero,
temos θ1 = 0 e β1 ≤ 1 − c5/(d1/21 log2 d1), para algum c5 > 0. Se definirmos η := c4/ρ então
1− c4/ log(xη) = τ , logo Dε,δ(x) contém no máximo um número menor ou igual a xη. Se esse
inteiro existe, definimo-lo como d1, logo τ ≤ 1 − c5/(d1/21 log2 d1), o que implica d1 ≥ log x
quando x é suficientemente grande.
Corolário 4.4.2. Se A ∈ A então B ∈ B para todo B satisfazendo 0 < B < 1/A.
Demonstração. Seja δ > 0 pequeno. O Teorema dos Números Primos, o lema B.4.1 e as
equações (4.14) e (4.11) nos dizem que:
pi(y; d, a)
pi(y)
≥ 7
8
pi(y; d, a)
y/ log y
≥ 3
4
ψ(y; d, a)
y
≥ 5
8y
 ∑
p≤y
p≡a (mod d)
log p
 ≥ 1
2ϕ(d)
Logo, pi(y; d, a) ≥ pi(y)
2ϕ(d)
para todo x, y grandes, com 1 ≤ d ≤ min{x1/A−δ, y/x1−1/A+δ} e d
não divisível por nenhum elemento deD1/A−δ(x), que é um conjunto com no máximoD1/A−δ
inteiros, todos maiores que log x.
Corolário 4.4.3. Se A 6= ∅ então B 6= ∅.
Dessa forma, a não vacuidade de A, que é um conjunto intimamente ligado aos zeros
das L-séries, implica a não vacuidade de B, que por sua vez implica a não vacuidade de
E , donde segue que existem infinitos números de Carmichael. Já a não vacuidade de A é
garantida pelo seguinte teorema, citado no apêndice C e demonstrado em [7].
Teorema 4.4.4. Seja 0 < ε < 1/5. Para todos 1− ε < σ ≤ 1 e T ≥ 1 existe γ(ε) ≥ 1 tal que:
N(σ, T, d) ≤ γ(ε)(Tq)(2+ε)(1−σ).
Corolário 4.4.5. O conjunto A é não vazio.
Atualmente, os melhores resultados dizem que todos os números maiores que 12/5 per-
tencem a A e isso implica que todos os números positivos menores que 5/12 pertencem a B
(e consequentemente a E), logo temos C(x) ≥ x25/144 para todo x suficientemente grande. É
claro que essa cota para C(x) pode ser melhorada, já que a princípio existem mais elementos
nos conjuntos B e E do que os que vêm do teorema 4.2.2 e do corolário 4.4.2.
44 CAPÍTULO 4. INFINITOS NÚMEROS DE CARMICHAEL
Apêndice A
A teoria de Fourier
A.1 Uma integral
Lema A.1.1.
∫ ∞
−∞
senx
x
dx = pi.
Demonstração. Sejam f(z) =
eiz
z
e γ o caminho da figura abaixo (percorrido no sentido anti-
horário):
Figura A.1.1. Caminho γ.
Temos
∫
γ
f(z)dz = 0 pois f é holomorfa em γ, que é um caminho fechado. Dividindo γ
em partes, γ = γε ∪ [ε,N ] ∪ γN ∪ [−N,−ε], onde γε é um semicírculo de raio ε orientado em
sentido horário e γN é uma semicircunferência de raio N em sentido anti-horário, temos:
• Caminho γε: se ε → 0 então eiεeiθ → 1 e portanto o Teorema da Convergência Domi-
nada nos diz que:
∫
γε
eiz
z
dz =
∫ 0
pi
eiεe
iθ
εeiθ
iεeiθdθ = −i
∫ pi
0
eiεe
iθ
dθ → −ipi.
• Caminho γN : notemos que para todo N > 0 vale:∣∣∣∣∫
γN
eiz
z
dz
∣∣∣∣ = ∣∣∣∣∫ pi
0
eiNe
iθ
dθ
∣∣∣∣ ≤ ∫ pi
0
∣∣∣eiNeiθ∣∣∣ dθ = ∫ pi
0
e−N sen θdθ.
45
46 APÊNDICE A. A TEORIA DE FOURIER
Seja 0 < δ < pi/2. Temos que [0, pi] = [0, δ]∪ [δ, pi−δ]∪ [pi−δ, pi]. Em θ ∈ [0, δ] ou [pi−δ, pi]
temos e−N sen θ < 1, logo
∫ δ
0
e−N sen θdθ =
∫ pi
pi−δ e
−N sen θdθ < δ. Em θ ∈ [δ, pi − δ] temos
sen θ estritamente maior que zero (maior que uma constante positiva). Logo, se N →
∞ então e−N sen θ → 0 e portanto ∫ pi−δ
δ
e−N sen θdθ → 0 pelo Teorema da Convergência
Dominada.
Fazendo ε → 0, δ → 0 e N → ∞ obtemos
∫
γε∪γN
f(z)dz = −ipi. Como f(z) = e
iz
z
=
cos z + i sen z
z
segue que
∫ ∞
−∞
senx
x
dx = −1
i
∫
γε∪γN
f(z)dz = pi.
Como
senx
x
é uma função par obtemos para todo b 6= 0:∫ ∞
0
senx
x
dx =
pi
2
e
∫ ∞
0
sen bx
x
dx =
∫ ∞
0
sen bx
bx
d(bx) =
pi
2
sgn(b).
A.2 A transformada de Fourier
Definição A.2.1. Seja k ∈ N. Definimos o conjunto Lk(R) = {f : R→ C; ∫R |f(x)|kdx <∞},
onde f é integrável no sentido de Lebesgue. Em particular, L1(R) =
{
f : R→ C; ∫R |f(x)|dx <∞}.
Vale ressaltar que toda função Riemann-integrável é Lebesgue integrável.
Definição A.2.2. Seja f ∈ L1(R). Definimos f̂(y) := ∫R f(x)e−2piixydx como a Transformada de
Fourier de f . A condição f ∈ L1(R) garante a existência da integral anterior.
Teorema A.2.1 (Lema de Riemann-Lebesgue). Se f ∈ L1(R) então lim
y→∞
f̂(y) = 0.
Demonstração. A prova desse fato consiste em provar para funções constantes, usar a lineari-
dade da integral para mostrar para funções simples e notar que essas formam um subespaço
denso de L1(R). Notando que se o teorema vale para um subespaço denso então também
valerá para L1(R), o resultado segue. A prova com detalhes pode ser encontrada em [5].
Definição A.2.3. Seja I ⊂ R um intervalo. Dizemos que f : I → C é de variação limitada se existe
C > 0 tal que para toda partição x0 < x1 < · · · < xr de I temos:
k−1∑
i=0
|f(xi+1)− f(xi)| < C.
Se I = R então dizemos que f é de variação total limitada.
Dado intervalo I definimos a variação total V ba (f) para a, b ∈ R por:
V ba (f) = sup
{
r−1∑
i=0
|f(xi+1)− f(xi)|
}
onde tiramos o supremo sobre todas as partições x0 < x1 < · · · < xr, xi ∈ I e a ≤ x0 ≤ xr ≤ b.
A.2. A TRANSFORMADA DE FOURIER 47
Seja a = inf I (possivelmente a = −∞). Claramente, a função x → V xa (f) é crescente.
Além disso, a função x→ V xa (f)− f(x) também é crescente, pois se x < y então:
[V ya (f)− f(y)]− [V xa (f)− f(x)] = V yx (f)− [f(y)− f(x)] ≥ 0,
uma vez que x < y é apenas uma partição.
A partir disso, concluimos que se f é uma função de variação limitada então f pode-se
escrever como diferença de funções crescentes, a saber, f(x) = V xa − [V xa − f(x)].
Lema A.2.2. Sejam I = [a, b] ⊂ R um intervalo limitado e f uma função de variação limitada em I .
Se g é uma função Riemann integrável em I e G uma primitiva de g então:∣∣∣∣∫
I
f(x)g(x)dx− [f(b)G(b)− f(a)G(a)]
∣∣∣∣ ≤ V ba (f) sup |G|.
Demonstração. Dado ε > 0 existe δ > 0 tal que para toda partição a = x0 < x1 < · · · < xr = b
e todo yi ∈ [xi−1, xi] com |xi − xi−1| < δ temos:∣∣∣∣∣
∫ b
a
f(x)g(x)dx−
r∑
i=1
f(yi)g(yi)(xi − xi−1)
∣∣∣∣∣ < ε.
Escolha, pelo Teorema do Valor Médio, yi tal queG(xi)−G(xi−1) = g(yi)(xi−xi−1). Dessa
forma, reorganizando os termos obtemos:∣∣∣∣∣
∫ b
a
f(x)g(x)dx−
r∑
i=1
f(yi)[G(xi)−G(xi−1)]
∣∣∣∣∣ < ε
∣∣∣∣∣
∫ b
a
f(x)g(x)dx− f(y1)G(x0) + f(yr)G(xr) +
r−1∑
i=0
[f(yi)− f(yi+1)]G(xi)
∣∣∣∣∣ < ε.
Assim, usando a desigualdade triangular e fazendo ε→ 0 obtemos:
∣∣∣∣∫ b
a
f(x)g(x)dx− [f(yr)G(xr)− f(y1)G(x0)]
∣∣∣∣ ≤
∣∣∣∣∣
r−1∑
i=0
[f(yi)− f(yi+1)]G(xi)
∣∣∣∣∣+ ε
≤
r−1∑
i=0
|f(yi)− f(yi+1)||G(xi)|+ ε
=⇒
∣∣∣∣∫ b
a
f(x)g(x)dx− [f(b)G(b)− f(a)G(a)]
∣∣∣∣ ≤ V ba (f) sup |G|.
No teorema seguinte, usaremos o lema A.1.1.
Teorema A.2.3. i) Se f é uma função de variação total limitada e integrável em R então∫
R
f(x)e2piixydx = O
(
1
1 + |y|
)
.
48 APÊNDICE A. A TEORIA DE FOURIER
ii) Se f é uma função contínua em uma vizinhança do 0 e
f(x)
1 + |x| é integrável então:
lim
y→∞
∫
R
f(x)
sen(pixy)
pix
dx = f(0).
Demonstração. i) Temos que a função y → ∫ f(x)e2piixydx é limitada, logo existe C > 0 tal que∣∣∫ f(x)e2piixydx∣∣ < C para todo x. Notemos também que se f é de variação total limitada
então existem limx→±∞ f(x). Sendo f integrável obtemos limx→±∞ f(x) = 0. Usando o lema
anterior com a→ −∞, b→∞, g(x) = e2piixy e G(x) = e2piixy
2piiy
, temos:∣∣∣∣∫
R
f(x)e2piixy
∣∣∣∣ ≤ V +∞−∞ (f)2pi|y| .
Logo: ∣∣∣∣∫
R
f(x)e2piixy
∣∣∣∣ ≤ min{V +∞−∞ (f)2pi|y| , C
}
= O
(
1
1 + |y|
)
.
ii) Para a segunda parte, vamos primeiro mostrar o caso f(0) = 0 e f é crescente. Seja
G0(x) =
∫ x
0
sen(pit)
pit
dt. Temos que G0 é uma função ímpar e limitada. Aplicando o lema A.2.2
temos para todo δ > 0 e y > 0 que:∣∣∣∣∫ δ
0
f(x)
sen(pixy)
pix
dx− (f(δ)G0(δy)− f(0)G0(0))
∣∣∣∣ ,
logo pela desigualdade triangular (lembrando que f(0) = 0) temos:∣∣∣∣∫ δ
0
f(x)
sen(pixy)
pix
dx
∣∣∣∣ ≤ |f(δ)||G0(δy)|+ V δ0 (f) sup
[0,δy]
|G0|. (A.1)
Sendo f contínua em 0, dado ε > 0 existe δ > 0 tal que |x| < δ implica |f(x)| < ε. Assim,
como f é também crescente segue que V x0 (f) é contínua em 0, logo V x0 (f) < ε sempre que
|x| < δ. Dessa forma, temos:
lim sup
y→∞
∣∣∣∣∫ δ
0
f(x)
sen(pixy)
pix
dx
∣∣∣∣ ≤ ε|G0(δy)|+ ε sup
[0,δy]
|G0|
≤ 2ε sup
[0,δy]
|G0| ≤ 2ε sup |G0|
=⇒ lim
y→∞
∣∣∣∣∫ δ
0
f(x)
sen(pixy)
pix
dx
∣∣∣∣ = 0.
Por outro lado, sabemos que para o δ > 0 acima escolhido existe Cδ > 0 tal que:∣∣∣∣f(x)pix
∣∣∣∣ < Cδ |f(x)|pi(1 + |x|)
A.2. A TRANSFORMADA DE FOURIER 49
sempre que |x| ≥ δ. Logo: ∫ ∞
δ
∣∣∣∣f(x)pix
∣∣∣∣ dx < Cδpi
(∫ ∞
δ
|f(x)|
1 + |x|dx
)
,
que é finito por hipótese. Pelo teorema A.2.1 (Lema de Riemann-Lebesgue) temos:
lim
y→∞
∫ ∞
δ
f(x)
sen(pixy)
pix
dx = 0.
Fazendo o mesmo para o intervalo (−∞, 0] obtemos:
lim
y→∞
∫
R
f(x)
sen(pixy)
pix
dx = 0,
e (ii) fica provado no caso f(0) = 0 e f crescente.
Supondo agora f(0) = 0 mas f não crescente, sabemos que f pode-se escrever como
f(x) = f1(x) − f2(x), onde as fi’s são crescentes, contínuas em 0, de variação limitada em
uma vizinhança de 0, com fi(x)
1+|x| integrável e fi(0) = 0 para i = 1, 2. Logo:
lim
y→∞
∫
R
f1(x)
sen(pixy)
pix
dx = 0
lim
y→∞
∫
R
f2(x)
sen(pixy)
pix
dx = 0
=⇒ lim
y→∞
∫
R
f(x)
sen(pixy)
pix
dx = 0,
assim o teorema vale para qualquer f com f(0) = 0.
Caso f(0) 6= 0 seja g(x) = f(x)− f(0). Temos que g satisfaz todas as hipóteses e g(0) = 0.
Pelo caso acima e pelo lema A.1.1, temos:
lim
y→∞
∫
R
g(x)
sen(pixy)
pix
dx = 0
=⇒ lim
y→∞
∫
R
f(x)
sen(pixy)
pix
dx = lim
y→∞
∫
R
f(0)
sen(pixy)
pix
dx = f(0).
Seja f uma função real que toma valores complexos, periódica de período 1 (ou seja,
f(x + n) = f(x) para todo x ∈ R e n ∈ Z). Temos que f pode ser vista como uma função do
quociente R/Z em C. Se f ∈ L1(R/Z) definimos sua transformada de Fourier como:
f̂(n) =
∫
R/Z
f(x)e−2piinxdx.
Teorema A.2.4. Seja f ∈ L1(R/Z). Suponhamos que f é contínua em x e é de variação limitada em
50 APÊNDICE A. A TEORIA DE FOURIER
uma vizinhança de x. Então:
lim
N→∞
∑
|n|≤N
f̂(n)e2piinx = f(x).
Demonstração. Substituindo a definição de f̂ no lado esquerdo acima sem o limite obtemos:
N∑
n=−N
(∫ 1/2
−1/2
f(y)e−2piinydy
)
e2piinx =
∫ 1/2
−1/2
(
N∑
n=−N
f(y)e2piin(x−y)
)
dy
=
∫ 1/2
−1/2
f(y)H(x, y)dy,
onde:
H(x, y) :=

[
e(N+1/2)2pii(x−y) − e−(N+1/2)2pii(x−y)
epii(x−y) − e−pii(x−y)
]
, se x 6= y
2N + 1, se x = y
=

sen[(2N + 1)pi(x− y)]
sen[pi(x− y)] , se x 6= y
2N + 1, se x = y.
Observemos que a função H é contínua em R2. Logo:
N∑
n=−N
(∫ 1/2
−1/2
f(y)e−2piinydy
)
e2piinx =
∫ 1/2
−1/2
f(y)
sen[(2N + 1)pi(x− y)]
sen[pi(x− y)] dy.
Fazendo u = y − x⇒ du = dy, segue pela continuidade de H que a anterior soma vale:
lim
ε→0+
∫ −ε
−1/2
f(u+ x)
sen[(2N + 1)piu]
sen(piu)
du+ lim
ε→0+
∫ 1/2
ε
f(u+ x)
sen[(2N + 1)piu]
sen(piu)
du
=
∫
R
hx(u)
sen[(2N + 1)piu]
piu
du,
onde:
hx(u) :=

f(u+ x)
piu
sen(piy)
, se 0 < |u| ≤ 1/2
f(x), se u = 0
0, se |u| > 1/2.
Pelo teorema A.2.3 temos que lim
N→∞
∫
R
hx(u)
sen[(2N + 1)piu]
piu
= hx(0) = f(x).
O teorema seguinte (devido a Dirichlet) é parecido com o teorema acima, com a diferença
de que no teorema abaixo a função f não é periódica.
A.3. O SOMATÓRIO DE POISSON 51
Teorema A.2.5. Suponhamos que f ∈ L1(R) e que x ∈ R. Suponhamos também que f é de variação
limitada em uma vizinhança de x e que f é contínua em x. Então:
lim
Y→∞
∫ Y
−Y
f̂(y)e2piixydy = f(x).
Demonstração. A prova é completamente análoga à do teorema anterior.
A.3 O somatório de Poisson
Teorema A.3.1 (Fórmula do Somatório de Poisson). Seja f : R → R uma função contínua,
integrável e de variação total limitada. Suponhamos que exista uma função integrável par g : R →
R+ e decrescente em R+. Se |f(x)| ≤ g(x) para todo x então:
∑
n∈Z
f(x+ n) = lim
M→∞
M∑
m=−M
f̂(m)e2piimx.
Demonstração. Pelos critério de Cauchy e critério de Weierstrass, o lado esquerdo acima con-
verge para uma função contínua de x. Como f é de variação total limitada segue que o
mesmo lado esquerdo é também uma função de variação total limitada. E mais: essa função
é periódica de período 1, logo pertence a L1(R/Z). Seja F (x) =
∑
n∈Z f(x+n). Pelo Teorema
da Convergência Dominada temos que:
F̂ (m) =
∫
R/Z
F (x)e−2piimxdx =
∫ 1
0
F (x)e−2piimxdx
=
∫ 1
0
∑
n∈Z
f(x+ n)e−2piimxdx =
∑
n∈Z
∫ 1
0
f(x+ n)e−2piimxdx
=
∑
n∈Z
∫ n
n−1
f(x)e−2piimxdx =
∫
R
f(x)e−2piimxdx = f̂(m).
Logo, esse teorema segue pelo teorema A.2.4 aplicado para a função F .
Corolário A.3.2. Nas mesmas condições do teorema anterior temos:∑
n∈Z
f(n) =
∑
m∈Z
f̂(m).
52 APÊNDICE A. A TEORIA DE FOURIER
Apêndice B
Riemann, Dirichlet e os teoremas dos
números primos
Esse apêndice é dedicado ao estudo dos teoremas dos números primos, que será útil na
demonstração da não vacuidade dos conjuntos A e, portanto, B e E . Veremos adiante que
o Teorema dos Números Primos está intimamente ligado à função Zeta de Riemann, en-
quanto sua generalização, o Teorema dos Números Primos em Progressão Aritmética, está
intimamente ligado à uma generalização da função Zeta: as L-séries de Dirichlet.
B.1 A função ζ de Riemann
Nessa seção apenas enunciaremos alguns resultados clássicos acerca da função Zeta. Todas
as demonstrações podem ser encontradas em [3]. Começamos relembrando a definição (que
já foi dada no capítulo 1), a fatoração de Euler e a primeira parte da extensão.
Definição B.1.1. Definimos a função Zeta de Riemann como a única extensão meromorfa de:
ζ(s) =
∑
n≥1
1
ns
(B.1)
para o plano complexo.
Teorema B.1.1 (Euler). A função Zeta satisfaz:
ζ(s) =
∏
p
(
1− 1
ps
)−1
. (B.2)
Sabemos que a soma definida em (B.1) só faz sentido se σ > 1. Podemos estendê-la para
σ > 0 usando a integrando de Riemann-Stieltjes por partes, donde segue que:
ζ(s) =
s
s− 1 − s
∫ ∞
1−
{t}
ts+1
dt.
Notemos que a expressão do lado direito acima tem um polo simples em s = 1.
53
54 APÊNDICE B. RIEMANN, DIRICHLET E OS TEOREMAS DOS NÚMEROS PRIMOS
Definição B.1.2. Para σ > 0 definimos a função Gamma como Γ(s) =
∫ ∞
0
e−tts−1dt.
A função Γ(s) é uma "extensão" da função fatorial nos naturais, pois Γ(1) = 1 e:
Γ(s+ 1) = sΓ(s) (B.3)
sempre que <(s) > 0. Portanto, para n ∈ Z temos Γ(n+ 1) = n!.
Podemos estender a função Γ para o resto do plano usando a equação funcional (B.3), o
que nos leva a:
Γ(s− n) = Γ(s)
(s− 1)(s− 2) . . . (s− n) ,
logo Γ possui polos simples nos inteiros negativos.
A função ζ possui um polo simples em s = 1 de resíduo 1. Ademais, ζ satisfaz a equação:
pi−s/2Γ
(s
2
)
ζ(s) = pi−(1−s)/2Γ
(
1− s
2
)
ζ(1− s).
Isso significa que a função (por enquanto definida para σ > 0):
ξ(s) :=
1
2
s(s− 1)pi−s/2Γ(s/2)ζ(s)
é simétrica em relação à reta σ = 1/2 e é holomorfa, já que Γ é holomorfa em σ > 0 e ζ possui
polo em s = 1 que é cancelado com o fator s−1. Estendendo-a para todo o plano como ξ(s) =
ξ(1 − s) obtemos que ζ possui zeros simples nos inteiros negativos pares (−2,−4,−6, . . . ),
uma vez que Γ possui polos simples nos inteiros negativos. Esses zeros de ζ são chamados
zeros triviais. Concluimos que em σ > 1 a função ζ não tem zeros e em σ < 0 a função
ζ só possui os zeros triviais. O caso difícil ocorre quando 0 ≤ σ ≤ 1 e essa é a chamada
"faixa crítica". Segundo a Hipótese de Riemann, que é um dos problemas em aberto mais
importantes da matemática, os zeros não triviais da função ζ , que são infinitos enumeráveis,
estão todos sobre a reta σ = 1/2.
Definição B.1.3. Seja f : C → C uma função inteira. Dizemos que f tem ordem finita se existe α
tal que para todo β > α temos f(z) = O(eβ|z|). Nesse caso, dizemos também que f tem ordem α.
O capítulo 11 de [3] mostra que se f tem ordem 1, f(0) 6= 0 e {sn} são os zeros de f então
podemos escrever:
f(s) = eA+Bs
∞∏
n=1
(
1− s
sn
)
es/sn
e o capítulo seguinte mostra que ξ tem ordem 1. Dois resultados demasiado importantes ao
se definir a função ξ são a simetria e o fato de que os zeros de ξ são exatamente os zeros não
triviais de ζ , pois esses são os únicos que não serão cancelados com os polos de Γ. Logo,
B.2. O TEOREMA DOS NÚMEROS PRIMOS 55
sendo ρ os zeros de ξ existem A e B complexos tais que:
ξ(s) = eA+Bs
∏
ρ
(
1− s
ρ
)
es/ρ. (B.4)
Temos que eA = ξ(0) = ξ(1) = 1
2
pi−1/2Γ(1/2) lim
s→1
(s − 1)ζ(s) = 1/2, logo A = − log 2.
A constante B é obtida combinando derivações logaritmicas de algumas das equações já
citadas e seu valor é B = 1
2
log 4pi − 1
2
γ − 1, como foi mostrado no capítulo 12 de [3]. Com
isso, é fácil mostrar que se ρ = β + iθ é um zero de ζ então |θ| > 6.
As equações (B.2) e (B.4) determinam duas fatorações boas para a função Zeta: uma em
função dos números primos e a outra em função das suas raízes.
É conhecido que a função ζ não possui zeros em σ = 1, como foi mostrado no capítulo 13
de [3]. Com isso, é fácil mostrar, pela simetria da função ξ, que ζ também não possui zeros
em σ = 0. E vale mais:
Teorema B.1.2. Seja ρ = β + iθ um zero da função ζ . Então:
1. |θ| > 6;
2. existe c > 0 tal que β < 1− c
log θ
.
Seja N(T ) o número de zeros de ζ(s) no retângulo 0 < σ < 1, 0 < θ < T . Assumimos que
T não coincide com a parte imaginária de nenhum zero de ζ . O capítulo 15 de [3] é dedicado
a mostrar que:
N(T ) =
T
2pi
log
T
2pi
− T
2pi
+O(log T ). (B.5)
B.2 O Teorema dos Números Primos
Definição B.2.1. A função Λ : N→ R de von Mangoldt é definida por:
Λ(n) =
log p, se n = pk para algum k ∈ N∗;0, caso contrário.
Definição B.2.2. A função ψ : R→ R de Tchebyshev é definida por:
ψ(x) =
∑
n≤x
Λ(n).
O capítulo 17 de [3] mostra que se ρ = β + iθ percorre as raízes não triviais de ζ então:
ψ(x) = x−
∑
|θ|<T
xρ
ρ
− ζ
′(0)
ζ(0)
− 1
2
log(1− x−2) +R(x, T ), (B.6)
56 APÊNDICE B. RIEMANN, DIRICHLET E OS TEOREMAS DOS NÚMEROS PRIMOS
onde |R(x, T )| = O
(
x log2(xT )
T
+ log xmin
{
1,
x
T 〈x〉
})
e 〈x〉 é a diferença entre x e a potên-
cia de primo mais próxima, distinta de x caso x seja potência de primo. Em particular:
ψ(x) = x−
∑
ρ
xρ
ρ
− ζ
′(0)
ζ(0)
− 1
2
log(1− x−2).
Como consequência das equações (B.6) e (B.5) e parte 2 do teorema B.1.2, escolhendo T
tal que (log T )2 = log x, existe c > 0 tal que:
ψ(x) = x+O(xe−c(log x)
1/2
), (B.7)
e essa equação implica o:
Teorema B.2.1 (dos Números Primos). Existe c0 > 0 tal que se li(x) :=
∫ x
2
dt
log t
então:
pi(x) = li(x) +O(xe−c0(log x)
1/2
).
A prova de que a equação B.7 implica o teorema acima pode ser encontrada no capítulo
18 de [3]. Essa versão do Teorema dos Números Primos é uma forma mais forte que a dada
pelo teorema 0.0.5 na introdução, pois ela determina o erro ao aproximar pi(x). Além disso,
não é difícil mostrar que:
lim
x→∞
li(x)
x/ log x
= 1.
Por outro lado, se optarmos por fazer d = 1 no lema B.4.1 então obtemos diretamente a
forma do Teorema dos Números Primos enunciada na introdução.
B.3 As L-séries de Dirichlet
Essa seção é dedicada ao estudo das L-séries de Dirichlet. Como veremos, todos os resulta-
dos são de certa forma análogos aos da função Zeta e todas as afirmações que fizemos estão
demonstradas em [3].
Definição B.3.1. Seja χ um caráter módulo q. Definimos uma L-série de Dirichlet como a única
extensão meromorfa de:
L(s, χ) =
∑
n≥1
χ(n)
ns
(B.8)
para o plano complexo.
Teorema B.3.1 (Euler). As L-séries satisfazem:
L(s, χ) =
∏
p
(
1− χ(p)
ps
)−1
.
B.3. AS L-SÉRIES DE DIRICHLET 57
Seja q ≥ 1 inteiro. Aplicando a fórmula de Euler podemos relacionar ζ e L pela equação:
L(s, χ1) = ζ(s)
∏
p|q
(
1− 1
ps
)
.
Notemos que o símbolo de Legendre é um caráter. Notemos também que semdc(n, q) = 1
então n é invertível módulo p e assim χ(n) = χ(n−1). Definimos a soma de Gauss vista pelo
caráter módulo q como:
τ(χ) =
q∑
m=1
χ(m)e2piim/q.
É conhecido que |τ(χ)| = √q (ver capítulo 9 de [3]).
Podemos definir ξ para caráteres. Seja χ um caráter módulo q. Em σ > 0, tomemos:
ξ(s, χ) :=
(
pi
q
)−(s+a)/2
Γ
(
s+ a
2
)
L(s, χ). (B.9)
A simetria de ζ é transferida para as L-séries como:
ξ(1− s, χ) = i
a√q
τ(χ)
ξ(s, χ),
onde:
a =
0, se χ(−1) = 11, se χ(−1) = −1.
Como na função ζ , os zeros importantes das L-séries são os que ficam na faixa crítica
0 < <s < 1. A Hipótese Generalizada de Riemann (outro problema em aberto) diz que
todos esses zeros têm a parte real igual a 1/2.
Novamente análogo à ξ(s), que é de ordem 1 (como mostrado no capítulo 12 de [3]),
podemos escrever:
ξ(s, χ) = eA+Bs
∏
ρ
(
1− s
ρ
)
es/ρ,
mas dessa vezA eB dependem de χ. De fato,A = log ξ(0, χ), que podemos também escrever
em termos de L(1, χ). Quanto a B, temos <B(χ) = −1
2
∑
ρ
(
1
ρ
+
1
ρ
)
= −
∑
ρ
<1
ρ
. Em
particular, se χ é real então B(χ) é negativo e vale o mesmo tanto que no caso da função
ζ . A dificuldade em estimar B(χ) está relacionada ao fato de que L(s, χ) pode ter um zero
próximo de s = 0. Observamos ainda que para um caráter complexo χ, os zeros de L(s, χ)
são simétricos em relação a σ = 1/2, mas não são simétricos em relação ao eixo real.
Mesmo podendo ter um zero próximo a s = 0, L(s, χ) ainda possui uma região sem
zeros, como a que foi dada pelo teorema B.1.2 no caso da função ζ . De fato, o capítulo 14 de
[3] mostra que:
Teorema B.3.2. Existe c > 0 tal que:
58 APÊNDICE B. RIEMANN, DIRICHLET E OS TEOREMAS DOS NÚMEROS PRIMOS
1. Se χ é um caráter complexo módulo q então L(s, χ) não tem zeros na região definida por:
σ >

1− c
log q|θ| , se |θ| ≥ 1;
1− c
log q
, se |θ| < 1.
2. Se χ é um caráter real não trivial então L(s, χ) pode ter um único zero na região acima. Se
existir, esse zero β+ iθ será real e simples e irá satisfazer β ≥ 1− c/(√q log2 q). (Se a Hipótese
Generalizada de Riemann for verdadeira então tal zero não existe.)
Seja χ um caráter módulo q. Definimos N(T, χ) como o número de zeros de L(s, χ) no
retângulo 0 < σ < 1, |θ| < T . Assumimos que T não coincide com a parte imaginária de
nenhum zero de L(s, χ). O capítulo 16 de [3] mostra que:
1
2
N(T, χ) =
T
2pi
log
qT
2pi
− T
2pi
+O(log T + log q). (B.10)
O fator 1/2 no lado esquerdo acima é devido ao fato de que tomamos |θ| < T em relação a
N(T, χ) e não 0 < θ < T , como em N(T ).
B.4 O Teorema dos Números Primos em Progressão Aritmética
Análogo à função de Tchebyshev, se χ é um caráter módulo q e mdc(q, a) = 1 então definimos
as funções:
Definição B.4.1.
ψ(x; q, a) :=
∑
n≤x
n≡a (mod q)
Λ(n);
ψ(x, χ) :=
∑
n≤x
Λ(n)χ(n).
O capítulo 19 de [3] mostra que se χ 6= χ1, 2 ≤ T ≤ x e β1 é o possível zero real de L(s, χ)
(que se existe é necessariamente único e simples) então:
ψ(x, χ) = −x
β1
β1
−
∑
|t|<T
xρ
ρ
+R0(x, T ), (B.11)
onde |R0(x, T )| = O
(
x(log qx)2
T
+ x1/4 log x
)
e a soma ocorre sobre as raízes ρ 6∈ {β1, 1− β1}
de L(s, χ). O termo em β1 acima pode ser removido se tal raiz não existe, como no caso dos
caráteres complexos.
B.4. O TEOREMA DOS NÚMEROS PRIMOS EM PROGRESSÃO ARITMÉTICA 59
Pela definição acima e pelas relações de ortogonalidade vistas na seção 2.1, segue que:
ψ(x; q, a) =
1
ϕ(q)
∑
χ
ψ(x, χ)χ(a) (B.12)
Além disso, o capítulo 20 de [3] mostra que ψ(x, χ1) é bem aproximado por ψ(x), isto é:
|ψ(x, χ1)− ψ(x)| = O(log q. log x),
mas pela equação (B.7) temos ψ(x) = x + O(xe−c(log x)1/2). Portanto, usando a aproximação
acima ao separar o caráter trivial da soma na equação (B.12), temos:
ψ(x; q, a) =
x
ϕ(q)
+
1
ϕ(q)
∑
χ 6=χ1
χ(a)ψ(x, χ) +O
(
xe−c(log x)
1/2
+ (log qx)2
ϕ(q)
)
. (B.13)
A equação (B.11) pode ser compactada usando o teorema B.3.2 e a equação (B.10), que
nos leva a:
ψ(x, χ) = −x
β1
β1
+R1(x, T ),
onde |R1(x, T )| = O
(
x(log qx)2e−c(log x)/ log qT +
x(log qx)2
T
+ x1/4 log x
)
. Notemos que ao es-
colher q ≤ eC(log x)1/2 e T = eC(log x)1/2 para qualquerC > 0 teremos |R1(x, T )| = O(xe−C′(log x)1/2)
para algum C ′ (que depende unicamente de C), logo:
ψ(x, χ) = −x
β1
β1
+O(xe−C
′(log x)1/2),
e assim obtemos:
ψ(x; q, a) =
x
ϕ(q)
− χ1(a)x
β1
ϕ(q)β1
+O(xe−C
′(log x)1/2). (B.14)
Lema B.4.1. Sejam d, a inteiros positivos primos entre si. Então:
lim
y→∞
pi(y; d, a)
y/ log y
= lim
y→∞
ψ(y; d, a)
y
.
Demonstração. Seja M :=
⌊
log y
log 2
⌋
. Temos:
ψ(y; d, a) =
∑
p≤y
p≡a (mod d)
log p+
∑
pm≤y
pm≡a (mod d)
m≥2
log p ≤ log y
∑
p≤y
p≡a (mod d)
1 +
M∑
m=2
log y.pi(y1/m)
≤ log y.pi(y; d, a) +M log y.pi(y1/2) ≤ log y.pi(y; d, a) + log
2 y
log 2
pi(y1/2),
o que implica:
lim
y→∞
ψ(y; d, a)
y
≤ lim
y→∞
pi(y; d, a)
y/ log y
.
60 APÊNDICE B. RIEMANN, DIRICHLET E OS TEOREMAS DOS NÚMEROS PRIMOS
Por outro lado, se 1 < w < y então:
pi(y; d, a) = pi(w; d, a) +
∑
w<p≤y
p≡a (mod d)
1 ≤ w +
∑
w<p≤y
p≡a (mod d)
log p
logw
≤ w + ψ(y; d, a)
logw
,
e escolhendo w = y
log2 y
obtemos:
pi(y; d, a)
y/ log y
≤ 1
log y
+
ψ(y; d, a)
y
log y
log y − 2 log log y ,
o que implica:
lim
y→∞
pi(y; d, a)
y/ log y
≤ lim
y→∞
ψ(y; d, a)
y
.
O lema acima aliado ao Teorema dos Números Primos nos diz que a equação (B.14)
implica o:
Teorema B.4.2 (dos Números Primos em Progressão Aritmética). Seja C > 0. É válida a
Propriedade dos Números Primos em Progressão Aritmética com parâmetro eC(log x)1/2 . Em outras
palavras, dado ε > 0 existe x0 tal que, se x ≥ x0 e a, q são inteiros positivos primos entre si com
q ≤ eC(log x)1/2 , então: ∣∣∣∣pi(x; q, a)pi(x) − 1ϕ(q)
∣∣∣∣ < εϕ(q) .
O teorema de Dirichlet (0.0.6) enunciado na introdução é corolário do teorema acima,
pois fixados a, q inteiros positivos primos entre si então dado C > 0 temos q ≤ eC(log x)1/2
para todo x grande.
Apêndice C
Sobre os zeros das L-séries
C.1 Uma cota para os zeros
Nessa seção, enunciaremos os lemas para a demonstração do teorema 4.4.4, que também está
enunciado a seguir. Tanto os lemas quanto o teorema estão provados em [7]. Em particular,
veremos que existe A > 2 para os quais existe γ(A) ≥ 1 tal que para todo σ ≥ 1 − 1/A e
T ≥ 1,
N(σ, T, d) ≤ γ(A)(Td)A(1−σ)
para todo d inteiro positivo. Em outras palavras, teremos que A 6= ∅, o que implicará que
existem infinitos números de Carmichael.
Teorema C.1.1. Seja 0 < ε < 1/5. Para todos 1− ε < σ ≤ 1 e T ≥ 1 existe γ(ε) ≥ 1 tal que:
N(σ, T, d) ≤ γ(ε)(Tq)(2+ε)(1−σ).
Começamos com uma definição:
Definição C.1.1. Sejam r um inteiro livre de quadrados e f : N∗ → R uma função multiplicativa.
Definimos pseudocaráter como a função fr : N∗ → R tal que fr(n) = f(mdc(r, n)).
Não é difícil mostrar que pseudocaráteres são funções multiplicativas e periódicas. Além
disso, por questões de simplicidade vamos denotar frfr′(n) = fr(n)fr′(n) e
∑′ como a soma
sobre todos os números livres de quadrado coprimos com q, onde q é um inteiro positivo.
Lema C.1.2. Seja:
M(s, χ, fr) :=
∞∑
d=1
ξdχ(d)fr(d)
ds
∏
p| r
mdc(r,d)
[
1 + (f(p)− 1)χ(p)
ps
]
,
onde ξd = O(1). Se <s > 1 então:
L(s, χ)M(s, χ, fr) =
∞∑
n=1
∑
d|n
ξd
 χ(n)fr(n)
ns
. (C.1)
61
62 APÊNDICE C. SOBRE OS ZEROS DAS L-SÉRIES
Lema C.1.3. Se os números h(d; r, r′) são definidos pela equação:
∏
p|rr′
p 6|mdc(r,r′)
[
1 +
f(p)− 1
ps
] ∏
p|mdc(r,r′)
[
1 +
(f(p))2 − 1
ps
]
=
∞∑
d=1
h(d; r, r′)
ds
então frfr′(n) =
∑
d|n
h(d; r, r′).
Lema C.1.4. Seja f(n) := µ(n)ϕ(n). Temos:
∑
d
h(d; r, r′)
d
= δ(r − r′)ϕ(r),
onde δ(r − r′) é o delta de Kronecker. Além disso:∑
d
|h(d; r, r′)| ≤
∏
p|r
(p+ 1)
∏
p|r′
(p+ 1).
Sejam 1 < z1 < z2 números reais. Definimos a forma quadrática:
S :=
∑
n≤x
∑
d|n
λd
2
onde
λd =

µ(d), se 1 ≤ d < z1,
µ(d) log(z2/d)/ log(z2/z1), se z1 ≤ d ≤ z2,
0, se d > z2.
Lema C.1.5.
S =

x
log(z2/z1)
+O
(
x
log2(z2/z1)
)
, se x > z2,
x log(x/z1)
log2(z2/z1)
+O
(
x
log2(z2/z1)
)
, se z1 < x < z2.
Lema C.1.6. Se logR ≥ (log q)1/2 e R→∞ então:
∑
r≤R
′
r−1 = 6pi−2
∏
p|q
(logR)(1 + o(1))
1 + p−1
Seja χ um caráter não trivial módulo q e seja ρ = β + iθ um zero da função L(s, χ) no
retângulo R(σ, T ) := [σ, 1] × [−T, T ]. Definimos também f(n) := µ(n)ϕ(n) (como no lema
C.1.4), ξd := λd e a(n) :=
∑
d|n λd. Além disso, suponha que 1/2 ≤ σ < 1, T ≥ 1, ε > 0 e que
os números R ≥ 1 e X ≥ 1 satisfazem:(log q)1/2 ≤ logR = O(qT ),Xσ ≥ [(qT )1/2Rz2]1+ε. (C.2)
C.1. UMA COTA PARA OS ZEROS 63
Definimos x := X log2(qT ) e:
g(s, χ) :=
∑
z1<n≤x
a(n)χ(n)e−n/Xn−s
′∑
r≤R
r−1fr(n).
Lema C.1.7. É válido que:
|g(ρ, χ)| ≥ (1− ε)ϕ(q)
q
6
pi2
logR.
Lema C.1.8. Seja:
f(s, χ) =
N∑
n=1
anχ(n)
ns
.
Temos que: (
J∑
j=1
|f(sj, χj)|
)2
≤
N∑
n=1
|an|2
bn
J∑
j,k=1
ηjηkB(sj + sk, χjχk),
onde os ηj’s são números complexos unitários e B(s, χ) :=
∑∞
n=1 bnχ(n)n
−s, onde os bn’s são quais-
quer números reais positivos tais que a série B(s, χ) é absolutamente convergente para todo par
(s, χ) = (sj + sk, χjχk).
Lema C.1.9. O número de zeros de L(s, χ) no quadrado [σ, 1]× {|t− T | ≤ (1− σ)/2} é:
O((1− σ) log(q(T + 1)) + 1)
Como pode ser visto em [7], os lemas acima são usados para demonstrar o teorema cen-
tral desse apêndice, que foi enunciado também em 4.4.4.
64 APÊNDICE C. SOBRE OS ZEROS DAS L-SÉRIES
Referências Bibliográficas
[1] ALFORD, W. R.; GRANVILLE, A.; POMERANCE, C. There are infinitely many
Carmichael numbers. Annals of Mathematics, 1994.
[2] BOMBIERI, E.; Le Grand Crible dans la Théorie Analytique des Nombres, second edi-
tion. Astérisque 18, 1987.
[3] DAVENPORT, H.; Multiplicative number theory. Springer-Verlag, 1980.
[4] GE, Y.; A note on the Carmichael Function. Mathematical Reflections, 2007.
[5] HARDY, G. H., ROGOSINSKI, W. W.; Fourier series. Cambridge: University Press,
1956.
[6] HARMAN, G.; On the number of Carmichael numbers up to x. Bull. London Math.
Soc., 2005.
[7] JUTILA. J.; On Linnik’s constant. Math. Scand. 41, 1977.
[8] MARTINEZ, F. B.; et al. Teoria dos Números: um passeio com primos e outros números
familiares pelo mundo inteiro. Rio de Janeiro: IMPA, 2010.
[9] PATTERSON, S. J.; An introduction to the theory of the Riemann zeta-function. Cam-
bridge studies in advanced mathematics, 1988.
[10] TENENBAUM, G.; Introduction to analytic and probabilistic number theory. Cam-
bridge studies in advanced mathematics, 1990.
65