Números primos

Um número inteiro $n$ diferente de $\pm 1$ e de $0$ é dito primo se os únicos divisores de $n$ são $\pm 1$ e $\pm n$. No caso contrário, o número é dito composto. Os números $1$, $-1$, e $0$ não são considerados nem primos nem compostos.

Por exemplo, o número $-5$ é primo, pois ele é divisível por apenas $\pm 1$ e $\pm 5$. O número $6$ é composto, pois ele é divisível, por exemplo, por $2$. É fácil verificar que um número $n$ é primo (composto) se e somente se $-n$ é primo (composto).

A demonstração do seguinte resultado é imediato da definição dos números primos.

Todo número diferente de $1$ ou $-1$ é divisível por um primo.

A seguinte é uma propriedade importante dos números primos.

Sejam $p$ um primo e $a,b\in\Z$ tais que $p\mid ab$. Então $p\mid a$ ou $p\mid b$.
Assuma que as condições do Teorema estão válidas e que $p\nmid a$. Então $\mdc pa=1$ e obtemos do Algoritmo de Euclides que existem $u,v\in\Z$ tais que $up+va=1$. Multiplicando por $b$, obtemos que
\[
upb+vab=b.
\]
Como $p$ divide $ab$, o número $p$ divide $vab$, então $p$ divide as duas parcelas no lado esquerdo da última equação. Mas isso implica que $p\mid b$.

Se $n$ é um número grande (centenas ou milhares de dígitos), então pode ser difícil verificar se $n$ é primo. O primeiro algoritmo teoricamente eficaz para testar primalidade de um número grande foi apresentado por Manindra Agrawal, Neeraj Kayal e Nitin Saxena em 2002. Este algoritmo é conhecido como o Algoritmo AKS.

O seguinte teorema foi conhecido já na antiguidade por Euclides.

Existem infinitos primos.
Suponha com o objetivo de obter uma contradição que existem apenas finitos primos. Vamos então fazer uma lista dos primos positivos: $p_1=2$, $p_2=3$, $p_3=5,\ldots,p_m$. Considere o número
\[
N=p_1p_2p_3\cdots p_m+1.
\]
Ora $N$ é positivo e é maior que dois. Além disso, $N$ deve ser divisível por algum primo $p$. Por outro lado, os primos $p_1,\ldots,p_m$ não dividem $N$, pois o resto de $N$ quando for dividido por estes primos é igual a $1$. Isto implica que $p$ precisa ser um novo primo que não está na suposta lista de todos os primos. Isto é uma contradição que significa que a nossa suposição foi errada; ou seja, o número dos primos precisa ser infinito.