In teoria dei numeri, il teorema di Lucas fornisce il resto che si ottiene dividendo il coefficiente binomiale per un numero primo in termini dell'espansione in base dei numeri interi e .
Il teorema di Lucas apparve per la prima volta nel 1878 in articoli di Édouard Lucas.* (part 1); (part 2); (part 3)
Formulazione Per numeri interi non negativi e ed un numero primo , vale la seguente relazione di congruenza:
dove
e
sono rispettivamente le espansioni in base di e di . Questo utilizza la convenzione che se .
Conseguenza Un coefficiente binomiale è divisibile per un numero primo se e solo se almeno una delle cifre in base di è maggiore della cifra corrispondente di .
Dimostrazioni Ci sono diversi modi per dimostrare il teorema di Lucas. Faremo prima un ragionamento in combinatoria e poi una dimostrazione basata su funzioni generatrici.
Ragionamento in combinatoria Si indichi con un insieme di elementi e lo si divida in cicli di lunghezza per i vari valori di . Allora ognuno di questi cicli può essere ruotato separatamente così che un gruppo , che è il prodotto cartesiano dei gruppi ciclici , agisca su . Allora questo agisce anche sui sottoinsiemi di grandezza . Dato che il numero di elementi in è una potenza di , lo stesso è vero per ogni sua orbita. Quindi per calcolare modulo , dobbiamo considerare solamente determinati punti. Questi punti sono i sottoinsiemi che sono unione di alcuni dei cicli. Più precisamente si può dimostrare per induzione su , che deve avere esattamente cicli di grandezza . Quindi il numero di scelte per è esattamente
Dimostrazione basata su funzioni generatrici Questa dimostrazione è da accreditarsi a Nathan Fine.
Se è un numero primo e è un numero intero con , allora il numeratore del coefficiente binomiale
è divisibile per mentre il denominatore non lo è. Quindi divide . In termini di funzioni generatrici ordinarie questo significa che
Continuando per induzione, abbiamo per ogni numero intero non negativo che
Ora indichiamo con un numero intero non negativo e con un numero primo. Scriviamo in base così che per qualche intero non negativo e per gli interi con .
Allora
dove nel prodotto finale, è la -esima cifra della rappresentazione in base di . Questo dimostra il teorema di Lucas.
Variazioni e generalizzazioni
Teorema di Kummer Andrew Granville ha generalizzato il teorema di Lucas per il caso in cui è la potenza di un numero primo.
Note
Collegamenti esterni
Alternative proof of Lucas's theorem
Categoria:Teoremi sui numeri primi Categoria:Combinatoria Categoria:Teoria dei numeri