Teorema de Euclides

O teorema de Euclides é um resultado fundamental estabelecido em teoria de números que garante a existência de uma infinidade de números primos.

O conjunto formado pelos números primos é infinito.

Existem várias demonstrações bem conhecidas desse teorema.

A demonstração de Euclides

Euclides de Alexandria: "Há mais números primos do que qualquer quantidade proposta de números primos."

Euclides ofereceu uma demonstração em sua obra Os Elementos (Livro IX, Proposição 20),[1] demonstração aqui parafraseada:

Tomando-se L , {\displaystyle L,} uma lista finita qualquer de números primos: L = { p 1 , p 2 , p 3 , . . . , p n } {\displaystyle L=\left\{p_{1},p_{2},p_{3},...,p_{n}\right\}}

Pode-se mostrar que existem números primos que não estão nessa lista. Da seguinte maneira:

Sendo P {\displaystyle P} o produto de todos os números primos na lista: P = p 1 × p 2 × p 3 × . . . × p n {\displaystyle P=p_{1}\times p_{2}\times p_{3}\times ...\times p_{n}}

E sendo q = P + 1 {\displaystyle q=P+1}

Então, q {\displaystyle q} pode ser primo ou não:

  • Se q é primo então há pelo menos um número primo a mais que não está listado.
  • Se q não é primo, então algum fator primo p divide q. Esse fator p não está na nossa lista L: se estivesse, ele dividiria P (pois P é o produto de todos os número na lista); mas como sabemos, p divide P + 1 = q. Então, para não deixar resto, p teria que dividir a diferença entre os dois números, que é (P + 1) − P ou seja, 1. Mas não existe número primo que divida 1, assim haveria uma contradição, logo, p não pode estar na lista. Isso significa que pelo menos mais um número primo existe além dos que estão na lista.

Isso prova que para qualquer lista finita de números primos, há um número primo que não está na lista. Portanto, existem infinitos números primos.

É muitas vezes erroneamente relatado que Euclides provou esse resultado por contradição, iniciando pela suposição de que o conjunto inicialmente considerado contém todos os números primos, ou que contém precisamente os n menores primos, ao invés de qualquer conjunto finito arbitrário de números primos.[2]

Demonstração por contradição

Suponhamos que o conjunto dos números primos seja finito: P = { 2 , 3 , 5 , . . . , p } . {\displaystyle \mathbb {P} =\left\{2,3,5,...,p\right\}.}

Assim, tomemos o número m , {\displaystyle m,} tal que: m = ( 2 × 3 × 5 × . . . × p ) + 1 {\displaystyle m=(2\times 3\times 5\times ...\times p)+1}

Note que m {\displaystyle m} não é divisível por nenhum elemento de P , {\displaystyle \mathbb {P} ,} pois o resto da divisão é sempre 1.

Assim, m {\displaystyle m} é outro número primo ou é um número composto cujos fatores são números primos que não estão na lista.

Logo, nossa suposição inicial não tem lugar.

Assim, o conjunto dos números primos não é finito. O que prova o Teorema.

Exemplos

Se o conjunto P {\displaystyle P} que aparece na demonstração do teorema for constituído dos primeiros r {\displaystyle r} números primos, então as fatorações de n = 2 ⋅ 3 ⋅ … ⋅ p r + 1 {\displaystyle n=2\cdot 3\cdot \ldots \cdot p_{r}+1} para alguns valores de r {\displaystyle r} são as seguintes:

