Fator primo

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (Encontre fontes: ABW  • CAPES  • Google (notícias • livros • acadêmico)). (Janeiro de 2022)

Este artigo carece de reciclagem de acordo com o livro de estilo. Sinta-se livre para editá-lo(a) para que este(a) possa atingir um nível de qualidade superior. (Janeiro de 2022)

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,

${\displaystyle 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.^[3]

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

${\displaystyle 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:

${\displaystyle 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 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.

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.

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

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

então

${\displaystyle \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).

• 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