Scomposizione in fattori primi

Scomporre un numero in fattori primi e sapere se è primo

Ogni intero maggiore o uguale a 2 si scrive come prodotto di numeri primi in un solo modo, a meno dell’ordine dei fattori: è il teorema fondamentale dell’aritmetica. 360 = 2³ × 3² × 5, 1001 = 7 × 11 × 13, e 97 non si scompone affatto: è primo. Questo calcolatore fornisce la scomposizione, dice subito se il numero è primo o composto e mostra la tabella delle divisioni successive come si imposta a scuola.

La scomposizione è la chiave di molti calcoli: semplificare frazioni, trovare MCD e mcm, contare i divisori, semplificare radici quadrate. È utile agli studenti della scuola secondaria di primo e secondo grado, agli insegnanti che preparano le verifiche, a chi partecipa ai Giochi di Archimede e a chiunque sia curioso di crittografia: la sicurezza di RSA si basa sulla difficoltà di fattorizzare numeri molto grandi.

1. Inserisci il numero

   Digita un intero in «Numero intero da scomporre» (a partire da 2, fino a 18 cifre). Spazi e separatori delle migliaia vengono ignorati, quindi 600.851.475.143 funziona così com’è. I pulsanti di «Prova:» caricano esempi pronti.

2. Leggi il verdetto

   L’etichetta indica «Numero primo» oppure «Non è primo: numero composto», poi compare la scomposizione con gli esponenti (360 = 2³ × 3² × 5) e la forma estesa. Il pulsante «Copia» mette 2^3 × 3^2 × 5 negli appunti.

3. Esplora le proprietà

   Le schede di «Proprietà aritmetiche» mostrano τ(n), σ(n), φ(n), il numero di fattori primi distinti ω(n) e con molteplicità Ω(n), se n è un quadrato perfetto, la somma dei divisori propri e il primo precedente e successivo (fino a 10¹²).

4. Verifica a mano

   La tabella «Divisioni successive (tabella in colonna)» ripete ogni passaggio (360 ÷ 2 = 180…) fino al quoziente 1, e «Tutti i divisori» elenca i divisori in ordine crescente, con quelli primi evidenziati.

Il metodo: teorema fondamentale e formule

Per un intero n ≥ 2, la scomposizione si scrive n = p1a1 × p2a2 × … × pkak. Si ottiene dividendo per il più piccolo fattore primo finché possibile; basta provare i divisori fino a √n, perché un numero composto ha sempre un fattore primo minore o uguale alla sua radice quadrata.

Con i numeri grandi lo strumento concatena tre fasi: divisione per i primi fino a 10.000, test di Miller-Rabin deterministico per riconoscere i primi e algoritmo rho di Pollard (variante di Brent) per spezzare i cofattori composti. Tutti i calcoli usano interi esatti, senza arrotondamenti.

• p₁ < p₂ < … < p_k: i fattori primi distinti in ordine crescente; il loro numero si indica con ω(n).
• a_i: l’esponente (la molteplicità) di p_i; la somma a₁ + … + a_k è Ω(n), il numero di fattori contati con ripetizione.
• τ(n) = (a₁ + 1)(a₂ + 1)…(a_k + 1): il numero di divisori, perché ogni divisore sceglie per ciascun p_i un esponente tra 0 e a_i.
• σ(n) = ∏ (p_i^a_i+1 − 1) / (p_i − 1): la somma di tutti i divisori; s(n) = σ(n) − n dice se il numero è perfetto, abbondante o difettivo.
• φ(n) = n × ∏ (1 − 1/p_i): la funzione φ di Eulero, cioè quanti interi da 1 a n sono coprimi con n.
• Quadrato perfetto: n è un quadrato se e solo se tutti gli a_i sono pari; allora √n = ∏ p_i^a_i/2, per esempio √1024 = 2⁵ = 32.

Esempi di scomposizione in fattori primi

A cosa serve la scomposizione in fattori primi?

• Semplificare le frazioni: 84/360 = (2² × 3 × 7)/(2³ × 3² × 5) = 7/30, dopo aver eliminato i fattori comuni 2² × 3 = 12.
• Trovare il denominatore comune: il mcm di 360 e 84 è 2520, il minimo comune denominatore per sommare 1/360 e 1/84.
• Semplificare le radici quadrate: √360 = √(2² × 3² × 10) = 2 × 3 × √10 = 6√10: ogni coppia di fattori uguali si porta fuori dalla radice.
• Contare ed elencare i divisori: utile nei problemi di suddivisione (disporre 360 sedie in file uguali: 24 disposizioni file × colonne possibili) e nei compiti sulla divisibilità.
• Crittografia e sfide: RSA si basa sulla difficoltà di fattorizzare; il celebre problema 3 di Project Euler chiede il più grande fattore primo di 600.851.475.143, cioè 6857.

Errori frequenti

• Dividere per un numero non primo: dividere 360 per 4 o per 6 dà un quoziente giusto ma una scomposizione incompleta; si divide solo per 2, 3, 5, 7, 11, 13…
• Considerare 1 un numero primo: 1 ha un solo divisore e non compare mai in una scomposizione.
• Confondere 2³ con 2 × 3: 2³ = 2 × 2 × 2 = 8, mentre 2 × 3 = 6; l’esponente conta le ripetizioni del fattore.
• Credere primo un numero che «sembra» primo: 51 = 3 × 17, 91 = 7 × 13 e 1001 = 7 × 11 × 13 sono composti; prova sempre fino alla radice quadrata.

Tutti i calcoli avvengono localmente nel tuo browser, con aritmetica intera esatta (BigInt): nessun numero viene inviato o salvato. Limiti: massimo 18 cifre; i primi vicini sono mostrati fino a 10¹², l’elenco dei divisori fino a 1000 divisori e la tabella delle divisioni fino a 40 fattori primi contati con molteplicità.