Fator primo

Predefinição:Mais notas Predefinição:Reciclagem 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.

Predefinição:ÂncoraFunções Omega

A função Predefinição:Math representa o número de fatores primos distintos de n, enquanto a função Predefinição:Math (Omega maiúscula) representa o número total de fatores primos de Predefinição:Math.

se

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

então

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

Por exemplo, Predefinição:Math,

então

e

• Predefinição:Math para Predefinição:Math = 1, 2, 3, ... é, respectivamente, 0, 1, 1, 1, 1, 2, 1, 1, 1, ... Predefinição:OEIS.
• Predefinição:Math para Predefinição:Math = 1, 2, 3, ... é, respectivamente, 0, 1, 1, 2, 1, 2, 1, 3, 2, ... Predefinição: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