UNIVERSIDADE ESTADUAL DE GOIÁS
Unidade Universitária de Ciências Exatas e Tecnológicas
Curso de Licenciatura em Matemática
Números Primos: A Odisseia de Alguns Matemáticos em Busca de uma
Fórmula Inimaginável
Aymaás Dos Santos Tavares
ANÁPOLIS
2015
2
Aymaás Dos Santos Tavares
Números Primos: A Odisseia de Alguns Matemáticos em Busca de uma
Fórmula Inimaginável
Trabalho
de
Curso
apresentado
a
Coordenação Adjunta de TC, como parte
dos requisitos para obtenção do título de
Graduado no Curso de Licenciatura em
Matemática da Universidade Estadual de
Goiás sob a orientação da professora
Msc. Selma Marques de Paiva.
ANÁPOLIS
2015
3
4
AGRADECIMENTOS
Agradeço ao meu Deus, pelo auxílio que nunca faltou e a sua presença
constante em todo o tempo, ao meu querido e amigo Espírito Santo, por ter me
guiado até aqui.
A minha família, ao meu pai José, a minha querida mãe Marta, por me ensinar
a confiar no Senhor Jesus sempre e esperar nele a providência e a minha irmã
Aynoã.
Agradeço a minha professora orientadora Selma Marques de Paiva pela
paciência.
5
“Os números primos são as pérolas que
adornam a vastidão infinita do universo de
número que os matemáticos exploraram ao
longo
dos
séculos.
Eles
despertam
a
admiração dos matemáticos: 2, 3, 5, 7, 11,
13, 17, 19, 23... números eternos que
existem
em
uma
espécie
de
mundo
independente de nossa realidade física. São
um presente da natureza para a matemática.”
Marcus du Sautoy
6
LISTA DE TABELA
Tabela 1: Tabela de Criptografia................................................................................43
7
LISTA DE FIGURAS
Figura 1: Euclides .................................................................................26
Figura 2: Eratóstenes ............................................................................27
Figura 3: Pierre de Fermat ....................................................................30
Figura 4: Leonhard Euler .......................................................................33
Figura 5: C. F. Gauss ............................................................................35
8
RESUMO
O presente trabalho disserta sobre alguns fragmentos da história dos números primos agregando a
essa história alguns matemáticos e suas contribuições para a teoria dos números primos. Abrange
também, algumas questões específicas que é o caso dos testes de primalidade e o RSA que é uma
aplicação dos números primos. A preferência por esse tema advém das incertezas que esses
números proporcionam para os matemáticos e por se tratar de um problema presente por
aproximadamente 2.000 anos, e ainda, o anseio de um dia, no final de alguma demonstração
matemática poder admirar a fórmula precisa e exata dos números primos. Assim, esse trabalho tem
como objetivo compreender e indicar os resultados mais relevantes em teoria dos números no que se
refere ao avanço do conhecimento dos números primos, sendo uma pesquisa de caráter bibliográfico.
O trabalho objetiva auxiliar e difundir um pouco sobre o conhecimento histórico e o enigma dos
números primos.
Palavras-chave: História; Matemática; Números Primos.
9
SUMÁRIO
APRESENTAÇÃO .................................................................................................... 10
CAPÍTULO 1 ............................................................................................................. 12
A Origem de Alguns Conjuntos Numéricos e dos Números Primos....................... 12
CAPÍTULO 2 ............................................................................................................. 19
Primícias Básicas da Aritmética ............................................................................. 19
2.1 Definições ..................................................................................................... 19
2.2 Teoremas...................................................................................................... 20
CAPÍTULO 3 ............................................................................................................. 24
A História de Alguns Matemáticos Pioneiros no Estudo dos Números Primos ...... 25
3.1 Euclides de Alexandria ................................................................................. 26
3.2 Eratóstenes, de Cirene ................................................................................. 27
3.3 Pierre de Fermat ........................................................................................... 30
3.4 Leonhard Euler ............................................................................................. 33
3.5 Carl Friedrich Gauss ..................................................................................... 35
CAPÍTULO 4 ............................................................................................................. 37
Testes de Primalidade ........................................................................................... 37
4.1 Testes Primitivos .......................................................................................... 38
4.2 Teste de Lucas ............................................................................................. 39
4.3 Teste de Pepin.............................................................................................. 40
CAPÍTULO 5 ............................................................................................................. 42
Uma Aplicação dos Números Primos: RSA ........................................................... 42
CONSIDERAÇÕES FINAIS ...................................................................................... 48
REFERÊNCIAS......................................................................................................... 50
10
APRESENTAÇÃO
A matemática com seus enigmas têm desafiado ao longo dos séculos alguns
dos
mais
renomados
membros
da
comunidade
científica
matemática,
especificamente o enigma dos números primos, que provocou em várias gerações
de matemáticos como, por exemplo: Euclides, Pierre de Fermat, Leonhard Euler e
Gauss o desejo de solucioná-lo.
Esse enigma dos números primos tem recebido uma grande atenção por
parte dos matemáticos, visto que ainda é um problema insolúvel, já que nenhum
matemático foi capaz de abrir o “alfarrábio1 da matemática” e decifrar os códigos dos
números primos e pronunciar tal fórmula, isto é, a peça fundamental da solução dos
números primos, não foi posicionada no seu devido lugar.
A importância desses números para a matemática é comprovada quando eles
são entendidos como sendo os próprios “átomos da aritmética”, há ainda quem diga
que os números primos são compreendidos por seres inteligentes de outros
mundos, segundo Peruzzo:
Por seu caráter básico na formação de todos os números, os números
primos já foram usados, por exemplo, como código de contato com seres
inteligentes de outros mundos. Nas sondas exploratórias Pioneer e
Voyager, entre vozes de pessoas falando em diversas línguas, músicas,
sons da natureza e imagens, foram colocados números primos. Há a
esperança que algum ser inteligente poderá entender a sequência dos
primeiros números primos contido no disco (PERUZZO, 2012, p.2).
Quanto mais difícil e complexo a fórmula dos números primos se apresenta,
mais admirável e sublime os matemáticos a veem. Segundo Piet Hein: “Um
problema que vale a pena ser atacado prova seu valor contra-atacando”, os
números primos contra-atacam os matemáticos, mantendo a sua fórmula
inimaginável à mente humana.
Este trabalho objetiva reunir alguns assuntos mais pertinentes a cerca da
teoria dos números primos, com ênfase em alguns momentos da história e em
algumas fórmulas que pressupomos ser fundamentais para a teoria dos mesmos.
1
Livro antigo e de leitura cansativa.
11
Acentuamos que não vamos nos estender aos números inteiros, limitaremos aos
números naturais.
No primeiro capítulo trazemos de uma forma sucinta a evolução dos conjuntos
numéricos e o aparecimento do enigma dos números primos.
No segundo capítulo apresentamos os principais teoremas e definições, que
servirão para estruturar as próximas análises.
No terceiro capítulo tecemos as histórias de alguns matemáticos que
trabalharam com os números primos e que deixaram vários teoremas e conjecturas
para enriquecer os conhecimentos dessa teoria.
Os conhecimentos prosperaram, no entanto, sem a fórmula exata que os
definiam, com isso, afirmar que um número natural era primo ou não se tornou uma
façanha para poucos matemáticos persistentes. Assim era necessário um método
que tivesse como objetivo classificar um número natural sendo primo ou composto;
surgem, então, os testes de primalidade, apresentados no capítulo quatro deste
trabalho.
Por muito tempo achou-se que os números primos se isolavam na
matemática pura, isto é, não havia uma aplicação real para esse conceito até surgir
o algoritmo RSA, uma aplicação muito utilizada nos dias atuais, mencionada no
capítulo cinco, seguida de um exemplo.
Em linhas gerais, o trabalho apresenta um pouco da história dos números
primos, mas não ocultando a virtude desses números, isto é, enfatizando que os
números primos são impenetráveis até hoje, pois esses números são a própria glória
da matemática.
Por “capricho” dos números primos em não se exporem, o interesse em
compreender suas bases elementares vêm aumentando, e se materializam em
formas de perguntas: Quais foram os matemáticos que cooperaram para o avanço
no conceito desses números primos? Quantos números primos existem? Quais
foram as fórmulas e hipóteses desses matemáticos? Como saber se um número é
de fato primo? Mesmo sem uma fórmula, os números primos tem aplicação? Neste
trabalho apresentaremos algumas soluções possíveis para cada uma dessas
questões, que tem por finalidade compreender melhor o universo dos números
primos.
12
CAPÍTULO 1
A Origem de Alguns Conjuntos Numéricos e dos Números Primos
Na maior parte das ciências, uma geração põe abaixo o que a outra
construiu, e o que a outra estabeleceu a outra desfaz. Somente na
Matemática é que cada geração constrói um novo andar sobre a antiga
estrutura.
Hermann Hankel
A Matemática evoluiu juntamente com a sociedade. As concepções de
números datam de tempos longínquos, com início na era paleolítica, onde os
homens habitavam em cavernas.
Esse período é chamado de pré-histórico e, todos os conhecimentos dessa
época estão registrados exclusivamente em cavernas e, tais registros recebem o
nome de figuras rupestres ou artes rupestres que eram desenhos de pessoas,
animais e marcas parecidas com um bastão “|” um do lado do outro. Acredita-se que
esses desenhos manifestam um pensamento quantitativo, por parte dos homens da
pré-história. É desse modo, que o pensamento matemático surge, pela necessidade
de se contar objetos em sua volta.
O ato de pensar em “corresponder” um objeto, com um bastão “|” pode
suscitar o pensamento abstrato no ser humano, pois o homem começa a interpretar
o mundo em sua volta, não mais apenas com o que ele vê, mas através de um
pensamento intuitivo.
Diante desse conhecimento adquirido pelos homens da pré-história e a
necessidade de contar objetos, surge o conceito de número natural, que em tempos
atuais é representado pelo símbolo ℕ dado por {1, 2, 3 ,...n, n+1...} . Os números
naturais ou conjunto dos números naturais é infinito, pois dado um número natural n
sempre vai existir um número, também natural, n+1 .
13
Ao longo do desenvolvimento histórico dos números, o conjunto dos números
naturais foi estudado com mais interesse pelos matemáticos, principalmente os
pitagóricos e os chineses. No entanto, o interesse dos pitagóricos pelos números
naturais era voltado pelas propriedades “místicas” dos números, pois a numerologia
era uma ciência importante naquela época, na atualidade é classificada como
pseudociência.
Desses estudos surgiram vários números com propriedades instigantes, que é
o caso dos números perfeitos: o número n é chamado de número perfeito, se a
soma dos seus divisores próprios, exceto o próprio n, é igual a n. Os números
amigos: os números a e b são chamados de números amigos se, cada um deles é
igual à soma dos divisores do outro. Os números deficientes: o número d é chamado
de número deficiente se a soma dos seus divisores, exceto ele mesmo, é menor do
que d.
O fascínio pelos números teve seu apogeu quando encontraram uma
sequência numérica impermeável, contida no conjunto dos números naturais; um
segredo que jamais foi revelado, do qual mente nenhuma até hoje foi capaz de
alcançar tal grau de abstração e complexidade, necessário para enfrentar com
ousadia esses números e colocar o ponto final nesse segredo matemático. Tais
números são chamados de números primos e sua busca se torna uma odisseia para
os matemáticos que os estudam, pois é o segredo muito bem protegido pelo
universo matemático.
A dificuldade imposta por esses números advém de sua definição: Um
número natural p ≠ 1 é dito número primo se, e somente se, os únicos divisores não
negativos são 1 e p. O matemático Euclides de Alexandria, provou que os números
primos são infinitos, demonstração publicada, há cerca de 300 a. C. no livro “IX de
Os Elementos”.
Por decorrência de sua definição, os números primos acabam estando a
esmo no conjunto dos números naturais, isto é, não há um padrão que possibilite
definir uma fórmula precisa e exata, a qual satisfaça às peculiaridades dos números
primos. Em trabalho recente, Peruzzo (2012) caracteriza os números primos como
sendo os próprios átomos da aritmética, pois são os números indivisíveis.
14
O documento mais antigo sobre estes átomos da aritmética é entalhado em
um osso, conhecido como Osso de Ishango que registra uma sequência de números
primos, segundo Du Sautoy:
O primeiro indício impreciso do momento em que a humanidade se deu
conta das qualidades especiais dos números primos é um osso datado de
6500 a.C. , conhecido como Osso de Ishango que foi descoberto em 1960
nas montanhas da África Central Equatorial. Nele estão inscritas três
colunas contendo quatro séries de entalhes. Em uma dessas colunas
encontramos 11, 13, 17 e 19 entalhes, uma lista de todos os números
primos entre 10 e 20 ( SAUTOY, 2007, p.30).
Pela dificuldade que se têm de falar a respeito dos números primos, esses
números ficaram entre os conceitos mais nobres na matemática, os matemáticos
mais “importantes” tentaram exigir que a sequência dos números primos se
revelasse, porém, todas as tentativas foram em vão. No entanto, desses estudos
surgiram várias contribuições para a teoria dos números primos.
No processo evolutivo humano e no aperfeiçoamento do conhecimento
quantitativo é observada ainda uma carência no conjunto dos números naturais.
Nesse conjunto não existia resposta para um cálculo, do tipo m - n, onde n > m,
presente no cotidiano social, uma vez que os homens, já tinham emigrado das
cavernas para as cidades primitivas.
Do fato de existir um desequilíbrio intelectual no ser humano, visto que eram
incapazes de dizer com exatidão a solução do cálculo, da forma m – n, com n > m,
houve a necessidade de sanar essa lacuna, então surgem novos números: os
“Números Negativos” e, ao acrescentar esses números aos números naturais, esse
conjunto, então formado, recebe o nome de conjunto dos números inteiros,
representado pelo símbolo ℤ advindo da palavra alemã Zahl, que significa número,
dado por {...-2, -1, 0, 1, 2...} a primeira vez que os números negativos apareceram
em uma obra, foi no ano 628 d.C. na obra do indiano Brahmagupta.
O ser humano continua sua evolução social e intelectual e, conjuntamente,
surgem novas dificuldades e perguntas que precisam ser respondidas.
São estudados outros números com características em comum, como é o
caso dos números racionais ou conjunto dos números racionais, que são escritos da
15
forma
m
com n ≠ 0 , onde m e n são números inteiros, essa representação é
n
conhecida como fração, embora não fossem vistas como um número pelos primeiros
matemáticos, pois não era uma numeração bem constituída, agregando ainda à
dificuldade e o pouco conhecimento que se tinha de trabalhar com as frações
utilizando as regras dos números inteiros.
As frações só tiveram destaque quando se observou que as regras dos
números inteiros eram utilizadas na sua resolução. A necessidade dos números
racionais, representado pelo símbolo ℚ , surgiu da necessidade de se medir e de
comparar.
Mesmo com a infinitude de números já descobertos, havia ainda questões
não resolvidas, como era o caso da diagonal de um quadrado de lado 1, isto é, qual
era o valor dessa diagonal ? Qual é o valor de
2 ? Não havia nenhuma resposta
entre os números naturais, números inteiros e números racionais que satisfizesse o
problema. Assim, era necessário outro conjunto de números, conhecido hoje, como
números irracionais ou conjunto dos números irracionais.
A introdução dos números irracionais representada pelo símbolo
Ι
no
universo matemático ficou oculta por algum tempo, somente um seleto número de
matemáticos sabiam da existência desses números “desordenados”. Esses
matemáticos eram conhecidos por seguir a doutrina do matemático Pitágoras (aprox.
500 – 300 a.C.). Os pitagóricos defendiam a ideia de perfeição, e a introdução
desses números poderiam desestruturar a doutrina pitagórica, e arruinar a imagem
de excelência da matemática como ciência perfeita.
O segredo dos números irracionais foi sendo descoberto por outros
matemáticos, que se interessaram pelos números. Não havia como ocultar tais
números, até que a formalização desses números foi estabelecida como sendo os
números não racionais, cujos algarismos após a vírgula são infinitos e nunca se
reproduzem na mesma ordem.
Diante da existência dos conjuntos numéricos, observou-se que não havia um
conjunto que contivesse todos os demais conjuntos, pois de um lado isolado ficava o
conjunto dos números irracionais e, do outro, o conjunto dos números racionais , isto
é, os números naturais estão contidos no conjunto dos números inteiros, que estão
16
contidos no conjunto dos números racionais. Assim, a união de todos os conjuntos é
chamada de conjunto dos números reais, representado pelo símbolo ℜ .
As descobertas numéricas foram aparecendo ao passo que as necessidades
surgiram e hoje temos inúmeras teorias a respeito dessa infinitude numérica.
17
CAPÍTULO 2
Primícias Básicas da Aritmética
O grande arquiteto do Universo começa a parecer-nos um puro
matemático.
James Jeans
Neste capítulo apresentaremos os principais teoremas e definições da Teoria
dos Números, que servirão para estruturar as próximas análises, baseando nos
livros: Números: Construção e Propriedades de Valdir V. Silva; Introdução à Teoria
dos Números de Olimpio R. Gomes e Jhone C. Silva; Fundamentos da Aritmética de
Hygino H. Domingues e Primos de Mersenne ( e outros primos muito grande) de
Carlos G. Moreira e Nicolau Saldanha.
Segundo Filho (2009), definição e teorema na percepção matemática se
caracterizam, sendo:
Definir matematicamente um objeto é dar-lhe um nome mediante
determinadas propriedades que o caracterizem e o identifiquem
plenamente. Um teorema é uma afirmação matemática condicional ou
implicativa que precisa de uma demonstração para garantir sua validade.
Um teorema constitui-se de duas partes: as hipóteses, que fazem parte das
premissas, admitidas como verdadeiras [...] e a tese, que é a conclusão do
teorema. (FILHO 2009, p. 65 e p. 75)
_______________________________________________________Definições 2.1
Definição 2.1.1 Número:
1. A unidade é aquela que em virtude do qual cada uma das coisas que existe é
chamado um;
18
2. Um número é composto por uma multiplicidade de unidade.
Essa definição de Número foi dada por Euclides de Alexandria e publicada em
sua obra “Os Elementos”.
Definição 2.1.2 Divisibilidade: Dados dois números inteiros m e n com m ≠ 0,
dizemos que m divide n se, existir um número q
Notação: m | n, então
um q, tal que n = m q;
m n, então
um q, tal que n = m q.
tal que n = m q.
Definição 2.1.3 Algoritmo de Euclides: Se a e b são números inteiros, com b ≠ 0,
então existem e são únicos os números r e q
que satisfazem às seguintes
condições:
a = bq + r e 0 ≤ r < b .
Definição 2.1.4 Máximo Divisor Comum: Sejam a e b
, com a e b diferentes de
zero. O máximo divisor comum de a e b é o número natural d que satisfaz as
seguintes condições:
(i)
d | a e d | b;
(ii) Se existe um
d1
tal que
d1 a
e
d1 |b , então d1 | d .
Notação: mdc (a, b) = d
Definição 2.1.5 Mínimo Múltiplo Comum: Sejam a e b
, com a e b diferente de
zero. O mínimo múltiplo comum de a e b é o número natural s que satisfaz as
seguintes condições:
(i)
a | s e b | s;
19
(ii) Se existe um
s1
tal que
a | s1 e b| s1 , então s | s1 .
Notação: mmc(a, b) = s
Definição 2.1.6 Número Primo: o número natural p ≠ 1 é classificado como número
primo se, e somente se, os únicos divisores não negativos de p são 1 e p.
No VII e IX livros da obra “Os Elementos”, o matemático e professor da
famosa biblioteca de Alexandria, Euclides, dedicou a estabelecer as bases
fundamentais da aritmética e definiu número primo sendo.
Definição 2.1.7 Número Composto: Número composto é um número natural que
não é um número primo, diferente de 1 e 0.
Euclides definiu o número composto, sendo: um número composto é aquele
que é medido por algum número.
Definição 2.1.8 Números Primos entre si: Dois números m e n diferentes de zero
são chamados de primos entre si, se mdc (a, b)= 1.
Definição 2.1.9 Pseudoprimos de Fermat: Números compostos que satisfazem o
pequeno teorema de Fermat, (teorema 2.2.2, p.20).
n
Definição 2.1.10 Números de Fermat: Todos os números da forma 22 +1 com n
Definição 2.1.11 Números de Mersenne: Todo número da forma 2 p -1 , com p sendo
um número primo.
Definição 2.1.12 Congruência Módulo m: Sejam a e b números inteiros e m um
número inteiro maior que 1. Dizemos que a é congruente a b módulo m se m divide
a diferença a – b.
20
Notação: a ≡ b (mod m).
________________________________________________Teoremas 2.2
Teorema 2.2.1 Teorema Fundamental da Aritmética: Se n ∈ ℤ e n > 1 , então
existem
e
são
únicos
os
números
primos
p1 ≤ p2 ≤ p3 ... ≤ pk
tais
que
n = p1 ⋅ p2 ⋅ p3 ...pk .
Para demonstrar esse teorema é necessário enunciar o segundo princípio de
indução e um lema.
Segundo Princípio de Indução: Seja p(n) uma função proposicional cujo domínio é o
conjunto dos números inteiros maiores que, ou iguais, a um inteiro dado a.
Suponhamos que:
(i) p (a) é verdadeiro;
(ii) Se r é um número inteiro maior que a (r > a) e p(s) é verdadeiro para todo
s satisfazendo a ≤ s < r , então p(r) é verdadeiro.
Então temos que p(n) é verdadeiro para todo n ≥ a .
Lema: Sejam p,q1 ,q2 ,...qn números primos e suponhamos que p divide o produto
q1 ⋅ q2 ⋅ ...⋅ qn . Então p = q j para algum j ∈{1,2,3...n} .
Demonstração do Teorema Fundamental da Aritmética:
1ª etapa: provar a existência. Para isso será utilizado o método do segundo princípio
de indução.
Base de Indução: Devemos mostrar que p(2) é verdadeiro. Como o número 2 é
primo, então p (2) é verdadeiro.
21
Hipótese de Indução: Suponhamos que p (k) é verdadeiro para todo 2 ≤ s < k , essa
suposição nos leva a validar a existência de números primos p1 ≤ p2 ≤ p3 ... ≤ pr
tais que s = p1 ⋅ p2 ⋅ p3 ...pr . Precisamos mostrar a afirmação para k, ou seja, que
p(k) é verdadeiro.
É necessário provar que existem números primos p1 ≤ p2 ≤ p3 ... ≤ pr tais que
k = p1 ⋅ p2 ⋅ p3 ...pr . Se k for um número primo então k = p1 , mas se k for um número
composto, então k é o produto de dois números, isto é, k = v ⋅ u com 1 ≤ u < k e
1 ≤ v < k , pela Hipótese de indução existem primos wi e t y , i, y ∈{1,2,3,...n} tais
que:
n
n
i =1
y =1
u = ∏ wi e v = ∏ t y . .
Assim k = wi ⋅ t y , então k pode ser escrito como um produto de primos, logo
p(k) é verdadeiro.
2ª etapa: unicidade, para isso será utilizado o lema já enunciado.
Para provar a unicidade o método mais eficaz é supor a existência dupla e
mostrar que, são iguais.
Assim, suponhamos que k tenha duas decomposições:
k = p1 ⋅ p2 ⋅ p3 ...pi e k = p1 ⋅ p2 ⋅ p3 ...p j .
Sem perder a generalidade, suponhamos que j ≥ i , assim p1 | q j , isto é
p1 = qn para algum n ∈{1, 2 ,3 ,...j} . (Lema)
Vamos supor que p1 = q j , assim temos que: p1 ⋅ p2 ⋅ p3 ...pi = p1 ⋅ q2 ⋅ q3 ...q j
logo p2 ⋅ p3 ...pi = q2 ⋅ q3 ...q j se repetíssemos esse processo í vezes teremos pn = qn
para todo n ∈{1, 2 ,3 ,...j} , assim podemos afirmar que i = j , do contrário i > j
teríamos p1 ⋅ p2 ...pi = p1 ⋅ p2 ...pi ⋅ qi+1 ...q j o que levaria a 1= qi+1 ...q j , isto é, q j seria
um divisor de 1 o que é impossível. Logo pn = qn para todo n ∈{1, 2 ,3 ,...j} e i = j ,
o que prova que a decomposição é única.
22
Teorema 2.2.2 Pequeno Teorema de Fermat: Seja p um número primo e a um
inteiro, então a p ≡ a(mod p) .
Demonstração:
Se a não é múltiplo de p e considerando a sequência de números
a,2a,3a,...,(p -1)a , e sendo 1 ≤ i < j ≤ p -1 , como ja - ia = (j - i)a , logo p (j - i)a
implica p (ja - ia) que por sua vez p ja , j = 1, 2, 3, ...(p -1) , sendo assim o resto
da divisão euclidiana dos números a, 2a,3a,...,(p -1)a
por p, formam uma
permutação dos números 1 ⋅ 2 ⋅ 3...(p -1) , temos que:
a ⋅ 2a ⋅ 3a...(p -1)a ≡ 1⋅ 2 ⋅ 3...(p -1) ( mod p )
que é equivalente
( p -1) !a p-1 ≡ ( p -1) ! ( mod p ) ,
mas o mdc ( p -1, p ) = 1 , logo a p-1 ≡ 1 ( mod p ) , multiplicando a nos dois lados da
congruência, temos:
a p ≡ a ( mod p ) .
Se a for múltiplo de p, então a ≡ 0(mod p) e
a p ≡ 0 p (mod p) que é o
mesmo que a p ≡ 0(mod p) por transitividade concluímos que a p ≡ a ( mod p ) .
Teorema 2.2.3 Teorema de Euler: Todo inteiro m >1 ,
a ∈ Z primo com m vale a
congruência:
a φ( m ) ≡ 1 ( mod m )
Para demonstrar o teorema de Euler necessário enunciar uma função,
conhecida como função
Definição: A função
de Euler:
ϕ : ℕ* ⇒ ℕ* que associa a cada m∈ℕ* o número de elemento
do conjunto {k ∈ N * |1 ≤ k ≤ m, mdc(k,m)= 1} é chamada de função
Notação: φ(m)
de Euler.
23
Demonstração:
Sejam s1 ,s2 ,s3 ...sk inteiros de 1 a m , inclusive os extremos, que são primos
com m (k = φ(m)) , dividamos cada asi por m:
asi = mqi +ri (0 ≤ ri < m)
Se existisse um primo p tal que p | m e p | ri então p | asi , mas então p | a
ou p | si o que é impossível, visto que mdc(a,m)= 1 ∀ i 1 ≤ i ≤ k .
Observemos a sequência de restos, r1 ,r2 ,r3 ...rk . Nesta sequência não existem
elementos
que
se
repetem,
de
fato,
ri = rj (1 ≤ i, j ≤ k; i ≠ j ) , então
se
asi - mqi = as j - mq j , portanto a(si - s j )= m(qi - q j ) , levando em consideração que
mdc(a,m)= 1 então m|(si - s j ) com 1 ≤ si , s j ≤ m então teríamos que ter si = s j o
que é impossível uma vez que i ≠ j .
Assim
{s1 ,s2 ,s3 ...sk }= {r1 ,r2 ,r3 ...rk } se
multiplicarmos
as
congruências
asi ≡ r(mod
m) decorrente asi = mqi +ri (0 ≤ i < m ) .
i
a k s1 , s2 , s3 ...sk ≡ ( as1 ) ⋅ ( as2 ) ⋅ ( as3 ) ...( ask ) ≡ r1 , r2 , r3 ...rk ( mod m )
os produtos s1 ⋅ s2 ⋅ s3 ⋅ ... ⋅ sk e r1 ⋅ r2 ⋅ r3 ⋅ ... ⋅ rk são iguais, o produto r1 ⋅ r2 ⋅ r3 ...rk pode ser
cancelado, pois m é primo com cada ri ou si , na última congruência o que resulta
em, a k ≡ 1(mod m) , como k = φ(m) :
a φ(m) ≡ 1(mod m) .
Teorema 2.2.4 Teorema da Infinitude dos Números Primos: O conjunto formado
pelos números primos é infinito.
Demonstração:
24
Suponhamos que o conjunto dos números primos seja finito, listamos todos
os números desse conjunto finito:
P = { p1 , p2 , p3 ...pn } .
Agora construímos um número, de tal forma que esse número, seja o produto
de todos os números primos do conjunto P mais 1:
N = p1 ⋅ p2 ⋅ p3 ...pn +1 .
Temos duas condições:
(i) Se N for um número primo, então existe um número primo que não pertence
ao conjunto P , logo não podemos afirmar que o conjunto dos números
primos é finito, concluímos que existem infinitos números primos.
(ii) Se N for um número composto, então existe pi tal que pi | N , i = 1,2,3...n .
Que
é
o
mesmo:
pi | p1 ⋅ p2 ⋅ p3 ...pn +1 .
Seja
outro
número:
M = p1 ⋅ p2 ⋅ p3 ...pn , então pi | M . Logo,
pi |(N - M)
pi |(p1 ⋅ p2 ⋅ p3 ...pn +1)-(p1 ⋅ p2 ⋅ p3 ...pn )
pi |1
mas, se pi |1 , temos que 1 = pi ⋅ q absurdo, logo o conjunto P não pode ser finito,
Concluímos que o conjunto P , dos números primos, é infinito.
25
CAPÍTULO 3
A História de Alguns Matemáticos Pioneiros no
Estudo dos Números Primos
Os matemáticos não suportam admitir a possibilidade de que talvez, não
exista, uma explicação para o modo como a natureza, escolheu os primos.
Marcus du Sautoy
Um enigma matemático insolúvel, até então, tem instigado grandes
matemáticos, mentes brilhantes se rendem a tamanha complexidade que o
envolvem, esse enigma se chama números primos.
As
incertezas
que os
números primos
proporcionam, desafiam
os
matemáticos. Um problema que se arrasta há tempos e ainda ninguém foi capaz de
por um ponto final nesse enigma, isto é, nenhuma mente humana conseguiu
alcançar tal grau de abstração e complexidade necessária para decifrá-lo. Diante
desse impasse sobre a existência de uma fórmula exata e precisa dos números
primos, exímios matemáticos passaram grande parte de suas vidas dedicando-se ao
estudo dessa fórmula inimaginável.
Ao longo de 2.000 anos os números primos são conhecidos e estudados e,
até no início do século XXI, não se sabe uma fórmula com tamanha precisão que
possa gerar somente números primos e possibilite aos matemáticos saber qual é a
sua localização na sequência do conjunto dos números naturais.
O matemático inglês G. H. Hardy (1877 – 1947) disse que “qualquer tolo pode
fazer perguntas sobre os números primos que o mais sábio dos homens não
consegue responder”, essa frase de Hardy revela o pouco conhecimento que temos
sobre tais números.
A busca pela fórmula dos números primos mobilizou vários matemáticos,
alguns deles contribuíram de forma significativa para o avanço nessa teoria. No
26
entanto, esses significativos progressos ainda não permitiam que um matemático
pudesse responder uma pergunta, simples: existe uma fórmula para os números
primos?
Considerados como os átomos da aritmética, “os números primos constituem
a parte irredutível do sistema numérico, sendo a base de todos os números”
(PERUZZO, 2012, p.2).
A dificuldade dos matemáticos para encontrar essa fórmula geradora dos
números primos advém da forma como os números primos estão localizados, não há
um padrão. O matemático Leonhard Euler afirma que:
Alguns mistérios sempre escapam ao espírito humano. Para nos
convencermos, é suficiente olhar uma tabela de números primos e veremos
que não existe nenhuma ordem, nenhuma regra entre eles. (1675, apud
SAUTOY, 2007, p.13)
Euler falava sobre como os números primos são dispostos em sua sequência.
Mesmo com tamanha complexidade que há em volta da fórmula dos números
primos, muitos matemáticos enfrentaram o universo desconhecido da matemática
em prol de desvendar os enigmáticos números.
Alguns personagens mais renomados na matemática estudaram os números,
indecifráveis, e desses estudos surgiram definições, teoremas e conjecturas, que é o
conhecimento mais próximo da teoria enigmática dos números primos, isto é,
norteiam a teoria.
A seguir, alguns matemáticos que trabalharam para decifrar os números
primos.
_____________________________________________Euclides de Alexandria 3.1
Não se sabe muito a respeito da vida de Euclides,
antes de ser professor e diretor do setor de matemática na
Biblioteca de Alexandria; só que o mesmo era um
matemático grego e acredita-se que foi aluno do grande
filósofo Platão; onde e quando nasceu ou morreu são
27
informações que se perderam na história. O que realçou na vida de Euclides, não foi
o próprio Euclides, mas sua matemática rigorosa.
Reconhecido como um grande pensador da geometria, Euclides não se
limitou a estudar apenas a geometria, mas estudou e fez grandes contribuições para
Teoria dos Números, especificamente para Teoria dos Números Primos.
Nos primeiros anos trabalhando na biblioteca, exercia a função de professor,
conta-se que:
Um aluno que começara a tomar lição com ele, perguntou: afinal, que
vantagem poderia obter com aqueles conhecimentos. Em resposta,
Euclides chamou seu escravo e disse: “Dê-lhe uma moeda, porque ele
precisa ganhar com aquilo que aprendeu”. (GARBI, 2010, p.58)
O clímax da sua história ocorreu quando reuniram alguns conhecimentos
matemáticos em 13 livros, conhecidos como Os Elementos. Trata-se de uma
formalização dos conceitos matemáticos, uma grande parte dos Elementos é
dedicada à geometria, no entanto, nos livros VII e IX, Euclides estabelece os
conceitos fundamentais de Teoria dos Números.
Especificamente no livro IX Euclides demonstra com rigor, mas entrelaçado
de uma elegância singular, que os números primos são infinitos.
Essa contribuição para a Teoria dos Números Primos foi um convite para os
futuros matemáticos se aventurarem nesse universo desconhecido. Mesmo que
Euclides tenha tentado provar uma fórmula que define os números primos, todas as
suas tentativas foram frustradas, no entanto, uma peça do quebra-cabeça dos
números
primos
foi
colocada
no
lugar
certo,
era
necessário
esperar
aproximadamente 70 anos até que se ouvisse falar outra vez da pedra angular da
matemática, os números primos.
____________________________________________Eratóstenes, de Cirene 3.2
Após a demonstração da infinitude dos números primos,
houve-se um esquecimento desses números por parte dos
matemáticos,
o
problema
era
complexo
e
fugia
dos
conhecimentos matemáticos daquela época, uma vez que esses
28
números não respeitam um padrão matemático.
Só foi pronunciada outra vez a definição de números primos nos corredores
da grande Biblioteca de Alexandria, na voz do matemático Eratóstenes, há cerca de
240 a.C. quando se tornou diretor da Biblioteca.
Nascido por volta de 274 a.C. na cidade de Cirene, Eratóstenes ousou
responder aquilo que não havia resposta, isto é, decidiu enfrentar e exigir respostas
da sequência dos números primos. O Beta da matemática, assim que era visto por
alguns, pois em toda área do conhecimento que atuava sempre existia um nome
mais importante que o seu, embora fosse visto como um ilustre sábio da época,
levou por toda sua vida a posição de segundo lugar. Ficou famoso por ter calculado
o tamanho aproximado da Terra; seus conhecimentos norteiam a História,
Geografia, Astronomia e Matemática.
Na matemática, estudou Teoria dos Números, e embarcou em uma viagem
pelos números primos, à procura da resposta: qual é a fórmula dos números primos?
Uma viagem que não chegou ao seu destino; no entanto, se não podia dizer qual é a
fórmula dos números primos, poderia dizer quais são os números primos. Nessa
perspectiva, Eratóstenes forjou um método para obter essa resposta.
Não se pode afirmar com precisão, Eratóstenes tinha em mãos a certeza da
infinitude dos números primos e um olhar cauteloso para à definição de números
primos, com isso nasce o método mais simples e intrigante, de trazer conhecido, os
números primos de 2 até N, esse método ficou conhecido como Crivo de
Eratóstenes.
Basicamente Eratóstenes, engenhosamente listou a sequência de 2 até N
com N
.
Para fazer o exemplo a seguir suponhamos que N seja 25:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25.
Excluindo dessa sequência todos os números múltiplos de dois, exceto o
próprio 2, pois esses não poderiam ser primos, uma vez que contraria a definição de
números primos para o conjunto dos números naturais, isto é, um número múltiplo
29
de dois é da forma 2K, e o conjunto dos divisores de 2K é {1,2,k,2k} . Ficando
apenas os números:
2, 3, 5, 7, 9, 11, 13,15, 17, 19, 21, 23, 25
Nessa fase do Crivo de Eratóstenes, retira-se todos os múltiplos de 3, exceto
o próprio 3, Pois, os números múltiplos de 3 são da forma 3K cuja os divisores de
3K são {1,3,k,3k} , o que contraria a definição de números primos, logo todos os
múltiplos de 3 não são primos. Ficando apenas os números:
2, 3, 5, 7, 11, 13, 17, 19, 23, 25.
Novamente retiramos todos os múltiplos de 5, exceto o próprio 5, os números
múltiplos de 5 são da forma 5K, cuja seus divisores são {1,5,k,5k} o que contraria a
definição de números primos, logo a sequência de múltiplos de 5, não são primos.
Ficando apenas:
2, 3, 5, 7, 11, 13, 17, 19, 23.
(1)
Observe que nessa última sequência não tem números múltiplos de 7
excluindo o próprio 7, não tem de 11, nem de 13, 17, 19 e 23. Quando chegamos a
esse resultado, de não ter múltiplos de K tal que, 2 < k < N , segundo o Crivo de
Eratóstenes podemos afirmar que a sequência (1) é uma sequência de números
primos.
Ao analisarmos o método de Eratóstenes para encontrar uma sequência finita
de números primos, podemos dizer que quanto maior for o N, mais trabalhoso o
Crivo de Eratóstenes se apresenta, isto é, se N for um número com 6 algarismos o
crivo se torna inviável. Segundo afirma Ávila (1991, p. 20):
Com o crivo de Eratóstenes podem-se determinar, sem auxílio de
máquinas, todos os números primos até 200, 400 ou 500, por exemplo.
Com o auxílio de computadores, o crivo de Eratóstenes, convenientemente
adaptado, permite determinar os números primos até limites bem altos.
Eratóstenes tem um fim triste aos 80 anos, já cego, privou-se da alimentação
e morreu em 194 a. C.
30
Mais um degrau no edifício dos números primos é alcançado; uma
contribuição significativa que Eratóstenes proporcionou, mas ainda bem distante da
fórmula dos números primos.
__________________________________________________Pierre de Fermat 3.3
Nascido em 1601 na frança, filho de um próspero
comerciante de pele, Pierre de Fermat não conhecia as
ciências exatas, pois era um jurista por formação, que
futuramente seria um magistrado.
A paixão pelos números ocorreu quando restaurava, em
1629, uma obra antiga de Diofanto; isso era comum na época,
para ser específico o livro “Aritmética”. Ao restaurar tal livro,
nasce um célebre matemático amador, que estudava apenas nas horas vagas, mas
o suficiente para se constituir como um dos matemáticos mais respeitados até hoje,
pela sua grande colaboração para os vastos conceitos da matemática.
Com uma timidez ousada, Fermat o príncipe dos amadores, reaparece com
conceitos antigos, esquecidos pelo tempo:
Fundador da moderna Teoria dos Números, Fermat tinha particular
interesse por esse assunto, parado desde que a biblioteca de Alexandria foi
incendiada. (CONTADOR, 2006, p.188)
Tinha o poder de despertar em seus amigos cientistas, o interesse pela Teoria
dos Números, através de trocas de cartas, mas sempre sem demonstrar nenhum
teorema que enunciava. Nessas cartas, Fermat propunha desafios aos colegas,
como dizia Contador:
Fermat tinha o costume de fazer anotações às margens dos livros que lia, e
normalmente essas anotações traziam teoremas sem sua dedução. Era
comum Fermat enviar cartas a seus colegas com esses teoremas, depois
desafiava seus contemporâneos a encontrarem a dedução. Ele mesmo
nunca relatava suas deduções. ( CONTADOR, 2006, p.184)
Exemplos de alguns dos teoremas de Fermat:
31
Teorema I: Sejam dois números m e n primos entre si, onde, n é primo: m
n −1
é
divisível por n.
Teorema II: Um número primo da forma 4n+1 pode ser representado como a soma
de dois quadrados.
Coube ao matemático Leonhard Euler (1707-1783) demonstrar, esses
teoremas.
O fascínio pela Teoria dos Números levou Fermat a estudar os números
primos, desse estudo “nasce” um teorema. Fermat escreve uma carta ao seu amigo,
Bernard Frénicle de Bessy (1612-1675) em 1640, enunciando o teorema, como de
praxe, não seguia uma demonstração.
Fermat afirmou que se p é um número primo e a é um inteiro, então a
p
congruência se verifica: a ≡ a(mod p ) . (teorema 2.2.2. p.20)
Essa congruência pode ser vista como um subsídio para verificar se p é um
número primo, isto é, suponha que queremos testar se 47 é um número primo, tendo
47
a = 3, se 3 deixar resto 3 no módulo 47, então o número 47 é primo, isto foi o que
Fermat queria dizer com a congruência.
Verificando se 47 realmente é um número primo:
310 ≡ 17(mod 47)
(3 )
10
4
≡ 17 4 (mod 47)
17 4 ≡ 2(mod 47)
Por transitividade, isto é, a ≡ b (mod m ) e b ≡ c (mod m ) , então a ≡ c (mod m ) ,
temos que:
340 ≡ 2(mod 47)
340 ⋅ 37 ≡ 2 ⋅ 37 (mod 47)
2 ⋅ 37 ≡ 3(mod 47)
347 ≡ 3(mod 47) .
32
Portanto, pelo Teorema de Fermat o número 47 é um número primo; este
teorema é conhecido como o Pequeno Teorema de Fermat, demonstrado por Euler
em 1736.
O teste para verificar se um número é primo ou composto, pelo Pequeno
Teorema de Fermat falha, por exemplo: queremos testar se 561 é um número primo,
utilizando o pequeno Teorema de Fermat, com a = 2.
240 ≡ 1(mod 561)
(2 )
40
10
≡ 110 (mod 561)
2 400 ≡ 1(mod 561)
2400 ⋅ 2100 ≡ 1 ⋅ 2100 (mod 561)
2100 ≡ 67(mod 561)
2500 ≡ 67(mod 561)
2500 ⋅ 260 ≡ 67 ⋅ 260 (mod 561)
67 ⋅ 260 ≡ 1(mod 561)
2560 ≡ 1(mod 561)
2560 ⋅ 2 ≡ 1 ⋅ 2(mod 561)
2561 ≡ 2(mod 561)
Pelo Pequeno Teorema de Fermat o número 561 é um número primo, o que é
uma inverdade, visto que, a decomposição de 561 em fatores primos é
561 = 3 ⋅11 ⋅17 , portanto 561 é um número composto.
O teorema indica que 561 é um número primo, para esses números
compostos que possuem propriedades que se esperam apenas para números
primos, chamamos de pseudoprimo.
O número 561 é um pseudoprimo de Fermat, esses números são escassos,
no Pequeno Teorema de Fermat conjectura-se que os pseudoprimo de Fermat são
infinitos.
Em uma carta enviada para um matemático, Fermat afirmava ter solucionado
o problema matemático, que desafiou Euclides e Eratóstenes e outros matemáticos.
33
Na carta, Fermat dizia que tinha encontrado a chave que abriria o segredo mais
oculto da matemática, tinha encontrado uma fórmula precisa e exata dos números
22 + 1 , n ∈ ℕ .
n
primos, expressa pela seguinte forma:
Para n ≤ 4 a fórmula é verdadeira, Fermat acreditou que era para todos os
números naturais, talvez pela dificuldade de fazer os cálculos para o próximo n, isto
é, para n = 5, à afirmação de Fermat é falsa, pois:
5
22 + 1 = 232 + 1 = 4294967297 = 641 ⋅ 6700417
Não há nenhum estudo que mostre que existam mais números primos de
Fermat, além dos primeiros cinco encontrados pelo próprio.
Em 1665 Fermat morre, no entanto, é lembrado não por ter sido um
magistrado, mas pela contribuição para a matemática e seus inúmeros teoremas
sem demonstração. Para a Teoria dos Números Primos, Fermat é responsável por
“trazer de novo a aritmética”, perdida nos escombros da antiga biblioteca de
Alexandria.
___________________________________________________Leonhard Euler 3.4
Leonhard Euler nasceu em 1707 na cidade de Basileia,
aprendeu com o pai o gosto pela matemática, no entanto, o pai
de Euler desejava que seu filho fosse clérigo, mas a vocação
de Euler não era ser membro da igreja, mas ser acadêmico na
Academia de Ciências de São Petersburgo.
Em 1726, Euler parte para a Academia de Ciências de
São Petersburgo, onde adquiriu um respeito de todos os
matemáticos da Europa, principalmente da corte representada por Catarina, a
Grande.
Euler é visto como águia matemática, por sua grande contribuição para
matemática
e,
porque,
se
reunirmos
todas
as
suas
obras,
teríamos
aproximadamente entre 60 a 80 volumes. Euler foi tão engenhoso nos conceitos
matemáticos, que após 50 anos de sua morte, que ocorreu em 1783, a Academia de
São Petersburgo publicava seus trabalhos. O matemático francês, Pierre Simon
34
Marquis de Laplace (1749 – 1827) dizia que Euler era o mestre de todos nós: “Leiam
Euler, leiam Euler, ele é o mestre de todos nós”.
Euler foi atraído pela Teoria dos Números, influenciado pelo matemático e
amigo Christian Goldbach, em troca de cartas. Goldbach conjecturou em 1742 para
Euler que todo número par poderia ser expresso pela soma de dois números primos,
esse diálogo escrito com Goldbach, abriu caminhos para Euler, que já estudava as
conjecturas de Fermat, exibir suas descobertas e demonstrações.
Euler foi responsável por demonstrar o Pequeno Teorema de Fermat. Não
satisfeito, generalizou o teorema ao introduzir a função
como função
, que hoje é conhecida
de Euler, função essa que gera a quantidade de números primos
com um determinado n, contido nos naturais.
A função
de Euler, são todos os números da sequência:
1, 2, 3, 4,..,n-1, n.
Que são primos com n, isto é, se o máximo divisor comum de n com um
número m, tal que 1
m
n resultar em 1.
Então Euler afirmou que, todo inteiro m > 1 ,
a ∈ ℤ , primo com m vale a
congruência:
aϕ ( m ) ≡ 1( mod m ) .
Ao estudar as obras de Fermat, Euler se depara com problemas sem
respostas, um deles é sobre os números primos que Euler investe tempo e estudo
para solucionar; tentou ultrapassar as barreiras estabelecidas pelos números primos,
pois queria encontrar uma fórmula simples, que fosse a resposta que tanto Euclides
desejava encontrar.
Nos estudos de Euler, a procura da fórmula dos números primos, se vê frente
a uma fórmula quadrática n² + n + 41, onde ele observou que para n entre 0 e 39
essa fórmula quadrática gera números primos, no entanto para n = 40 a fórmula
resulta em um número composto, Euler ficou intrigado com essa observação.
Todos os matemáticos de Euclides até Euler insistiam para que a matemática
abrisse caminhos, que levasse ao segredo dos números primos, mas o caminho era
35
árduo e labiríntico; era primordial que outra pergunta fosse proferida no universo
matemático, que pudesse alcançar o mais profundo e complexo conceito para
decifrar os números primos.
_______________________________________________Carl Friedrich Gauss 3.5
A pergunta que tanto era essencial para desatar os
nós dos números primos foi ouvida na voz “do mais notável
dos matemáticos”, filho de jardineiro e de mãe analfabeta.
Carl Friedrich Gauss se revelou um grande pensador da
matemática com três anos, pois nessa idade já corrigia os
erros de aritmética de seu pai, aos 15 anos ganhou um livro
de logaritmos e se encantou.
Mas foi com 17 anos que Gauss decidiu dedicar-se à matemática. O respeito
entre os cientistas da época veio quando Gauss tinha 24 anos, ele anunciou que
sabia onde os astrônomos deveriam encontrar um corpo celeste perdido, o pequeno
planeta Ceres, que foi descoberto pelo astrônomo Giuseppe Piazzi, mas ao passar
próximo do sol o planeta desapareceu.
O príncipe da matemática, assim é identificado Gauss, quando menino
ganhou uma tábua de números primos e sempre se dedicou ao estudo da
matemática pura, especificamente a Teoria dos Números; teve um apego pelos
números primos, diz-se que todos os dias Gauss contava certa quantidade de
números primos.
Sua contribuição se deu em quase todos os campos matemáticos. Tinha certa
cautela em revelar suas descobertas, que ele reproduzia todas em um diário, com
uma escrita que só ele entendia, até hoje não se sabe o significado de muitas
palavras contidas nesse diário, como por exemplo, não se sabe o que Gauss quis
dizer com “VicimusGEGAN”.
Mas o olhar de gênio foi quando Gauss observou e questionou quantos
primos tem entre 2 até 1000, entre 2 até 100000 e assim sucessivamente. Ao passo
que relacionou números primos com logaritmos, até então, ninguém pensou nessa
perspectiva, mas Gauss sim.
Então Gauss podia estimar aproximadamente, quantos números primos tinha
entre 2 e n pela expressão:
36
n
.
log n
Também inseriu na Teoria dos Números a função de contagem dos números
primos representada pela fórmula:
1
dt , n ∈ ℕ.
2 ln t
n
π ( n) ≅ ∫
A função
π ( n ) conta a quantidade de números primos da sequência de 2 a
n, devemos salientar que neste caso,
π
nada tem a ver com o número 3,1415..., se
trata apenas de um símbolo para representar a função de contagem dos números
primos.
A demonstração da aproximação da função
π ( n ) dada pela integral definida,
e a maneira com que Gauss foi induzido a formalizar foi omitida, uma vez que não
cabe a sua demonstração por se tratar de conceitos de nível superior ao nosso
trabalho.
37
CAPÍTULO 4
Testes de Primalidade
Quanto mais o homem se preocupa com os números, mais os números
torturam o homem.
Renato Sousa Lopes
O insucesso nas tentativas para deduzir uma fórmula precisa e exata dos
números primos levou os matemáticos a não afrontar a matemática desses números,
visto que diversos matemáticos tinham perdido a batalha intelectual com a rainha
das ciências, pois essa, não permitiu que nenhum matemático contemplasse tal
fórmula.
Quanto mais se estudava sobre os números primos, mais números primos
eram encontrados, até o momento em que dizer se um número é primo ou
composto, tornou-se uma façanha difícil para os matemáticos. Nesse episódio dos
números primos, o interesse em sua totalidade não era deduzir uma fórmula para os
primos, mas “simplesmente” afirmar se um número é primo.
Observou-se que não havia na teoria dos números primos, um método
simples e rápido que verificasse se determinado número é primo, então era
necessário criar uma técnica matemática embasada na definição de números
primos, que sanasse esse problema, que surgiu no decorrer do estudo dos números
primos.
O matemático Gauss em 1798 afirmou que:
O problema de distinguir os números primos dos números compostos e de
exprimir estes últimos à custa de seus fatores primos deve ser considerado
como um dos mais importantes e dos mais úteis em Aritmética... A própria
dignidade da ciência requer que todos os meios possíveis sejam explorados
para a resolução de um problema tão elegante e tão famoso. (1798, apud
Ribenboim, 2001, p.11)
38
O crivo de Eratóstenes era uma técnica matemática, para conhecer um
número primo, mas trabalhosa para alguns casos, no entanto, era uma técnica
matemática, que a partir desse procedimento, levou os matemáticos a pensar em
outros métodos para conhecer as propriedades dos números, isto é, se um número
é primo ou composto. Os matemáticos sempre buscam construir seus pensamentos
em cima dos pilares elementares, o pensamento indutivo do crivo de Eratóstenes,
proporcionou isto aos matemáticos.
Como é impossível dizer, qual é o próximo número primo em sua sequência
ou ver uma fórmula que gerasse somente números primos, poderíamos dizer se um
número é primo ou não. Então foi introduzido na Teoria dos Números Primos o Teste
de Primalidade que objetiva responder tal pergunta:
n ∈ ℕ é um número primo?
__________________________________________________Testes Primitivos 4.1
O primeiro modo de dizer se n ∈ ℕ é um número primo, é decompondo n em
fatores de números primos, se n tiver apenas um fator primo, isto é, a única forma de
fatorar n é o próprio n, então classificamos n, sendo um número primo, do contrário,
se
n
possui em sua
α
decomposição mais
de
um
fator primo,
isto
é,
α
α
n = p1 1 ⋅ p2 2 ... pn n , então n, neste caso será um número composto.
O crivo de Eratóstenes é considerado um teste de primalidade, pois o crivo
permite dizer se
p
tal que,
2 ≤ p ≤ n é primo ou não. (Capitulo 3, item 3.2)
Outro método é pela radiciação, conhecido como Teste da Raiz, este teste é
simples, mas executável apenas para um n ∈ ℕ “pequeno”, pois se n for um número
com 6 algarismos, por exemplo, o teste se torna exaustivo. Para verificar se
n∈ℕ
é um número primo, utilizando o Teste da Raiz, basta dividir o número n por todos os
primos menor ou igual à
n , se nenhum desses números primos menor que a n
dividir n, então pelo Teste de Raiz podemos afirmar que n é primo, caso exista um
número primo
composto.
p
menor que a
n , de forma que esse p | n , então n é um número
39
O Pequeno Teorema de Fermat, também permite saber se um determinado
número é primo, como foi visto no capítulo 3, o Teorema, conjecturado pelo
matemático Fermat, não leva o nome de Teste de Primalidade, mesmo possuindo a
característica necessária para ser classificado como tal, o motivo é que o teorema
apresenta pseudoprimos.
___________________________________________________Teste de Lucas 4.2
Considere n um número natural ímpar, e f um número também natural, que
satisfaça 2 ≤ f ≤ n − 1 , temos às seguintes condições:
i.
Se f n −1 ≡ 1(mod n) ;
n −1
ii.
Se f
piαi
≡/ 1(mod n) , onde p são os fatores primos de n − 1 , isto é,
n − 1 = p1 1 ⋅ p2 2 ⋅ p3 3 ... pi i , i ∈ℕ .
α
α
α
α
Se essas condições forem asseguradas, então n é um número primo pelo
Teste de Lucas.
A demonstração da veracidade do Teste de Lucas será omitida.
Exemplo 1: utilizando o Teste de Lucas para verificar se 7 é um número
primo: informações para desenvolver o Teste de Lucas, n = 7; n-1 = 6 e f = 5 tal
que, 2 ≤ 5 ≤ 6 .
O primeiro requisito é verificar se f
n −1
≡ 1(mod n ) , isto é, 56 ≡ 1(mod 7) :
54 ≡ 2(mod 7)
54 ⋅ 52 ≡ 2 ⋅ 52 (mod 7)
56 ≡ 2 ⋅ 52 (mod 7)
2 ⋅ 52 ≡ 1(mod 7)
56 ≡ 1(mod 7)
40
Logo 56 é côngruo a 1 no módulo 7.
A segunda condição é trabalhar na congruência os fatores de números primos
de n-1, que são 6 = 2 ⋅ 3 .
n −1
Na congruência f
α
pi i
≡/ 1(mod n) , devemos mostrar, para p = 2 que 53 não é
côngruo a 1 no módulo 7 o que é verdade, visto que 53 ≡ 6(mod 7) , portanto,
53 ≡/ 1(mod 7) . Para p = 3 devemos mostrar que 5 2 não é côngruo a 1 no módulo 7, o
que também é verdade, pois 52 ≡ 4(mod 7) . Logo, pelo Teste de Lucas o número 7 é
primo, pois satisfez as duas condições do Teste.
____________________________________________________Teste de Pepin 4.3
A base fundamental do Teste de Pepin se alicerça no número de Fermat, já
apresentado no capítulo 3 item 2.1.10, no entanto, escreveremos uma notação
2 2 + 1 , onde n ∈ ℕ . Essa notação
n
diferente para os números gerados pela fórmula
objetiva simplificar os cálculos do Teste de Pepin, tal notação escrita da forma
Fn = 22 + 1 .
n
O
b
Fn −1
2
número
de
Fn = 2 2 + 1
n
Fermat
é
primo
para
n >1,
quando,
≡ − 1(mod Fn ) , onde b = 5.
Exemplo 1: Testando se
F3 é primo.
É necessário verificar se a congruência é verdadeira, isto é, se
5
F3 −1
2
≡ −1(mod F3 ) .
F3 = 22 + 1 = 257 ;
3
F3 − 1
= 128
2
Assim sendo, temos que mostrar que 5128 ≡ −1(mod 257) :
510 ≡ 139(mod 257)
(5 )
10
10
≡ 13910 ( mod 257 )
5100 ≡ 13910 ( mod 257 )
41
13910 ≡ 465 ( mod 257 )
465 ≡ 96 ( mod 257 )
5100 ≡ 96 ( mod 257 )
5100 ⋅ 520 ≡ 96 ⋅ 520 (mod 257)
96 ⋅ 520 ≡ 120(mod 257)
5120 ≡ 120(mod 257)
5120 ⋅ 58 ≡ 120 ⋅ 58 (mod 257)
120 ⋅ 58 ≡ −1(mod 257)
5128 ≡ −1(mod 257) .
128
Como mostramos que 5 ≡ −1(mod 257) , podemos afirmar pelo Teste de Pepin
que
F3 é um número primo.
Nos limitamos neste trabalho, a apresentar apenas estes testes de
primalidade que nos ajuda a perceber a primalidade dos números
42
CAPÍTULO 5
Uma Aplicação dos Números Primos: RSA
Não há ramo da matemática, por abstrato que seja que não possa um dia
vir a ser aplicado aos fenômenos do mundo real.
Lobachevsky
A matemática dos números primos mostrou-se impenetrável, qualquer
tentativa para decifrar seus códigos é inútil, no entanto, surge dessa dificuldade um
algoritmo. Este algoritmo de criptografia é o RSA que deve o seu nome aos três
professores que o criaram: Ronald Rivest, Adi Shamir e Leonard Adleman. O
algoritmo tem as suas bases fundamentais alicerçadas no conceito intransitável da
matemática: os números primos, isto é, o RSA se mantém indecifrável, uma vez que
se une aos números primos.
O RSA é um sistema utilizado principalmente em transações bancárias, e
agências de segurança, mas também em mensagens de e-mail e compras online,
nos dizeres de Sautoy o autor afirma que:
A segurança de RSA se baseia na nossa incapacidade de responder
questões básicas sobre os números primos. Nosso conhecimento sobre
eles é suficiente para gerar esses códigos para a internet, mas não para
decifrá-los. Entendemos uma metade da equação, mas não a outra.
( SAUTOY, 2007, p. 21)
O algoritmo do RSA utiliza-se de duas chaves, uma pública e a outra privada,
onde a chave privada é formada por um par de números (n, d), e a chave pública é
formada também por um par de números (n, c). Deve-se escolher adequadamente
os números n, d e c, pois eles compõem as chaves do algoritmo.
O algoritmo RSA geram as chaves da seguinte forma:
43
i.
São escolhidos dois números primos p e q, da ordem de 10100 no
mínimo;
ii.
Faça o produto de p e q, p ⋅ q = n este n é o número presente em
ambas às chaves;
iii.
Escolha c < n, tal que c e (p -1) ⋅ (q -1) sejam primos entre si;
iv.
Escolha d tal que (c ⋅ d) ≡ 1mod ( p -1) ⋅ ( q -1)  .
Para converter uma mensagem A (texto-original), onde 0 < A < n em uma
mensagem cifrada C (texto-cifrado), devemos utilizar a chave pública (n, c) e aplicar
o seguinte algoritmo, que objetiva cifrar a mensagem A.
A c ≡ C ( mod n )
assim temos a mensagem cifrada C, pelo algoritmo do RSA.
Para decifrar a mensagem C, é necessário utilizar a outra chave, a chave
privada (n, d), e aplicar o seguinte algoritmo:
Cd ≡ A ( mod n )
assim, temos novamente a mensagem original A.
Na prática o algoritmo do RSA funciona assim: vamos relacionar cada letra do
alfabeto a um número, isto é:
44
A partir da tabela criptografamos a palavra Número, vamos chamar de m a
mensagem simples e de A a mensagem criptografada.
m = Número
A = 341079719491
Gerando as chaves do algoritmo RSA:
São escolhidos dois números primos p e q da ordem de 10100 no mínimo,
para exemplificar tomaremos dois números primos p e q “pequenos” de maneira que
sejam possíveis os cálculos sem ter a necessidade de usar programa
computacional.
p = 13 e q = 11.
Fazer o produto de p e q (
p ⋅ q = n ) onde n é o número presente em ambas
as chaves.
n = 13 ⋅ 11
n = 143
Escolher c < n, tal que c e ( p − 1) ⋅ ( q − 1) sejam primos entre si, isto é,
mdc c, ( q -1) ⋅ ( p -1)  =1.
c = 71
(13 -1) ⋅ (11-1) = 120
mdc ( 71,120 ) = 1
Calcular um número d tal que (c ⋅ d) ≡ 1mod ( p -1) ⋅ ( q -1)  .
71⋅ d ≡ 1( mod 120 )
d = 191.
Assim obtivemos que: n =143 , c = 71 e d = 191, a partir desses dados, temos:
Chave Pública (c, n) = (71, 143)
Chave Privada (d, n) = (191, 143)
45
Já conhecidas as chaves do RSA é necessário dividir a mensagem A, que é a
mensagem criptografada em blocos, no entanto existem duas condições:
i.
Cada bloco deve ser menor que n = 143;
ii.
Não se pode iniciar um bloco com o algarismo zero.
Assim, temos que:
A = 341079719491
A = 34 – 10 – 79 – 71 – 94 – 91
Com a Chave Pública (c, n) = (71, 143) ciframos cada bloco de A com o
algoritmo do RSA, utilizando a congruência:
A c ≡ C ( mod n )
onde C é a mensagem cifrada, fazendo os cálculos, temos:
3471 ≡ 122 ( mod143 )
1071 ≡ 43 ( mod143 )
7971 ≡ 79 ( mod143 )
7171 ≡ 115 ( mod143 )
9471 ≡ 61( mod143 )
9171 ≡ 91( mod143 )
portanto C = 122 – 43 – 79 – 115 – 61 – 91 , isto é, C = 12243791156191.
Para decifrar a mensagem C, temos que utilizar a Chave Privada (d, n) =
(191, 143), juntamente com a congruência específica e dividir a mensagem em
blocos com as mesmas condições:
i.
Cada bloco deve ser menor que n = 143;
ii.
Não se pode iniciar um bloco com o algarismo zero.
46
Assim temos que:
C = 12243791156191
C = 122 – 43 – 79 – 115 – 61 – 91.
utilizando a congruência Cd ≡ A ( mod n ) em cada bloco, para decifrar a mensagem,
onde A é a mensagem inicial criptografada através da tabela 1.
122191 ≡ 34 ( mod143 )
43191 ≡ 10 ( mod143 )
79191 ≡ 79 ( mod143 )
115191 ≡ 71( mod143 )
61191 ≡ 94 ( mod143 )
91191 ≡ 91( mod143 )
Assim temos que: A = 34 – 10 – 79 – 71 – 94 – 91, voltando à tabela 1, e
decodificando a mensagem A, temos:
A=N–ú–m–e–r–o
A = Número
Uma das Maneiras de quebrar o algoritmo RSA seria conhecer os números
primos p e q que são fundamentais na construção do algoritmo, levando em
consideração que tanto p como q são números primos da ordem de 10100 no
mínimo, Lemos afirma que:
Caso por engano, jogássemos fora os primos p e q, e mantivermos apenas
o seu produto n, as maneiras mais promissoras para recuperar p e q seriam
procurar no lixão ou usar técnicas de hipnose, o que parece ser uma derrota
da matemática. ( LEMOS, 2005, p. 78)
47
Como vimos, o algoritmo RSA é um algoritmo seguro e um exemplo de
aplicação dos números primos que parece ser eficaz, já que o mesmo é utilizado nos
dias atuais, mesmo com toda tecnologia que temos.
48
CONSIDERAÇÕES FINAIS
A temporada à procura da fórmula dos números primos inicia-se através do
matemático Euclides de Alexandria provando a infinitude dos números primos e até
hoje essa busca continua, “seria necessário Prometeu roubar a fórmula divina e dar
aos mortais?”. (lembrando que Prometeu furtou o fogo divino, com o qual presenteou
a Humanidade)
Qual a fórmula exata e precisa dos números primos? Diante dessa pergunta
toda a comunidade científica matemática silencia-se, ainda não há um matemático
que consiga romper com esse silêncio.
Enquanto não temos a fórmula dos números primos para analisar e entender
seus
mistérios,
devemos
nos
embasar nos
caminhos
encontrados
pelos
matemáticos rumo a essa fórmula, caminhos esses que formam os teoremas e
definições que cada vez mais nos aproximam de compreender de fato um pouco
mais sobre os números primos.
O presente trabalho aborda este caminho, iniciando nos conceitos primordiais
da matemática que são os números naturais até chegar ao objeto de estudo que são
os números primos.
Segundo o escritor Rubens Alves (1995): "A coisa não está nem na partida e
nem na chegada, mas na travessia" e, é essa travessia que valorizamos, isto é,
apresentamos de forma sucinta um pouco da história dos números primos desde os
tempos de Euclides aos pensamentos revolucionários de Gauss até o algoritmo do
RSA, tudo com o objetivo de reunir alguns conhecimentos e alguns matemáticos
mais significativos para a teoria dos números primos, e assim adquirir
conhecimentos necessários para dialogar com o universo desses números.
Ao reunir tais conhecimentos podemos, de forma implícita, margear a tão
sonhada fórmula dos números primos, pois compreendemos que a matemática não
despreza os conhecimentos anteriores, mas são esses os alicerces fundamentais da
teoria, neste caso, a teoria dos números primos.
Nessa perspectiva trabalhamos a história desses números, de acordo com os
PCNs (1998, p. 43) que acentua a importância da história da matemática, afirmando
que:
49
Em muitas situações, o recurso à história da matemática pode esclarecer
ideias matemáticas que estão sendo construídas [...], especialmente para
dar respostas a alguns “porquês” e, desse modo, contribuir para a
constituição de um olhar mais crítico sobre os objetos de conhecimento.
Em suma, o trabalho aprecia a importância da história da matemática para
entender de fato os conceitos matemáticos, sendo nessa vertente que relacionamos
a “matemática abstrata” com a “história da matemática”, de modo que o trabalho
possa contribuir tanto para quem compreende a matemática, quanto para aqueles
que não são integrados aos seus conceitos.
50
REFERÊNCIAS
ALVES, Rubens. Estórias de quem gosta de ensinar: O fim dos Vestibulares.11.
editora. Campinas, SP:Papirus, 2007.
Ávila, Geraldo. A Distribuição dos Números Primos. Revista do Professor de
Matemática, RPM 19. 1991. 19 p – 26 p.
BRASIL, Ministério da Educação e Cultura, Secretaria de Educação Média e
Tecnológica. Parâmetros curriculares nacionais: Terceiro e Quarto Ciclos do
Ensino Fundamental. Brasília: MEC, 1998.
CONTADOR, Paulo R. M. Matemática, uma Breve História. 3. ed. São Paulo:
Livraria da Física, 2006.
DOMINGUES, Hygino H. Fundamentos de Aritmética. São Paulo: Atual, 1991.
Filho, Daniel C. M. Manual de Redação de Matemática: com um dicionário
etimológico-explicativo de palavras usadas na Matemática e um capítulo especial
sobre como escrever uma dissertação. Campinas Grande: RG, 2009.
GARBI, Gilberto G. A Rainha das Ciências. 5. ed. rev e ampl. São Paulo: Editora
Livraria da Física. 2010.
GOMES, Olimpio G.; SILVA, Jhone. C. Estrutura Algébrica para Licenciatura:
Introdução à Teoria dos Números. 1. ed. Brasília: Ed. Do Autor, 2008.
LEMOS, Manuel. Criptografia, Números Primos e algoritmos. 4. ed. Rio de
Janeiro: IMPA, 2010.
MOREIRA, Carlos G.; SALDANHA Nicolau. Primos de Mersenne (e outros primos
muito grandes). 3. ed. Rio de Janeiro: IMPA, 2008.
PERUZZO, Jucimar. O Fascínio dos Números Primos. Santa Catarina: Irani. 2012.
RIBENBOIM, Paulo. Números Primos: Velhos Mistérios e Novos Recordes. Rio de
Janeiro: IMPA, 2001.
SAUTOY, Marcus du. A Música dos Números Primos: A História de um Problema
não Resolvido na Matemática. Tradução: Diego Alfaro. Rio de Janeiro: Jorge Zahar
Editora, 2007.
SILVA, Valdir. V. Números: Construção e Propriedades. Goiânia: UFG, 2005.