r {\displaystyle r} n = 2 ⋅ 3 ⋅ … ⋅ p r + 1 {\displaystyle n=2\cdot 3\cdot \ldots \cdot p_{r}+1} Fatoração de n {\displaystyle n} Tipo
1 {\displaystyle 1} 3 = 2 + 1 {\displaystyle 3=2+1} 3 {\displaystyle 3} primo
2 {\displaystyle 2} 7 = 2 ⋅ 3 + 1 {\displaystyle 7=2\cdot 3+1} 7 {\displaystyle 7} primo
3 {\displaystyle 3} 31 = 2 ⋅ 3 ⋅ 5 + 1 {\displaystyle 31=2\cdot 3\cdot 5+1} 31 {\displaystyle 31} primo
4 {\displaystyle 4} 211 = 2 ⋅ 3 ⋅ 5 ⋅ 7 + 1 {\displaystyle 211=2\cdot 3\cdot 5\cdot 7+1} 211 {\displaystyle 211} primo
5 {\displaystyle 5} 2311 = 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 + 1 {\displaystyle 2311=2\cdot 3\cdot 5\cdot 7\cdot 11+1} 2311 {\displaystyle 2311} primo
6 {\displaystyle 6} 30031 = 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 + 1 {\displaystyle 30031=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1} 59 ⋅ 509 {\displaystyle 59\cdot 509} composto
7 {\displaystyle 7} 510511 = 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ⋅ 17 + 1 {\displaystyle 510511=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17+1} 19 ⋅ 97 ⋅ 277 {\displaystyle 19\cdot 97\cdot 277} composto

A demonstração de Euler

Leonhard Euler.

A demonstração do matemático suíço Leonhard Euler apoia-se no teorema fundamental da aritmética: que cada número tem uma única fatorização prima. Sendo P o conjunto de todos os números primos, Euler escreveu que:

∏ p ∈ P 1 1 − 1 / p = ∏ p ∈ P ∑ k ≥ 0 1 p k = ∑ n 1 n . {\displaystyle \prod _{p\in P}{\frac {1}{1-1/p}}=\prod _{p\in P}\sum _{k\geq 0}{\frac {1}{p^{k}}}=\sum _{n}{\frac {1}{n}}.}

A primeira igualdade é dada pela fórmula para a série geométrica em cada termo do produto. Para mostrar a segunda igualdade, distribua o produto sobre a soma:

∏ p ∈ P ∑ k ≥ 0 1 p k = ∑ k ≥ 0 1 2 k × ∑ k ≥ 0 1 3 k × ∑ k ≥ 0 1 5 k × ∑ k ≥ 0 1 7 k × ⋯ = ∑ k , l , m , n , ⋯ ≥ 0 1 2 k 3 l 5 m 7 n ⋯ = ∑ n 1 n {\displaystyle \prod _{p\in P}\sum _{k\geq 0}{\frac {1}{p^{k}}}=\sum _{k\geq 0}{\frac {1}{2^{k}}}\times \sum _{k\geq 0}{\frac {1}{3^{k}}}\times \sum _{k\geq 0}{\frac {1}{5^{k}}}\times \sum _{k\geq 0}{\frac {1}{7^{k}}}\times \cdots =\sum _{k,l,m,n,\cdots \geq 0}{\frac {1}{2^{k}3^{l}5^{m}7^{n}\cdots }}=\sum _{n}{\frac {1}{n}}}
∏ p ∈ P 1 1 − 1 / p = ∏ p ∈ P ∑ k ≥ 0 1 p k = ∑ n 1 n . {\displaystyle \prod _{p\in P}{\frac {1}{1-1/p}}=\prod _{p\in P}\sum _{k\geq 0}{\frac {1}{p^{k}}}=\sum _{n}{\frac {1}{n}}.}

No resultado, todo o produto de primos aparece exatamente uma vez e pelo teorema fundamental da aritmética essa soma é igual a soma de todos os inteiros.

A soma na direita é a série harmônica, que diverge. Portanto o produto na esquerda deve divergir também. Como todos os termos do produto são finitos, o número de termos tem de ser infinito; então, existem infinitos números primos.

A demostração de Furstenberg

O matemático israelense Hillel Furstenberg introduziu uma demonstração que usa topologia geral.

Referências

  1. ↑ James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.
  2. ↑ Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52.

Ver também

Wikilivros
Wikilivros
O wikilivro Teoria de números tem uma página sobre Teorema de Euclides

Ligações externas

  • Portal da matemática