Como o título indica, este trabalho compõe-se de duas partes. Na primeira parte, são apresentadas as noções de número primo, número composto, números primos entre si, primos gémeos, números perfeitos e divisores próprios. Apresentamos também alguns resultados sobre números primos, como o Teorema de Euclides, o Teorema Fundamental da Álgebra e outros resultados que ainda estão por provar, que são as Conjecturas de Goldbach e dos Primos Gémeos. Ao longo do texto, são dadas a conhecer algumas curiosidades que pretendem alertar para o alcance actual do estudo dos números primos. Também apresentamos alguns tipos de números primos: Números de Mersenne, Números de Fermat e Primos Gaussianos. De entre os métodos de “procura” de números primos, destacamos uma abordagem clássica, o ‘Crivo de Eratóstenes’, e temos ainda os testes de primalidade de Fermat e de Wilson. A Lei Logarítmica de Legendre, a Conjectura de Gauss e o Refinamento de Riemann são as técnicas apresentadas no âmbito da distribuição dos números primos. Fazemos ainda uma breve alusão aos números que são soma de dois quadrados e terminamos a primeira parte com uma aplicação dos números primos, os códigos secretos, onde é descrito e exemplificado o sistema de codificação R.S.A..

Na segunda parte, vamos falar de fracções e de algumas das suas possíveis aplicações. Inicialmente, introduzimos a noção de dízima infinita periódica e de ciclos de fracções. Dentro dos ciclos das fracções, salientam-se as congruências e as diferentes utilizações que se podem fazer dos mesmos.

São apresentados alguns exemplos, muito interessantes, utilizados por mágicos e cartomantes, com jogos de cartas estabelecendo a ligação entre as fracções e estas actividades místicas.

Fazemos um recuo no tempo, até à antiguidade egípcia, onde eram usadas as fracções unitárias e à Grécia Antiga, na Escola Pitagórica para falar da descoberta da relação existente entre a harmonia da música e as fracções. Continuando a viagem no tempo, chegamos às fracções contínuas, aí veremos como elas se resolvem e o teor da sua importância.

Um número natural diz-se primo se tiver como divisores apenas a unidade e ele próprio.

Exemplos: 2, 3, 5, 7, 11,...

O natural 1 não é primo nem composto.

Os naturais que não são primos dizem-se números compostos.

Dois números naturais dizem-se primos entre si se não tiverem divisores comuns com excepção da unidade.

Exemplo: 8 e 9 são primos entre si.

Euclides (300 a.C.) provou que:

Existem infinitos números primos.

O maior número primo conhecido foi descoberto em 2001:

213466917 – 1

com 4053946 dígitos.

A busca de novos números primos continua…

Desde tempos remotos, os números primos suscitaram muito interesse entre os matemáticos, pelo facto de não haver uma sequência lógica no seu conjunto.

Teorema Fundamental da Álgebra: Qualquer número natural se exprime de forma única ( a menos da ordem) como produto de factores primos.

Foi também provado por Gauss o

Este resultado garante-nos a existência e unicidade da decomposição canónica de um natural em factores primos.

Os números primos têm um comportamento muito irregular, pelo que as questões mais frequentes entre os matemáticos são:

Dado um natural, como saber se ele é primo ou não?

Dados dois naturais distintos, como saber quantos primos existem entre eles?

Para responder a esta questão, serão apresentados mais adiante os testes de primalidade.

Para esta pergunta, temos uma resposta muito simples, que foi deixada por Eratóstenes, um matemático, filósofo, poeta e bibliotecário de Alexandria em 200 a.C.. Ele encontrou uma forma muito simples de saber quais os primos que estão entre dois números distintos. O seu algoritmo ficou conhecido por “Crivo de Eratóstenes”.

Começa-se por escrever uma tabela, como por exemplo a seguinte de 2 a 50:

