Departamento de Matemática e
Engenharias
Quantos primos existem?
História e aplicações
Trabalho elaborado no âmbito da cadeira de
Fundamentos Históricos da Matemática
Inserida no Mestrado em Matemática
Rafael Domingos Garanito Luís
Funchal, Fevereiro 2005
Índice
Introdução
3
1 Um pouco de História
1.1 Breve História dos números primos . . . . . . . . . . . . . . . . . . .
5
5
1.2 Porque é que se tenta descobir novos números primos?
1.2.1 Pela tradição . . . . . . . . . . . . . . . . . . .
1.2.2 Pelas perspectivas futuras . . . . . . . . . . . .
1.2.3 Pelo desafio de descobrir coisas raras . . . . . .
1.2.4 Para testar Hardware . . . . . . . . . . . . . . .
1.2.5 Para saber mais sobre a sua distribuição . . . .
1.3 Aplicações dos números primos . . . . . . . . . . . . .
1.3.1 Criptografia . . . . . . . . . . . . . . . . . . . .
1.3.2 Biologia . . . . . . . . . . . . . . . . . . . . . .
2 Algumas proposições dos Livros
clides"
2.1 Proposição 29 do Livro VII . .
2.2 Proposição 30 do Livro VII . .
2.3 Proposição 31 do livroVII . . .
2.4 Proposição 20 do Livro IX . . .
2.5 Proposição 35 do Livro IX . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 8
. 8
. 9
. 9
. 9
. 9
. 10
. 10
. 13
VII e IX dos "Elementos de Eu.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14
14
15
16
17
18
3 Trabalhando com primos
21
3.1 Quantos números primos existem? . . . . . . . . . . . . . . . . . . . . 21
3.2 Outras demonstrações da infinidade números dos primos . . . . . . . 24
3.2.1 Demonstração de Euler . . . . . . . .
3.2.2 Demonstração de Washington . . . .
3.2.3 Demonstração de Kummer . . . . . .
3.3 Algoritmos para determinar números primos
3.3.1
3.3.2
3.3.3
3.3.4
3.3.5
.
.
.
.
24
25
25
26
O crivo de Eratóstenes . . . . . . . . . . . . . . . . . . . . . .
Algoritmos de Lucas . . . . . . . . . . . . . . . . . . . . . . .
Algoritmo de Brillhart, Lehmer & Selfridge . . . . . . . . . . .
Algoritmo de Pepin para testar a primalidade dos números de
Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algoritmo para testar a primalidade de números de Mersenne
26
28
29
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
29
29
2
4 Progressões geométricas
30
4.1 Definição e principais propriedades . . . . . . . . . . . . . . . . . . . 30
4.2 Uma progessão geométrica especial . . . . . . . . . . . . . . . . . . . 33
5 Conclusão
37
Bibliografia
38
Introdução
Os principais objectivos deste trabalho são, traduzir algumas das mais importantes
propriedades dos livros VII e IX dos Elementos de Euclides, bem como apresentar
a demostração feita por Euclides, que estão no sítio da Internet,
http : //aleph0.clarku.edu/˜djoyce/java/elements/toc.html
mantido pelo conhecido D. E. Joyce, da Universidade de Clark e estabelecer uma
relação dessas propriedades com o que se faz hoje em dia.
Euclides, define número primo como sendo aquele que é medido apenas pela
unidade, e número composto como sendo aquele que é medido por algum número.
Note-se que Euclides não considera a unidade como um número e assim assegura
a distinção entre número primo e número composto. Repare-se que na definição 1,
Livro VII, Euclides diz que "uma unidade é aquela que em virtude da qual, cada
coisa que existe é chamada um" e logo a seguir define número como sendo " uma
multitude composta por unidades". Podemos interpretar multitude como sendo
uma multidão ou muitos. Actualmente para definirmos número primo, pensamos
nos números naturais que têm dois e só dois divisores, e todos os números naturais
que não fazem parte deste conjunto são compostos.
O livro VII é constituído por 20 definições e 39 proposições. Das proposições,
destaco a 30,"se dois números, multiplicados entre si originam algum número, e
qualquer número primo mede o produto, então também mede um dos números
iniciais", que em linguagem corrente podemos interpretar do seguinte modo - seja
d um primo, se d divide ab, então d divide a ou b. A proposição 31, é também
importante, por ser provavelmente a primeira prova formal por recorrência e diz que
"qualquer número composto é medido por algum número primo".
Na proposição 20 do Livro IX, Euclides prova o carácter potencialmente infinito
dos números primos, sem nunca se referir ao termo infinito.
Da observação que se faz à distribuição dos números primos, surge um resultado
importante - "O Teorema dos Números Primos": - e diz que o número de primos
x
até x é assimptóticamente aproximado por log(x)
, para x suficientemente grande.
Uma versão parcial do conhecido Teorema Fundamental da Aritmética, aparece
no livro IX, na proposição 14, "se um número é o menor que é medido por números
primos, então ele não é medido por nenhum outro primo excepto aqueles que o
mediam desde o princípio". Ora, prova-se que todo o inteiro a > 1 é produto de
primos, existem k ≥ 1 , n1 , n2 , ..., nk e números primos p1 , p2 , ..., pk tais que pi 6= pj
k
Y
nk
n1 n2
e a = p1 p2 ...pk =
pni i . Esta factorização em números primos de a é única a
i=1
menos da ordem dos factores.
3
4
Podemos também encontrar no livro IX, um método para determinar a soma
(Sn ) dos n primeiros termos de uma progressão geométrica de razão r. Com efeito,
1 − rn
. É um
sabemos que se un = u1 rn−1 e Sn = u1 + u2 + ... + un então Sn = u1
1−r
pouco dentro deste contexto que irei trabalhar.
Relativamente à estrutura do trabalho, ele encontra-se dividido em quatro pequenos capítulos.
Como este trabalho insere-se no âmbito de uma cadeira de História da Matemática,
no primeiro capítulo faço uma breve história dos números primos, o que motivou o
seu estudo desde há pelo menos 25 séculos e da sua utilidade nos tempo de hoje.
No capítulo seguinte, apresento as proposições 29, 30 e 31 do Livro VII e as
proposições 20 e 35 do Livro IX dos "Elementos de Euclides" bem como as respectivas demonstrações feitas por Euclides.
Como estas proposições referem-se (excepto a proposição 35, Livro IX) a números
primos, no capítulo 3 faço um breve estudo sobre números primos, apresentando
algumas propriedades que achei importante aflorar. Apresento uma demostração,
em "notação moderna", da importante proposição 20 do Livro IX, bem como outras
demonstrações, nomeadamente de Euler, Washington e Kummer.
Como estes números são objecto de estudo por muitos investigadores, existem
alguns algoritmos para testar a primalidade de um número. Assim, além do conhecido crivo de Eratóstenes, apresento outros algoritmos muitas vezes utilizados,
para testar a primalidade de um dado número.
Como a proposição 35 do Livro IX fornece-nos um processo para determinar a
soma dos n primeiros termos de uma proporção continuada (actualmente conhecida
por progressão geométrica), achei importante fazer uma breve referência a este tipo
de proporção, nomeadamente, um processo alternativo ao que Euclides apresenta,
e que é muitas vezes utilizado hoje em dia, quando se determina pela primeira vez
a soma dos n primeiros termos de uma progressão geométrica. Na segunda parte
deste capítulo, podemos encontrar uma progressão geométrica especial, que está
relacionada com a matemática da música. Um exemplo é a análise das sequências
das notas da escala musical igualmente temperada.
Capítulo 1
Um pouco de História
1.1
Breve História dos números primos
O estudo dos números primos1 data desde os antigos matemáticos gregos.
Os pitagóricos (500 - 300 a.C.) interessavam-se em compreender a razão de ser
dos números inteiros, procurando explicar através deles a essência de todas as coisas.
Assim, classificavam os números de acordo com as suas características. Entendiam a
ideia de primalidade e interessavam-se por números perfeitos e amigáveis2 . Podemos
encontrar em "A Cidade de Deus", de Santo Agostinho, a síntese mais completa do
ideal pitagórico: "O número é perfeito em si mesmo e não porque Deus criou todas
as coisas em seis dias. O inverso é mais verdadeiro, Deus criou as coisas em seis dias
porque este número é perfeito. E continuaria perfeito mesmo que o trabalho de seis
dias não existisse"[2].
Quando "Os Elementos" de Euclides aparecem (± 300 a.C.), já muitos dos resultados importantes sobre números primos tinham sido provados. Segundo António Machiavelo3 , a demonstração de que há uma infinidade de números primos
(mais à frente transcrevo a demostração feita por Euclides e apresento uma versão
"mais moderna", bem como outras demonstrações alternativas) é um "monumento
à elegância e ao engenho Humano"[4]. De facto, é uma das primeiras demonstrações
conhecidas a usar o método da contradição, com vista à obtenção de um resultado. Note-se que o termo infinito é cuidadosamente evitado por Euclides tanto no
enunciado como na demostração.
O matemático grego Eratóstenes (276 - 196 a.C.) apresentou um algoritmo para
determinar números primos, o Crivo de Eratóstenes (ver 3.3.1).
1
Números naturais, maiores que a unidade, que não podem ser escritos como produto de números
menores, isto é, são números que admitem dois e só dois divisores, ele próprio e a unidade.
2
Um número diz-se perfeito se igualar a soma dos seus divisores naturais, incluindo 1 mas
excluíndo o próprio (1+2+3=6). Os primeiros 4 números perfeitos são o 6, 28, 496 e 8128.
Um par de números diz-se amigáveis se os divisores de um somam-se ao do outro e vice-versa.
Exemplo: 220 e 284.
D220 = {1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, 220}
D284 = {1, 2, 4, 71, 142, 284}
A soma dos divisores de 220 é igual à soma dos divisores de 284.
3
Professor no Departamento de Matemática Pura da Faculdade de Ciências da Universidade do
Porto.
5
6
Segue-se um largo período de tempo de interregno, na história dos números
primos e só no início do século XVII Fermat (1601-1665) prova uma especulação
conjecturada por Albert Girard4 , que diz que todo o número primo da forma 4n + 1
pode ser escrito de um só modo como soma de dois quadrados e, foi capaz de nos
mostrar que qualquer número pode ser escrito como soma de quatro quadrados.
Criou um novo método para factorizar números grandes. Também provou o que é
hoje conhecido como Pequeno Teorema de Fermat (para distinguir do denominado
Grande Teorema de Fermat): seja n um número primo então para qualquer número
inteiro a, tem-se que an ≡ a (mod n). Tal teorema prova em parte, o que foi chamado
de Hipótese Chinesa, que data de cerca de 2000 anos antes, e que diz que um inteiro
n é primo, se e só se o número 2n −2 é divisível por n. A outra metade deste teorema
é falsa; por exemplo 2341 − 2 é divisível por 341, e 341=31x11.
Marin Mersenne (1588-1648) conjecturou que os números da forma 4n − 1 e F n 5
são sempre primos, mas este resultado falha. Esta falha só é detectada 100 anos mais
tarde, quando Euler (1707-1783) demonstra que 232 + 1 = 4294967297 é divisível
por 641, portanto não é primo.
Os números da forma 2n − 1 também foram alvo da atenção dos matemáticos,
devido ao facto de que caso n não seja um número primo, então estes números são
compostos, logo factorizáveis. Os números escritos desta forma são vulgarmente
chamados de números de Mersenne6 , devido ao estudo que este matemático lhe
dedicou. Nem todos os números da forma 2n − 1 com n primo são números primos.
São conhecidos 41 números primos de Mersenne, sendo o maior 224036583 − 1,
datado de 15 Maio de 2004 (um recorde do projecto GIMPS, the Great Internet
Mersenne Prime Search), que tem qualquer coisa como 7235733 algarismos7 . Destes
41, destaco o número 211213 −1, determinado por Gillies em 1963, na Universidade de
Illinois com 3376 algarismos. O departamento de Matemática estava tão orgulhoso,
4
Matemático francês, nasceu em 1595, St. Mihiel, França, emigrou para a Holanda e aos 22
anos frequentou pela primeira vez a Universidade de Leiden. Faleceu a 8 de Dezembro de 1632 em
Leiden.
n
5
Números de Fermat, são todos os que têm a forma F n = 22 + 1. Os primeiros números de
Fermat são, F 0 = 3, F 1 = 5, F 2 = 17, F 3 = 257, F 4 = 65537
6
Os números da forma M n = 2n − 1 com n um número primo são chamados de números
de Mersenne. Estes números podem ser primos ou compostos. Por exemplo M 2 = 3, M 3 = 7,
M 5 = 31, M 7 = 127, são números primos, mas já M 11 = 23×89 não é primo. Mersenne constactou
que os números M n são também primos para n = 13, 17, 19, 31, 67, 127, 257; no entanto, ele estava
errado quanto a 67 e a 257 e não incluíu 61, 89, 107 entre os primos inferiores a 257, que também
produzem números de Mersenne primos.
O problema é reconhecer de entre os números de Mersenne os que são primos e de entre os
compostos os respectivos factores.
Foi estabelecido por Euler em 1750, e demonstrado mais tarde em 1775, por Lagrange, um
resultado tornado clássico, sobre os factores dos números de Mersenne: Se q é um número primo
tal que q ≡ 3(mod 4) então 2q + 1 divide M q se e só se 2q + 1 é um número primo; neste caso se
q > 3 então M q é um número composto.
Temos então que para q = 11, 23, 83, 131, 179, 191, 239, 251, M q tem como factores respectivamente 23, 47, 167, 263, 359, 383, 479, 503.
7
Para determinar o número de dígitos do número, é obvio que não se os conta um a um,
utiliza-se o seguinte processo descrito por António Machiavelo: como 10n−1 é o primeiro número
com n dígitos, resulta que N tem n dígitos se e só se 10n−1 ≤ N < 10n , o que é equivalente a
n − 1 ≤ log10 (N ) < n. Então o número de dígitos de N é igual a blog10 (N )c + 1, onde bxc denota
a parte inteira de x, isto é, o maior inteiro que não ultrapassa x.
7
que o presidente Dr. Bateman mandou alterar o carimbo dos envelopes para "211213 −
1 is prime" como podemos observar na figura.
Euler também tem um papel importantíssimo na teoria dos números primos,
P1
, com n ∈ IN e n
e prova que a série harmónica com n primo é divergente (
n
primo). Determinou que a expressão n2 + n + 17, fornece primos para 0 ≤ n ≤ 15 e
a expressão n2 + n + 41 fornece primos para 0 ≤ n ≤ 39.
Em 1936 Derrick Henry Lehmer (1905-1991) mostrou que para uma expressão
da forma n2 + n + A, com A > 41, fornecesse primos para A − 1 valores consecutivos
de n, A deveria ser superior a 125 × 107 e que não havia, no máximo, mais do que
uma expressão com esta propriedade, para além das duas referidas.
Também foi testado outros polinómios em n, nomeadamente n2 − n + 41 (produz
primos para 0 ≤ n ≤ 40) e n2 − 79n + 1601 (produz primos para 0 ≤ n ≤ 79).
Estas fórmulas fornecem-nos alguns números primos. Assim, alguns matemáticos
estavam empenhados em encontrar fórmulas ricas em primos, mas Goldbach (16901764) provou em 1752 que nenhum polinómio em n com coeficientes inteiros gera
todos os primos.
Numa primeira abordagem, os números primos parecem não ter uma ordem
especifica de aparecimento. Aparentemente são "indomáveis", parecem ocorrer de
um modo completamente caótico entre os números naturais, deixando a impressão
de não haver nenhum padrão, nenhuma regularidade na forma como aparecem.
No entanto, apesar dessa aparente desorganização individual, e a uma uma
grande escala, a distribuição de números primos parece ter alguma regularidade
quando agrupados. Legendre (1765-1843) e Gauss (1777-1855) fizeram ambos extensos cálculos sobre a densidade dos números primos. Diz-se que, um dia Gauss
contou a um amigo que sempre que tinha 15 minutos de folga, ocupava-os contando
os números primos num alcance de 1000 números. É provável que, no fim da sua
vida Gauss tenha contado todos os números primos até 3 milhões.
Assim, conjecturou um resultado, que mais tarde foi demostrado por C. de la
Vallée Poussin (1866-1962) e por J. Hadarmarf (1865-1963), independentes um do
outro, conhecido como "O Teorema dos Números Primos": o número de primos até
x
x é assimptóticamente aproximado por log(x)
, para x suficientemente grande8 .
8
Seja π (x) a função que conta o número de números primos abaixo de x. Assim, π(13) = 6,
pois existem 6 primos ≤13: 2, 3, 5, 7, 11, 13. O valor de π(x) não muda até que x chegue ao
próximo número primo, ou seja, π(13) =π(14) = π(15) = π(16) 6= π(17). Portanto, π(x) aumenta
em saltos de 1, mas o intervalo entre esses saltos é irregular. Observando os inteiros, conclui-se que,
em média, esses intervalos tornam-se cada vez maiores, isto é, a chance de um inteiro escolhido ao
acaso ser primo diminui quando avançamos para os números maiores.
Para um valor elevado de x, π (x) ≈ logx x , ou seja, lim π(x)
= 1. Podemos escrever o teorema
x
x→+∞
de forma equivalente a
π(x)
x
≈
1
log x ,
log x
e interpretá-lo como dizendo que a densidade média de números
8
Nos últimos anos, a distinção entre número primo e número composto, e em
particular certas factorizações, ganhou especial importância devido à criptografia de
chave pública.
1.2
Porque é que se tenta descobir novos números
primos?
Os números primos são os números nos quais os números naturais se decompõem,
por exemplo, 12 = 22 × 3 e são objecto de estudo desde há muitos séculos.
Uma das razões desse estudo resulta do facto de parecerem surgir de um modo
algo caótico entre os números naturais, sem nenhum padrão aparente.
Para além do interesse obvio para os matemáticos, esta área do conhecimento
tem também tido aplicações importantes, por exemplo, nas telecomunicações (manter a privacidade das mesmas), por meio de sistemas de codificação, ou seja, da
criptografia.
A seguir podemos ver algumas dessas razões.
1.2.1
Pela tradição
Provavelmente foi Euclides o primeiro matemático a definir número primo no seu
livro "Os Elementos". O seu objectivo era caracterizar os números perfeitos pares.
No entanto, apercebeu-se de que os números perfeitos pares (não existem até há
data números perfeitos ímpares) estavam relacionados com os números primos da
forma 2n − 1, para algum número primo n (actualmente conhecidos por números de
Mersenne). Portanto, a procura deste tipo de números já dura à cerca de 2300 anos.
Números deste tipo (primos muito grandes) foram minuciosamente estudados
por grandes matemáticos. Para citar alguns Cataldi, Descartes, Fermat, Mersenne,
Frenicle, Leibniz, Euler, Landry, Lucas, Catalan, Sylvester, Cunningham, Pepin,
Putnam e Lehmer e outros. O que um investigador pode-se interrogar é o facto de:
"como posso resistir ao encanto de me juntar a tal ilustre grupo?"
É certo que muita da teoria dos números foi desenvolvida enquanto se decidia
como se tratar os grandes números, como caracterizar os seus factores e descobrir
de entre os quais, os que eram números primos.
primos (a probabilidade de que um dado inteiro seja primo) aproxima-se de
aumenta sem limites. Na tabela seguinte podemos ver a relação entre
x
10
102
103
104
105
106
107
108
π (x)
4
25
168
1229
9592
78498
664579
5761455
π(x)
x
1
log(x)
0,4
0,25
0,168
0,1229
0,0959
0,0785
0,0665
0,0576
0,4343
0,2171
0,1448
0,1086
0,0869
0,0724
0,0620
0,0543
π(x)
x
e
1
log x à
1
log(x) :
medida que x
9
Assim, a tradição pela procura de números primos assume um papel importante,
a não ser pelo orgulho de ter descoberto o maior número primo.
1.2.2
Pelas perspectivas futuras
Quando se tenta encontrar números primos recordistas, o que se está a fazer não é
mais do que fumentar a investigação. Assim, a busca de tais primos é ainda usada
por professores para motivarem os seus alunos na pesquisa matemática e talvez para
os incentar a futuras carreiras nas áreas de ciências e engenharias, aumentando assim
áreas do conhecimento humano.
1.2.3
Pelo desafio de descobrir coisas raras
Os números primos de Mersenne, que são nos dias de hoje os maiores números primos
conhecidos, são raros e portanto belos. Já foi dito que apenas se conhece 41 destes
números primos. Portanto, do conjunto dos números naturais, apenas se conhece 41
números primos de Mersenne em toda a História da Humanidade. Podemos afirmar
então, que é muito raro encontrar estes números. O mesmo se aplica a outros primos
em geral.
1.2.4
Para testar Hardware
Este tem sido um argumento utilizado por muitos para a evolução computacional
em geral, logo é uma boa motivação para as companhias produtoras de hardware.
Desde o princípio da computação electrónica, que programas com o intuito de
encontrar grandes números primos têm sido utilizados como teste para hardware.
Por exemplo, o projecto GIMPS foi utilizado pela Intel para testar os chips de
Pentium II e Pentium Pro antes de serem lançados no mercado.
O famoso "bug do Pentium" foi descoberto pelo matemático norte-americano
Thomas Nicely quando tentava calcular a constante dos números primos gémeos9 .
Ora, como são feitos milhões de cálculos, e conhecendo se um número é primo
ou não, o tempo de resposta que o processador leva para testar a primalidade do
número indica-nos a velocidade do processador.
1.2.5
Para saber mais sobre a sua distribuição
Apesar da Matemática não ser uma ciência experimental, é frequente procurar exemplos para testar conjecturas (que após tal, espera-se que alguém demonstre). Com o
evoluir do tamanho dos números, evolui, de certo modo, o conhecimento que temos
sobre a distribuição dos mesmos. O Teorema dos números primos provavelmente foi
descoberto através de uma observação mais atenta às tabelas de números primos e
verificação da sua distribuição
9
Primos gémeos são números primos da forma p e p + 2 . Os mais pequenos pares de números
primos gémeos são (3, 5), (5, 7),(11, 13)e(17, 19).
10
1.3
1.3.1
Aplicações dos números primos
Criptografia
A criptografia é a ciência de esconder o significado de um mensagem. Consiste na
aplicação de um algoritmo aos dados por forma a que eles se tornem ilegíveis. Para
recuperar os dados originais será necessário conhecer o algoritmo de desencriptação
ou decifragem.
As aplicações básicas da criptografia são a confidencialidade (garantir que apenas
quem autorizado pode ler os dados) e a autenticação/integridade (garantir que os
dados têm a origem correcta e que não foram alterados entre origem e destino).
Existem ainda outras aplicações, como por exemplo a assinatura digital.
Na prática, juntamente com os algoritmos utilizam-se chaves, mesmo que os
algoritmos sejam conhecidos é necessária a chave correta.
A segurança de um sistema baseia-se no facto de que é muito fácil multiplicar
números, enquanto que há a convicção de que é muito difícil factorizá-los (não é
nada confortável factorizar números, por exemplo com 200 casas decimais).
Assim, grandes grupos financeiros, como por exemplo o banco responsável pela
criação de notas, utilizam algumas destas ideias para garantir que as notas não são
falsificadas. Ou, até as grandes potencias militares na codificação/descodificação de
certas mensagens.
Deste modo, uma factorização de um novo número pode representar uma boa
segurança na confidencialidade mensagens. O tempo que um indivíduo levaria para
descobrir essa factorização e então decifrar a mensagem poderia não ser suficiente
até a concretização da mesma.
Estes mecanismos de codificação são usualmente conhecidos por "chave pública".
Esta expressão é utilizada porque o processo de codificação pode ser conhecido por
todos, sendo apenas o processo de descodificação mantido secreto. Este tipo de
codificação é muitas vezes utilizado na Internet em trasacções financeiras.
Exemplo de codificação assimétrica
É necessário um natural N, da forma pq, onde p e q são primos distintos, e um
outro natural r primo relativamente a (p − 1) (q − 1) . Os números N e r podem
ser conhecidos por todos, mas a factorização de N deve ser mantida em segredo.
Os símbolos a transmitir são os números a verificando 0 ≤ a < N. Em vez de
se transmitir a, transmite-se o resto da divisão de ar por N. A descodificação
corresponde ao cáculo de a. Este cálculo só é prático se se conhecerem os factores
primos de N.
Vejamos então um exemplo para um N com factorização simples.
Seja um número que é o produto de dois números primos, por exemplo N = 26,
que é 13 × 2. Se subtraírmos uma unidade a cada um dos números primos, obtemos
12 e 1, e se multiplicarmos esses dois números obtém-se 1 × 12 = 12 e podemos
simbolizar este novo número F .
Escolhe-se agora um número que não tenha qualquer factor com F , por exemplo
o 5(r), pois é o menor dos números permitidos. 5, juntamente com o número original
26 são aqueles que se anunciam no nosso catálogo público.
Para codificar uma mensagem, deveremos proceder do seguinte modo:
11
1. Substituir as letras do alfabeto da uma forma óbvia A = 1, B = 2, C = 3, e
assim sucessivamente.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
2. A codificação é então efectuada substituindo o número correspondente a cada
letra por esse mesmo número elevado à quinta potência (sendo 5 o primeiro dos
números do catálogo), mas registando apenas o resto quando contando em grupos
de 26 (o segundo número do catálogo). Conta-se em mod 26.
Para codificar a palavra SU CESSO:
1. Procede-se à realização do primeiro passo e obtemos 19, 21, 3, 5, 19, 19, 15.
2. É agora codificada notando que :
195
215
35
55
195
195
155
=
=
=
=
=
=
=
2476099 = 95234 × 26 + 15
14084101 = 157080 × 26 + 21
243 = 9 × 26 + 9
3125 = 120 × 26 + 5
2476099 = 95234 × 26 + 15
2476099 = 95234 × 26 + 15
759375 = 29206 × 26 + 19
ou, equivalentemente como congruência mod 26
195
215
35
55
195
195
155
≡
≡
≡
≡
≡
≡
≡
15 (mod 26)
21 (mod 26)
9 (mod 26)
5 (mod 26)
15 (mod 26)
15 (mod 26)
19 (mod 26)
obtendo assim a sequência 15, 21, 9, 5, 15, 15, 19.
Então 15, 21, 9, 5, 15, 15, 19 é a forma cifrada da palavra SUCESSO. Para se descodificar é necessário possuir a "chave" que a transformará de 15, 21, 9, 5, 15, 15, 19
para 19, 21, 3, 5, 19, 19, 15.
É um número conhecido por receptor da cifra. Para o obter é necessário conhecer
primeiro o F . Mais especificamente, é o número que, quando multiplicado pelo
primeiro número do catálogo (5 ), dá resto de 1 quando se conta em grupos de F
(12 ). Este número secreto de "decifração de códigos" no caso do nosso exemplo é,
portanto, 5 pois 5 × 5 = 25 = 2 × 12 + 1, ou 5 × 5 ≡ 1 (mod 12) . A descodificação é
agora efectuada exactamente do mesmo modo como foi realizada a codificação, mas
12
usando o número secreto 5 como a nova potência a que os números da cifra deverão
ser elevados. Assim, tomando a forma codificada 15, 21, 9, 5, 15, 15, 19, passamos a
calcular os restos
155
215
95
55
155
155
195
≡
≡
≡
≡
≡
≡
≡
19 (mod 26)
21 (mod 26)
3 (mod 26)
5 (mod 26)
19 (mod 26)
19 (mod 26)
15 (mod 26)
e obtemos a sequência 19, 21, 3, 5, 19, 19, 15, ou seja SU CESSO.
Exemplo de codificação simétrica
Um tipo de codificação que não substitui cada letra particular da mensagem original
pelo mesmo substituto é o sistema de codificação muitas vezes conhecido como cifra
de Vigenere.
Uma forma de o fazer é pensar numa palavra, por exemplo SUCESSO, e escrevêla repetidamente por baixo da mensagem a ser codificada, da seguinte forma (a
acentuação de uma letra é tomada como inexistente):
O MEU OBJECT IV O É F AZER O MEST RADO
S UCE SSOSU CESS O SUCES S OSUCESSO
Como o O é a décima quinta letra do alfabeto e o S que se encontra por baixo
é a 19a , então se somarmos 15 com 19 obtemos 34. Como este valor é superior a
26, começa-se de novo o alfabeto do princípio, associando o A ao 27, o B ao 28,
conforme representado na tabela seguinte:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
Portanto 34 corresponde à letra à letra H. Da mesma maneira, para a segunda
letra da mensagem, o M(13) é adicionado ao U(21) que está por baixo para produzir o substituto codificado H(34). A terceira letra da mensagem é E (5) que
tem por baixo C (3) e se adicionarmos estes dois valores obtemos H (8) . E assim
sucessivamente até obtermos a seguinte sequencia de letras:
13
HHHZHU F XZW NOHT Y V CJKHBXNW W T W D
em que, retira-se os espaços entre as palavras para tornar a decifração mais difícil.
Para descodificar a sequência obtida, é necessário ter conhecimento da palavra
chave, SUCESSO, e procede-se de forma análoga à que se utilizou para codificar
a mensagem, mas em vez de somar, subtrai-se. Como o resultado terá de ser um
número positivo toma-se o valor, por exemplo do H superior ao de S e assim obtémse 34-19=15 que corresponde à letra O.
1.3.2
Biologia
Várias espécies adoptam mecanismos de defesa para se protegerem dos predadores.
A cigarra periódica inventou uma estratégia para minimizar o impacto da predação
e garantir assim a continuidade da sua espécie.
Emergem em ciclos de 13 e 17 anos, não existindo ciclos de 12, 14, 15, 16 ou 18
anos. A opção pelo 13 e 17 tem duas razões: além de serem números primos, são
números que excedem em muito a duração de vida dos seus predadores. Em geral,
muitos dos seus predadores têm ciclos de vida de 2 a 5 anos. Se o ciclo de vida da
cigarra fosse de 15 em 15 anos e o do seu predador de 5 em 5 anos, cada explosão
reprodutiva era atingida pelo predador. Assim, ao adoptar um número primo alto,
como por exemplo, o 17, as cigarras estão a minimizar o número de coincidências,
que neste caso só ocorrerá a cada 85 anos.
Portanto, no caso das cigarras fica garantido uma população abundante quando
o seu ciclo coincidir com o do predador.
A adopção deste ciclo (13 ou 17) é resultado de processos de adaptação ao ambiente e ao tipo de predador, mas como elas fazem esta contagem, ainda é um mistério
para a ciência.
Capítulo 2
Algumas proposições dos Livros
VII e IX dos "Elementos de
Euclides"
Das proposições dos livros VII e IX dos "Elementos de Euclides" apresento as
proposições 29, 30 e 31 do livro VII e 20 e 35 do livro IX e as respectivas demonstrações (tradução à letra). Em todas consta um guia para melhor compreensão
da mesma, sendo que nas proposicões 30 (VII) e 35 (IX) são feitos os passos da
demonstração de Euclides em notação "mais moderna".
"Dois dos mais interessantes resultados dos livros de Euclides são as proposições
31 (VII) e 20 (IX). O seu interesse reside sobretudo no que revelam sobre o modo
como os antigos gregos tratavam de questões relacionadas com o infinito"[2]. Na
primeira Euclides prova que qualquer número composto é divisível por algum primo.
É um dos mais antigos registos de uma prova formal por recorrência. Na segunda,
provou o carácter potencialmente infinito dos números primos, sem nunca usar o
termo infinito.
As traduções foram efectuadas da conhecida página de D.E. Joyce de Clark
University, em http://aleph0.clarku.edu/~djoyce/java/elements/toc.html.
2.1
Proposição 29 do Livro VII
Qualquer número primo e outro qualquer que não seja medido pelo primeiro são
números primos entre si.
Prova. Seja A um número primo que não mede B.
Digo que B e A são primos entre si.
Se B e A não são primos entre si, então algum número C mede-os. Uma vez que C
mede B, e A não mede B, então C não é o mesmo que A.
14
15
Agora, uma vez que C mede B e A, então também mede A que é primo, embora
não seja o mesmo que ele, o que é impossível. Logo nenhum número mede B e A.
Assim A e B são primos entre si.
Então, qualquer número primo e outro qualquer que não seja medido pelo primeiro
são números primos entre si.
Guia: Se um número primo não divide um outro número então eles são primos
entre si. Por exemplo, 11 não divide 15, logo 11 e 15 são primos entre si.
2.2
Proposição 30 do Livro VII
Se dois números, multiplicados entre si originam algum número, e qualquer número
primo mede o produto, então também mede um dos números iniciais.
Prova. Sejam A e B dois números que multiplicados um pelo outro, originam
C, e seja D um número primo qualquer que mede C.
Digo que D mede um dos números, A ou B.
Consideremos que D não mede A.
D é primo, então A e D são primos entre si. Consideremos que existe tantas
unidades em E quantas as vezes que D mede C.
Uma vez que D mede C de acordo com as unidades em E, então D multiplicado
por E origina C (definição 15, Livro VII)1 .
Além disso, A multiplicado por B também origina C, então o produto de D e E é
igual ao produto de A e B. Então D está para A como B está para E (proposição
19, Livro VII)2 .
Mas D e A são primos entre si, e números primos entre si são também os menores,
e os menores medem os números que têm a mesma razão, o mesmo número de vezes, o
maior o maior e o menor o menor, isto é, o antecedente o antecedente e o consequente
o consequente, então D mede B (proposições 213 e 204 , Livro VII).
1
"É dito que um número multiplica um número, quando aquele que é multiplicado, é somado a
si próprio, tantas vezes quantas unidades houver no outro". Por exemplo, se 3 é multiplicado por
6, e como 6 é 1+1+1+1+1+1, logo, 3 multiplicado por 6 é 3+3+3+3+3+3.
2
"Se quatro números são proporcionais, então o número originado pelo primeiro e o quarto
é igual ao número originado pelo segundo e o terceiro; e, se o número originado pelo primeiro
e o quarto é igual ao número originado pelo segundo e o terceiro, então os quatro números são
a
c
proporcionais". Algebricamente, = se e só se ad = bc.
b
d
3
"Números primos entre si são os menores entre aqueles que têm a mesma razão que eles"
4
"Os menores números entre aqueles que têm a mesma razão que eles, medem aqueles que têm
a mesma razão o mesmo número de vezes, o maior do maior e o menor do menor". Algebricamente,
a
c
dada uma razão , se é a mesma razão e é menor entre todas as que têm a mesma razão, então
b
d
c divide a e d divide b, além disso, c divide a o mesmo números de vezes que d divide b.
16
De modo análogo, podemos mostar, que se D não mede B, então mede A. Logo
D mede um dos números A ou B.
Guia: Esta proposição afirma que se p é um número primo, e sempre que p
divide o produto de dois números, então ele divide pelos menos um deles. Esta é de
facto uma propriedade que caracteriza os números primos, ou seja, nenhum número
composto tem esta propriedade.
Passos da demostração: Suponha-se que um número primo d divide o produto
ab. Euclides mostra na sua prova, que se d não divide a, então d divide b, e de modo
análogo, se d não divide b, então divide a. Logo temos que d, ou divide a ou divide
b.
Suponhamos que d não divide a, então pela proposição 29 (Livro VII), d e a
d
b
ab
são primos entre si. Seja e = , então = . Pela proposição 21(Livro VII) a
d
a
e
d
razão é irredutível, logo pela proposição 20 (Livro VII), d divide b.
a
De modo análogo, se prova que se d não divide b então d divide a.
2.3
Proposição 31 do livroVII
Qualquer número composto é medido por algum número primo.
Prova. Seja A um número composto.
Digo que A é medido por algum número primo.
Como A é composto portanto é medido por algum número B (definição 13, Livro
VII)5 .
B ou é primo ou é composto. Se B é um primo, então já encontrámos o número
e a prova termina aqui.
Mas se B é um número composto, algum número o mede. Seja C o número que
o mede.
Uma vez que C mede B, e B mede A, portanto C também mede A. C ou é primo
ou é composto.
Se C é um número primo, já encontrámos o número e a prova termina aqui.
Mas, se C é um número composto, algum número o mede. Assim, se continuarmos
com este processo, então algum número primo será encontrado que mede o número
imediatamente anterior e que também mede A. Se não for encontrado então uma
sequência infinita de números mede o número A, cada um menor que o outro, o que
é impossível para números.
Portanto, encontrar-se-á algum número que mede o número imediatamente anterior e que também mede A.
Portanto, qualquer número composto é medido por algum número primo.
5
"Um número composto é aquele que é medido por algum número".
17
Guia: Esta proposição afirma que se a é um número composto então existe um
primo p tal que p | a.
2.4
Proposição 20 do Livro IX
Existem mais números primos que qualquer quantidade dada de números primos.
Prova. Sejam A, B e C números primos dados.
Digo que existe mais números primos que A, B e C.
Tome-se o menor número DE medido por A, B e C. Some-se a unidade DF a
DE. Então EF ou é primo ou não é.
Primeiro consideremos que EF é primo. Então encontraram-se os números primos A, B ,C e EF que são mais que A, B e C.
Consideremos agora que EF não é primo. Então EF é medido por algum número
primo (proposição 31, Livro VII)6 . Seja G o número primo que mede EF .
Digo que G não é igual a nenhum dos números A, B e C.
Consideremos, se possível, que G é igual a algum dos números A, B ou C.
Agora, como A, B e C medem DE, logo G também mede DE. Mas G também
mede EF , logo G, sendo um número, mede também o resto, a unidade DF , o que
é absurdo.
Assim G não é igual a nenhum dos números A, B ou C. E por hipótese G é
primo. Logo os números primos A, B ,C e G foram encontrados, que são mais que
A, B e C.
Logo, existem mais números primos que qualquer quantidade dada de números
primos.
Guia: Suponhamos que há um número finito de números primos. Seja m o
mínimo múltiplo comum entre eles todos. Considere-se o número m + 1. Não poderá
ser primo uma vez que é maior que todos os primos. Logo não é primo. Então de
acordo com a proposição 31 (Livro VII), algum número primo g divide m + 1. Mas
g não pode ser nenhum dos primos, uma vez que todos eles dividem m e não divide
m + 1. Logo o facto de assumirmos que existe um número finito de primos leva a
uma contradição. Logo não existe um número finito de primos.
Comentário: Um bom comentário a esta proposição é o de João Filipe Queiró[6],
no livro "História da Matemática", página 279:
"Para a história da matemática, esta proposição de Euclides é interessante, pelo
que revela de conformidade com as regras aristotélicas.
6
"Qualquer número composto é medido por algum número primo"
18
Aristóteles distinguira dois conceitos de infinito. Está-se em presença do infinito
actual quando uma infinidade de objectos é efectivamente dada e encarada como um
todo. O infinito potencial manifesta-se quando, dada qualquer quantidade finita,
é sempre possível conceber uma quantidade maior (mas ainda finita). Segundo
Aristóteles, no discurso científico, não deveria ser feita alusão ao infinito actual.
Contornar a questão em termos de infinito potencial permitia evitar as situações
paradoxais a que o infinito frequentemente dá origem, e de que os argumentos de
Zenão acerca do movimento são um ilustração que o próprio Aristóteles refere.
Ora, na proposição 20, Livro IX Euclides mostra que, dada qualquer quantidade
de números primos, é sempre possível indicar uma quantidade maior de números
primos. Ou seja, provou a carácter potencialmente infinito dos números primos, sem
nunca afirmar que existem em acto infinitos números primos, Portanto, a postura
de Euclides está em sintonia com o preceito aristotélico de banir o infinito actual
das considerações científicas".
2.5
Proposição 35 do Livro IX
Se tantos números quantos se queira estiverem em proporção continuada, e se se
subtrai ao segundo e ao último o primeiro, então o excesso do segundo está para o
primeiro como o excesso do último está para a soma de todos antes dele.
Prova. Considere-se que existem tantos números quantos quisermos em proporção continuada, A, BC, D e EF , começando A como o menor, e que sejam
subtraídos de BC e EF os números BG e HF , cada um igual a A.
Digo que GC está para A como EH está para a soma de A, BC, e D.
Seja F K igual a BC, e F L igual a D. Então, uma vez que, F K é igual a BC, e
de F K a parte F H é igual à parte BG, então o resto HK é igual ao resto GC.
E como EF está para D, como D está para BC, e como BC está para A,
enquanto D é igual a F L, BC é igual a F K, e A é igual a F H, então EF está para
F L como LF está para F K, e como F K está para F H (proposição 11, Livro
VII)7 .
7
"Se um todo está para um todo como um número subtraído está para um número subtraído,
a
e
então o resto está para o resto como o todo está para o todo". Algebricamente, se = , então
c
f
a−e
a
= .
c−f
c
19
Tomando-os separadamente, EL está para LF como LK está para F K, e como
KH está para F H (proposição 13, Livro VII)8 .
Uma vez que, um dos antecedentes está para um dos consequentes como a soma
dos antecedentes está para a soma dos consequentes, então KH está para F H como
a soma de EL, LK e KH está para a soma de LF , F H, e HF (proposição 12,
Livro VII)9 .
Mas KH é igual a CG, F H é igual a A, e a soma de LF , F K e HF é igual à
soma de D, BC e A, logo CG está para A como EH está para a soma de D, BC e
D.
Logo o excesso do segundo está para o primeiro, como o excesso do último está
para a soma dos anteriores a ele.
Guia: Esta proposição diz que se a sequência de números a1 , a2 , a3 , ..., an , an+1
está em proporção continuada
a1
a2
an
=
= ... =
,
a2
a3
an+1
então
a2 − a1
an+1 − a1
=
.
a1
a1 + a2 + ... + an
Esta conclusão dá-nos um modo de calcular a soma dos termos de uma proporção
continuada, isto é:
an+1 − a1
.
a2 − a1
Se denotarmos o primeiro termo por a e a razão dos termos por r, obtemos uma
fórmula familiar:
a1 + a2 + ... + an = a1
rn − 1
=a
a + ar + ar + ar + ... + ar
r−1
Sumário da prova: A prova desta proposição é mais compreensível quando é
traduzida para notação algébrica.
2
A = a1
BC = a2
..
.
D = an
EF = an+1
n+1
3
BG = F H = a1
GC = a2 − a1
EH = (an+1 − a1 ) : (a2 : a1 )
Para cada proporção, por exemplo
an+1
an
=
,
an
an−1
8
"Se quatro números são proporcionais então são também proporcionais alternadamente". Ala
c
a
b
gebricamente, se = então = .
b
d
c
d
9
"Se qualquer número de números são proporcionais, então um dos antecedentes está para um
dos consequentes, como a soma dos antecedentes está para a soma dos consequentes". Algebricax1
x2
xn
x1 + x2 + ... + xn
x1
x2
xn
mente se
=
= ... =
então
=
=
= ... =
.
y1
y2
yn
y1 + y2 + ... + yn
y1
y2
yn
20
tome-se separadamente de acordo com a proposição 11, Livro VII, para obter
então
an+1 − an
an
=
,
an − an−1
an−1
an − an−1
an+1 − an
=
.
an
an−1
Juntando as conclusões temos:
an+1 − an
an − an−1
a2 − a1
=
= ... =
.
an
an−1
a1
Usando agora a proposição 11, Livro VII, resulta
an+1 − an + an − an−1 + ... + a2 − a1
a2 − a1
=
.
an + an−1 + ... + a2 + a1
a1
Mas an+1 − an + an − an−1 + ... + a2 − a1 = an+1 − a1 , logo temos
an+1 − a1
a2 − a1
=
a1 + a2 + ... + an
a1
Capítulo 3
Trabalhando com primos
Na primeira parte deste capítulo apresento algumas propriedades com as respectivas
demonstrações, que estão relaccionadas com as proposições do capítulo anterior e
outras que Euclides provou e que aparecem nos livros VII e IX. Também apresento outros resultados que achei importante aflorar, e que em meu entender vêm
enriquecer o breve estudo que fiz sobre os números primos. Descrevo um algoritmo
para decidir se um número é primo.
Na segunda parte do capítulo, aparecem as demonstrações de Euler, Washington e Kummer para a infinidade dos números primos e na terceira parte alguns
algoritmos para testar a primalidade de números.
3.1
Quantos números primos existem?
Definição 3.1 Um inteiro a divide um inteiro b se existe um inteiro q tal que
b = qa. Escreve-se a | b se a divide b. O inteiro q diz-se o quociente, o inteiro a
diz-se um múltiplo ou um divisor de b e b diz-se divisível por a.
Podemos resumir as proposições 31 e 32 do Livro VII, dos Elementos de Euclides,
do seguinte modo:
Proposição 3.2 Todo o inteiro maior que 1 é divisível por um número primo.
Prova. Seja a > 1 qualquer. Se a é um número primo, então como a é divisível
por si próprio, a é divisível pelo primo p = a. Se a não é um primo então existe um
inteiro positivo 1<a2 < a tal que a2 | a. Se a2 é primo, então o primo p = a2 divide
a. Se a2 não é primo então existe um inteiro positivo 1 < a3 < a2 tal que a3 | a2 , e
a3 | a. Ora se a3 é primo então o primo p = a3 divide a. Se a3 não é primo então
existe um 1 < a4 < a3 tal que a4 | a3 . E continuando com este processo obtemos
inteiros ai tal que 1 < ai < ai−1 < ... < a2 < a1 e ai | a. Este processo termina no
máximo em a − 1 passos e encontramos um divisor ai de a que é um primo.
Uma versão "mais moderna" da importante proposição 20 do Livro IX dos "Elementos de Euclides" pode ser:
Proposição 3.3 Há um infinidade de números primos.
21
22
Prova. Suponhamos que existe apenas um número finito de primos. Sejam p1 ,
p2 , ..., pn todos os números primos distintos. Seja m = p1 × p2 × ... × pn + 1, e como
todo o inteiro maior que 1 é divisível por um número primo (proposição 3.2), existe
um número primo que divide m. Como p1 , p2 , ..., pn são únicos números primos,
então existe i ∈ {1, ...n} tal que pi | m. Mas pi | p1 × p2 × ... × pn e pi também divide
m − p1 × p2 × ... × pn ou seja pi | 1 porque m − p1 × p2 × ... × pn = 1.
Sabemos que se b é um inteiro positivo e se b | 1 então b = 11 . Assim pi = 1, o
que é um absurdo, porque 1 não é um número primo. Portanto existe um número
infinito de primos.
2e
Para
√ decidir se um número n é um primo basta verificar se nenhum primo entre
n divide n.
Proposição
√ 3.4 Seja n ≥ 2 um número. Suponha-se que nenhum número primo
entre 2 e n divide n, então n é um número primo.
√
Prova. Seja n ≥ 2 tal que nenhum número primo entre 2 e n divide n. Vamos
supor com vista a um absurdo que n não é primo. Então n é fa forma n = ab para
alguns inteiros 1 < a, b < n. Pela proprosição 3.2 existem números primos p e q √
tal
que p | a e q | b. Como√p √
e q dividem também n temos por hipótese p, q > n
Portanto n = ab ≥ pq > n n = n que é um absurdo, logo n é um número primo.
Exemplo 3.5 Seja n = 91. Para
√ verificar se n = 91 é um número primo basta ver
que nenhum primo entre 2 e 91 divide 91.
√
√
91 < 100 = 10
Os números primos entre 2 e 10 são: 2, 3, 5 e 7 e nenhum destes números divide
91, portanto 91 é primo.
Para usar esta propriedade precisamos de um lista dos números primos entre 2
e um número n ≥ 2. O matemático grego Eratóstenes inventou um algoritmo para
obter esta lista - Crivo de Eratóstenes, ver 3.3.1.
O crivo de Eratóstenes e a proposição 3.4 dão um algoritmo para decidir se um
número é primo:
Algoritmo 3.6 Dado n ≥ 2 faça-se uma lista M dos primos entre 2 e
o crivo de Eratóstenes. Se nenhum primo de M divide n, n é primo.
√
n usando
√
√
Exemplo 3.7 Seja n = 1021, temos 1021 < 1024 = 32 e usando o crivo de
Eratóstenes encontramos os primos entre 2 e 32 que são 2, 3, 5, 7, 11, 13, 17, 19,
29 e 31 e nenhum destes números primos divide 1021. Portanto 1021 é um primo.
1
Seja b um inteiro positivo. Temos que b | 1 , logo existe um inteiro positivo k tal que 1 = kb.
Mas k e b são inteiros positivos e terão que ser necessáriamente 1 pois caso contrário para termos
kb = 1, k teria que ser o inverso de b, e nesse caso não seria inteiro (excepto o caso em que 1 é o
inverso de 1).
23
Podemos encontrar a proposição que se segue no livro VII (proposição 30) dos
"Elementos de Euclides", mas alargada a números inteiros.
Proposição 3.8 Seja p ≥ 1 um inteiro. Tem-se que p é primo se e só se para todos
a, b ∈ IZ : se p | ab então p | a ou p | b.
Prova. (=⇒) suponhamos que p é um primo e p | ab para alguns a, b ∈ IZ.
Se p - a então mdc (a, p) = 1 ou seja a e p são primos entre si e como p | ab por
hipótese então p | b.
(⇐=) Seja d um divisor positivo de p, então ∃e (inteiro) tal que p = de, ou seja,
p | de. Por hip. p | d ou p | e. Se p | d temos p = d. Se p | e temos e = pe0 para um
e0 ∈ IZ. Portanto p = de = dpe0 implica 1 = de0 ou seja d | 1, donde, d = 1.
Corolário 3.9 Seja p um primo e a1 , a2 , ..., ak inteiros. Se p | a1 × a2 × ... × ak
então ∃i ∈ {1, ...k} : p | ai .
Prova.
p | a1 × a2 × ... × ak
p | a1 ou p | a2 × a3 × ... × ak
p | a1 ou p | a2 ou p | a3 × a4 × ... × ak
..
.
=⇒
=⇒
..
.
=⇒ p | a1 ou p | a2 ou ... ou p | ak
logo ∃i ∈ {1, ...k} : p | ai .
A proposição 14 do Livro IX dos "Elementos de Euclides" é uma versão parcial
da propriedade seguinte.
Proposição 3.10 (Teorema Fundamental da Aritmetica) Todo o inteiro a >
1 é produto de primos, existem k ≥ 1 , n1 , n2 , ..., nk e números primos p1 , p2 , ..., pk
tais que pi 6= pj e
a=
pn1 1 pn2 2 ...pnk k
=
k
Y
pni i
i=1
Esta factorização em números primos de a é única a menos da ordem dos factores.
Prova. Seja a > 0, pela proposição 3.2 existe um primo p1 tal que p1 | a. Ora
1 ≤ pa1 < a e se pa1 6= 1 existe mais um número primo p2 que divide pa1 . Então
1≤
Se
a
p1 p2
a
a
<
p1 p2
p1
6= 1 existe um número primo p3 que divide
1≤
a
.
p1 p2
Assim,
a
a
<
p1 p2 p3
p1 p2
E continuando este processo de construção, obtemos os números primos p1 , p2 , ..., pm
a
tais que
= 1, isto é, a = p1 p2 ...pm (alguns dos primos pi podem ser
p1 p2 ...pm
24
iguais). Seja k = |{p1 , p2 , ..., pm }| o número de primos diferentes. Existem expoentes
n1 , n2 , ..., nk tal que
a = p1 p2 ...pm =
pn1 1 pn2 2 ...pnk k
=
k
Y
pni i
i=1
Sejam a = q1 ...qr = p1 ...pm duas factorizações de a em números de primos. Sem
perda de generalidade podemos supor que r ≥ m. Temos q1 | a, mas a = p1 p2 ...pm
e pelo corolário 3.9 existe i ∈ {1, .., m} tal que q1 | pj . Como pj é um primo e
q1 6= 1 temos q1 = pj . Podemos supor que j = 1 (sem perda de generalidade) e se
dividirmos a por q1 temos q2 q3 ...qr = p2 p3 ...pm , e continua-se este processo dividindo
por p2 , p3 , ..., pm . Se r 6= m chegamos depois de m passos à equação pr−m ...pr = 1.
Logo pi = 1 para todo r − m ≤ i ≤ m, o que é uma contradição porque os pi são
números primos e por definição diferentes de 1. Portanto r = m.
Exemplo 3.11 3259 872 = 25 × 33 × 73 × 11
3.2
Outras demonstrações da infinidade números
dos primos
3.2.1
Demonstração de Euler
Base da demonstração de Euler
Não é uma demostração directa, e à primeira vista parece ser pouco natural;
mas conduz-nos a importantes desenvolvimentos. Euler mostrou que devem existir
infinitos números primos pelo facto de uma certa expressão formada por todos os
números primos ser infinita.
1
Se p é um número primo, então < 1; consequentemente, temos que a soma da
p
X 1
1
=
série geométrica é
1 . Do mesmo modo, se q é outro número primo
k
p
1
−
p
k≥0
X 1
1
então,
=
.
qk
1 − 1q
k≥0
µ
¶µ
¶
1
1
1
1
1
1
1 1 1
1
1 + + 2 + ...
1 + + 2 + ... = 1 + + + 2 + 2 + ...
1 ×
1 =
p p
q q
p q p
q
1− p 1− q
A parte direita é a soma dos inversos de todos os números naturais da forma
ph × q k , h, k ≥ 0, cada um contado uma única vez, porque cada número natural tem
uma única factorização como produto de números primos. Esta simples ideia é a
base da demonstração de Euler
Prova. Suponhamos que p1 , p2 , ..., pn são todos números primos. Para cada
X 1
1
=
. Mutiplicando estas n igualdades obtemos:
j = 1, . . . , n,
k
p
1 − p1j
k≥0 j
Ã
!
n
Y
1
1
1
1
E1
=
1 ×
1 × ... ×
1
1 − p1
1 − p2
1 − p1n
1
−
p
j=1
j
25
A parte esquerda é a soma dos inversos de todos os naturais, cada um contado
uma e uma só vez - o que advém do teorema fundamental da aritmética. Isto é
X1
1
1
1
×
×
...
×
=
1
1
n
1 − p1
1 − p2
1 − p1n
P1
é divergente (série harmónica), sendo uma série de termos positivos,
Mas a série,
n
a ordem da sua soma é irrelevante. Temos que a parte esquerda de E1 é infinita
quando a parte direita é finita. Isto é absurdo.
3.2.2
Demonstração de Washington
Base da demonstração de Washington
É uma demonstração, datada de 1980 e, que segue a via da álgebra comutativa.
Os ingredientes são os factos elementares da teoria dos domínios ideais principais,
factorização única dos domínios, domínios de Dedekind, e números algébricos, e
pode ser encontrada em qualquer livro de texto sobre o assunto.
1. Em qualquer corpo numérico (de grau finito), o anel formado pelos seus
números algébricos, é um domínio de Dedekind: cada ideal é de um modo único o
produto de ideiais primos.
2. Em qualquer corpo numérico (de grau finito), existe apenas um número finito
de ideais primos que dividem qualquer número primo p.
3. Um domínio de Dedekind constituído apenas por ideais primos finitos é um
domínio ideal principal, e como tal, cada elemento é, até às unidades, o produto de
elementos primos de um só modo.
p
Prova. Considere-se o corpo de todos os números da forma a + b (−5), onde
a, b são números racionais. O anel dos números algébricos apeste corpo consiste
dos
p
números desta forma com a, b números inteiros. 2, 3, 1 + (−5), 1 − (−5) são
elementos primos deste anel, porque não podem ser decompostos em factores que
sejam inteiros algébricos, a nãopser que um p
dos factores seja "unidade" 1 ou -1.
Note-se também que (1 + (−5))(1 − (−5)) = 2 × 3, a decomposição de 6
num produto de números primos não é única até às unidades, portanto temos que o
anel não é um domínio de factorização único; consequentemente, não é um domínio
ideal principal. Logo, deve conter infinitos ideais primos (pelo facto 3 acima) e (pelo
facto 2 acima) por isso, existe um número infinito de números primos.
3.2.3
Demonstração de Kummer
Prova. Suponhamos que existe um número finito de primos p1 < p2 < ... < pr .
Seja N = p1 p2 ...pr > 2 . O inteiro N −1, pelo teorema fundamental da aritmética
é o produto de números primos. Então ∃pi , com i ∈ {1, ..., r} tal que pi é um divisor
primo em comum entre N − 1 e N; logo, pi divide N − (N − 1) = 1, o que é absurdo
3.3
Algoritmos para determinar números primos
26
3.3.1
O crivo de Eratóstenes
Eratóstenes de Cirene, teve a ideia de obter todos os números primos não superiores
a um número dado - O Crivo de Eratóstenes. Este pode ser descrito do seguinte
modo:
Para obter todos os números primos não superiores a n procede-se do seguinte
modo:
1. Escreve-se em sequência crescente todos os números desde 2 até n.
2. O primeiro primo da sequência é 2, pelo que todos os múltiplos de 2, superiores
a 2 não são primos e portanto devem ser eliminados da sequência.
3. O próximo número não riscado é o 3, que é primo, pelo que deve-se eliminar
todos os múltiplos de 3 superiores a 3.
4. Novamente, o próximo número não riscado é 5, que é primo, então elimina-se
todos os múltiplos de 5 superiores a 5.
5. E assim sucessivamente até ao fim.
Os números que ficaram na sequência, são obviamente os que não foram riscados, portanto todos os primos até n (foram eliminados da lista, todos os números
compostos, e só esses).
Note-se que quando se atinge n2 este procedimento pode terminar, pois se n2 é
primo o dobro não o é.
Na tabela seguinte está exemplificado o crivo de Eratóstenes para n = 100 :
11
21
/
31
41
51
/
61
71
81
/
91
/
2
12
/
22
/
32
/
42
/
52
/
62
/
72
/
82
/
92
/
3
13
23
33
/
43
53
63
/
73
83
93
/
/4
14
/
24
/
34
/
44
/
54
/
64
/
74
/
84
/
94
/
5
15
/
25
/
35
/
45
/
55
/
65
/
75
/
85
/
95
/
/6
16
/
26
/
36
/
46
/
56
/
66
/
76
/
86
/
96
/
7
17
27
/
37
47
57
/
67
77
/
87
/
97
/
/8
18
/
28
/
38
/
48
/
58
/
68
/
78
/
88
/
98
/
/9
19
29
39
/
49
/
59
69
/
79
89
99
10
/
20
/
30
/
40
/
50
/
60
/
70
/
80
/
90
/
100
/
Na impossibilidade de determinar todos os primos (sabe-se que são infinitos), na
lista seguinte podemos ver todos os primos que vão até 7919.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271,
277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479,
487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
27
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039,
1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129,
1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237,
1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327,
1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553,
1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637,
1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753,
1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873,
1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993,
1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087,
2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207,
2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309,
2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399,
2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539,
2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659,
2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731,
2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843,
2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963,
2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083,
3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217,
3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329,
3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457,
3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547,
3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659,
3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769,
3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889,
3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007,
4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127,
4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241,
4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357,
4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483,
4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603,
4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723,
4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861,
4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969,
4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081,
5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209,
5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347,
5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449,
5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569,
5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689,
5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813,
5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903,
28
5923,
6073,
6199,
6301,
6397,
6563,
6689,
6803,
6917,
7027,
7187,
7309,
7477,
7561,
7681,
7817,
5927,
6079,
6203,
6311,
6421,
6569,
6691,
6823,
6947,
7039,
7193,
7321,
7481,
7573,
7687,
7823,
3.3.2
5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053,
6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173,
6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287,
6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379,
6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551,
6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673,
6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791,
6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907,
6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013,
7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159,
7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297,
7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457,
7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549,
7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669,
7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789,
7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919
6067,
6197,
6299,
6389,
6553,
6679,
6793,
6911,
7019,
7177,
7307,
7459,
7559,
7673,
7793,
Algoritmos de Lucas
Estes algoritmos são baseados no Pequeno Teorema de Fermat (an ≡ a (mod n), com
n um números primo e a um inteiro qualquer).
Algoritmo de Lucas de 1876
Seja N > 1. Assuma-se que existe um inteiro a > 1 tal que:
1. aN −1 ≡ 1 (mod N)
2. am 6= 1 (mod N) para m = 1, 2, ..., N − 2.
Então N é um número primo.
Defeitos do algoritmo: pode parecer perfeito, mas requer N − 2 sucessivas multiplicações por a, e a busca dos resíduos do módulo N (demasiadas operações).
Algoritmo de Lucas de 1891
Seja N > 1. Assuma-se que existe um inteiro a > 1 tal que:
1. aN −1 ≡ 1 (mod N)
2. am 6= 1 (mod N) para cada m < N, tal que m seja divisor de N − 1.
Então N é um número primo.
Defeitos apresentados por este algoritmo: requer o conhecimento prévio de todos
os factores de N − 1.
29
3.3.3
Algoritmo de Brillhart, Lehmer & Selfridge
Em 1927, Lehmer tornou o algoritmo de Lucas datado de 1891 mais prático, mas
este foi ainda tornado mais flexível por Brillhart, Lehmer & Selfridge em 1975.
Algoritmo de Brillhart, Lehmer & Selfridge
Seja N > 1. Assuma-se que para cada factor primo q de N − 1 existe um inteiro
a = a(q) > 1 tal que:
1. aN −1 ≡ 1 (mod N)
2. a
N −1
q
6= 1 (mod N)
Então N é um número primo.
Defeitos do algoritmo: mais uma vez, é necessário conhecer os factores primos
de N − 1, mas poucas congruências têm de satisfeitas.
3.3.4
Algoritmo de Pepin para testar a primalidade dos
números de Fermat
n
Como os números de Fermat (F n = 22 + 1) crescem muito rapidamente em função
de n, torna-se muito trabalhoso testar a sua primalidade. No entanto, Pepin obteve
em 1877 um algoritmo para testar a primalidade detes números.
Algoritmo de Pepin
n
Seja F n = 22 +1, com n3 2, e k3 2. Então as seguintes condições são equivalentes:
1. F n é um número primo e
2. k
F n −1
2
k
= −1;
Fn
≡ −1 (mod F n )
Este algoritmo é praticamente uma aplicação da fórmula de Euler para os factores
de F n (Euler demonstrou que todos os factores de F n , com n3 2, são da forma
k × 2n+2 + 1 e através do qual descobriu que 641 divide F 5 : F 5 = 641 × 6700417) .
No entanto se F n é composto este não nos indica qualquer factor deste.
3.3.5
Algoritmo para testar a primalidade de números de
Mersenne
Os números da forma M n = 2n − 1 com n um número primo são chamados de
números de Mersenne. A sua consideração deriva do estudo de números perfeitos.
Algoritmo
M n = 2n + 1 é um número primo se e só se M n divide Sn−2 , com (Sk )k≥1 , uma
sucessão definida recursivamente por :
S0 = 4, Sk+1 = Sk2 − 2
Capítulo 4
Progressões geométricas
A proposição 35 do livro IX "dos Elementos de Euclides" indica-nos um processo
para determinar a soma dos termos de um "proporção continuda". Neste capítulo
faço uma breve referência à progressão geométrica, apresentando um processo alternativo ao de Euclides, para determinar a soma dos n primeiros termos de uma
progressão geométrica.
Na segunda parte do capítulo faço referência a uma progressão geométrica especial, quando se estuda a matemática da música. Embora nunca tenha estudado
música achei muito interessante e motivador o facto de podemos fazer um leitura
matemática de algo que nos é muito familiar.
4.1
Definição e principais propriedades
Definição 4.1 Uma progressão geométrica é uma sequência de números reais, onde
cada termo a parir do segundo, é igual ao anterior, multiplicado por uma constante
denominada razão.
Se a progressão geométrica genérica for (u1 , u2 , u3 , ..., un , ...), onde u1 é o primeiro
termo, e un for o termo de ordem n de razão r, da definição resulta:
u2 = u1 × r
u3 = u2 × r = u1 × r2
u4 = u3 × r = u1 × r3
..
.
un = un−1 × r = u1 × rn−1
..
.
un = u1 × rn−1 é denominado o termo geral da progressão geométrica.
Proposição 4.2 Em toda a progressão geométrica um termo é a média geométrica
dos termos imediatamente anterior e posterior.
30
31
2
Prova. un+1 × un−1 = u1 × rn × u1 × rn−2 = u21 × r2n−2 = u21 × (rn−1 ) =
2
(u1 × rn−1 ) = u2n
Proposição 4.3 O produto dos termos equidistantes dos extremos de uma progressão geométrica é constante.
Prova. Considere-se os n primeiros termos da progressão. Ou temos um número
par de termos ou um número ímpar de termos.
Se o número de termos for par, resulta:
u1 × un = u1 × u1 rn−1 = u21 rn−1
u2 × un−1 = u1 r × u1 rn−2 = u21 rn−1
u3 × un−2 = u1 r × u1 rn−3 = u21 rn−1
..
.
n
n
u n2 × u n2 +1 = u1 r 2 −1 × u1 r 2 +1−1 = u21 rn−1
Se o número de termos for ímpar e denotando [x] o menor inteiro superior a x,
temos:
u1 × un = u1 × u1 rn−1 = u21 rn−1
u2 × un−1 = u1 r × u1 rn−2 = u21 rn−1
u3 × un−2 = u1 r × u1 rn−3 = u21 rn−1
..
.
n
n
n
u[ n ]−1 × u[ n ]+1 = u1 r[ 2 ]−2 u1 r[ 2 ] = u21 r2×[ 2 ]−2 = u21 rn+1−2 = u21 rn−1
2
2
n
n
n
u2[ n ] = u1 r[ 2 ]−1 u1 r[ 2 ]−1 = u21 r2×[ 2 ]−2 = u21 rn−1
2
Podemos determinar a soma dos n primeiros termos de uma progressão como se
segue. Seja Sn esse valor.
Sn = u1 + u2 + ... + un−1 + un = u1 + u1 r + ... + u1 rn−2 + u1 rn−1
Da relação anterior podemos determinar −rSn e obtemos
−rSn = −u1 r − u1 r2 − ... − u1 rn−1 − u1 rn
e se somarmos as duas relações resulta:
Sn − rSn = u1 − u1 rn ⇔ (1 − r) Sn = u1 (1 − rn )
Donde podemos escrever o seguinte propriedade:
Proposição 4.4 A soma dos n primeiros termos de uma progressão geométrica de
1 − rn
termo geral un = u1 rn−1 é dada por Sn = u1
.
1−r
32
Corolário 4.5 Nas condições do teorema anterior, se |r| < 1 então Sn = u1
para n grande.
Prova. Como |r| < 1 então lim rn = 0 donde o resultado.
1
1−r
n→+∞
Exemplo 4.6 Usando esta ideia determina-se que a dízima infinita periódica 0,999...=1
0, 9999.... = 0, 9 + 0, 99 + 0, 999 + 0, 9999 + ...
9
99
999
9999
=
+
+
+
+ ...
10 µ 100 1000 10000 ¶
1
1
1
9
1+
+ 2 + 3 + ...
=
10
10 10
10
¶
µ
9
10
1
9
=
×
=1
=
1
10 1 − 10
10
9
x
+ ... = 100 pode ser deterExemplo 4.7 A solução da equação x + x2 + x4 + x8 + 16
minada se tivermos em atenção que no primeiro membro temos a soma dos termos
de uma progressão geométriuca de razão 12 com um número infinito de parcelas.
¶
µ
1
1
x
1
1
x x x
+ ... = x 1 + + 2 + 3 + ... = x
x+ + + +
2 4 8 16
2 2
2
1−
1
2
= 2x
Donde 2x = 100 ⇔ x = 50.
Exemplo 4.8rUm outro exemplo também interessante é o de saber qual o limite
q p
√
da expressão x x x x... onde x é positivo e o número de radicais aumenta
indefinidamente.
v s
u
r q
r q
u
√
√
t
1
x x x x x... = x 2 × x x x... =
1
1
1
1
= x 2 × x 4 × x 8 × x 16 × ...
1
1
+ 13 +....
22
2
= x2+
µ
¶
1
= x2
1
1
1− 2
1
= x 2 ×2 = x
Exemplo 4.9 Sabendo que S = 9 + 99 + 999 + 9999 + 99999 + .... + 999......99 onde
a última parcela contém n algarismos pretende-se determinar o valor de 10n+1 −
9 (S + n) .
33
Sabemos que S tem n parcelas, donde:
10n+1 − 9 (S + n) = 10n+1 − 9 [(9 + 99 + 999 + .... + 999......99) + (1 + 1 + 1 + ... + 1)]
= 10n+1 − 9 [(9 + 1) + (99 + 1) + (999 + 1) + ... + (999......99 + 1)]
£
¤
= 10n+1 − 9 10 + 102 + 103 + ... + 10n
1 − 10n+1
= 10n+1 − 9 × 10 ×
1 − 10
1 − 10n+1
= 10n+1 − 9 × 10 ×
= 10
−9
4.2
Uma progessão geométrica especial
Quando se estuda a matemática da música, como por exemplo, a análise das sequências das notas sonoras da escala musical igualmente temperada, encontra-se
os valores das sequências de notas de um oitava, que formam uma progressão geométrica, cuja razão é:
1
2 12 ≈ 1, 0594631
Assim podemos determinar os 13 primeiros termos da progressão, onde o primeiro
termo é a unidade e os termos seguintes obtidos através das sucessivas multiplicações
por 1, 0594631 :
n
1
2
3
4
5
6
7
8
9
10
11
12
13
1
un = 2 12 × un−1
1
1,0594631
1,1224620
1,1892071
1,2599210
1,3348399
1,4142136
1,4983071
1,5874011
1,6817928
1,7817974
1,8877486
2
Esta sequência de 13 termos da progressão geométrica representa a sequência
das notas da escala musical igualmente temperada, já que 12 são os seus intervalos
musicais compondo um oitava. O valor de u2 = 1, 0594631 corresponde ao primeiro
intervalo. O 13o termo pertence à próxima oitava, isto é, se começarmos pela nota
do −1, quando percorrer uma oitava, a frequência dessa nota é o dobro - 2. Assim
se a nota escolhida for La2, que tem uma frequência de 220Hz, quando percorrer
uma oitava, a frequência será de 440Hz.
34
Para a nota La2, ao multiplicar os termos da progressão por 220 obtemos a
sequência:
n
1
2
3
4
5
6
7
8
9
10
11
12
13
un
1
1,0594631
1,1224620
1,1892071
1,2599210
1,3348399
1,4142136
1,4983071
1,5874011
1,6817928
1,7817974
1,8877486
2
220 × un
220
233,081882
246,94164
261,625562
277,18262
293,664778
311,126992
329,627562
349,228242
369,994416
391,995428
415,304692
440
Notas
La2
La#
Si
Do
Do#
Re
Re#
Mi
Fa
Fa#
Sol
Sol#
La3
Se continuarmos a determinar novos termos da progressão, iremos determinar,
notas das oitavas seguintes.
Se pensarmos na progressão cujos termos são os inversos da descrita anterior1
mente, isto é 1 iremos obter a seguinte sequência:
2 12
1
un = 2 12 × un−1
1
1,0594631
1,122462
1,1892071
1,259921
1,3348399
1,4142136
1,4983071
1,5874011
1,6817928
1,7817974
1,8877486
2
2,1189262
2,2449241
2,3784142
2,5198421
2,6696797
2,8284271
2,9966142
3,1748021
−1
tn = 2 12 × tn−1
1
0,9438743
0,8908987
0,8408964
0,7937005
0,7491535
0,7071068
0,6674199
0,6299605
0,5946036
0,5612310
0,5297315
0,5
0,4719372
0,4454494
0,4204482
0,3968503
0,3745768
0,3535534
0,33371
0,3149803
35
Os termos da sucessão tn podem representar os comprimentos das cordas que
percurtiu-se para obter as várias frequências da progressão geométrica de razão
1,0594631.
Observação 4.10 Os valores da sucessão tn que aparecem ilustrados na figura, a
partir do t2 inclusivé, têm um pequeno lapso no arredondamento, pelo que deve-se
considerar os que figuram na tabela.anterior.
36
"À Circunferência mais externa do lado das frequências, corresponde a circunferência mais interna do lado do Comprimento das Cordas. Quanto mais alta é a
frequência menor é o comprimento da corda que produz sua vibração. Repare-se
que embora os invervalos sejam iguais, eles vão ocupando espaços cada vez maiores
do lado das frequências e o inverso ocorre do lado do comprimento das cordas".
Capítulo 5
Conclusão
Ao longo deste trabalho fiz um breve estudo sobre números primos. Partindo de
uma abordagem histórica, fui introduzindo alguns conceitos e propriedades que caracterizam estes números.
Foram traduzidas as proposições 29, 30 e 31 do Livro VII e as proposições 20 e 35
do Livro IX dos "Elementos de Euclides", bem como as respectivas demonstrações
feitas por Euclides há cerca de 23 séculos, que são apresentadas no sítio da Internet,
http : //aleph0.clarku.edu/˜djoyce/java/elements/toc.html
mantido por D. E. Joyce, da Universidade de Clark . Como estas proposições estão
escritas numa linguagem por vezes dificil, em todas aparece um guia, para melhor
ilustar as mesmas.
Neste lote de proposições constam duas das mais importantes proposições escritas
por Euclides. A proposição 31 do Livro VII, por ser uma das mais antigas provas
formais por recorrência de que há registos, e a proposição 20 do Livro IX, onde
Euclides prova o caráter potencialmente infinito dos números primos.
Do breve estudo que fiz sobre os números primos, para além de ter abordado
outras demonstrações famosas da infinidade dos números primos apresentei uma
versão do importante teorema, actualmente conhecido por "Teorema Fundamental
da Aritmética".
Com o desenvolvimento da informática, foi surgindo números primos cada vez
maiores, daí a necessidade de testar a sua primalidade. Assim, para além de ter
apresentado alguns algoritmos que determinam números primos, também abordei
outros que testam a sua primalidade.
No último capítulo, fiz uma breve referência às propriedades das progressões
geométricas, referindo uma curiosa e interessante aplicação na música.
37
Bibliografia
[1] Albuquerque, R. Stenio, Em busca da perfeição, Sociedade Brasileira de
Matemática.
[2] Fernandes, Rui Loja e Ricou, Manuel, "Introdução à Álgebra", Colecção Ensino
da Ciência e da Tecnologia, IST, 2004.
[3] Katz, Victor J., A History of Mathematics An Introduction, Second Edition,
Addison Wesley Longman, 1998
[4] Machiavelo, António, A importância de ser ou não primo, artigo da Gazeta da
Matemática, Sociedade Portuguesa de Matemática, no . 148, Janeiro 2005.
[5] Nogueira, J. Eurico, e outros, Contar e Fazer Contas - Uma introdução à Teoria
dos Números, Gradiva, 2004.
[6] Estrada, M.F. et al., História da Matemática, Universidade Aberta, 2000.
[7] Struik, Dirk J., História Consisa das Matemáticas, Gradiva, 1992.
[8] http://aleph0.clarku.edu/~djoyce/java/elements/toc.html
[9] http://alf1.cii.fc.ul.pt/~ferferr/PversusNP.pdf
[10] http://members.tripod.com/caraipora/pgmuitoespecial.htm
[11] http://www.educ.fc.ul.pt/
[12] http://www.ime.uerj.br/~progerio/monografia/2003_4/index.html
[13] http://www.utm.edu/research/primes/
[14] http://www.uniandrade.br/simposio/pdf/mat104.pdf
[15] http://www.utm.edu/research/primes/notes/proofs/infinite/
38