Teorema fundamental da aritmética - Fundamental theorem of arithmetic
Na teoria dos números , o teorema fundamental da aritmética , também chamado de teorema da fatoração única , afirma que todo número inteiro maior que 1 pode ser representado exclusivamente como um produto de números primos, até a ordem dos fatores. Por exemplo,
O teorema diz duas coisas sobre este exemplo: primeiro, que 1200 pode ser representado como um produto de primos e, segundo, que não importa como isso seja feito, sempre haverá exatamente quatro 2s, um 3, dois 5s e nenhum outro primos no produto.
O requisito de que os fatores sejam primos é necessário: as fatorações contendo números compostos podem não ser únicas (por exemplo, ).
Este teorema é uma das principais razões pelas quais 1 não é considerado um número primo : se 1 fosse primo, então a fatoração em primos não seria única; por exemplo,
Versão original de Euclides
Livro VII, proposições 30, 31 e 32, e livro IX, proposição 14 de Euclides 's Elements são essencialmente a declaração e prova do teorema fundamental.
Se dois números multiplicados um pelo outro formarem algum número, e qualquer número primo medir o produto, ele também medirá um dos números originais.
- Euclides, Livro dos Elementos VII , Proposição 30
(Na terminologia moderna: se um p primo divide o produto ab , então p divide a ou b ou ambos.) A proposição 30 é chamada de lema de Euclides e é a chave na prova do teorema fundamental da aritmética.
Qualquer número composto é medido por algum número primo.
- Euclides, Livro dos Elementos VII , Proposição 31
(Na terminologia moderna: todo número inteiro maior que um é dividido igualmente por algum número primo.) A proposição 31 é provada diretamente por descendência infinita .
Qualquer número é primo ou medido por algum número primo.
- Euclides, Livro dos Elementos VII , Proposição 32
A proposição 32 é derivada da proposição 31 e prova que a decomposição é possível.
Se um número for o menor medido por números primos, ele não será medido por nenhum outro número primo, exceto aqueles que o mediram originalmente.
- Euclides, Livro dos Elementos IX , Proposição 14
(Na terminologia moderna: um mínimo múltiplo comum de vários números primos não é um múltiplo de qualquer outro número primo.) Livro IX, proposição 14 é derivado do Livro VII, proposição 30, e prova parcialmente que a decomposição é única - um ponto criticamente anotado por André Weil . De fato, nesta proposição os expoentes são todos iguais a um, então nada é dito para o caso geral.
O artigo 16 do Gauss ' Disquisitiones Arithmeticae é uma indicação moderna cedo e prova empregando aritmética modular .
Formulários
Representação canônica de um número inteiro positivo
Cada número inteiro positivo n > 1 pode ser representado exatamente de uma maneira como um produto de potências primárias:
onde p 1 < p 2 <... < p k são primos e n i são inteiros positivos. Essa representação é comumente estendida a todos os inteiros positivos, incluindo 1, pela convenção de que o produto vazio é igual a 1 (o produto vazio corresponde a k = 0).
Essa representação é chamada de representação canônica de n ou forma padrão de n . Por exemplo,
- 999 = 3 3 × 37,
- 1000 = 2 3 × 5 3 ,
- 1001 = 7 × 11 × 13.
Os fatores p 0 = 1 podem ser inseridos sem alterar o valor de n (por exemplo, 1000 = 2 3 × 3 0 × 5 3 ). Na verdade, qualquer número inteiro positivo pode ser representado exclusivamente como um produto infinito obtido sobre todos os números primos positivos:
onde um número finito de n i são inteiros positivos e os demais são zero. Permitir expoentes negativos fornece uma forma canônica para números racionais positivos .
Operaçoes aritimeticas
As representações canónicos do produto, maior divisor comum (MDC), e menos múltiplo comum (LCM) de dois números um e b pode ser expressa simplesmente em termos das representações canónicas de um e b -se:
No entanto, a fatoração de inteiros , especialmente de grandes números, é muito mais difícil do que produtos de computação, GCDs ou LCMs. Portanto, essas fórmulas têm uso limitado na prática.
Funções aritméticas
Muitas funções aritméticas são definidas usando a representação canônica. Em particular, os valores das funções aditivas e multiplicativas são determinados por seus valores nas potências dos números primos.
Prova
A prova usa o lema de Euclides ( Elementos VII, 30): Se um primo divide o produto de dois inteiros, então ele deve dividir pelo menos um desses inteiros.
Existência
Deve ser mostrado que todo número inteiro maior que 1 é primo ou um produto de primos. Primeiro, 2 é primo. Então, por indução forte , assuma que isso é verdadeiro para todos os números maiores que 1 e menores que n . Se n for primo, não há mais nada a provar. Caso contrário, não são inteiros um e b , em que n = AB , e um < um ≤ b < n . Por hipótese de indução, um = p 1 p 2 ⋅⋅⋅ p j e b = q 1 q 2 ⋅⋅⋅ q k são produtos de números primos. Mas então n = ab = p 1 p 2 ⋅⋅⋅ p j q 1 q 2 ⋅⋅⋅ q k é um produto de primos.
Singularidade
Suponha, ao contrário, que haja um inteiro que tem duas fatorações principais distintas. Deixe n ser o número inteiro e pelo menos tal gravação n = p 1 p 2 ... p j = Q 1 Q 2 ... q k , em que cada p i e q i é primo. Vemos que p 1 divide q 1 q 2 ... q k , então p 1 divide algum q i pelo lema de Euclides . Sem perda de generalidade, digamos que p 1 divide q 1 . Dado que p 1 e q 1 são primos, segue-se que p 1 = q 1 . Voltando às nossas fatorações de n , podemos cancelar esses dois fatores para concluir que p 2 ... p j = q 2 ... q k . Agora temos duas fatorações principais distintas de algum inteiro estritamente menor que n , o que contradiz a minimalidade de n .
Singularidade sem o lema de Euclides
O teorema fundamental da aritmética também pode ser provado sem usar o lema de Euclides. A prova a seguir é inspirada na versão original de Euclides do algoritmo euclidiano .
Suponha que seja o menor inteiro positivo que é o produto de números primos de duas maneiras diferentes. A propósito, isso implica que , se existir, deve ser um número composto maior que . Agora diga
Cada deve ser distinto de todos os Caso contrário, se digamos então não existiria algum inteiro positivo que é menor do que s e tem dois fatorações principais distintos. Pode-se também supor que , trocando as duas fatorações, se necessário.
Ambiente e um tem, segue-se que
Como os inteiros positivos menos do que s foram suposto ter um primeiro-factorização única, deve ocorrer na fatoração de qualquer um ou Q . O último caso é impossível, como Q , sendo menor do que s , deve ter um primeiro-factorização única, e difere de todos os do primeiro caso também é impossível, como, se é um divisor de ele deve ser também um divisor de que é impossível como e são primos distintos.
Portanto, não pode existir um menor inteiro com mais de uma única fatoração primo distinta. Todo número inteiro positivo deve ser um número primo, que seria fatorado exclusivamente, ou um composto que também fatore exclusivamente em primos ou, no caso do inteiro , não fatore em nenhum primo.
Generalizações
A primeira generalização do teorema é encontrada na segunda monografia de Gauss (1832) sobre reciprocidade biquadrática . Este artigo introduziu o que hoje é chamado de anel de inteiros de Gauss , o conjunto de todos os números complexos a + bi , onde a e b são inteiros. É agora denotado por Ele mostrou que este anel tem as quatro unidades ± 1 e ± i , que os números não-zero e não-unitários caem em duas classes, primos e compostos, e que (exceto para a ordem), os compostos têm fatoração única como um produto de primos.
Da mesma forma, em 1844, enquanto trabalhava na reciprocidade cúbica , Eisenstein introduziu o anel , onde é uma raiz cúbica da unidade . Este é o anel dos inteiros de Eisenstein , e ele provou que tem as seis unidades e que tem fatoração única.
No entanto, também foi descoberto que a fatoração única nem sempre é válida. Um exemplo é dado por . Neste anel um tem
Exemplos como esse fizeram com que a noção de "primo" fosse modificada. Em que pode ser comprovado que, se qualquer um dos factores acima referidos pode ser representada como um produto, por exemplo, 2 = ab , em seguida, uma de um ou b deve ser uma unidade. Esta é a definição tradicional de "primo". Também pode ser provado que nenhum desses fatores obedece ao lema de Euclides; por exemplo, 2 não divide nem (1 + √ −5 ) nem (1 - √ −5 ), embora divida seu produto 6. Na teoria algébrica dos números 2 é chamado de irredutível em (apenas divisível por si mesmo ou uma unidade), mas não primo em (se divide um produto, deve dividir um dos fatores). A menção de é necessária porque 2 é primo e irredutível. Usando essas definições, pode ser provado que em qualquer domínio integral um primo deve ser irredutível. O lema clássico de Euclides pode ser reformulado como "no anel dos inteiros todo irredutível é primo". Isso também é verdade em e mas não em
Os anéis nos quais a fatoração em irredutíveis é essencialmente única são chamados de domínios únicos de fatoração . Exemplos importantes são anéis polinomiais sobre inteiros ou sobre um campo , domínios euclidianos e domínios ideais principais .
Em 1843, Kummer introduziu o conceito de número ideal , que foi desenvolvido posteriormente por Dedekind (1876) na teoria moderna de ideais , subconjuntos especiais de anéis. A multiplicação é definida para ideais, e os anéis nos quais eles têm fatoração única são chamados de domínios de Dedekind .
Existe uma versão de fatoração única para ordinais , embora exija algumas condições adicionais para garantir a exclusividade.
Veja também
- Fatoração de inteiros - Decomposição de um inteiro em um produto
- Assinatura principal - Multiset de expoentes principais em uma fatoração principal
Notas
Referências
O Disquisitiones Arithmeticae foi traduzido do latim para o inglês e o alemão. A edição alemã inclui todos os seus artigos sobre a teoria dos números: todas as provas de reciprocidade quadrática, a determinação do sinal da soma de Gauss, as investigações sobre a reciprocidade biquadrática e notas não publicadas.
- Gauss, Carl Friedrich; Clarke, Arthur A. (tradutor para o inglês) (1986), Disquisitiones Arithemeticae (Segunda, edição corrigida) , Nova York: Springer , ISBN 978-0-387-96254-2
- Gauss, Carl Friedrich; Maser, H. (tradutor para o alemão) (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition) , New York: Chelsea, ISBN 0-8284-0191-8
As duas monografias que Gauss publicou sobre reciprocidade biquadrática têm seções numeradas consecutivamente: a primeira contém os §§ 1–23 e a segunda os §§ 24–76. As notas de rodapé que as fazem referência têm a forma "Gauss, BQ, § n ". As notas de rodapé que fazem referência às Disquisitiones Arithmeticae são da forma "Gauss, DA, Art. N ".
- Gauss, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima , Göttingen: Comment. Soc. regiae sci, Göttingen 6
- Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda , Göttingen: Comment. Soc. regiae sci, Göttingen 7
Estes estão em Werke de Gauss , Vol II, pp. 65-92 e 93-148; As traduções para o alemão estão nas páginas 511-533 e 534-586 da edição alemã das Disquisitiones .
- Baker, Alan (1984), Uma introdução concisa à teoria dos números , Cambridge, Reino Unido: Cambridge University Press, ISBN 978-0-521-28654-1
- Euclid (1956), Os treze livros dos Elementos , 2 (Livros III-IX), Traduzido por Thomas Little Heath (Second Edition Unabridged ed.), New York: Dover , ISBN 978-0-486-60089-5
- Hardy, GH ; Wright, EM (2008) [1938]. Uma introdução à teoria dos números . Revisado por DR Heath-Brown e JH Silverman . Prefácio de Andrew Wiles . (6ª ed.). Oxford: Oxford University Press . ISBN 978-0-19-921986-5. MR 2445243 . Zbl 1159.11001 .
- A. Kornilowicz; P. Rudnicki (2004), "Fundamental teorema of arithmetic", Formalized Mathematics , 12 (2): 179-185
- Long, Calvin T. (1972), Elementary Introduction to Number Theory (2ª ed.), Lexington: DC Heath and Company , LCCN 77-171950.
- Pettofrezzo, Anthony J .; Byrkit, Donald R. (1970), Elements of Number Theory , Englewood Cliffs: Prentice Hall , LCCN 77-81766.
- Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (segunda edição) , Boston: Birkhäuser, ISBN 0-8176-3743-5
- Weil, André (2007) [1984]. Teoria dos números: uma abordagem através da história de Hammurapi a Legendre . Clássicos modernos da Birkhäuser. Boston, MA: Birkhäuser. ISBN 978-0-817-64565-6.
- Weisstein, Eric W. "Número anormal" . MathWorld .
- Weisstein, Eric W. "Fundamental Theorem of Arithmetic" . MathWorld .
links externos
- Por que o teorema fundamental da aritmética não é óbvio?
- GCD e o Teorema Fundamental da Aritmética no corte do nó .
- PlanetMath: Prova do teorema fundamental da aritmética
- Blog do Último Teorema de Fermat: Fatoração Única , um blog que cobre a história do Último Teorema de Fermat de Diofanto de Alexandria à prova de Andrew Wiles .
- "Fundamental Theorem of Arithmetic" por Hector Zenil, Wolfram Demonstrations Project , 2007.
- Sujeira, James. "1 e números primos" . Numberphile . Brady Haran .