Fatoração em Primos
Decomponha qualquer número inteiro em seus fatores primos com a árvore de fatoração completa. Útil para MMC, MDC e álgebra.
O que é Fatoração em Primos?
A fatoracao em numeros primos (decomposicao em fatores primos) e o processo de escrever qualquer numero inteiro maior que 1 como produto de numeros primos. Um numero primo e aquele divisivel apenas por 1 e por ele mesmo. Exemplos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Todo numero composto tem uma fatoracao prima unica (Teorema Fundamental da Aritmetica).
Algoritmo de fatoracao: divida o numero pelo menor primo possivel (comecando por 2); continue dividindo o quociente pelos primos em ordem crescente ate que o quociente seja 1. Exemplo: 360 = 2 x 180 = 2 x 2 x 90 = 2 x 2 x 2 x 45 = 2 x 2 x 2 x 3 x 15 = 2 x 2 x 2 x 3 x 3 x 5 = 2^3 x 3^2 x 5. Aplicacoes fundamentais: calculo de MMC e MDC (fundamentais para frações e teoria dos numeros); criptografia RSA (baseia-se na dificuldade de fatorar numeros muito grandes, com centenas de digitos); e teoria computacional dos numeros.
Como calcular?
Para fatorar um número em primos, divida-o pelo menor primo possível (começando pelo 2) e continue dividindo o quociente pelo menor primo que o divide, até chegar ao quociente 1. Organize as divisões em uma coluna: à esquerda os quocientes e à direita os divisores primos. O resultado é o produto de todos os divisores primos utilizados, cada um elevado ao número de vezes que aparece. Teste sempre os primos na ordem crescente: 2, 3, 5, 7, 11, 13 e assim por diante.
Fórmula
N = p₁^a₁ × p₂^a₂ × ... × pₙ^aₙ (onde p são primos e a são expoentes)Exemplo prático
Fatore o número 360 em fatores primos: 360 ÷ 2 = 180 180 ÷ 2 = 90 90 ÷ 2 = 45 45 ÷ 3 = 15 15 ÷ 3 = 5 5 ÷ 5 = 1 Portanto, 360 = 2³ × 3² × 5¹ = 2 × 2 × 2 × 3 × 3 × 5.
Perguntas Frequentes
Como fatorar um numero em primos passo a passo?
Metodo da divisao sucessiva (arvore de fatores): Exemplo: fatorar 252. 252 / 2 = 126; 126 / 2 = 63; 63 / 3 = 21; 21 / 3 = 7; 7 / 7 = 1. Resultado: 252 = 2^2 x 3^2 x 7. Verificacao: 4 x 9 x 7 = 252. Para numeros maiores: teste divisibilidade por primos em ordem (2, 3, 5, 7, 11, 13...) ate que o quociente seja 1 ou um primo. Regras de divisibilidade: por 2 (termina em numero par); por 3 (soma dos digitos divisivel por 3); por 5 (termina em 0 ou 5).
O que e um numero primo?
Um numero primo e divisivel apenas por 1 e por si mesmo (sem outros divisores). Os 25 primos abaixo de 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. O numero 1 NAO e primo (por definicao matematica). O numero 2 e o unico primo par. Para verificar se um numero N e primo: teste divisibilidade por todos os primos ate a raiz quadrada de N. Existem infinitos numeros primos (demonstrado por Euclides, 300 a.C.).
Como a fatoracao e usada para calcular MMC e MDC?
MDC: produto dos fatores comuns com MENOR expoente. MMC: produto de TODOS os fatores com MAIOR expoente. Exemplo: 12 e 18. 12 = 2^2 x 3; 18 = 2 x 3^2. MDC = 2^1 x 3^1 = 6 (fatores comuns com menor expoente). MMC = 2^2 x 3^2 = 36 (todos os fatores com maior expoente). Verificacao: MDC x MMC = 6 x 36 = 216 = 12 x 18. Para tres ou mais numeros: o processo e o mesmo, usando todos os fatores dos numeros.
A fatoracao prima tem aplicacoes na criptografia?
Sim! A criptografia RSA (usada em HTTPS, cartoes de credito, assinaturas digitais) baseia-se no problema da fatoracao: e facil multiplicar dois primos grandes (ex: p x q onde p e q tem 300 digitos cada), mas computacionalmente inviavel fatorar o produto (mesmo com os supercomputadores mais rapidos). Chave publica RSA = n (produto de dois primos); chave privada = os fatores. A seguranca se baseia no tempo de fatoracao que levaria bilhoes de anos. Computadores quanticos podem um dia quebrar esse sistema.
O que e o crivo de Eratostenes?
O crivo de Eratostenes e um algoritmo antigo (300 a.C.) para encontrar todos os primos ate um limite N. Algoritmo: escreva todos os numeros de 2 a N; marque 2 como primo e risque todos os seus multiplos; vance para o proximo nao riscado (3) e risque seus multiplos; repita ate raiz(N). Os numeros nao riscados sao todos os primos ate N. Para encontrar primos ate 100: começa riscando multiplos de 2, 3, 5 e 7 (primos ate sqrt(100)=10). Muito eficiente para primos pequenos; para numeros muito grandes, usa-se o teste de Miller-Rabin.
Todo numero e divisivel por algum primo?
Sim! Todo inteiro N > 1 e divisivel por algum numero primo (pelo menos por ele mesmo, se for primo). Isso decorre do Teorema Fundamental da Aritmetica: todo inteiro N > 1 pode ser escrito de forma unica como produto de primos (a fatoracao prima e unica, exceto pela ordem dos fatores). Exemplos: 2 = 2 (primo); 4 = 2^2; 100 = 2^2 x 5^2; 1.000 = 2^3 x 5^3. Numeros com fatoracao prima 'bonita' (poucos fatores, pequenos expoentes) facilitam calculos de MMC, MDC e divisibilidade.