Fator primo

Origem: Wikipédia, a enciclopédia livre.

Em teoria dos números, os fatores primos de um inteiro positivo são os números primos que dividem esse inteiro exatamente.[1]

A fatoração prima de um número inteiro positivo é uma lista dos fatores primos cujo produto resulta no inteiro, juntamente com suas multiplicidades; o processo de determinação desses fatores é chamado de fatoração de inteiros. O teorema fundamental da aritmética , diz que cada número inteiro positivo tem uma única fatoração prima.[2]

Para encurtar a fatoração prima, os fatores são muitas vezes expressos em potências (multiplicidades). Por exemplo,

em que os fatores 2, 3 e 5, tem multiplicidades 3, 2 e 1, respectivamente.

Para um factor primo p de n, a multiplicidade de p é o maior expoente para o qual pa divide n exatamente.

Para um inteiro positivo n, o número de fatores primos de n e a soma dos fatores primos de n (sem contar a multiplicidade) são exemplos de funções aritméticas de n que são aditivas , mas não completamente aditivas.[3]

Quadrados perfeitos[editar | editar código-fonte]

Quadrados perfeitos podem ser reconhecidos pelo fato de que todos os seus fatores primos têm multiplicidade par. Por exemplo, o número 144 (o quadrado de 12) tem os seguintes fatores primos

Estes podem ser reorganizados para tornar o padrão mais visível:

Como cada fator primo aparece um número par de vezes, o número original pode ser expresso como o quadrado de algum número menor. Da mesma forma, cubos perfeitos terão fatores primos cujas multiplicidades são múltiplos de três, e assim por diante.

Números inteiros primos entre si[editar | editar código-fonte]

Números inteiros positivos sem fatores primos em comum são ditos primos entre si (coprimos). Dois inteiros a e b também podem ser definidos como primos entre si se o seu máximo divisor comum mdc(a, b) = 1. O algoritmo de Euclides pode ser usado para determinar se dois números inteiros são primos entre si sem conhecer seus fatores primos; o algoritmo é executado em um tempo em que é polinomial no número de dígitos envolvidos.

O número inteiro 1 é coprimo para todo inteiro positivo, incluindo ele mesmo. Isso decorre do fato de ele não ter fatores primos, é o produto vazio. Isto implica mdc(1, b) = 1 para qualquer b ≥ 1.

Aplicativos de criptografia[editar | editar código-fonte]

Determinar os fatores primos de um número é um exemplo de um problema freqüentemente usado para garantir a segurança de criptografia em criptografia de sistemas;[4] acredita-se que esse problema requer um tempo super-polinomial no número de dígitos — é relativamente fácil construir um problema que levaria mais tempo do que o conhecido da idade do universo para resolver usando algoritmos em computadores atuais.

Funções Omega[editar | editar código-fonte]

A função ω(n) representa o número de fatores primos distintos de n, enquanto a função Ω(n) (Omega maiúscula) representa o número total de fatores primos de n.[2]

se

,

então

Por exemplo, 24 = 23 × 31,

então

ω(24) = 2

e

Ω(24) = 3 + 1 = 4

  • ω(n) para n = 1, 2, 3, ... é, respectivamente, 0, 1, 1, 1, 1, 2, 1, 1, 1, ... (sequência A001221 na OEIS).
  • Ω(n) para n = 1, 2, 3, ... é, respectivamente, 0, 1, 1, 2, 1, 2, 1, 3, 2, ... (sequência A001222 na OEIS).

Veja também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. Jensen, Gary R. (2004). Arithmetic for Teachers: With Applications and Topics from Geometry. [S.l.]: American Mathematical Society 
  2. a b Riesel, Hans (1994), Prime numbers and computer methods for factorization, ISBN 978-0-8176-3743-9, Basel, Switzerland: Birkhäuser 
  3. Melvyn B. Nathanson (1996). Additive Number Theory: the Classical Bases. Col: Graduate Texts in Mathematics. 234. [S.l.]: Springer-Verlag. ISBN 0-387-94656-X 
  4. Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. (outubro de 1996). Handbook of Applied Cryptography. [S.l.]: CRC Press. ISBN 0-8493-8523-7