Come si scompone un numero
Si divide il numero per il più piccolo primo che lo divide (2, poi 3, 5, 7…) e si ripete sul quoziente finché si arriva a 1. I divisori usati sono i fattori primi.
Per 5.040:
5.040 ÷ 2 = 2.520 → ÷ 2 = 1.260 → ÷ 2 = 630 → ÷ 2 = 315 → ÷ 3 = 105 → ÷ 3 = 35 → ÷ 5 = 7 → ÷ 7 = 1
Quindi 5.040 = 2⁴ × 3² × 5 × 7.
A cosa serve
La scomposizione è la base per calcolare MCD e mcm, semplificare frazioni e radici e contare i divisori. Sulla difficoltà di scomporre numeri con centinaia di cifre si basa la sicurezza di sistemi di crittografia come RSA.
Domande frequenti
Ogni numero ha una sola scomposizione in fattori primi?
Sì: è il teorema fondamentale dell'aritmetica. Ogni intero maggiore di 1 si scrive in un solo modo come prodotto di numeri primi, a meno dell'ordine dei fattori.
Come fa il calcolatore con i numeri molto grandi?
Prova prima i divisori piccoli, poi verifica se ciò che resta è primo con il test di Miller-Rabin e, se non lo è, cerca un fattore con l'algoritmo rho di Pollard. Così scompone in un attimo qualsiasi numero fino a 20 cifre.
Fonti
- Euclide, Elementi, libro IX, proposizione 14 (unicità della scomposizione) e libro IX, proposizione 20 (infinità dei primi)
- Pollard JM. A Monte Carlo method for factorization. BIT Numerical Mathematics, 1975