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
- 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1} possui pelo menos dois divisores: e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.
Teorema da existência de fatoração
- Teorema
Todo número inteiro positivo maior do que um tem decomposição em fatores primos.
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:
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 12=2^2\cdot 3}
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1234=2\cdot 617}
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1234567=127\cdot 9721}
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 12345678=2\cdot 3^2\cdot 47\cdot 14593}
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 123456789=3^2\cdot 3607\cdot 3803}
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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}} 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
Considere o conjunto .
Quem são os elementos que permitem "gerar" todos os demais através da multiplicação? Acompanhe:
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | ... |
---|---|---|---|---|---|---|---|---|---|---|
fatoração de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} | 2 | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\cdot 2} | 6 | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\cdot 2\cdot 2} | 10 | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\cdot 6} | 14 | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\cdot 2\cdot 2\cdot 2} | 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\mathbb{Z}} . De modo geral, um elemento Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} é um elemento redutível de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\mathbb{Z}} , então Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=2p\cdot 2q = 4\cdot pq} , ou seja, todo elemento redutível é um múltiplo de 4.
Os elementos irredutíveis de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\mathbb{Z}} 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\mathbb{Z}} possui uma decomposição em fatores irredutíveis. Predefinição:Prova
Uma última consideração a respeito do conjunto Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\mathbb{Z}} (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:
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 60 = 2 \cdot 30 = 6 \cdot 10}
E como se verifica facilmente, os números acima são todos irredutíveis em Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}} , além de sua estrutura multiplicativa.
O monóide de Hilbert
Seja Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} possui as seguintes propriedades:
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\cdot b \in H } , quaisquer que sejam Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a,b \in H } ;
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(a\cdot b\right)\cdot c = a\cdot \left(b\cdot c\right) = a\cdot b\cdot c } , para quaisquer Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a,b,c \in H } ;
- O elemento neutro da multiplicação, o número inteiro 1, está em Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} .
Este conjunto Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} é conhecido como o monóide de Hilbert.
A propriedade 1 decorre dos seguintes cálculos: Se Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=4n+1} e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle b=4m+1} então
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} ). Acompanhe a fatoração de alguns elementos de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} :
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} | 1 | 5 | 9 | 13 | 17 | 21 | 25 | 29 | ... | 45 | ... | 65 | ... | 117 | ... |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
fatoração de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} | 1 | 5 | 9 | 13 | 17 | 21 | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5\cdot 5} | 29 | ... | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5\cdot 9} | ... | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5\cdot 13} | ... | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 9\cdot 13} | ... |
Outros monóides
É possível obter outros exemplos similares procedendo de forma análoga com os conjuntos Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ an+1: n\in \mathbb{N} \}} , e em alguns casos com Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ an+b: n, a, b \in \mathbb{N} \}} (para quais Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a, b} ainda funciona?). Também o conjunto Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ x^2 + y^2: x,y \in \mathbb{N}\}} possui essas propriedades.
Teorema de Euclides
- Teorema
Existe uma infinidade de números primos.
Demonstração de Euclides
Exemplos
Se o conjunto Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} que aparece na demonstração do teorema for constituído dos primeiros Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} números primos, então as fatorações de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 2 \cdot 3 \cdot \ldots \cdot p_r + 1} para alguns valores de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} são as seguintes:
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 2 \cdot 3 \cdot \ldots \cdot p_r + 1} | Fatoração de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} | Tipo |
---|---|---|---|
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3 = 2+1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3} | primo |
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 7 = 2\cdot3 +1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 7} | primo |
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 31 = 2\cdot3\cdot5 +1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 31} | primo |
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 211 = 2\cdot3\cdot5\cdot7 +1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 211} | primo |
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2311 = 2\cdot3\cdot5\cdot7\cdot11 +1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2311} | primo |
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 30031 = 2\cdot3\cdot5\cdot7\cdot11\cdot13 +1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 59\cdot509} | composto |
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 7} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 510511 = 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17 +1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 19\cdot97\cdot277} | composto |
A demonstração acima pode ser adaptada para mostrar que o monóide de Hilbert Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} possui infinitos elementos irredutíveis. Observe: Predefinição:Demonstração
- Observação
Não serve escolher Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = b_1, \ldots, b_r + 1 } . Por que?
Demonstração de Hermite
Esta demonstração, assim como algumas outras, é uma variante daquela dada por Euclides. Acompanhe: Predefinição:Demonstração
Exemplos
Uma tabela como a anterior pode ser feita para os números Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x(n)} . Neste caso, tem-se:
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x(n) = n!+1} | Fatoração de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x(n)} | Tipo |
---|---|---|---|
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2 = 1+1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2} | primo |
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3 = 1\cdot2+1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3} | primo |
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 7 = 1\cdot2\cdot3+1} | Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 7} | primo |
composto | |||
Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5} | 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
Exemplos
Tomando , obtem-se a seguinte tabela:
Fatoração de | ||
---|---|---|
Teorema fundamental da aritmética
- 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
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.
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:
Essa função oferece uma forma "elegante" de se fazer certas demonstrações. Por exemplo, a irracionalidade de é provada assim: Predefinição:Demonstração
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: Predefinição:Demonstração
Exercícios
- Demonstre os seguintes fatos:
- Se (com ) for um número primo maior do que , então ou .
- O produto de dois elementos quaisquer do conjunto é ainda um elemento deste conjunto.
- 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.