Fattorizzazione prima

Scomposizione in fattori primi: l'impronta che ogni numero possiede una sola volta

Ogni intero maggiore di 1 è un prodotto di numeri primi e — è questo a renderlo utile — lo è in un solo modo. Il teorema fondamentale dell'aritmetica garantisce l'unicità della scomposizione, ed è per questo che funziona come impronta e che tanto altro vi si appoggia, dalla riduzione delle frazioni alla crittografia a chiave pubblica.

Come funziona

• Scompone un numero nei suoi fattori primi, in forma di potenze e scritto per esteso.
• Conta i divisori senza elencarli, direttamente dagli esponenti.
• Dice se il numero è primo, che è semplicemente il caso in cui si scompone in se stesso.

every integer above 1 factorises into primes in exactly one way

  360 = 2 x 2 x 2 x 3 x 3 x 5
      = 2^3 x 3^2 x 5

the number of divisors follows from the exponents
  d(n) = (3 + 1) x (2 + 1) x (1 + 1) = 24

Esempio pratico

Scomporre 360 estraendo ripetutamente il più piccolo primo che divide.

1. 360 / 2 = 180
2. 180 / 2 = 90
3. 90 / 2 = 45 2 appears three times
4. 45 / 3 = 15
5. 15 / 3 = 5 3 appears twice
6. 5 / 5 = 1 5 appears once
7. result 2^3 x 3^2 x 5

360 = 2³ × 3² × 5, e nessun'altra combinazione di primi dà 360. Dai soli esponenti segue il numero di divisori: (3+1)(2+1)(1+1) = 24, perché ogni divisore sceglie da 0 a 3 due, da 0 a 2 tre e 0 oppure 1 cinque.

Come leggere il risultato

• La formula dei divisori merita di essere conosciuta per sé. Non serve mai elencarli per contarli: aggiungi uno a ogni esponente e moltiplica, perché costruire un divisore significa scegliere in modo indipendente quanti di ciascun primo includere.
• La divisione per tentativi deve provare solo fino alla radice quadrata. Se n ha un fattore maggiore di √n, ha necessariamente anche quello corrispondente al di sotto: oltre la radice non resta nulla da trovare. Per questo scomporre un numero di sei cifre è istantaneo.
• Dopo 2 e 3 lo strumento avanza di sei in sei e verifica solo 6k−1 e 6k+1. Tutti gli altri resti sono già divisibili per 2 o 3, il che scarta gratis due terzi dei candidati.
• Che la fattorizzazione sia difficile per numeri molto grandi è una proprietà, non un limite di questo strumento. RSA si fonda sul fatto che moltiplicare due primi grandi è facile mentre recuperarli non lo è: quell'asimmetria è l'intero argomento di sicurezza.

Domande frequenti

1 è un numero primo?

No, ed escluderlo è una scelta deliberata, non una svista. Se 1 contasse come primo, le scomposizioni smetterebbero di essere uniche — 6 potrebbe essere 2×3, o 1×2×3, o 1×1×2×3 — e il teorema che rende utile la fattorizzazione richiederebbe un'eccezione scomoda in ogni enunciato.

Perché il mio numero si scompone solo in se stesso?

Perché è primo. Un primo non ha divisori oltre a 1 e se stesso, quindi la sua scomposizione è un singolo termine con esponente uno. Lo strumento lo dice esplicitamente invece di lasciartelo dedurre da un elenco di un solo elemento.