Teoria de números/Números primos

Um pouco de história Os números primos são conhecidos pela humanidade há muito tempo. No papiro Rhindi, por exemplo, há indícios de que o antigo povo egípcio já possuía algum conhecimento sobre esse tipo de números. No entanto, os registros mais antigos de um estudo explícito sobre números primos é devido aos gregos. Os Elementos de Euclides (cerca de 300 aC), contém teoremas importantes sobre números primos, incluindo a demonstração de sua infinitude o teorema fundamental da aritmética. Euclides também mostrou como construir um número perfeito a partir de um primo de Mersenne. Ao grego Eratóstenes, atribui-se um método simples para o cálculo de números primos, conhecido atualmente como crivo de Eratóstenes. Por outro lado, nos tempos atuais, os grandes números primos são encontrados por computadores, através de testes de primalidade mais sofisticados, como por exemplo o teste de primalidade AKS. Neste capítulo será definido o que são esses números primos, e serão apresentados os principais resultados acerca destes números.

Definição de número primo

Como já foi observado no capítulo anterior, o fato da divisibilidade ser reflexiva (propriedade 1) e que $1$ é divisor de qualquer número inteiro (propriedade 8) garantem que todo número inteiro $a$ diferente de $1$ e $-1$ possui pelo menos dois divisores: $1$ e $a$. Com isso em mente, alguém poderia se perguntar:

• O que os números primos têm de tão especial, já que todos os números inteiros têm ao menos dois divisores?

É essencial notar que a definição acima exige que um número possua exatamente dois divisores positivos, antes de poder ser chamado de número primo. Assim, a definição exclui automaticamente o número $1$ da lista de números primos, pois ele possui um único divisor positivo: o próprio 1. Além disso, seria redundante dizer na própria definição que um número é primo somente se os seus únicos divisores são ele mesmo e a unidade, pois isso decorre da exigência de que $p$ tenha apenas dois divisores positivos.

Agora é possível explicar melhor a "decomposição em blocos básicos" apresentada no início desse texto.

Primeiramente, observe como os elementos de ${\mathbb{Z}}^{+}$ estão "ordenados" pela divisibilidade na figura a seguir:

No que diz respeito a multiplicação, será mostrado que todo número inteiro pode ser decomposto em um produto de números primos. Ou seja, os números primos são realmente "blocos básicos" que permitem a construção de todos os outros números inteiros, a partir de multiplicações.

Este resultado, de grande importância é sintetizado no próximo teorema.

Exemplos

Com o auxílio de um computador, e algum software para computação algébrica, verifica-se ques são verdadeiras as seguintes igualdades:

$12=2^2\cdot 3$

$123=3\cdot 41$

$1234=2\cdot 617$

$12345=3\cdot 5\cdot 823$

$123456=2^6\cdot 3\cdot 643$

$1234567=127\cdot 9721$

$12345678=2\cdot 3^2\cdot 47\cdot 14593$

$123456789=3^2\cdot 3607\cdot 3803$

e ainda:

$12345678901234567=7\cdot 1763668414462081$

Na página Factorization using the Elliptic Curve Method está disponível um pequeno aplicativo que determina a fatoração de um número ou expressão numérica. O aplicativo foi escrito em Java, e não precisa ser baixado para poder ser executado.

Nos próximos exemplos, são apresentados alguns sub-conjuntos de $\mathbb{Z}$ onde a operação de multiplicação continua (bem) definida. Esses conjuntos, assim como o conjunto dos números inteiros, possuem "blocos básicos" que permitem gerar todos os seus elementos a partir da multiplicação. No entanto, os exemplos servirão como motivação para o Teorema fundamental da artimética que será demosntrado posteriormente. Esse teorema garante que um número inteiro só possui uma decomposição em fatores primos, ou seja, se Carlos e Joana encontrarem duas fatorações em primos para um certo número inteiro $n$, então ambos encontraram os mesmos números primos, cada um aparecendo a mesma quantidade de vezes nas duas fatorações.

Ao contrário do que se possa esperar, essa propriedade não é uma consequência imediata das definições de divisibilidade e de números primos. Na verdade, a unicidade só é válida porque $\mathbb{Z}$ possui além de uma estrutura multiplicativa, uma estrutura aditiva com "boas propriedades". É a partir das propriedades de ambas as estruturas, que o teorema poderá ser demonstrado.

Os próximos exemplos servirão, portanto, para mostrar que em conjuntos onde se tem apenas uma estrutura multiplicativa, a decomposição em fatores "primos" (será dado um novo significado ao termo) pode não ser única.

O conjunto dos números pares positivos

Considere o conjunto $2\mathbb{N}=\{2n:n\in \mathbb{N}\}=\{2,4,6,8,10,12,14,16,\dots \}$.

