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

Definição

Um número primo é um número natural que tem exatamente dois divisores positivos (distintos). Um número que não é primo é chamado de composto.

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.

Teorema da existência de fatoração

Teorema

Todo número inteiro positivo maior do que um tem decomposição em fatores primos.

Demonstração

Dado um número inteiro $n$, vamos mostrar por indução que $n=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{r}$, com cada $p_{j}$ sendo um número primo. De fato, para $n=2$, o teorema é válido, pois basta tomar $p_{1}=2$. Se $n>2$, e $n$ for primo, a afirmação é obviamente verdadeira, pois é suficiente escolher $p_{1}=n$. Considere então que $n>2$ é composto, e que a hipótese de indução é que todo número menor que $n$ admite decomposição em fatores primos. Logo, existem inteiros $a$ e $b$ tais que $n=a\cdot b$. Além disso, $a$ e $b$ são menores que $n$. Pela hipótese de indução, tem-se $a=q_{1}\cdot q_{2}\cdot \ldots \cdot q_{m}$ e $b=t_{1}\cdot t_{2}\cdot \ldots \cdot t_{n}$, com cada $q_{j}$ e cada $t_{j}$ sendo um número primo, donde segue que: $n=a\cdot b=\left(q_{1}\cdot q_{2}\cdot \ldots \cdot q_{m}\right)\cdot \left(t_{1}\cdot t_{2}\cdot \ldots \cdot t_{n}\right)$ Assim, basta renomear os primos $q_{j}$ e $t_{j}$ como $p_{1},\ldots ,p_{r}$, e tem-se o 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,\ldots \}$.

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.

Prova
Esta prova é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

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,\ldots \}$.

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. $\left(a\cdot b\right)\cdot c=a\cdot \left(b\cdot c\right)=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

Teorema

Existe uma infinidade de números primos.

Demonstração de Euclides

Demonstração

Considere um conjunto finito de números primos, contendo uma quantidade arbitrária de elementos. Denote tal conjunto por $P=\{p_{1},\ldots ,p_{r}\}$. Seja $n=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{r}+1$. Como $n\in \mathbb {N}$, então $n$ tem algum fator primo $p$, ou seja, $p|n$. Se $p\in P$, seria verdade que $p|1=n-(p_{1}\cdot p_{2}\cdot \ldots \cdot p_{r})$, devido a linearidade da divisibilidade. Mas nenhum primo divide 1, então $p\not \in P$. Assim, mostrou-se que não importa quantos elementos tenha um certo conjunto $P$ de números primos, sempre existirá um outro número primo que não está em $P$, ou seja, existe uma infinidade de números primos!

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 \ldots \cdot p_{r}+1$ para alguns valores de $r$ são as seguintes:

$r$	$n=2\cdot 3\cdot \ldots \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:

Demonstração

Se $\{b_{1},\ldots ,b_{r}\}$ são elementos irredutíveis de $H$, então $n=4(b_{1},\ldots ,b_{r})+1$ é também um elemento de $H$ (por quê?), e portanto possui decomposição em fatores irredutíveis em $H$. Seja $b$ um dos fatores que aparecem na decomposição de $n$. Então $b\not =b_{j},\!$, para $j=1\ldots r$, caso contrário $b|1$ (pelo mesmo motivo de antes). Logo existem infinitos números irredutíveis em $H$.

Observação

Não serve escolher $n=b_{1},\ldots ,b_{r}+1$. Por que?

Demonstração de Hermite

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

Demonstração

Para cada número natural $n$, defina-se $x(n)=n!+1$. Como qualquer outro número natural, $x(n)$ possui algum fator primo $p$. No entanto, este fator não pode ser divisor de qualquer número menor ou igual a $n$, pois neste caso, dividiria também $n!$, e consequentemente seria divisor de $1=x(n)-n!$. Portanto, $p$ tem que ser maior do que $n$. Resumindo, dado qualquer inteiro positivo $n$, existe um número primo que é maior do que $n$, ou seja, o conjunto dos números primos é infinito.

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

Demonstração

