DemonstraçõesDemonstração - Infinitude dos Números Primos

Fórum de coletânea das melhores demonstrações de teoremas de matemática.
Se você quiser postar uma demonstração aqui, poste, inicialmente, no fórum correspondente utilizando o título "Demonstração Teorema X" e substitua com o nome do teorema/fórmula que você postou e, depois, envie o link para um moderador pedindo para sua mensagem ser movida para o fórum "Demonstrações". Somente moderadores poderão mover sua mensagem para este fórum.

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
Cássio
3 - Destaque
Mensagens: 895
Registrado em: Seg 12 Dez, 2011 14:05
Última visita: 29-09-22
Localização: PETROLINA/PE
Fev 2013 21 11:17

Demonstração - Infinitude dos Números Primos

Mensagem não lida por Cássio »

Teorema: Existem infinitos números primos.

1ª Demonstração (Clássica - Euclides)

Suponha que exista uma quantidade finita de números primos, para ser mais preciso, [tex3]n\in\mathbb{N}[/tex3] número primos. Sejam eles [tex3]p_1,\ p_2,\ ...,\ p_n[/tex3] os tais números primos.

Considere o número [tex3]P=(p_1\cdot p_2\cdot p_3\cdot...\cdot p_n)+1.[/tex3] Pelo Teorema Fundamental da Aritmética, sabemos que [tex3]P[/tex3] pode ser decomposto em fatores primos. Então existe algum primo [tex3]p_i[/tex3] que divide [tex3]P=(p_1\cdot p_2\cdot p_3\cdot...\cdot p_n)+1.[/tex3]
Mas como só existem [tex3]n[/tex3] primos, então esse [tex3]p_i[/tex3] deve ser igual a algum dos primos [tex3]p_1,\ p_2,\ ...,\ p_n.[/tex3]
Mas se [tex3]p_i[/tex3] é igual a algum destes primos, então [tex3]p_i\mid (p_1\cdot p_2\cdot...\cdot p_n).[/tex3] Como [tex3]p_i\mid P=(p_1\cdot p_2\cdot p_3\cdot...\cdot p_n)+1[/tex3] e [tex3]p_i\mid (p_1\cdot p_2\cdot p_3\cdot...\cdot p_n),[/tex3] temos que [tex3]p_i\mid(P-(p_1\cdot p_2\cdot p_3\cdot...\cdot p_n))=1.[/tex3] Um absurdo, pois [tex3]1[/tex3] não é primo.
Logo, não pode existir uma quantidade específica de primos, se não chegamos a este absurdo. Logo, existem infinitos números primos

--------------------------------------------------------------------------------

2ª Demonstração: (devida a Paul Erdös)

Todo número natural [tex3]n[/tex3] maior que 1 pode ser escrito na forma [tex3]n=ab^2,[/tex3] onde [tex3]b\ge 1[/tex3] e [tex3]a> 1[/tex3] é dito um número "livre de quadrados" (é apenas uma maneira de dizer que não existe quadrado perfeito, diferente de 1, que divida [tex3]a[/tex3] ).
Resposta