Vamos então ver como funciona este método.

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 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Fixa-se o primeiro número primo, que é o 2 e eliminam-se todos os seus múltiplos, excepto o próprio 2.

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 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Fixa-se o número primo que aparece a seguir ao 2, que é o 3 e eliminam-se todos os seus múltiplos, excepto o próprio 3.

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 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Fixa-se o número primo a seguir ao 3, que é o 5 e eliminam-se todos os seus múltiplos, excepto o próprio 5.

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 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Procede-se do mesmo modo para o 7.

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 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Os números que permanecem na tabela são todos os primos menores que 50.

Este método pode ser utilizado para qualquer natural n, no entanto, para números naturais muito grandes não é eficiente.

Há ainda a notar que o número 1 não deve ser incluído na tabela, caso contrário ao eliminar os seus múltiplos, eliminavam-se todos os números da tabela.

Seguidamente, são apresentadas algumas noções, não tão básicas como as primeiras, mas mais direccionadas para as relações que se podem estabelecer entre os números primos.

Dois naturais dizem-se primos gémeos se forem primos e a sua diferença for igual a 2.

Exemplo: 11 e 13, 17 e 19, 269 e 271

Chama-se número perfeito a um número natural que seja igual à soma dos seus divisores próprios.

Os divisores próprios de um natural são todos os seus divisores exceptuando ele próprio.

A título de curiosidade: Os números perfeitos menores que 10000 são: 6, 28, 496, 8128 Os maiores primos gémeos descobertos são

2409110779845 260000 ± 1

que têm 18075 dígitos.

Os números da forma Mn = 2n - 1 em que n é primo são os números de Mersenne.

O último número de Mersenne descoberto foi

M3021377 = 23021377 - 1

Os primeiros números de Mersenne são M2, M3, M5, M7, M13

Mersenne foi teólogo e matemático francês no séc. XVII.

Euler provou que todos os números perfeitos pares têm a forma de um número de Mersenne. Os números perfeitos ímpares ainda estão por descobrir, sabe-se apenas que até 10300 não existe nenhum.

Define-se o n-ésimo número de Fermat do seguinte modo:

Fn = 2n + 1, com n uma potência de 2.

Os únicos números de Fermat que se conhecem são:

F0, F1, F2, F3, F4

Fermat foi matemático no início do séc.XVII, colega de Mersenne.

Fermat conjecturou que todo o número desta forma seria um número primo.

Mas Euler provou que F5 é composto ( F5 = 641×6700417)

Actualmente, o número de Fermat que está em dúvida é F24 que tem 5050446 dígitos.

Relativamente aos primos de Fermat, Gauss provou que se p for um primo de Fermat, pode-se construir com régua e compasso um polígono regular com p lados, usando as regras de Euclides.

Os inteiros gaussianos são números complexos em que, tanto a parte real como a imaginária são números inteiros.

Primo Gaussiano é um inteiro Gaussiano que só é divisível por ele próprio e por um.

Exemplo: 2 + 3i

Exemplo: 1 + i e 1 - i

Conjectura de Goldbach:

Qualquer número natural par n 6 pode ser escrito como soma de dois números ímpares.

Conjectura dos primos gémeos:

Existe uma infinidade de primos gémeos.

Teste de Fermat: Todo o número primo p deve satisfazer

ap-1 1 mod p , qualquer que seja a não divisível por p.

Exemplos:

1) p = 7 (primo), a = 10

107-1 = 106 1 ( mod 7)

2) 212-1 = 211 = 2048 8 ( mod 12) 12 não é primo

Os testes de primalidade servem para verificarmos se um número é ou não primo, sem termos que fazer a sua decomposição em factores primos.

Se um número não satisfizer a congruência então não é primo:

Teste de Wilson :

p é primo justamente quando (p – 1)! -1 mod p

O teste de Wilson já é uma condição necessária e suficiente de primalidade.

Números de Carmichael : são números que embora compostos, satisfazem o teste de Fermat para muitas bases.

Para números pequenos o teste de Fermat parece conduzir a um processo mais trabalhoso do que fazer os cálculos necessários para obter a sua decomposição em factores primos. No entanto, para números grandes a situação inverte-se.