Quem são os elementos que permitem "gerar" todos os demais através da multiplicação? Acompanhe:

$n$	2	4	6	8	10	12	14	16	18	...
fatoração de $n$	2	$2\cdot 2$	6	$2\cdot 2\cdot 2$	10	$2\cdot 6$	14	$2\cdot 2\cdot 2\cdot 2$	18	...

Observe que 6 não pode ser escrito como o produto de outros dois números pares, pois estes teriam que ser necessariamente menores que 6. Assim, é rápido verificar (fazendo alguns poucos testes) que tal fatoração não é possível.

Nesse sentido, o número 6 (assim como o 2, o 10, o 14 e o 18) é um elemento irredutível de $2\mathbb{Z}$. De modo geral, um elemento $n$ é irredutível se não puder ser decomposto em um produto. Os elementos que não são irredutíveis, são naturalmente chamados de redutíveis.

Observe que se $n$ é um elemento redutível de $2\mathbb{Z}$, então $n=2p\cdot 2q=4\cdot pq$, ou seja, todo elemento redutível é um múltiplo de 4.

Os elementos irredutíveis de $2\mathbb{Z}$ serão os "blocos básicos" a partir dos quais poderão ser gerados todos os outros números pares.

Da mesma forma como foi demonstrado que todo número inteiro possui uma decomposição em fatores primos, pode-se provar que todo elemento de $2\mathbb{Z}$ possui uma decomposição em fatores irredutíveis. Predefinição:Prova

Uma última consideração a respeito do conjunto $2\mathbb{Z}$ (e que justifica a escolha do mesmo para este exemplo), é que embora todos os seus elementos admitam uma fatoração em irredutíveis, pode haver mais de uma decomposição para um mesmo número. Veja:

$60=2\cdot 30=6\cdot 10$

E como se verifica facilmente, os números acima são todos irredutíveis em $2\mathbb{Z}$.

Essa característica sugere que se os números inteiros possuem uma única fatoração em primos, isso se deve a alguma outra propriedade de $\mathbb{Z}$, além de sua estrutura multiplicativa.

O monóide de Hilbert

Seja $H=4\mathbb{N}+1=\{4n+1:n\in \mathbb{N}\}=\{1,5,9,13,17,21,29,\dots \}$.

Verifica-se facilmente que a multiplicação de elementos de $H$ possui as seguintes propriedades:

1. $a\cdot b\in H$, quaisquer que sejam $a,b\in H$;
2. $(a\cdot b)\cdot c=a\cdot (b\cdot c)=a\cdot b\cdot c$, para quaisquer $a,b,c\in H$;
3. O elemento neutro da multiplicação, o número inteiro 1, está em $H$.

Este conjunto $H$ é conhecido como o monóide de Hilbert.

A propriedade 1 decorre dos seguintes cálculos: Se $a=4n+1$ e $b=4m+1$ então

$a\cdot b=(4n+1)\cdot (4m+1)=4(4n^2+m+n)+1=4p+1$

Novamente, tem-se a decomposição em fatores irredutíveis (fatores que não são produto de outros elementos em $H$). Acompanhe a fatoração de alguns elementos de $H$:

$n$	1	5	9	13	17	21	25	29	...	45	...	65	...	117	...
fatoração de $n$	1	5	9	13	17	21	$5\cdot 5$	29	...	$5\cdot 9$	...	$5\cdot 13$	...	$9\cdot 13$	...

Outros monóides

É possível obter outros exemplos similares procedendo de forma análoga com os conjuntos $\{an+1:n\in \mathbb{N}\}$, e em alguns casos com $\{an+b:n,a,b\in \mathbb{N}\}$ (para quais $a,b$ ainda funciona?). Também o conjunto $\{x^2+y^2:x,y\in \mathbb{N}\}$ possui essas propriedades.

Teorema de Euclides

Demonstração de Euclides

Exemplos

Se o conjunto $P$ que aparece na demonstração do teorema for constituído dos primeiros $r$ números primos, então as fatorações de $n=2\cdot 3\cdot \dots \cdot p_r+1$ para alguns valores de $r$ são as seguintes:

$r$	$n=2\cdot 3\cdot \dots \cdot p_r+1$	Fatoração de $n$	Tipo
$1$	$3=2+1$	$3$	primo
$2$	$7=2\cdot 3+1$	$7$	primo
$3$	$31=2\cdot 3\cdot 5+1$	$31$	primo
$4$	$211=2\cdot 3\cdot 5\cdot 7+1$	$211$	primo
$5$	$2311=2\cdot 3\cdot 5\cdot 7\cdot 11+1$	$2311$	primo
$6$	$30031=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1$	$59\cdot 509$	composto
$7$	$510511=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17+1$	$19\cdot 97\cdot 277$	composto

