Fatoração em números primos

Como funciona o método das divisões sucessivas

Divida o número pelo menor primo que o divide exatamente (2, depois 3, 5, 7, 11…) e repita a operação com o quociente até chegar a 1. Os divisores usados no caminho são os fatores primos. Veja o 360, por exemplo: divida por 2 três vezes (360 → 180 → 90 → 45), por 3 duas vezes (45 → 15 → 5) e por 5 uma vez, e então 360 = 2³ × 3² × 5.

Para que serve a fatoração em primos

É a base para encontrar o MDC e o MMC: o máximo divisor comum sai da multiplicação dos fatores primos comuns com o menor expoente, enquanto o mínimo múltiplo comum pega os fatores comuns e não comuns com o maior expoente. É também assim que você simplifica frações e conta os divisores de um número (some 1 a cada expoente e multiplique). Curiosidade: a enorme dificuldade de fatorar números gigantescos é o que mantém segura a criptografia RSA, usada por bancos e sites.

Por que cada número tem uma única fatoração

É o teorema fundamental da aritmética: todo número inteiro maior que 1 pode ser escrito como produto de números primos de uma única maneira, sem contar a ordem dos fatores. Não é óbvio e precisa ser demonstrado, mas é a razão pela qual a fatoração funciona como a carteira de identidade do número.

A utilidade prática decorre daí: dois números são comparados olhando para os fatores em vez dos valores. O máximo divisor comum pega os fatores comuns com o menor expoente, o mínimo múltiplo comum pega todos os fatores com o maior expoente, e nenhuma das duas operações exige testar os divisores um a um.

Você para na raiz quadrada

Para saber se um número é primo, você não precisa testar todos os divisores até ele: basta chegar à sua raiz quadrada. Se um número tem um divisor maior que a raiz, ele necessariamente tem também um menor, e esse é o que você encontra primeiro.

É por isso que conferir que 9.973 é primo leva menos de vinte e cinco tentativas e não dez mil: você só testa os primos até 99. Na fatoração, o mesmo princípio diz quando parar: quando o quociente restante é menor que o quadrado do divisor atual, esse quociente é primo.

O número fácil de multiplicar e difícil de quebrar

Multiplicar dois números primos grandes é instantâneo; recuperar os dois fatores a partir do produto é dificílimo, e ninguém sabe fazer isso rápido com números de centenas de dígitos. A criptografia RSA, e portanto boa parte da segurança da internet, se apoia nessa assimetria.

Para números pequenos, por outro lado, a fatoração é imediata e útil todo dia: simplificar uma fração, encontrar o denominador comum, ver se uma raiz pode ser tirada para fora. É a mesma ferramenta em duas escalas completamente diferentes.

Veja também

Para o máximo divisor comum e o mínimo múltiplo comum, existe a Calculadora de MDC e MMC, e para reduzir uma fração, use Simplificar frações. Se o número for grande, veja Números primos.