Scomposizione in fattori primi

Come funziona il metodo delle divisioni successive

Si divide il numero per il più piccolo numero primo che lo divide esattamente (2, poi 3, 5, 7, 11…) e si ripete l'operazione sul quoziente, finché non si arriva a 1. I divisori usati lungo la strada sono i fattori primi. Per 360, ad esempio: si divide tre volte per 2 (360 → 180 → 90 → 45), due volte per 3 (45 → 15 → 5) e una volta per 5, quindi 360 = 2³ × 3² × 5.

A cosa serve la scomposizione in fattori primi

È la base per calcolare MCD e mcm: il massimo comune divisore si ottiene moltiplicando i fattori comuni presi con l'esponente più piccolo, il minimo comune multiplo prendendo fattori comuni e non comuni con l'esponente più grande. Serve anche per semplificare le frazioni ai minimi termini e per contare i divisori di un numero (si aggiunge 1 a ogni esponente e si moltiplica). Curiosità: la difficoltà di scomporre numeri enormi è ciò che tiene al sicuro la crittografia RSA usata da banche e siti web.

Perché ogni numero ha una sola scomposizione

È il teorema fondamentale dell'aritmetica: ogni numero intero maggiore di 1 si scrive come prodotto di numeri primi in un modo solo, a meno dell'ordine. Non è ovvio e va dimostrato, ma è la ragione per cui la scomposizione è una carta d'identità del numero.

Da qui viene l'utilità pratica: due numeri si confrontano guardando i loro fattori invece dei loro valori. Il massimo comune divisore prende i fattori comuni con l'esponente più piccolo, il minimo comune multiplo tutti i fattori con l'esponente più grande, e nessuna delle due operazioni richiede di provare i divisori uno per uno.

Ci si ferma alla radice quadrata

Per sapere se un numero è primo non serve provare tutti i divisori fino a lui: basta arrivare alla sua radice quadrata. Se un numero ha un divisore più grande della radice, ne ha per forza anche uno più piccolo, ed è quello che si trova prima.

È il motivo per cui verificare che 9.973 sia primo richiede meno di venticinque tentativi e non diecimila: si provano solo i primi fino a 99. Nella scomposizione lo stesso principio dice quando fermarsi: quando il quoziente rimasto è più piccolo del quadrato del divisore in corso, quel quoziente è primo.

Il numero facile da moltiplicare e difficile da spezzare

Moltiplicare due numeri primi grandi è istantaneo; ritrovare i due fattori dal prodotto è difficilissimo, e nessuno sa farlo in fretta su numeri di centinaia di cifre. È su questa asimmetria che si regge la crittografia RSA, cioè buona parte della sicurezza di internet.

Per i numeri piccoli, invece, la scomposizione è immediata e serve tutti i giorni: semplificare una frazione, trovare il denominatore comune, capire se una radice si può portare fuori. È lo stesso strumento a due scale completamente diverse.

Strumenti vicini

Per il massimo comune divisore e il minimo comune multiplo c'è Calcolo MCD e mcm, e per ridurre una frazione Semplifica frazioni. Se il numero è grande, guarda Numeri primi.