§ 1. Os números primos são os inteiros superiores a um que admitem apenas dois divisores inteiros (positivos).

Os primeiros são: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …

1. 1 não é primo, por definição.
2. Os dois divisores são sempre o 1 e o próprio número.
3. Todos os pares, com excepção do 2, não são primos, isto é, são composições de primos (produto de primos); por isso, os não primos são chamados compostos.

O processo mais antigo para construir uma tabela de números primos é utilizar um crivo: o mais simples  é o de Erastótenes (275-194 a. C.), grego , matemático, astrónomo e director da biblioteca de Alexandria.

Este processo elimina sucessivamente uma infinidade de números

1. todos os números de 2 em 2, com excepção do 2.
2. Começando no primeiro número não eliminado na fase anterior ( o 3), que se mantém,  eliminam-se todos os números de 3 em 3.
3. Começando no primeiro número não eliminado na fase 2 ( o 5), mantém-se esse número, e eliminam-se todos os números que lhe são múltiplos que ainda houver.
4. Repete-se este processo indefinidamente como indicado em 3.

Na prática será:

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, …

• Fase 2

2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, … —> eliminaram-se o  4, 8, 10, 12, 14, 16, … ( ou seja, todos os pares maiores ou iguais a 4)

• Fase 3

2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, … —> eliminaram-se o 9, 15, 21, 27, … (ou  seja, todos os múltiplos de 3 ainda não eliminados)

• Fase 4

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … —> é esta a lista acima, depois de se terem eliminado o múltiplo de 5 que é o 25, assim como todos os subsequentes ainda não eliminados).

§ 2. Cinco propriedades dos números primos:

1. Não existe um número primo maior do que todos os outros. A demonstração, que data de Euclides (séc. III a. C., professor na Universidade de Alexandria), é um clássico da Teoria dos Números / Aritmética teórica).
2. Um número só é primo se for da forma 4 n + 1 ou 4 n -1, em que n é um dos termos da sucessão 1, 2, 3, 4, 5, … .
3. Um inteiro maior do que 5 só é primo se for da forma 6 n + 1 ou 6 n + 5, em que o inteiro n pode ser 1, 2, 3, 4, 5, … .
4. Um inteiro maior do que 30 só é primo se for da forma 

   30 n + 1, 30 n + 7, 30 n + 11, 30 n + 13, 30 n + 17 , 30 n + 19, 30 n + 23, 30 n + 29,
    

   em que n é um inteiro maior ou igual a 1.

    

   Demonstração: um inteiro maior que 30 é da forma 30 n, 30 n + 1, 30 n + 2, … , 30 n + 28, 30 n + 29. Os pares, que são os da forma 30 n, 30 n + 2, 30 n + 4, … , 30 n + 26, 30 n + 28, não são primos. Os ímpares que restam uns podem ser primos e há outros que o não são de certeza.

   Neste momento temos

   30 n + 1, 30 n + 7, 30 n + 11, 30 n + 13, 30 n + 17 , 30 n + 19, 30 n + 23, 30 n + 29

   e

   30 n + 3, 30 n + 5, 30 n + 9, 30 n + 15, 30 n + 21, 30 n + 25, 30 n + 27.

   Como 30 = 2 x 3 x 5, tem-se

   • 30 n + 3 = 30 ( n + 1 ) = 2 x 3 x 5 ( n + 1)
   • 30 n + 5 = 5 ( 6 n + 1)
   • 30 n + 9 = 3 ( 10 n + 3 )
   • 30 n + 15 = 15 ( 20 n + 1 ) = 3 x 5 ( 20 n + 1 )
   • 30 n + 21 = 3 ( 10 n + 7 )
   • 30 n + 25 = 5 ( 6 n + 1 )
   • 30 n + 27 = 3 ( 10 n + 9 )

   ou seja, todos estes números têm mais do que dois divisores (incluindo o 1), pelo que não são primos. Por análise de todos os casos possíveis, conclui-se que apenas os da forma

   30 n + 1, 30 n + 7, 30 n + 11, 30 n + 13, 30 n + 17 , 30 n + 19, 30 n + 23, 30 n + 29

   poderão ser primos.

   Por este motivo só é necessário testar, quanto à divisibilidade, os inteiros que sejam de uma destas formas. Todos os outros são imediatamente excluídos: não poderão ser primos.

5. TEOREMA: Um  número p é primo, se e só se, não puder ser dividido  por nenhum primo menor do que a raiz quadrada de p.

EXEMPLO: Aplique este teorema e determine se 391 é primo ou não.

Como 19² = 361 < 391, 23² = 529 > 391, e 391 é ímpar basta verificar se 391 é divisível por 3, 5, 7, 11, 13, 17, 19. Pelos critérios de divisibilidade por 3 e por 5, vê-se que estes dois números não são divisores de 391. Testando os restantes, porque 391 / 17 = 23 conclui-se que 391 não é primo.

[Incluída resolução do exemplo em 30-8-2008, em consideração pelos meus leitores  que já ultrapassaram as mil visitas nesta entrada]