A demonstração acima pode ser adaptada para mostrar que o monóide de Hilbert $H$ possui infinitos elementos irredutíveis. Observe: Predefinição:Demonstração

Observação

Não serve escolher $n=b_1,\dots ,b_r+1$. Por que?

Demonstração de Hermite

Esta demonstração, assim como algumas outras, é uma variante daquela dada por Euclides. Acompanhe: Predefinição:Demonstração

Exemplos

Uma tabela como a anterior pode ser feita para os números $x(n)$. Neste caso, tem-se:

$n$	$x(n)=n!+1$	Fatoração de $x(n)$	Tipo
$1$	$2=1+1$	$2$	primo
$2$	$3=1\cdot 2+1$	$3$	primo
$3$	$7=1\cdot 2\cdot 3+1$	$7$	primo
$4$	$25=1\cdot 2\cdot 3\cdot 4+1$	$5\cdot 5$	composto
$5$	$121=1\cdot 2\cdot 3\cdot 4\cdot 5+1$	$11\cdot 11$	composto
...	...	...	...
$26951$	(bem grande!)	...	primo

Um fato curioso é que a última linha da tabela corresponde ao maior número primo da forma $n!+1$ para valores de $n$ até 35500.

Demonstração de Saidak

Exemplos

Tomando $N_1=2$, obtem-se a seguinte tabela:

$k$	$N_k$	Fatoração de $N_k$
$1$	$2=1+1$	$2$
$2$	$6=2\cdot (2+1)$	$2\cdot 3$
$3$	$42=6\cdot (6+1)$	$2\cdot 3\cdot 7$
$4$	$1806=42\cdot (42+1)$	$2\cdot 3\cdot 7\cdot 43$
$5$	$3263442=1806\cdot (1806+1)$	$2\cdot 3\cdot 7\cdot 43\cdot 13\cdot 139$

Teorema fundamental da aritmética

Na demonstração deste resultado será assumido que é válido um outro teorema, cuja justificativa só será apresentada no próximo capítulo. Trata-se de uma propriedade bastante elementar, que já era conhecida por Euclides (alguns anos A.C):

Predefinição:Teorema(I)

Observação

• Em Álgebra a propriedade mencionada é usada para definir "primo" e em geral, a "irredutibilidade" (definida nos exemplos do primeiro capítulo) não coincide com a noção de "primalidade".
• A estrutura aditiva de $\mathbb{Z}$ será crucial na demonstração desta propriedade e consequentemente, do teorema fundamental da aritmética.

Corolário

Esta é chamada de forma padrão da decomposição em fatores primos.

Outra forma de escrita é

$n=\prod _p{p}^{e_p}$, com $e_i=0$, exceto para uma quantidade finita de $p$'s.

A constatação da verdade dessas afirmações é elementar.

Aplicação

A partir dessa notação pode-se definir uma função $v_p:\mathbb{N}\to \mathbb{N}$ escolhendo $v_p(n)=e_p$. Verifica-se que a função acima definida goza das seguintes propriedades:

1. $v_p(m\cdot n)=v_p(m)+v_p(n)$
2. $v_p(m+n)\ge min(v_p(m),v_p(n))$

Essa função oferece uma forma "elegante" de se fazer certas demonstrações. Por exemplo, a irracionalidade de $\sqrt{2}$ é provada assim: Predefinição:Demonstração

Uma equivalência

Como foi mostrado, se a propriedade (I) for válida, tem-se a validade do teorema fundamental da aritmética. Na verdade, as duas proposições são equivalentes.

Lembre-se que para garantir uma equivalência lógica (para mais informações, consulte algumas seções do wikilivro sobre lógica), é preciso verificar duas implicações, uma das quais já foi demonstrada neste capítulo. Resta ainda verificar o seguinte: ao supor a validade do teorema fundamental da aritmética, pode ser provada a propriedade (I)?

A resposta é afirmativa, e o motivo você encontrará nesta seção. Veja: Predefinição:Demonstração

Exercícios

1. Demonstre os seguintes fatos:
   1. Se $p=6k+r$ (com $0\le r\le 5$) for um número primo maior do que $3$, então $r=1$ ou $r=5$.
   2. O produto de dois elementos quaisquer do conjunto $\{6k+1:k\in \mathbb{Z}\}$ é ainda um elemento deste conjunto.
   3. O conjunto $\{6k+5:k\in \mathbb{Z}\}$ possui uma infinidade de números primos.

Por enquanto, há poucos exercícios sobre este capítulo. O leitor está convidado a adicionar mais exercícios nesta seção, para ajudar a melhorar o texto.