Vamos demonstrar que todo natural pode ser escrito na forma [tex3]n=ab^2:[/tex3]
Seja [tex3]n=p_1^{\alpha_{_{1}}}\cdot p_{_2}}^{\alpha_{_{2}}}\cdot...\cdot p_{_{k}}^{\alpha_{_{k}}},\ \ [p_1<p_2<...<p_n].[/tex3] Todos os números [tex3]\alpha_{_{1}},\ ...,\ \alpha_{_{k}}[/tex3] podem ser escritos na forma [tex3]\alpha_{_{i}}=2q_{_{i}}+r_{_{i}},\ \ 0\le r_i<2.[/tex3] Daí: [tex3]n=(p_{_{1}}^{2q_{_{1}}}\cdot p_{_{2}}^{2q_{_{2}}}\cdot ...\cdot p_{_{k}}^{2q_{_{k}}})(p_{_{1}}^{r_{_{i}}}\cdot...\cdot p_{_{k}}^{r_{_{k}}})=(p_{_{1}}^{q_{_{1}}}\cdot...\cdot p_{_{k}}^{q_{_{k}}})^2\cdot(p_{_{1}}^{r_{_{i}}}\cdot...\cdot p_{_{k}}^{r_{_{k}}})[/tex3] . Faça [tex3]b=p_{_{1}}^{q_{_{1}}}\cdot...\cdot p_{_{k}}^{q_{_{k}}}[/tex3] e [tex3]a=p_{_{1}}^{r_{_{i}}}\cdot...\cdot p_{_{k}}^{r_{_{k}}}.[/tex3] É claro que [tex3]a[/tex3] é livre de quadrados, pois todos os [tex3]r_{_{i}}[/tex3] são [tex3]0[/tex3] ou [tex3]1.[/tex3]
Suponhamos que existam exatamente [tex3]k[/tex3] números primos. Agora, vamos pensar quantos números menores que ou iguais à [tex3]n[/tex3] podem existir?
Por simples argumentos combinatórios, podemos concluir que podem existir no máximo [tex3]2^k\sqrt{n}[/tex3] números menores que [tex3]n.[/tex3]
De fato, existem duas escolhas para cada [tex3]r_i\ (0\ \mathrm{ou}\ 1)[/tex3] , totalizando num total de no máximo [tex3]2^k[/tex3] escolhas para [tex3]a.[/tex3]
Além disso, é fácil ver que se [tex3]a_1b_1^2[/tex3] é um número menor que ou igual a [tex3]n,[/tex3] então com certeza [tex3]b_1\le \sqrt{n}.[/tex3] Totalizando num total de no máximo [tex3]\sqrt{n}[/tex3] escolhas para [tex3]b.[/tex3]
Pelo princípio multiplicativo, a quantidade máxima de números menores que [tex3]n[/tex3] é [tex3]2^k\sqrt{n}.[/tex3]
Portanto, se existem no máximo [tex3]2^k\sqrt{n}[/tex3] números menores que ou iguais à [tex3]n[/tex3] , isso significa que [tex3]n\le 2^k\sqrt{n}.[/tex3]
Mas essa desigualdade é falsa para [tex3]n[/tex3] escolhido convenientemente.
De fato, estando [tex3]k[/tex3] definido, escolha um [tex3]n>2^{2k}.[/tex3] Nessas condições, temos que [tex3]2^k\sqrt{n}=2^k\sqrt{2^{2k}}=2^k\cdot 2^k=2^{2k}<n,[/tex3] contrariando a primeira desigualdade que encontramos.

Concluímos assim que existem infinitos números primos.

---------------------------------------------------------------------------------------------

3ª Demonstração:

Vamos provar que todos os números da forma [tex3]F(k)=2^{2^k}+1,\ \ n\in\mathbb{N}[/tex3] são primos entre si, o que carrega implicitamente uma prova que existem infinitos primos

Vamos usar o seguinte Lema: Sejam [tex3]a \in\mathbb{N^*}[/tex3] e [tex3]m,\ n,\ q,\ r\in\mathbb{N},[/tex3] tais que [tex3]m=nq+r,[/tex3] então
[tex3](a^{m}+1,\ a^n+1)=\begin{cases}\ (a^n+1,a^r+1),\ \ \ \mathrm{se}\ q\ \mathrm{par}\\ \ (a^n+1,a^r-1)\ \ \ \mathrm{se}\ q\ \mathrm{impar}\end{cases}[/tex3]
Não vamos precisar do caso ímpar, então vamos mostrar apenas o caso par.

Prova: Se [tex3]q[/tex3] é par, [tex3]\exists\ t\in\mathbb{N}\mid q=2t\Rightarrow a^{nq}-1=(a^{n})^{2t}-1[/tex3] .
Agora afirmamos que [tex3]a^n+1\mid a^{nq}-1=(a^n)^{2t}-1.[/tex3]
Resposta

