Teoria de números/Números primos

Origem: Wikilivros, livros abertos por um mundo aberto.

Anterior: Divisibilidade

Índice

Próximo: Máximo divisor comum

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á possuia 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.

Tabela de conteúdo 1 Definição de número primo 2 Teorema da existência de fatoração 3 Exemplos 3.1 O conjunto dos números pares positivos 3.2 O monóide de Hilbert 3.3 Outros monóides 4 Teorema de Euclides 4.1 Demonstração de Euclides 4.1.1 Exemplos 4.2 Demonstração de Hermite 4.2.1 Exemplos 4.3 Demonstração de Saidak 4.3.1 Exemplos 5 Teorema fundamental da aritmética 5.1 Demonstração do teorema fundamental da aritmética 6 Corolário 6.1 Aplicação 6.2 Uma equivalência 7 Exercícios

[editar] 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 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.

[editar] Teorema da existência de fatoração

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.

[editar] 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:

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

[editar] O conjunto dos números pares positivos

Considere o conjunto .

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

[editar] O monóide de Hilbert

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 :

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

[editar] Outros monóides

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

[editar] Teorema de Euclides

[editar] 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 . 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!

[editar] Exemplos

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?

[editar] 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 , 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.

[editar] Exemplos

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.

[editar] 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 , 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!).

[editar] Exemplos

Tomando , obtem-se a seguinte tabela:

		Fatoração de

[editar] 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):

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.

[editar] Demonstração do teorema fundamental da aritmética

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, m possui uma fatoração única, donde e , para cada índice. Assim, a fatoração de é única.

[editar] Corolário

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.

[editar] Aplicação

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.

[editar] 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 . 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 .

[editar] Exercícios

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.