Um número primo (ou simplesmente um “prim0”) é um número natural maior do que 1 que não possuí outros divisores positivos além dos 1 e de si mesmo.
Um número natural maior que 1 e que não é um número primo é chamado de número de composto.
Por exemplo, 5 é primo porque 1 e 5 são os únicos fatores inteiros positivos, enquanto que 6 é composto, porque tem os divisores 2 e 3, além de 1 e 6.
O teorema fundamental da aritmética estabelece o papel central dos números primos na teoria dos números:
Qualquer número inteiro maior do que um pode ser expresso como um produto de números primos, que é único salvo a sua ordenação.
A singularidade deste teorema requer a exclusão do número 1 como um primo, porque pode-se incluir arbitrariamente muitos instâncias de 1 em qualquer fatoração, por exemplo:
- 3, 1 × 3
- 1 × 1 × 3,
- etc,
São todas fatorações válidas de 3.
A propriedade de ser primo (ou não) é chamada primalidade.
Um método simples, porém lento de se verificar a primalidade de um dado número n é conhecido como divisão por tentativa:
Ele consiste em testar se n é um múltiplo de qualquer número inteiro entre 2 e √n.
Algoritmos muito mais eficientes do que a divisão por tentativa foram concebidos para testar a primalidade de números grandes.
Particularmente métodos rápidos estão disponíveis para os números de formas especiais, tais como números de Mersenne.
Em abril de 2014, o maior número primo conhecido estava em 17.425.170 dígitos decimais. Existem infinitos números primos, como demonstrado por Euclides por volta de 300 aC.
Não se conhece uma fórmula útil que separa todos os números primos de compostos. No entanto, a distribuição de números primos, ou seja, o comportamento estatístico dos primos de forma geral, pode ser modelado.
O primeiro resultado neste sentido foi o teorema do número primo, comprovada no final do século 19, o qual afirma que a probabilidade de que um determinado número n, escolhido aleatoriamente, seja primo é inversamente proporcional ao seu número de dígitos, ou ao logaritmo n.
Muitas perguntas sobre números primos permanecem ainda abertas, como a conjectura de Goldbach (a de que todo inteiro par maior que 2 pode ser expresso como a soma de dois números primos), e a conjectura dos primos gêmeos (a de que existem infinitos pares de números primos cuja diferença é 2) .
Tais questões impulsionaram o desenvolvimento de vários ramos da teoria dos números, enfocando aspectos analíticos ou algébricas dos números.