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

editar
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   é divisor de qualquer número inteiro (propriedade 8) garantem que todo número inteiro   diferente de   e   possui pelo menos dois divisores:   e  . 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   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   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   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

editar
Teorema

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

Demonstração
Dado um número inteiro  , vamos mostrar por indução que  , com cada   sendo um número primo.

De fato, para  , o teorema é válido, pois basta tomar  .

Se  , e   for primo, a afirmação é obviamente verdadeira, pois é suficiente escolher  .

Considere então que   é composto, e que a hipótese de indução é que todo número menor que   admite decomposição em fatores primos.

Logo, existem inteiros   e   tais que  . Além disso,   e   são menores que  .

Pela hipótese de indução, tem-se

  e
 ,

com cada   e cada   sendo um número primo, donde segue que:

 

Assim, basta renomear os primos   e   como  , e tem-se o teorema.

Exemplos

editar

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

 
 
 
 
 
 
 
 

e ainda:

 

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   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  , 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   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

editar

Considere o conjunto  .

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

  2 4 6 8 10 12 14 16 18 ...
fatoração de   2   6   10   14   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  . De modo geral, um elemento   é 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   é um elemento redutível de  , então  , ou seja, todo elemento redutível é um múltiplo de 4.

Os elementos irredutíveis de   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   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   (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:

 

E como se verifica facilmente, os números acima são todos irredutíveis em  .

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  , além de sua estrutura multiplicativa.

O monóide de Hilbert

editar

Seja  .

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

  1.  , quaisquer que sejam  ;
  2.  , para quaisquer  ;
  3. O elemento neutro da multiplicação, o número inteiro 1, está em  .

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

A propriedade 1 decorre dos seguintes cálculos: Se   e   então

 

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

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

Outros monóides

editar

É possível obter outros exemplos similares procedendo de forma análoga com os conjuntos  , e em alguns casos com   (para quais   ainda funciona?). Também o conjunto   possui essas propriedades.

Teorema de Euclides

editar
Teorema

Existe uma infinidade de números primos.

Demonstração de Euclides

editar
Demonstração
Considere um conjunto finito de números primos, contendo uma quantidade arbitrária de elementos. Denote tal conjunto por  .

Seja  . Como  , então   tem algum fator primo  , ou seja,  .

Se  , seria verdade que  , devido a linearidade da divisibilidade. Mas nenhum primo divide 1, então  .

Assim, mostrou-se que não importa quantos elementos tenha um certo conjunto   de números primos, sempre existirá um outro número primo que não está em  , ou seja, existe uma infinidade de números primos!

Exemplos

editar

Se o conjunto   que aparece na demonstração do teorema for constituído dos primeiros   números primos, então as fatorações de   para alguns valores de   são as seguintes:

    Fatoração de   Tipo
      primo
      primo
      primo
      primo
      primo
      composto
      composto

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

Demonstração
Se   são elementos irredutíveis de  , então   é também um elemento de   (por quê?), e portanto possui decomposição em fatores irredutíveis em  .

Seja   um dos fatores que aparecem na decomposição de  .

Então  , para  , caso contrário   (pelo mesmo motivo de antes).

Logo existem infinitos números irredutíveis em  .

Observação

Não serve escolher  . Por que?

Demonstração de Hermite

editar

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

Demonstração
Para cada número natural  , defina-se  .

Como qualquer outro número natural,   possui algum fator primo  . No entanto, este fator não pode ser divisor de qualquer número menor ou igual a  , pois neste caso, dividiria também  , e consequentemente seria divisor de  .

Portanto,   tem que ser maior do que  .

Resumindo, dado qualquer inteiro positivo  , existe um número primo que é maior do que  , ou seja, o conjunto dos números primos é infinito.

Exemplos

editar

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

    Fatoração de   Tipo
      primo
      primo
      primo
      composto
      composto
... ... ... ...
  (bem grande!) ... primo

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

Demonstração de Saidak

editar
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  , de tal modo que cada termo   tenha pelo menos   fatores primos. Dessa forma, inevitavelmente, conclúi-se que existem infinitos números primos.

A sequência inicia com  .

Como   e   não têm divisores em comum, o produto   possui ao menos 2 divisores primos.

Do mesmo modo,   e   não têm fatores em comum, logo   possui ao menos 3 fatores primos.

O processo pode continuar indefinidamente, definindo-se sempre  , e cada   terá no mínimo k fatores primos (verifique isto por indução!).

Exemplos

editar

Tomando  , obtem-se a seguinte tabela:

    Fatoração de  
     
     
     
     
     

Teorema fundamental da aritmética

editar
Teorema

A decomposição de um número inteiro   em fatores primos é única, exceto pela ordem. Em símbolos: Se  , e cada   e todo   é um número primo, então   e para cada   tem-se  , para alguma permutação  .

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   será crucial na demonstração desta propriedade e consequentemente, do teorema fundamental da aritmética.

Demonstração do teorema fundamental da aritmética

editar
Demonstração
A prova será feita por indução.

Se  , o resultado é imediato, então considere que o mesmo vale para todo número inteiro menor que  .

Supondo que existem duas decomposições para o inteiro  , ou seja,  , segue que algum   é múltiplo de  . Como a ordem dos fatores não é importante, pode-se supor que  .

Neste caso, seque que  , pois   e os únicos divisores de   são   e ele próprio.

Logo,

  implica que  

Certamente  , então pela hipótese de indução,   possui uma fatoração única, donde   e  , para cada índice .

Assim, a fatoração de   é única.

Corolário

editar
Corolário

Todo   pode ser escrito como  , com   e  .

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

Outra forma de escrita é

 , com  , exceto para uma quantidade finita de  's.

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

Aplicação

editar

A partir dessa notação pode-se definir uma função   escolhendo  . Verifica-se que a função acima definida goza das seguintes propriedades:

  1.  
  2.  

Essa função oferece uma forma "elegante" de se fazer certas demonstrações. Por exemplo, a irracionalidade de   é provada assim:

Demonstração
Se   fosse racional, poderia ser escrito como  , sendo que  , e  .

Neste caso, seria verdade que  , ou seja,  . Aplicando a função   em ambos os membros, segue que

 

No entanto, essa igualdade não é possível, pois o primeiro membro é um número par, e o último é ímpar.

Logo,   só pode ser irracional.

Uma equivalência

editar

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  . Então, pela definição de divisibilidade, existe algum número inteiro   tal que  .

Mas   e   possuem decomposição em fatores primos, então:

  e
 

Logo,  , ou seja,   precisa ser um dos  's ou um dos  's.

No primeiro caso, conclui-se que  , e no segundo  .

Exercícios

editar
  1. Demonstre os seguintes fatos:
    1. Se   (com  ) for um número primo maior do que  , então   ou  .
    2. O produto de dois elementos quaisquer do conjunto   é ainda um elemento deste conjunto.
    3. O conjunto   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.