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 ${\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.^[1]

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.^[2]

Se $p$ è un numero primo e $n$ è un numero intero con ${\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 ${\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}}$