O teste de Fermat para a primalidade é necessário, mas não é suficiente. Isto é, existem números que satisfazem o teste de Fermat e que não são primos.

Até 10 há 4 números primos, isto é, 1 em cada 2,5 números é primo.

Até 102 há 25 números primos, isto é, 1 em cada 4,0 números é primo.

Até 103 há 168 números primos, isto é, 1 em cada 6,0 números é primo.

Até 104 há 1229 números primos, isto é, 1 em cada 8,1 números é primo.

Até 105 há 9592 números primos, isto é, 1 em cada 10,4 números é primo.

Até 106 há 78498 números primos, isto é, 1 em cada 12,7 números é primo.

Parece que:

Até 10n, aproximadamente 1 em cada 2,3 n números é primo.

E o que acontecerá no caso geral?

Lei Logarítmica de Legendre :

Até ao número x, aproximadamente 1 em cada log x é primo,

onde log x é o logaritmo natural de x.

Conjectura de Gauss :

Mais ou menos 1/ln x dos números próximos de x são

primos.

Gauss conjecturou uma pequena modificação para a ideia de Legendre, que se pode expressar nos seguintes termos:

Estimativa de LegendreEstimativa de Legendre

Estimativa de GaussEstimativa de Gauss

Comparação das duas EstimativasComparação das duas Estimativas

Teorema dos Números Primos : 1

ln

)(lim

x

xx

x

Refinamento de Riemann :

O número de primos até x é aproximadamente

R(x) = Li(x) – 1/2 Li (x1/2) – 1/3 Li (x1/3) – 1/5 Li (x1/5) + 1/6 Li (x1/6) - ...

Ao coeficiente de 1/n Li (x1/n) chama-se número de Möbius, (n).

As conjecturas de Legendre e Gauss só foram provadas quase um século depois (1896), por Hadamard e de la Vallée Poussin, de modo independente um do outro, e constituem o

Em 1859, Riemann deu uma estimativa que, na maioria dos casos, é ainda melhor que as duas anteriores, chamada

Tabela Comparativa das Conjecturas de Tabela Comparativa das Conjecturas de Legendre, Gauss e RiemannLegendre, Gauss e Riemann

Os valores apresentados estão arredondados ao inteiro mais próximo.

A conjectura de Gauss dá uma estimativa melhor do que a de Legendre e, parece que o refinamento de Riemann é ainda melhor.

Fermat descobriu que:

Pode escrever-se um número primo, p, como soma de dois quadrados, apenas se p + 1 não for divisível por 4.

A decomposição é então única.

Exemplos :

1) 2, 5, 13, 17, 19,… podem escrever-se como soma de dois quadrados

2 = 12 + 12 , 5 = 22 + 12 , 13 = 32 + 22 , ...

2) 3, 7, 11, 19,… não são somas de dois quadrados, pois

3 + 1= 4 é divisível por 4, 7 + 1 = 8 é divisível por 4,…

Exemplo : 1000 = 23 53 23 + 1 = 9 não é divisível por 4 53 + 1 =126 não é divisível por 4

1000 é igual à soma de 2 quadrados

Para ver se um número positivo arbitrário, n, é igual á soma de dois quadrados, faz-se a sua decomposição em factores primos n = pa qb rc ... n é igual à soma de dois quadrados apenas quando nenhum dos números pa + 1, qb + 1, rc + 1, ... for divisível por 4.

A representação, neste caso, não é obrigatoriamente única:

1000 = 900 + 100 = 302 + 102

1000 = 676 + 324 = 262 + 182

A ideia dos códigos secretos perde-se no tempo.

Júlio César codificava as ordens enviadas aos seus generais.

Na guerra da França contra a Espanha, o matemático Francisco Vieta prestou serviços ao rei de França ( rei Henrique IV ) decifrando missivas espanholas. Os espanhóis ficaram tão impressionados com a descoberta de Vieta da cifra-chave que atribuíram o feito a um acto de bruxaria.

