Interpretare il risultato della scomposizione
La tabella seguente riporta la scomposizione di alcuni numeri familiari, così da chiarire il funzionamento della notazione esponenziale.
| Numero | Scomposizione in fattori primi | Numero di divisori |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 100 | 2² × 5² | 9 |
| 360 | 2³ × 3² × 5 | 24 |
| 17 (numero primo) | 17 (sé stesso, esponente 1) | 2 |
| 1024 | 2¹⁰ | 11 |
- La scomposizione di un numero primo coincide con il numero stesso elevato a esponente 1, e i divisori sono sempre esattamente 2: 1 e sé stesso. È precisamente questa la proprietà che definisce un numero primo.
- Il numero 1 non è né primo né composto e non possiede scomposizione in fattori primi (corrisponde al prodotto vuoto); questo calcolatore richiede pertanto un valore pari o superiore a 2.
- Con numeri molto grandi le divisioni successive diventano lente, poiché occorre provare i primi candidati fino alla radice quadrata del numero: è questo il motivo per cui fattorizzare numeri enormi (di centinaia di cifre) risulta computazionalmente arduo e costituisce la base di sicurezza della cifratura RSA.
Che cos'è la scomposizione in fattori primi?
Scomporre in fattori primi significa ridurre un numero intero all'insieme di numeri primi che, moltiplicati fra loro, lo generano. Un numero primo è un intero maggiore di 1 che possiede esattamente due divisori positivi: 1 e sé stesso (2, 3, 5, 7, 11, 13, ... sono i primi della serie). Ad esempio 360 si scompone in 2³ × 3² × 5, ossia 360 = 2×2×2×3×3×5.
Il teorema fondamentale dell'aritmetica, uno dei risultati cardine della teoria dei numeri, garantisce che ogni intero maggiore di 1 possieda una e una sola scomposizione in fattori primi, a meno dell'ordine in cui i fattori vengono scritti. È proprio questa unicità a rendere la scomposizione un'operazione ben definita e affidabile, e non una fra tante risposte ugualmente valide.
La scomposizione in fattori primi sostiene settori centrali della matematica e dell'informatica: serve a ricavare il massimo comune divisore e il minimo comune multiplo, a determinare tutti i divisori di un numero, a semplificare frazioni e radicali e — quando i numeri sono enormi — la sua difficoltà computazionale costituisce il fondamento matematico della crittografia a chiave pubblica RSA, che poggia sul fatto che fattorizzare un numero grande è assai più arduo che moltiplicarne i fattori.
Come si usa questo calcolatore di scomposizione in fattori primi
- Inserisci un numero intero pari o superiore a 2 (fino a mille miliardi).
- Il calcolatore divide ripetutamente per il più piccolo fattore primo possibile finché non resta 1, seguendo il metodo classico delle divisioni successive.
- Leggi la scomposizione in notazione esponenziale (per esempio 2³ × 3² × 5): ogni esponente indica quante volte quel primo compare nel prodotto.
- Controlla infine il numero complessivo di divisori positivi e la loro somma, entrambi ricavati direttamente dalla scomposizione.
Come si calcolano scomposizione, numero e somma dei divisori
Il metodo delle divisioni successive individua la scomposizione provando i primi candidati a partire da 2, dividendo il numero per ciascun primo tutte le volte in cui la divisione risulta esatta e passando poi al candidato seguente. Esempio svolto: 360 ÷ 2 = 180, ÷2 = 90, ÷2 = 45 (non più divisibile per 2, dunque il 2 compare 3 volte); 45 ÷ 3 = 15, ÷3 = 5 (non più divisibile per 3, dunque il 3 compare 2 volte); 5 ÷ 5 = 1 (il 5 compare una volta). Risultato: 360 = 2³ × 3² × 5.
Nota la scomposizione n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ, il numero complessivo di divisori positivi (compresi 1 e n stesso) si ottiene sommando 1 a ciascun esponente e moltiplicando i risultati: (e₁+1) × (e₂+1) × ... × (eₖ+1). Esempio svolto per 360 = 2³ × 3² × 5¹: (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24 divisori.
La somma di tutti i divisori si ricava invece dalla formula moltiplicativa: ogni potenza di primo p^e presente nella scomposizione contribuisce con (p^(e+1) − 1) ÷ (p − 1) — la somma della serie geometrica 1 + p + p² + ... + p^e — e tali contributi vengono moltiplicati fra loro su tutti i fattori primi. Esempio svolto per 360: il termine 2³ contribuisce con (2⁴−1)/(2−1) = 15, il termine 3² con (3³−1)/(3−1) = 13 e il termine 5¹ con (5²−1)/(5−1) = 6; moltiplicando, 15 × 13 × 6 = 1170, ossia la somma dei 24 divisori di 360.
Errori frequenti
- Interrompere la scomposizione prima di arrivare a 1: ogni fattore individuato va estratto completamente, non una sola volta, prima di passare al primo candidato successivo.
- Considerare 1 un numero primo: per convenzione matematica moderna 1 non è né primo né composto, e includerlo in una scomposizione violerebbe l'unicità garantita dal teorema fondamentale dell'aritmetica.
- Dimenticare che per contare i divisori conta l'esponente e non soltanto la base: la formula usa (esponente + 1) per ciascun primo, non il semplice numero di primi distinti.
- Dare per scontato che ogni numero grande abbia fattori primi piccoli: molti numeri grandi (in particolare i prodotti di due primi grandi) non ne hanno affatto, ed è proprio questa proprietà a renderli utili nelle applicazioni crittografiche.
Domande frequenti
Come si trova la scomposizione in fattori primi di un numero?
Dividi ripetutamente il numero per il più piccolo primo che lo divide esattamente, continuando con quello stesso primo finché la divisione resta esatta, poi passa al primo successivo e prosegui fino a ottenere come quoziente 1. Per 360: dividi tre volte per 2 (360→180→90→45), poi due volte per 3 (45→15→5) e infine una volta per 5 (5→1), ottenendo 360 = 2³ × 3² × 5.
Quanti divisori ha un numero?
Somma 1 a ciascun esponente della scomposizione e moltiplica fra loro i risultati. Per 360 = 2³ × 3² × 5¹ il conteggio è (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24. Il totale comprende tutti i divisori positivi, quindi anche 1 e il numero stesso.
Che cos'è il teorema fondamentale dell'aritmetica?
Il teorema fondamentale dell'aritmetica afferma che ogni intero maggiore di 1 può essere scritto come prodotto di numeri primi in un solo modo, a prescindere dall'ordine in cui i primi vengono elencati. Questa unicità rende la scomposizione un'operazione ben definita anziché una fra più risposte ugualmente valide, e sorregge buona parte della teoria dei numeri.
Il numero 1 è un numero primo?
No. Per convenzione matematica moderna 1 non è né primo né composto. Un numero primo è definito come dotato di esattamente due divisori positivi distinti (1 e sé stesso), mentre 1 ne possiede uno solo e dunque non rientra nella definizione. Escludere 1 dai primi è inoltre necessario perché valga il teorema fondamentale dell'aritmetica: altrimenti un numero potrebbe essere « scomposto » aggiungendo quanti fattori 1 si vuole.
Perché la scomposizione in fattori primi è importante per la crittografia?
La crittografia a chiave pubblica RSA sfrutta il fatto che moltiplicare due grandi numeri primi è computazionalmente facile, mentre risalire dal loro prodotto ai primi di partenza è estremamente oneroso con gli algoritmi classici oggi noti. Questa asimmetria — facile moltiplicare, difficile fattorizzare — consente di condividere apertamente la chiave pubblica (il prodotto) mentre la chiave privata (i fattori primi) resta segreta e, con primi sufficientemente grandi, di fatto irrecuperabile in tempi utili.
Come si calcola la somma di tutti i divisori di un numero?
Partendo dalla scomposizione n = p₁^e₁ × p₂^e₂ × ..., calcola (pᵢ^(eᵢ+1) − 1) ÷ (pᵢ − 1) per ciascun fattore primo e moltiplica i risultati. Per 360 = 2³ × 3² × 5 il termine 2³ dà (2⁴−1)/(2−1)=15, il termine 3² dà (3³−1)/(3−1)=13 e il termine 5¹ dà (5²−1)/(5−1)=6; moltiplicando, 15×13×6 = 1170, ossia la somma di tutti i divisori di 360.
Fonti
- Rosen KH. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2010. (Fundamental theorem of arithmetic, divisor functions.)
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008.
- Rivest RL, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 1978; 21(2): 120–126. (RSA and the factoring problem.)