UMA FÓRMULA DE LEGENDRE
Roberto Ribeiro Paterlini
Dedico este artigo aos matemáticos amadores
André Barbosa de Almeida Setti
Maria Helena Vidigal Barbosa de Almeida
Maria Isabel Vidigal Barbosa de Almeida
Os métodos de crivagem para determinação dos números primos são utilizados desde o tempo dos antigos gregos. É bem conhecido o chamado Crivo de Eratóstenes (confira [4] página 12). Posteriormente este método foi desenvolvido para a determinação de números primos especiais. Depois os métodos de crivagem começaram a ser utilizados para contagem de primos. Esta história está parcialmente contada em [1] página 429. Confira também [3] página 120 e [5] página 140. Após os trabalhos de V. Brun os métodos de crivagem passaram a ser utilizados mais extensivamente em Teoria dos Números. Confira [2].
A fórmula de Legendre
Legendre, em 1808, apresentou uma fórmula para determinar a quantidade de números
primos
,
onde
é um inteiro
.
Vamos apresentar e explicar esta fórmula.
Utilizamos a notação
maior dentre os inteiros
.
A função
é chamada função do maior inteiro. Por exemplo,
,
,
,
.
Começaremos com o seguinte resultado:
Lema Se
e
são inteiros positivos então
é o número dos inteiros do conjunto
que são divisíveis por
.
Demonstração. Se
,
nenhum inteiro de
é divisível por
.
Como
temos
,
e o resultado vale neste caso. Suponhamos
.
Seja 
o número de inteiros do conjunto
que são divisíveis por
.
Esses números são
,
,
,
,
.
Temos
,
portanto
.
Daí
(pois
é o maior inteiro
).
Isto termina a demostração do Lema.
Assim, dado
inteiro, a quantidade de números pares de 1 a
é
.
Por exemplo, se 
,
existem
números pares de 1 a 1000 (incluindo o próprio número 2). Por outro lado, de 1 a
1000 existem
números que
são divisíveis por 3.
Vamos calcular a quantidade de números em
que são divisíveis por 2 ou por 3. Aproveitaremos para introduzir uma
notação que vai ser útil mais adiante. Seja
conjunto dos inteiros de 1 a
que são divisíveis por 2 e seja
conjunto dos inteiros de 1 a
que são divisíveis por 3. Queremos encontrar o número de elementos de
.
Dado um conjunto
,
indicaremos por
o número de elementos de
.
Notemos que se
e
são conjuntos quaisquer, então
Este é o chamado Princípio da Inclusão-Exclusão.
Aplicando isso em nosso caso, temos
Para calcular
notemos primeiro que
é o conjunto dos números de 1 a
que são simultaneamente divisíveis por 2 e por 3. Como 2 e 3 são relativamente
primos estes são os números que são divisíveis por
.
Portanto
Com isso podemos completar a fórmula acima: a quantidade de números em
que são divisíveis por 2 ou por 3 é
Seja agora
o conjunto dos inteiros de 1 a
que são divisíveis por 5 (incluindo o próprio 5). Queremos encontrar o
número de elementos de
.
Começamos observando o Princípio da Inclusão-Exclusão para três
conjuntos:
Portanto a quantidade de números de 1 a
que são divisíveis por 2, 3 ou 5 é
Para generalizar esta fórmula usaremos a seguinte versão do Princípio da Inclusão-Exclusão:
Proposição. Seja
um conjunto e sejam
,
,
,
subconjuntos de
.
Então
onde
Demonstração: Confira [6], páginas 53 e 150.
Com esta proposição podemos obter uma fórmula para contagem de primos. Seja
um inteiro, e seja
o conjunto dos inteiros de 1 a
.
Sejam
os primos
.
Indiquemos por
o subconjunto de
formado pelos inteiros que são divisíveis por
(incluindo o próprio
).
Então
é o conjunto dos inteiros de 1 a
que são compostos e mais os primos acima. Lembrando que 1 não é primo, a
quantidade de números primos de 1 a
é
Esta fórmula tem uma versão mais compacta. Dado um número real
,
indicaremos por
a quantidade de números primos
.
é chamada função de contagem dos primos ou função densidade
dos primos. Consideremos ainda a função de Möbius
A fórmula de Legendre dada acima pode ser escrita
onde a soma se estende a todos os divisores
do produto dos primos
.
A fórmula de Legendre tem mais interesse teórico do que prático. Ela
não evita que, para se calcular
,
se tenha que calcular os números primos
.
Referências
[1] Dickson, E. L., History of The Theory of Numbers. Volume 1. New York, Chelsea Publishing Company, 1952.
[2] Halberstam, H. e Richert, H. E., Sieve Methods. London, Academic Press, 1974.
[3] Ribenboim, P., The Little Book of Big Primes. New York, Springer Verlag, 1991.
[4] Santos, J. P. de O., Introdução à Teoria dos Números.
Coleção Matemática Universitária. Rio de Janeiro, Instituto de
Matemática Pura e Aplicada, 1998.
[5] LeVeque, W. J., Fundamentals of Number Theory. Reading Massachusets,
Addison-Wesley, 1977.
[6] Morgado, A. C. O., Carvalho, J. B. P., Carvalho, P. C. P. e Fernandez, P.,
Análise Combinatória e Probabilidade. Coleção Professor de
Matemática. Rio de Janeiro, Sociedade Brasileira de Matemática, 1991.
Início desta página
Apresentado para publicação em 20/11/2001 por Roberto R. Paterlini, do DM-UFSCar.
Preparado para publicação na Internet por Roberto R. Paterlini, do DM-UFSCar.
Parcialmente utilizado o sistema Latex2html. Confira
General License Agreement and Lack of Warranty sobre condições de uso.
Publicado em 09/01/2002. Atualizado em 12/05/2002.