Em 1975, surgiu o Sistema R.S.A. ou Sistema de Chave Pública, devido a Rivest, Shamir e Adleman e que sumariamente consiste no seguinte:

Sistema de codificação R.S.A. ou sistema de chave pública :

O receptor escolhe dois primos p e q ( na ordem dos 100

dígitos cada um)

calcula n = p q

calcula (n) = (p – 1) (q – 1)

escolhe k, inteiro positivo tal que m.d.c. (k, (n)) = 1

o par (n,k) diz-se a chave pública

k diz-se o expoente de codificação

torna público o par (n, k), mas não os primos p e q

Fórmula de Codificação :

Mk R (mod n)

M representa a mensagem original

R representa a mensagem codificada

O processo de codificação começa com a conversão da

mensagem num número M, através de um “alfabeto digital”, no

qual letras, sinais de pontuação e algarismos são substituidos por

inteiros com dois dígitos.

O emissor ( conhecedor da chave pública) converte o número M

no número R através da

Fórmula de Descodificação: Rj M’ (mod n)

Expoente de Descodificação : j (n) kj 1 (mod (n))

O receptor (conhecedor de p e q) determina o

determina M’ Z através da

como M’ = M recorre ao “alfabeto digital” e obtém a

mensagem original.

A segurança deste método baseia-se na impossibilidade, em tempo útil, da factorização de primos grandes.

Exemplo:

Se p = 7, q = 2 tem-se n = 7 2 = 14 e (n) = (7-1)(2-1) = 6.

k é um inteiro positivo tal que m.d.c.( k, (n)) = 1 , como (n) = 2 3, escolho k = 5.

O par ( 14, 5) constitui a chave pública.

Codifiquemos a palavra “CAFÉ”:

M = 3165 ( mensagem original)

35 = 243 5 ( mod 14)15 = 1 1 ( mod 14) 65 = 7776 6 ( mod 14)55 = 3125 3 ( mod 14)

R = 5163 ( mensagem codificada)

O expoente de descodificação é tal que:

5j 1 ( mod 6) j = 11

511 3 ( mod 14)

111 1 ( mod 14)

611 6 ( mod 14)

311 5 ( mod 14)

M’ = 3165 = M

Recorrendo ao “alfabeto digital” obtemos novamente a palavra “CAFÉ”

076923,013

1

91

7

enquanto que

329670,091

30

A parte decimal de algumas fracções é obtida através da inversão dos dígitos de outra fracção com o mesmo denominador.

Exemplo:

7

1= 0,142857 142857...

7

2= 0,285714 285714...

7

3= 0,428571 428571...

4/7

56/7

7

1/7 1

3/74

2/72

5/78

As fracções podem ter dízimas finitas ou dizimas infinitas. As dízimas infinitas podem ser periódicas ou não periódicas. Vamos falar de fracções com dízima periódica.

O comprimento do primeiro ciclo é o menor número k para o qual se tem

10k 1mod p

Todas as fracções de denominador 7 têm o mesmo ciclo de dígitos que se repete. No entanto, há fracções com vários ciclos de dígitos, por exemplo, as fracções de denominador 13.

Vamos agora calcular o comprimento do primeiro ciclo de dígitos para fracções de denominador p:

17: 0588235294117647

19: 052631578947368421

23: 0434782608695652173913

29: 0344827586206896551724137931

31: 032258064516129 096774193548387

37: 027054081135162189243297378459486567

41: 0243904878073170975612195156342682936585

43: 023255813953488372093 046511627906976744186

47: 0212765957446808510638297872340425531914893617

Para um denominador primo (distinto de 2 ou 5) todos os ciclos têm o mesmo comprimento.

73

1= 0,031369863 01369863...

73

20= 0,02739726 02739726...

têm comprimento 8

Exemplo:

Como 73 é primo,

Número de ciclos comprimento por ciclo = p – 1, p denominador primo

Através do cálculo do comprimento por ciclo já sabemos que:

10k 1 mod p

Então tem-se:

10p-1 1 mod p , p 2, 5

Temos então:

Se p não dividir b,