Esta demonstração foi publicada recentemente pelo pesquisador Filip Saidak, em seu artigo A new proof of Euclid’s theorem de 2006. A prova consiste no seguinte: Forma-se uma sequência crescente de números $N_{1},\ldots N_{k},\ldots \!$, de tal modo que cada termo $N_{k}$ tenha pelo menos $k$ fatores primos. Dessa forma, inevitavelmente, conclúi-se que existem infinitos números primos. A sequência inicia com $N_{1}>1$. Como $N_{1}$ e $N_{1}+1$ não têm divisores em comum, o produto $N_{2}=N_{1}(N_{1}+1)$ possui ao menos 2 divisores primos. Do mesmo modo, $N_{2}$ e $N_{2}+1$ não têm fatores em comum, logo $N_{3}=N_{2}(N_{2}+1)$ possui ao menos 3 fatores primos. O processo pode continuar indefinidamente, definindo-se sempre $N_{k}=N_{k-1}(N_{k-1}+1)$, e cada $N_{k}$ terá no mínimo k fatores primos (verifique isto por indução!).

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

Teorema

A decomposição de um número inteiro $n\in \mathbb {N} ^{*}$ em fatores primos é única, exceto pela ordem. Em símbolos: Se $p_{1}\cdot \ldots \cdot p_{r}=n=q_{1}\cdot \ldots \cdot q_{s}$, e cada $p_{j}$ e todo $q_{j}$ é um número primo, então $r=s$ e para cada $j$ tem-se $p_{j}=q_{\sigma (j)}$, para alguma permutação $\sigma$.

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):

Teorema

Se um número primo divide o produto de dois números inteiros, então ele é divisor de um dos dois.

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

Demonstração do teorema fundamental da aritmética

Demonstração

A prova será feita por indução. Se $k=2$, o resultado é imediato, então considere que o mesmo vale para todo número inteiro menor que $k=n$. Supondo que existem duas decomposições para o inteiro $n$, ou seja, $n=p_{1}\cdot \ldots \cdot p_{r}=q_{1}\cdot \ldots \cdot q_{s}$, segue que algum $q_{j}$ é múltiplo de $p_{1}$. Como a ordem dos fatores não é importante, pode-se supor que $j=1$. Neste caso, seque que $p_{1}=q_{1}$, pois $p_{1}\not =1$ e os únicos divisores de $q_{1}$ são $1$ e ele próprio. Logo, $n=\mathbf {p_{1}} \cdot \ldots \cdot p_{r}=\mathbf {p_{1}} \cdot \ldots \cdot q_{s}$ implica que $m=p_{2}\cdot \ldots \cdot p_{r}=q_{2}\cdot \ldots \cdot q_{s}$ Certamente $m<n$, então pela hipótese de indução, $m$ possui uma fatoração única, donde $r=s$ e $p_{j}=q_{j}$, para cada índice$j$. Assim, a fatoração de $n$ é única.

Corolário

Corolário

Todo $n\in \mathbb {N} ^{*}$ pode ser escrito como $n=p_{1}^{e_{1}}\cdot \ldots \cdot p_{r}^{e_{r}}$, com $p_{1}<p_{2}<\ldots <p_{r}$ e $e_{i}\geq 1$.

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} \rightarrow \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)\geq 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:

Demonstração

Se ${\sqrt {2}}$ fosse racional, poderia ser escrito como ${\sqrt {2}}={\frac {a}{b}}$, sendo que $a,b\in \mathbb {Z}$, e $b\not =0$. Neste caso, seria verdade que $\left({\frac {a}{b}}\right)^{2}=2$, ou seja, $a^{2}=2b^{2}$. Aplicando a função $v_{2}$ em ambos os membros, segue que $2v_{2}(a)=v_{2}(a^{2})=v_{2}(2b^{2})=v_{2}(2)+2v_{2}(b)=1+2v_{2}(b)$ No entanto, essa igualdade não é possível, pois o primeiro membro é um número par, e o último é ímpar. Logo, ${\sqrt {2}}$ só pode ser irracional.

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:

Demonstração

Suponha que $p|ab$. Então, pela definição de divisibilidade, existe algum número inteiro $x$ tal que $ab=px$. Mas $a$ e $b$ possuem decomposição em fatores primos, então: $a=p_{1}\cdot \ldots \cdot p_{r}$ e $b=q_{1}\cdot \ldots \cdot q_{s}$ Logo, $px=ab=(p_{1}\cdot \ldots \cdot p_{r})\cdot (q_{1}\cdot \ldots \cdot q_{s})$, ou seja, $p$ precisa ser um dos $p_{j}$'s ou um dos $q_{j}$'s. No primeiro caso, conclui-se que $p|a$, e no segundo $p|b$.

Exercícios

1. Demonstre os seguintes fatos:
   1. Se $p=6k+r$ (com $0\leq r\leq 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.