2013/01/29

Os Números Primos

Muitas pessoas têm a ideia (errada) de que a Matemática é chata. Como vimos no outro dia, muitas vezes trata-se apenas de explicar as coisas de forma a que todos possam perceber, e até de forma divertida. Hoje, o Pedro Cabido vai relembrar aos mais esquecidos - ou desatentos - o que são os números primos.



Já me perguntaram algumas vezes o que é um número primo. E apesar de me lembrar de falar nisso na escola, foi uma daquelas coisas que acabei por esquecer pelo simples facto de nunca mais os ter usado desde então.

Mas então o que um número primo? Poderia achar-se que seria uma coisa muito complicada, de matemática avançada, mas não. Na realidade é uma coisa bastante simples que todos podem facilmente entender.

Por definição um número primo é: um número natural que tem exactamente dois divisores naturais distintos - o número 1 e ele próprio. Isto é, apenas pode ser divisível por ele próprio, e pelo 1 (e falando apenas de divisões que resultem em números inteiros - não vamos meter as casas decimais ao barulho).

Traduzindo isto com uns exemplos:

Vamos descobrir se o número 4 é primo:
4 / 1 = 4
4 / 4 = 1

Por aqui poderíamos achar que o 4 é um número primo, pois encaixa perfeitamente na definição. Mas estaria errado. O problema é que para ser um número primo apenas e só poderá ser divisível por estes dois valores, mas se o tentarmos dividir por dois:
4 / 2 = 2

Vemos que também dá conta certa. Logo não é número primo. (Sem surpresas: nenhum número par é número primo - com a excepção do 2 - já que todos eles podem ser divisíveis por 2.)

Outro exemplo:
7 / 1 = 7
7 / 7 = 1

No caso do número 7 podemos ver que é de facto um número primo pois ele só têm mesmo 2 números que dividindo dará um número inteiro. Podem tentar dividi-lo por 2, 3, 4, 5, e 6 para confirmarem que não dá conta certa. E tal como o 7 temos outros (aliás, infinitos números primos):
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,....

Como poderão imaginar, à medida que se vai avançando, os números primos tornam-se cada vez mais raros e difíceis de comprovar manualmente. Mas isso não impede que se coloquem os computadores a trabalhar por nós, o que ajuda a explicar que o maior número primo conhecido actualmente tenha quase 13 milhões de dígitos!

Embora possa parecer que estes números não servem para nada, as suas características especiais fazem com que sejam bastante úteis para algumas aplicações: como por exemplo a criptografia, geradores de números pseudo-aleatórios, etc.

Como podem ver é algo realmente básico mas que poderá dar para um assunto de conversa com alguém que goste deste tipo de coisas.


[por Pedro Cabido]

5 comentários:

  1. Olá,

    O que é isto da Google:


    Digite sua data de nascimento correta e selecione a próxima etapa

    Suas informações de cartão de crédito ou de identificação só serão utilizadas e armazenadas para reativar sua conta. Armazenaremos a data de nascimento em sua Conta do Google, mas não será exibida ou compartilhada sem sua permissão. Saiba mais.


    Data de nascimento: Dia12345678910111213141516171819202122232425262728293031Mêsjaneirofevereiromarçoabrilmaiojunhojulhoagostosetembrooutubronovembrodezembro

    Como gostaria de proceder?




    Usar meu cartão de crédito »

    Uma cobrança no valor de US$ 0.30 será feita no seu cartão.





    Enviar um formulário on-line »

    É necessária a cópia de um documento de identidade emitido pelo governo.





    Enviar um formulário por fax ou correio »

    É necessária a cópia de um documento de identidade emitido pelo governo.





    ©2011 Google - Página inicial do Google - Termos de Serviço - Política de Privacidade - Ajuda

    ResponderEliminar
  2. Grande Post! Realmente não sabia que usavam números primos em criptografia. Muito curioso isto ;)

    ResponderEliminar
  3. Se bem percebi há três tipos de caça aos números primos:
    - os que estão entre (2^x)-1 e (2^y)-1, ou seja, a caça por intervalos (o -1 é porque, com excepção do 2, todos os primos são ímpares, obviamente)
    - um que tenha mais algarismos (seja maior) do que o maior actualmente conhecido
    - dos primos primos conhecidos, verificar se têm determinadas características, por exemplo, se são do tipo (4^x)-1 ou (4^x)+1

    Parece que há aplicações que se instala no computador de casa para descobrir números primos e a única coisa que é preciso é ir deitando uma olhadela para ver se se teve sorte.

    Quanto à criptografia, parece que o truque é encontrar "os factores primos de números monstruosos" :)
    http://www.testonline.com.br/curprimos.htm

    ResponderEliminar
    Respostas
    1. Estive a magicar como é isto da factorização em números primos de um número monstruoso, para usar como chave de encriptação e acho que deve ser assim.

      P x Q = N em que N é um número com porradaria de algarismos e P e Q são números primos também com bastantes.

      Existe um problema com as mensagens encriptadas que é o receptor tem que receber a mensagem encriptada e ao mesmo saber qual é a chave com que foi encriptada. Eu vejo a coisa assim, encripta-se a mensagem com a chave PQ (chave privada) no fim da mensagem encriptada põe-se N (chave pública), quando a recebe o receptor sabe (p. ex., multiplica os números primos que já lhe deram até obter N) e obtém PQ.

      Deve ser uma coisa assim. Como os números primos são infinitos e a factorização de um número gigantesco em números primos é extremamente demorada, mesmo com supercomputadores, é bem possível que haja Governos que tenham os seus números primos como segredo de Estado.

      Eliminar
  4. https://play.google.com/store/apps/details?id=com.sergiocruz.Matematica
    Aplicação para cálculo dos números primos, MMC, MDC, Fatorização, Divisores, tabela de números primos e muito mais com explicações detalhadas.

    ResponderEliminar