bp-1 1 mod p

““PEQUENO TEOREMA DE FERMAT”PEQUENO TEOREMA DE FERMAT”

Como não há nada de especial acerca da base 10, podemos usar uma base b qualquer.

B ara lh ar in te rio r B ara lh ar exte rio r

B ara lh ar em casca ta

Exemplo:

Consideremos um baralho de 52 cartas (2n cartas).

Dividimos o baralho em duas partes iguais, ficamos com dois montes de 26 cartas cada (isto é, n cartas).

Baralhamos então em cascata interior, começando primeiro pela mão esquerda, depois a mão direita e assim sucessivamente.

Reparamos que logo após a primeira vez que realizamos esta acção, a carta que estava na posição 1 está agora na posição 2, a carta que estava na posição 2 ocupa agora a posição 4,…

As cartas só voltam a ocupar a posição inicial quando repetirmos o processo 52 vezes (2n vezes).

Se 2n + 1 for um número primo então o baralhar interior de 2n cartas 2n vezes faz com que as cartas regressem à posição inicial.

2s 1 mod 2n+1 , s número de vezes que se baralha

Depois de baralhar s vezes, a carta número k estará no lugar que era ocupado pela carta cujo número era 2sk mod 2n + 1. Então baralhando s vezes, as cartas acabam por voltar à posição inicial quando:

Exemplo:

Consideremos um baralho de 52 cartas (2n cartas).

Dividimos então o baralho em duas partes iguais, isto é, 26 cartas cada um (n cartas).

Baralhamos então em cascata exterior, começamos primeiro pela mão direita, depois a mão esquerda,…

Verificamos que a primeira e a última cartas ocupam sempre a mesma posição, de modo que só se baralham as restantes 50 cartas (2n – 2 cartas).

As cartas voltam a ocupar a posição inicial depois de baralharmos 50 vezes (2n - 2 vezes).

Se 2n – 1 for um número primo então o baralhar exterior das 2n cartas 2n – 2 vezes faz com que estas regressem à ordenação original.

2s 1 mod 2n-1 , s é o número de vezes que se baralha

Baralhando s vezes as cartas regressão à posição inicial quando:

O porquê da utilização das congruências 2n + 1 e 2n – 1 ?

Nas duas aplicações anteriores verifica-se que há ciclos que se repetem após um determinado número de vezes, por isso podemos utilizar então as congruências. No caso do baralhar em cascata interior essa congruência é 2n + 1, enquanto que no caso do baralhar em cascata exterior essa congruência já é de 2n – 1.

A cultura egípcia (2000 a. C.) já manejava o conceito de fracção, mas empregava unicamente fracções unitárias, isto é, fracções cujo numerador é 1 e denominador é um número natural.

A fracção a/b está escrita em forma egípcia se está decomposta da maneira seguinte:

a/b = 1/p + 1/q + 1/r + ... + 1/v, a, b, p, q, r, ... ,v

Exemplo:

3/5 = 1/3 + 1/5 + 1/15

PITÁGORAS Famoso matemático que viveu por volta de 571 – 496 a. C.

“Todas as coisas são números.”

Esta frase demonstra que já na antiguidade se reconhecia a importância da relação e da aplicação da matemática com o mundo real.

Como o próprio nome indica, as fracções pitagóricas estão relacionadas com Pitágoras e com a escola pitagórica.

Conta-se que Pitágoras ao observar os ferreiros a trabalhar nas suas oficinas, verificou que os martelos utilizados produziam sons harmoniosos. Inicialmente, terá pensado que isso se deveria à força com que os ferreiros batiam os martelos. No entanto, rapidamente verificou que a produção dos sons harmoniosos não se devia a esse facto, mas sim ao peso dos respectivos martelos.

Pitágoras observou que:

os pesos 12 e 6 ressoavam em dobro produziam a oitava

os pesos 12 e 9, 8 e 6 produziam a quarta

entre os pesos 9 e 8 produzia-se um tom inteiro

Pesos dos martelos dos ferreiros: 12, 9, 8 e 6

