Fator primo

número primo que divide um inteiro dado
(Redirecionado de Fatores primos)

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 perfeitosEditar

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 siEditar

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 criptografiaEditar

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 OmegaEditar

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émEditar

ReferênciasEditar

  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