Números primos

Vamos começar por uma conta detalhada usando o algoritmo de Euclides.
Vamos calcular $\mdc{232}{136}$. As divisões euclidianas serão as seguintes:
\begin{eqnarray*}
232&=&1\cdot 136+96\\
136&=&1\cdot 96+40\\
96&=&2\cdot 40+16\\
40&=&2\cdot 16+8\\
16&=&2\cdot 8+0.
\end{eqnarray*}
Obtemos então que $\mdc{232}{136}=8$.

Determinemos agora números $u,v\in\Z$ tais que
\[
u\cdot 232+v\cdot 136=\mdc{232}{136}=8.
\]
Vamos de cima para baixo nas contas do Algoritmo de Euclides. Obtemos das divisões acima que
\begin{align*}
96&=232-136\\
40&=136-96=136-(232-136)=-232+2\cdot 136\\
16&=96-2\cdot 40=(232-136)-2(-232+2\cdot 136)\\&=3\cdot 232-5\cdot 136\\
8&=40-2\cdot 16=(-232+2\cdot 136)-2(3\cdot 232-5\cdot 136)\\&=-7\cdot 232+12\cdot 136.
\end{align*}
Então obtemos que
\[
8=\mdc{232}{136}=-7\cdot 232+12\cdot 136.
\]
Note que os coeficientes $u=-7$ e $v=12$ não são únicos.

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$.

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$.

O seguinte teorema é bem conhecido dos nossos estudos prévios. Aqui nós vamos apresentá-lo sem demonstração;

Todo número natural maior ou igual a $2$ pode ser escrito como produto de primos positivos. Além disso, esta decomposição é unica a menos da ordem dos fatores.

Por exemplo, temos que
\[
120=2\cdot 2\cdot 2\cdot 3\cdot 5=2\cdot 2\cdot 3\cdot 5\cdot 2=\cdots=2^3\cdot 3\cdot 5.
\]

Algoritmos. Neste momento não se sabe se existe algum algoritmo que pode determinar eficientemente a fatoração de um número  grande. De fato, muitos métodos na criptografia estão baseados na suposição que uma pessoa que intercepta a mensagem não vai conseguir fatorar os números envolvidos e então não consegue decifrar o conteúdo.

O primeiro algoritmo eficiente 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 e é estudado no livro de Shoup.

O seguinte teorema foi conhecido já na antiguidade e apareceu em particular nos trabalhos de Euclides.

Existem infinitos primos.
 Suponha com o objetivo de obter uma contradição que existem apenas finitos primos, nomeadamente, $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$ não é primo, pois ele é maior que todos os primos que supostamente existem. 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.