title: Teorema di Lucas
text: # Teorema di Lucas
  
  In teoria dei numeri, il teorema di Lucas fornisce il resto che si ottiene dividendo il coefficiente binomiale ${\tbinom {m}{n}}$ per un numero primo p{\textstyle p} in termini dell'espansione in base $p$ dei numeri interi $m$ e $n$.
  
  Il teorema di Lucas apparve per la prima volta nel 1878 in articoli di Édouard Lucas.
  
  ## Formulazione
  
  Per numeri interi non negativi $m$ e $n$ ed un numero primo $p$, vale la seguente relazione di congruenza:
  
  ${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}$
  
  dove
  
  $m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},$
  
  e
  
  $n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}$
  
  sono rispettivamente le espansioni in base $p$ di $m$ e di $n$. Questo utilizza la convenzione che ${\displaystyle {\tbinom {m}{n}}=0}$ se $n>m$.
  
  ## Conseguenza
  
  Un coefficiente binomiale ${\tbinom {m}{n}}$è divisibile per un numero primo $p$ se e solo se almeno una delle cifre in base $p$ di $n$ è maggiore della cifra corrispondente di $m$.
  
  ## 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 $M$ un insieme di $m$ elementi e lo si divida in $m_{i}$ cicli di lunghezza $p^{i}$ per i vari valori di $i$. Allora ognuno di questi cicli può essere ruotato separatamente così che un gruppo $G$, che è il prodotto cartesiano dei gruppi ciclici $C_{p^{i}}$, agisca su $M$. Allora questo agisce anche sui sottoinsiemi $N$ di grandezza $n$. Dato che il numero di elementi in $G$ è una potenza di $p$, lo stesso è vero per ogni sua orbita. Quindi per calcolare ${\tbinom {m}{n}}$ modulo $p$, dobbiamo considerare solamente determinati punti. Questi punti sono i sottoinsiemi $N$ che sono unione di alcuni dei cicli. Più precisamente si può dimostrare per induzione su $k-i$, che $N$ deve avere esattamente $n_{i}$ cicli di grandezza $p^{i}$. Quindi il numero di scelte per $N$ è esattamente
  
  $\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}.$
  
  ### Dimostrazione basata su funzioni generatrici
  
  Questa dimostrazione è da accreditarsi a Nathan Fine.
  
  Se $p$ è un numero primo e $n$ è un numero intero con 1≤n≤p−1{\textstyle 1\leq n\leq p-1}, allora il numeratore del coefficiente binomiale
  
  ${\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}$
  
  è divisibile per $p$ mentre il denominatore non lo è. Quindi $p$ divide ${\displaystyle {\tbinom {p}{n}}}$. In termini di funzioni generatrici ordinarie questo significa che
  
  $(1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.$
  
  Continuando per induzione, abbiamo per ogni numero intero non negativo $i$ che
  
  $(1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.$
  
  Ora indichiamo con $m$ un numero intero non negativo e con $p$ un numero primo. Scriviamo $m$ in base $p$ così che $m=\sum _{i=0}^{k}m_{i}p^{i}$ per qualche intero non negativo $k$ e per gli interi $m_{i}$ con $0≤m_i≤p−1{\textstyle$ 0\leq m_{i}\leq p-1}.
  
  Allora
  
  ${\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{m_{i}}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{p-1}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}$
  
  dove nel prodotto finale, $n_{i}$è la $i$-esima cifra della rappresentazione in base $p$ di $n$. 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 $p$ è la potenza di un numero primo.
  