Teorema di Lucas

Il teorema di Lucas è il metodo classico per valutare un coefficiente binomiale modulo un numero primo quando n è abbastanza grande da rendere impraticabile il fattoriale di n. Il prodotto è esattamente C(n, k) mod p; se una cifra inferiore supera quella superiore corrispondente, l’intero valore è zero. La programmazione di gara, la teoria dei numeri combinatoria e i compiti di crittografia richiedono questa riduzione quando i fattoriali diretti traboccano o costano troppo.

Cosa afferma il teorema di Lucas e quando ne ha bisogno

Nella combinatoria elementare il coefficiente binomiale C(n, k) conta i sottoinsiemi di k elementi di un insieme di n elementi e vale il fattoriale di n diviso il fattoriale di k per il fattoriale di (n meno k). Quella forma chiusa diventa inutile non appena n supera alcune migliaia se serve solo la risposta modulo un piccolo primo: i fattoriali intermedi esplodono e le approssimazioni in virgola mobile perdono il residuo esatto. Il teorema di Lucas, intitolato a Édouard Lucas, risolve proprio questo problema modulare.

Ogni fattore usa argomenti minori di p, quindi si calcola con un breve ciclo moltiplicativo e inversi modulari che esistono perché p è primo e ogni denominatore è minore di p. Solo quel test risponde a molte domande del tipo «il binomiale è divisibile per questo primo?» senza calcolare un prodotto completo.

Il teorema richiede che p sia primo; per moduli composti lo stesso prodotto di cifre non è in generale valido, e questa capacità rifiuta deliberatamente un p non primo invece di restituire in silenzio un residuo errato. Studenti che incontrano il teorema nel materiale olimpico, sviluppatori che collegano librerie di programmazione competitiva e docenti che preparano laboratori di aritmetica modulare traggono vantaggio da un’unica funzione deterministica che impone l’ipotesi di primalità ed espone gli sviluppi di cifre usati nella dimostrazione.

Come questa calcolatrice applica il teorema di Lucas passo per passo

Invocchi la capacità con i campi interi n, k e p. Sia n sia k devono essere interi non negativi al massimo di un bilione; p deve essere un primo tra due e un milione e tre inclusi. L’implementazione valida prima tipi e limiti, poi esegue un test di primalità per divisione di prova deterministico su p.

Quando p è accettato, il risolutore percorre le cifre in base p di n e k dal meno significativo al più significativo. Ogni piccolo binomiale usa la formula moltiplicativa con inversi modulari tramite il piccolo teorema di Fermat (a elevato a p meno due modulo p), implementata con prodotti intermedi esatti in BigInt così da non perdere precisione entro i limiti pubblicati.

I casi limite sono stabili e documentati: quando k è zero o uguale a n il risultato è uno modulo p (o zero solo se p vale uno, che viene rifiutato); quando k supera n il risultato è zero; quando n e k sono entrambi zero gli array di cifre sono la sola cifra zero e il risultato è uno modulo p.