Prova: Proposição: [tex3]x, y>0\Rightarrow x+y\mid x^{2z}-y^{2z}[/tex3] .
Prova: Indução sobre [tex3]z.[/tex3]
Para [tex3]z=0[/tex3] é trivialmente verdade.
Suponhamos, agora, que [tex3]x+y\mid x^{2z}-y^{2z}.[/tex3]
Daí [tex3]x^{2(z+1)}-y^{2(z+1)}=x^2x^{2z}-y^2x^{2z}+y^2x^{2z}-y^2y^{2z}=[/tex3]
[tex3](x^2-y^2)x^{2z}+y^2(x^{2z}-y^{2z}).[/tex3]
Como [tex3]x+y\mid x^2-y^2[/tex3] e, por hipótese, [tex3]x+y\mid x^{2z}-y^{2z},[/tex3] decorre o resultado. Logo, [tex3](a^n)^{2t}-1=(a^n)^{2t}-1^{2t}.[/tex3] Basta considerar [tex3]x=a^n[/tex3] e [tex3]y=1.[/tex3]


Como [tex3]a^n+1\mid a^{nq}-1[/tex3] , podemos escrever a expressão [tex3]a^r(a^{nq}-1)[/tex3] como [tex3]a^r(a^{nq}-1)=(a^{n}+1)w,\ \ w\in\mathbb{N}.[/tex3]
Então, temos que: [tex3]a^m+1=a^{nq+r}+1=a^r(a^{nq}-1)+a^r+1=(a^n+1)w+a^r+1[/tex3] .
Daí: [tex3](a^m+1,\ a^n+1)=((a^n+1)w+a^r+1,\ a^n+1)[/tex3] . Uma propriedade do mdc é que [tex3](u,\ us+v)=(u,\ v)[/tex3] ,
daí: [tex3](a^m+1,\ a^n+1)=((a^n+1)w+a^r+1,\ a^n+1)=(a^r+1,\ a^n+1)[/tex3] CQD.
[tex3]=(a^n+1,\ a^r+1)[/tex3] C.Q.D.

Sabemos que se [tex3]k_1>k_2\Rightarrow k_1=k_2+l,\ \ l\in\mathbb{N^*}\Rightarrow 2^{k_{_{1}}}=2^{k_{_{2}}}\cdot2^{l}[/tex3] Ou seja, [tex3]2^{k_{_{1}}}=2^{k_{_{2}}}\cdot q+0[/tex3] , onde [tex3]q=2^{l}[/tex3] é par e [tex3]r=0[/tex3] . Agora usamos o lema, considerando [tex3]a=2,\ \ m=2^{k_1},\ \ n=2^{k_2},\ r=0[/tex3] e [tex3]q[/tex3] é par. Logo, pelo Lema, temos que [tex3](2^{2^{k_{_{1}}}}+1,\ 2^{2^{k_{_{2}}}}+1)=(2^{2^{k_{_{2}}}}+1,\ 2^0+1)=1.[/tex3]
Concluimos assim que [tex3](2^{2^{k_{_{1}}}}+1,\ 2^{2^{_{_{k_2}}}}+1)=1,\ \ \forall \ k_1\ne k_2\in\mathbb{N^*}.[/tex3]

Dessa forma, todos os números da forma [tex3]2^{2^{k}}+1[/tex3] são primos entre si. Se existissem finitos números primos, em algum momento dois números [tex3]F(k)[/tex3] acabariam repetindo o mesmo primo, contrariando o fato de todos os [tex3]F(k)[/tex3] ser primos entre si!

Resposta

OBS: Poderíamos ter usado outro número diferente [tex3]2^{2^k}.[/tex3] Só usei esse caso específico porque esses números são conhecidos como Números de Fermat. Fermat acreditava que [tex3]F(k)[/tex3] era sempre primo. Mas não é conhecido nenhum primo para [tex3]k\ge 5.[/tex3]
---------------------------------------------------------------------------------------------------------

Uma 4ª e 5ª demonstração pode ser feita mostrando que a soma
[tex3]\sum_{p\ \mathrm{primo}}\dfrac{1}{p}=\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{5}+...[/tex3]
é divergente. A prova não é tão elementar quanto as provas acima.

Última edição: Cássio (Qui 21 Fev, 2013 11:17). Total de 2 vezes.


"Se você se sente menos e menos satisfeito com suas respostas a perguntas que você mesmo elabora mais e mais perfeitamente, é sinal de que sua capacidade intelectual está aumentando."
Charles Churchman

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Demonstrações”