Centro de Ciências Exatas e Tecnológicas - CCET
UNIOESTE- CASCAVEL
XXV Semana Acadêmica da Matemática - 15 a 19 de Agosto de 2011
Números Primos e o Crivo de Erastótenes
Profa. Raquel Lehrer
1. O que é um número primo?
Um número p ∈ N é denominado primo, se p > 1 e se seus únicos
divisores naturais são p e 1. Indicamos por
P = {p ∈ N|p primo} ,
o conjunto de todos os números primos.
Um número n > 1 é dito composto se ele não é primo. Assim, n é
composto, se existem r, s ∈ N, 1 < s ≤ r < n com n = rs.
Tarefa 1: Quais os números primos que você conhece?
2. Por que o nome primo ?
Muitas pessoas acham que a palavra primo - para denotar os números
primos - está associada a alguma analogia de parentesco. Como veremos,
isso é totalmente falso. Esse ”primo” refere-se à ideia de primeiro, e tem
sua origem numa velha concepção numérica dos pitagóricos.
A noção de número primo foi, muito provavelmente, introduzida por
Pythagoras, 530 a.C., sendo que a mesma desempenhou um papel central
tanto na matemática como no misticismo pitagórico. A escola pitagórica
dava grande importância ao número um, que era chamada de unidade (em
grego: monad). Os demais números inteiros naturais - 2, 3, 4, etc tinham um caráter subalterno, sendo vistos como meras multiplicidades
geradas pela unidade e por isso recebiam a denominação número (em grego:
1
arithmós). Era como se tivéssemos uma famı́lia, onde a mãe era a monad
( unidade ) e os filhos os arithmói ( os números ).
Entre os pitagóricos, a preocupação com a geração dos números não
parava aı́. Já o próprio Pythagoras teria atinado que existem dois tipos de
arithmói:
a) os protoi arithmói ( números primários ou primos ) que são aqueles
que não podem ser gerados - via multiplicação - por outros arithmói,
como é o caso de 2, 3, 5, 7, 11, ...
b) os deuterói arithmói ( números secundários ) que são os que podem
ser gerados por outros arithmói, como é o caso de 4 = 2.2, 6 = 2.3,
8 = 2.4, 9 = 3.3, etc.
Assim, os primeiros matemáticos gregos dividiam o que hoje chamamos
de números inteiros naturais em três classes:
a) a monad ( ou unidade, ou 1 )
b) os protói arithmói ( números primos ) ou asynthetói arithmói ( números
incompostos ):2, 3, 5, 7, 11, etc.
c) os deuterói arithmói ( números secundários ) ou synthetói arithmói
( números compostos ):4, 6, 8, 9, 10, etc.
Entre os gregos, principalmente entre gregos pitagóricos de várias gerações
depois de Pythagoras, surgiram outras denominações para os números primos, como: retilı́neos, lineares e eutimétricos. Contudo, elas tiveram uso
muito restrito e cairam no desuso.
Acima, dissemos que ”a noção de número primo foi, muito provavelmente, introduzida por Pythagoras”. Com efeito, é impossı́vel ter completa
segurança nessa atribuição, pois Pythagoras não deixou nenhum escrito e
os documentos mais antigos que temos falando de suas ideias resumem-se
a pequenos fragmentos de textos escritos várias gerações depois dele. Contudo, esses fragmentos, apesar de conterem muito escassas informações, são
unânimes em afirmar que Pythagoras iniciou o estudo dos números primos.
O mais antigo livro de matemática que chegou completo aos nossos
tempos e que desenvolve sistematicamente o estudo dos números primos
é o Elementos de Euclides (300 a.C.). Como é sabido, Euclides seguiu
muito de perto a orientação matemática dos pitagóricos. Assim, não é
surpreendente que, no capı́tulo em que trata da Teoria dos Números, ele
defina número primo de um modo absolutamente compatı́vel com as idéias
2
pitagóricas expostas acima. Com efeito ( Elementos, VII, def.11 , na versão
de Heath ):
Número primo é todo aquele que só pode ser medido através da unidade.
A Arithmetiké do grego Nikomachos,( 100 d.C.), é o mais antigo livro
de Teoria dos Números, posterior ao Elementos de Euclides, que chegou até
nossos dias. Trata-se de uma visão filosófica e letrada do Elementos, sendo
que não há uma única demonstração entre os poucos tópicos abordados.
Apesar disso, teve grande repercussão na época e foi a base do primeiro
livro em latim que se escreveu sobre Teoria dos Números: o De Institutione
Arithmetica, do romano Boethius ( 500 d.C.). No livro de Boethius é onde
aparece, pela primeira vez, a denominação numerus primus como tradução
da tradicional protós arithmós preservada de Euclides por Nikomachos.
Ademais, Boethius, sempre seguindo Nikomachos, usa a velha classificação
pitagórica dos números naturais: primos ou incompostos versus secundários
ou compostos.
O Livro de Boethius foi, durante cerca de seiscentos anos, a única
fonte de estudos de Teoria dos Números disponı́vel na Idade Média. Em
torno de 1 200 d.C. iniciou-se o renascimento cientı́fico e matemático do
Mundo Cristão, com o afluxo das obras árabes e a tradução das obras gregas
preservadas no Mundo Islamita. É dessa época um dos mais influentes livros
de todos os tempos: o Liber Abacci, de Fibonacci. Esse grande matemático,
que havia estudado entre os muçulmanos do Norte da África, dizia que acha
melhor dizer primus em vez do incomposto preferido pelos árabes e outras
pessoas. Ficou assim, definitivamente, consagrada a denominação número
primo na Europa Cristã.
3. O Teorema Fundamental da Aritmética
Todo número 1 < n ∈ N pode ser escrito de maneira única como o
produto finito de primos, isto é, existem p1 , p2 , ..., Pr ∈ P tais que
n = p1 p2 ...pr .
Exemplos: 6 = 2.3 , 50 = 2.5.5 , 273 = 3.7.13, etc.
Tarefa 2: Como você escreveria como decomposição de primos os números
231, 527 e 323 ?
3
4. Estimativas sobre quantidades de primos
Teorema(Euclides): O conjunto P dos números primos é infinito.
Demonstração: Suponhamos que P = {p1 , p2 , p3 , ..., pr } fosse um conjunto
finito. Consideremos o número natural n = p1 · p2 · ... · pr + 1. Pelo Teorema
Fundamental da Aritmética, este n > 1 é divisı́vel por algum primo q. Pela
suposição, q = pk para algum k ∈ {1, 2, ..., r}. Mas daı́ segue que q divide
1, o que é um absurdo. Logo, nenhum conjunto finito pode abranger todos
os primos.
Teorema(Tchebychef ): Para 2 ≤ m ∈ N temos que sempre existe um
primo p com m < p < 2m.
Definição: Um par de números (p, p + 2) é denominado um gêmeo de
primos se ambos p e p + 2 são primos.
Exemplos: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31)...
Observação: É desconhecido se existe uma quantidade infinita de
gêmeos primos.
5. Por que números primos são tão importantes?
Você sabe para que servem os números primos ? Por que estudamos e
às vezes damos tanta ênfase a esse assunto ? Será que a sua aplicação está
apenas no âmbito da própria matemática ?
Quando você manda uma mensagem ou coloca uma senha de banco
na Internet, você sabia que são os números primos que garantem a sua
segurança ?
Não ? Então vamos por partes.
A criptografia trata-se do sistema que protege transações pela internet.
Criptografia (kriptós= escondido, oculto, grápho= grafia) : é a arte ou
ciência de escrever em cifra ou em códigos, de forma a permitir que somente
o destinatário a decifre e compreenda.
A codificação é feita usando números primos grandes que, mesmo com
os computadores atuais, levariam séculos para serem descobertos. Então,
só quem tem a chave pode decodificá-lo. Números compostos por primos
razoavelmente grandes podem proteger sistemas de senhas, pois a tarefa de
decompô-los empregando métodos braçais e mesmo computacionais é quase
impossı́vel.
É de longa data o fascı́nio pelos números primos. O tema sempre
instigou os matemáticos, como vimos. Temos uma proposição célebre, a
Conjectura de Goldbach de 1742:
4
Todo número par n > 4 é a soma de dois primos ı́mpares.
Vamos pensar sobre isso, então: 20 = 13+7 e 100 = 53+47 .
Tarefa 3: Que outros números pares você é capaz de encontrar que podem
ser escritos como soma de dois números primos ı́mpares ?
Para facilitar um pouco sua tarefa, vamos utilizar o Crivo de Eratóstenes.
Eratóstenes (285 a.C. 194 a.C)foi um matemático, gramático, poeta,
bibliotecário e astrônomo da Grécia Antiga. Nasceu em Cirene, Grécia,
e morreu em Alexandria. Estudou em Cirene, em Atenas e em Alexandria. Os contemporâneos chamavam-no de ”Beta”porque o consideravam o
segundo melhor do mundo em vários aspectos.
O Crivo de Eratóteles é um algoritmo e um método simples e prático
para encontrar números primos até um certo valor limite. Para exemplificálo, vamos determinar a lista de números primos entre 1 e 200.
Inicialmente, determina-se o maior número primo a ser checado. Ele
corresponde
à raiz quadrada do valor limite, arredondado para baixo. No
√
caso, 200 ∼
= 14, 14, arredondada para baixo, é 13.
O primeiro primo número primo da lista 2, portanto, circule-o. Risque
todos os números pares até o final da lista. O próximo número da lista é
3, que é primo. Circule-o, e risque todos os seus múltiplos até o final da
lista. O próximo número, 5, também é primo; circule-o e risque todos os
seus múltiplos. Continue assim até chegar no número 13, o último primo a
ser checado.
5
1
11
21
31
41
51
61
71
81
91
101
111
121
131
141
151
161
171
181
191
2
12
22
32
42
52
62
72
82
92
102
112
122
132
142
152
162
172
182
192
3
13
23
33
43
53
63
73
83
93
103
113
123
133
143
153
163
173
183
193
4
14
24
34
44
54
64
74
84
94
104
114
124
134
144
154
164
174
184
194
5
15
25
35
45
55
65
75
85
95
105
115
125
135
145
155
165
175
185
195
6
16
26
36
46
56
66
76
86
96
106
116
126
136
146
156
166
176
186
196
7
17
27
37
47
57
67
77
87
97
107
117
127
137
147
157
167
177
187
197
Números primos entre 1 e 200:
6
8
18
28
38
48
58
68
78
88
98
108
118
128
138
148
158
168
178
188
198
9
19
29
39
49
59
69
79
89
99
109
119
129
139
149
159
169
179
189
199
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
Tarefa 4: Agora, encontre como seriam escritos os números pares entre 5
e 200 como soma de dois números primos ı́mpares.
Fontes:
- Programa Gestão da Aprendizagem Escolar - Gestar II, Matemática: Caderno
do Formador. Brası́lia: Ministério da Educação, Secretaria de Educação Básica,
2008.
- Teoria dos Números - Texto de Aula, Professor Rudolf R. Maier - Universidade de Brası́lia - Departamento de Matemática - IE - 2001.
- http://athena.mat.ufrgs.br/ portosil/histo2.html
7