Teoria de números/Números primos: diferenças entre revisões
[edição verificada] | [edição verificada] |
Conteúdo apagado Conteúdo adicionado
m Desfeita a edição 178814 de 189.61.167.241 (Discussão): totalmente fora de contexto e repete informação que já foi colocada no texto |
m hack obsoleto: as fórmulas já aparecem em PNG e não há mais como exibi-las em HTML nem MathML (futuramente teremos MathJax) |
||
Linha 39:
}}
{{Demonstração
|Dado um número inteiro <math>n
De fato, para <math>n=2
Se <math>n>2
Considere então que <math>n>2
Logo, existem inteiros <math>a
Pela hipótese de indução, tem-se
:<math>a=q_1\cdot q_2 \cdot \ldots \cdot q_m
:<math>b=t_1\cdot t_2 \cdot \ldots \cdot t_n
com cada <math>q_j
:<math>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 <math>q_j
}}
Linha 61:
Com o auxílio de um computador, e algum software para [[w:Sistema de álgebra computacional|computação algébrica]], verifica-se ques são verdadeiras as seguintes igualdades:
:<math>6=2\cdot 3
:<math>123=3\cdot 41
:<math>1234=2\cdot 617
:<math>12345=3\cdot 5\cdot 823
:<math>123456=2^6\cdot 3\cdot 643\!</math>
:<math>1234567=127\cdot 9721
:<math>12345678=2\cdot 3^2\cdot 47\cdot 145693
:<math>123456789=3^2\cdot 3607\cdot 3803
e ainda:
:<math>12345678901234567=7\cdot 1763668414462081
Na página ''[http://www.alpertron.com.ar/ECM.HTM 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 <math>\mathbb{Z}
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 <u>uma decomposição</u> em fatores primos, ou seja, se Carlos e Joana encontrarem duas fatorações em primos para um certo número inteiro <math>n</math>, 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 <math>\mathbb{Z}
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.
Linha 83:
=== O conjunto dos números pares positivos ===
Considere o conjunto <math>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:
Linha 102:
|width="40px"| ...
|-
! fatoração de <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}n
| 2
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 2
| 6
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 2\cdot 2
| 10
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 6
| 14
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 2\cdot 2\cdot 2
| 18
| ...
Linha 118:
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 <math>2\mathbb{Z}
De modo geral, um elemento <math>n</math> é ''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 <math>n
Os elementos irredutíveis de <math>2\mathbb{Z}
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 <math>2\mathbb{Z}
{{Prova}}
Uma última consideração a respeito do conjunto <math>2\mathbb{Z}
:<math>60 = 2 \cdot 30 = 6 \cdot 10
E como se verifica facilmente, os números acima são todos irredutíveis em <math>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 <math>\mathbb{Z}
=== O monóide de Hilbert ===
Seja <math>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 <math>H
# <math> a\cdot b \in H </math>, quaisquer que sejam <math> a,b \in H </math>;
# <math> \left(a\cdot b\right)\cdot c = a\cdot \left(b\cdot c\right) = a\cdot b\cdot c </math>, para quaisquer <math> a,b,c \in H </math>;
# O elemento neutro da multiplicação, o número inteiro 1, está em <math>H
Este conjunto <math>H
A propriedade 1 decorre dos seguintes cálculos: Se <math>a=4n+1
:<math>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 <math>H
<center>
Linha 170:
|width="40px"| ...
|-
! fatoração de <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}n
| 1
| 5
Linha 177:
| 17
| 21
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}5\cdot 5
| 29
| ...
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}5\cdot 9
| ...
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}5\cdot 13
| ...
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}9\cdot 13
| ...
|}
Linha 190:
=== Outros monóides ===
É possível obter outros exemplos similares procedendo de forma análoga com os conjuntos <math>\{ an+1: n\in \mathbb{N} \}
== Teorema de Euclides ==
Linha 198:
=== 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 <math>P = \{ p_1, \ldots, p_r\}
Seja <math>n = p_1 \cdot p_2 \cdot \ldots \cdot p_r + 1
Se <math>p \in P
Assim, mostrou-se que não importa quantos elementos tenha um certo conjunto <math>P
}}
==== Exemplos ====
Se o conjunto <math>P
{| class="wikitable" style="text-align:center"
!<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}r
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}1
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}3
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}4
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}5
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}6
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}7
|}
A demonstração acima pode ser adaptada para mostrar que o monóide de Hilbert <math>H
{{Demonstração
|Se <math>\{ b_1, \ldots, b_r\}
Seja <math>b
Então <math>b\not=b_j,\!</math>, para <math>j = 1\ldots r
Logo existem infinitos números irredutíveis em <math>H
}}
;Observação:
Não serve escolher <math>n = b_1, \ldots, b_r + 1
=== 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 <math>n
Como qualquer outro número natural, <math>x(n)
Portanto, <math>p
Resumindo, dado qualquer inteiro positivo <math>n
}}
==== Exemplos ====
Uma tabela como a anterior pode ser feita para os números <math>x(n)
{| class="wikitable" style="text-align:center"
!<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}n
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}1
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}3
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}4
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}5
|-
| ... || ... || ... || ...
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}26951
|}
Um fato curioso é que a última linha da tabela corresponde ao maior número primo da forma <math>n!+1
=== Demonstração de Saidak ===
Linha 283:
|Esta demonstração foi publicada recentemente pelo pesquisador Filip Saidak, em seu artigo ''[[../Bibliografia|A new proof of Euclid’s theorem]]'' de 2006. A prova consiste no seguinte:
Forma-se uma sequência crescente de números <math>N_1,\ldots N_k,\ldots\!</math>, de tal modo que cada termo <math>N_k
A sequência inicia com <math>N_1>1
Como <math>N_1
Do mesmo modo, <math>N_2
O processo pode continuar indefinidamente, definindo-se sempre <math>N_k = N_{k-1}(N_{k-1} + 1)
}}
==== Exemplos ====
Tomando <math>N_1=2
{| class="wikitable" style="text-align:center"
!<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}k
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}1
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}3
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}4
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}5
|}
== Teorema fundamental da aritmética ==
{{Teorema
|A decomposição de um número inteiro <math>n \in \mathbb{N}^*
Se <math>p_1\cdot\ldots\cdot p_r = n = q_1\cdot\ldots\cdot q_s
}}
Linha 328:
* 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 <math>\mathbb{Z}
=== Demonstração do teorema fundamental da aritmética ===
{{Demonstração
|A prova será feita por indução.
Se <math>k=2
Supondo que existem duas decomposições para o inteiro <math>n
Neste caso, seque que <math>p_1=q_1
Logo,
:<math>n = \mathbf{p_1}\cdot\ldots\cdot p_r = \mathbf{p_1}\cdot\ldots\cdot q_s</math> implica que <math>m = p_2\cdot\ldots\cdot p_r = q_2\cdot\ldots\cdot q_s
Certamente <math>m <n
Assim, a fatoração de <math>n
}}
== Corolário ==
{{Corolário
|Todo <math>n \in \mathbb{N}^*
}}
Linha 355:
Outra forma de escrita é
:<math>n = \prod_{p} p^{e_p}
A constatação da verdade dessas afirmações é elementar.
=== Aplicação ===
A partir dessa notação pode-se definir uma função <math>v_p:\mathbb{N}\rightarrow\mathbb{N}
Verifica-se que a função acima definida goza das seguintes propriedades:
# <math>v_p(m\cdot n) = v_p(m) + v_p(n)
# <math>v_p(m + n) \ge 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 <math>\sqrt{2}
{{Demonstração
|Se <math>\sqrt{2}
Neste caso, seria verdade que <math> \left(\frac{a}{b}\right)^2=2
Aplicando a função <math>v_2
:<math>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, <math>\sqrt{2}
}}
Linha 385:
A resposta é afirmativa, e o motivo você encontrará nesta seção. Veja:
{{Demonstração
|Suponha que <math>p|ab
Mas <math>a
:<math>a = p_1\cdot\ldots\cdot p_r
:<math>b = q_1\cdot\ldots\cdot q_s
Logo, <math>px = ab = (p_1\cdot\ldots\cdot p_r) \cdot (q_1\cdot\ldots\cdot q_s)
No primeiro caso, conclui-se que <math>p|a
}}
== Exercícios ==
# Demonstre os seguintes fatos:
## Se <math>p=6k+r
## O produto de dois elementos quaisquer do conjunto <math>\{ 6k+1: k\in \mathbb{Z}\}
## O conjunto <math>\{ 6k+5: k\in \mathbb{Z}\}
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.
|