Existe uma proporção entre eles

6/8 = 9/12

Exemplo: Se o número das vibrações for

Dó = 24; Ré = 27; Mi = 30; Fá = 32; Sol = 36; Lá = 40; Si = 45; Dó = 48

Então:

Oitava: intervalo de Dó a Dó 48/24 = 2/1

Quinta: intervalo de Dó a Sol 36/24 = 3/2

Quarta: intervalo de Dó a Fá 32/24 = 4/3

Tom: intervalo de Dó a Ré 27/24 = 9/8

Ternos PitagóricosTernos Pitagóricos

b a c

3 4 5

5 12 13

7 24 25

8 15 17

9 40 41

Os ternos Pitagóricos são os números naturais que verificam a relação

b2 + a2 = c2, a, b, c +

Tabela com alguns exemplos de ternos pitagóricos

Nqp

pq

qp

a

b

,,

2

22

Exemplo:

a = 4

b = 3 4

3

As fracções contínuas são do tipo

é a fracção contínua correspondente.

Temos também que

comprimento : largura : diagonal 2pq : p2 – q2 : p2 + q2,onde p e q são números regulares (dividem potências de 60) e q é menor que 60

Podemos ainda verificar que:

a é o comprimento

b é a largura

c é a diagonal

Aplicando o teorema de Pitágoras a um triângulo isósceles cujos catetos são iguais a um, a hipotenusa é igual a 2, que não se pode exprimir na forma a/b, a, b N

Surgem os irracionais

Exemplo:

4

12

13

11

Como se resolve :

41

401

31

99

313

9

44

9

4

12

Notação: [1; 3, 2, 4]

Quocientes parciais: 1, 3, 2 e 4

O desenvolvimento por fracções contínuas fornece a melhor aproximação racional possível.

Exemplo:

=[3; 7, 15, 1, 292, ...]

[3; 7]

3 + 1/7 = 22/7

[3; 7, 15, 1]

115

17

13

15 + 1 = 16

1/16 + 7 = 113/16

16/113 + 3 = 355/113

Consideremos agora dois desenvolvimentos por fracções contínuas para o número :

A partir dos desenvolvimentos por fracções contínuas anteriores podemos verificar que a fracção que mais se aproxima do valor real do é 355/113, isto é aquela em que considerámos mais quocientes parciais.

22/7 = 3,1428571...

355/113 = 3,1415929...

= 3,14159265...

Ao considerar mais termos no desenvolvimento por fracções contínuas, obtemos resultados mais próximos do pretendido.

Para um número racional o desenvolvimento por fracções contínuas acaba por parar.

Para um número irracional isto não acontece.

Nos diapositivos número 27 e 28, onde está ‘Gaus’ deve ler-se ‘Gauss’.

Referências Biblográficas:

John Conway, Richard Guy, ‘O Livro dos Números ’

Natália Bebiano da Providência, ‘Matemática ou Mesas, Cadeiras e Canecas de Cerveja ’, Gradiva,2002

Tom M.Apostol, ‘Introduction to Analytic Number Theory’ ; New York Springer; 1995

‘Jornal de Matemática Elementar ’, Lisboa 15 de Maio de 2002

Referências Interactivas:

http://www.fc.ul.pt/icm/icm98/icm12/

http://geocities.com/CapeCanaveral/Hangar/8791/primos/primos.html http://www.utm.edu/research/primes/mersenne.shtml

http://www.spd.dcu.ie/johnbcos

http://www.dei.isep.ipp.pt/~andré/documentos/criptografia.html

http://www.educ.fc.ul.pt/semtem/semtem99/sem24/

http://www.7mares.terravista.pt/mil1/egipto/Rhind

http://www.educ.fc.ul.pt/icm/icm99/icm17 http://terravista.pt/bilene/7980

http://www.educ.fc.ul.pt/docentes/opombo/seminario/musica/

http://matemáticas.no.sapo.pt/pitagoras.htm

http://www.montfort.org.br/caderno/musicabeleza.html#IV