Fator primo

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

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.

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

$360=2\times 2\times 2\times 3\times 3\times 5=2^{3}\times 3^{2}\times 5,$

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 a para o qual p^a 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.

Quadrados perfeitos

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

$144=2\times 2\times 2\times 2\times 3\times 3=2^{4}\times 3^{2}.$

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

$144=2\times 2\times 2\times 2\times 3\times 3=(2\times 2\times 3)\times (2\times 2\times 3)=(2\times 2\times 3)^{2}=(12)^{2}.$

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

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

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; 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

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.

se

$n=\prod _{i=1}^{\omega (n)}p_{i}^{\alpha _{i}},$,

então

$\Omega (n)=\sum _{i=1}^{\omega (n)}\alpha _{i}.$

Por exemplo, 24 = 2³ × 3¹,

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

• Número composto
• Divisor
• Tabela de fatores primos
• Crivo de Eratóstenes
• Erdős–Kac teorema
• Ω(n), ω(n), vp(n) – decomposição de potências de primos