Teorema di Lucas

In teoria dei numeri, il teorema di Lucas fornisce il resto che si ottiene dividendo il coefficiente binomiale ${\displaystyle {\tbinom {m}{n}}}$ per un numero primo ${\textstyle p}$ in termini dell'espansione in base ${\displaystyle p}$ dei numeri interi ${\displaystyle m}$ e ${\displaystyle n}$.

Il teorema di Lucas apparve per la prima volta nel 1878 in articoli di Édouard Lucas.^[1]

Per numeri interi non negativi ${\displaystyle m}$ e ${\displaystyle n}$ ed un numero primo ${\displaystyle p}$, vale la seguente relazione di congruenza:

${\displaystyle {\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}}$

dove

${\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}$

e

${\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}$

sono rispettivamente le espansioni in base ${\displaystyle p}$ di ${\displaystyle m}$ e di ${\displaystyle n}$. Questo utilizza la convenzione che ${\displaystyle {\displaystyle {\tbinom {m}{n}}=0}}$ se ${\displaystyle n>m}$.

Un coefficiente binomiale ${\displaystyle {\tbinom {m}{n}}}$è divisibile per un numero primo ${\displaystyle p}$ se e solo se almeno una delle cifre in base ${\displaystyle p}$ di ${\displaystyle n}$ è maggiore della cifra corrispondente di ${\displaystyle m}$.

Ci sono diversi modi per dimostrare il teorema di Lucas. Faremo prima un ragionamento in combinatoria e poi una dimostrazione basata su funzioni generatrici.

Si indichi con ${\displaystyle M}$ un insieme di ${\displaystyle m}$ elementi e lo si divida in ${\displaystyle m_{i}}$ cicli di lunghezza ${\displaystyle p^{i}}$ per i vari valori di ${\displaystyle i}$. Allora ognuno di questi cicli può essere ruotato separatamente così che un gruppo ${\displaystyle G}$, che è il prodotto cartesiano dei gruppi ciclici ${\displaystyle C_{p^{i}}}$, agisca su ${\displaystyle M}$. Allora questo agisce anche sui sottoinsiemi ${\displaystyle N}$ di grandezza ${\displaystyle n}$. Dato che il numero di elementi in ${\displaystyle G}$ è una potenza di ${\displaystyle p}$, lo stesso è vero per ogni sua orbita. Quindi per calcolare ${\displaystyle {\tbinom {m}{n}}}$ modulo ${\displaystyle p}$, dobbiamo considerare solamente determinati punti. Questi punti sono i sottoinsiemi ${\displaystyle N}$ che sono unione di alcuni dei cicli. Più precisamente si può dimostrare per induzione su ${\displaystyle k-i}$, che ${\displaystyle N}$ deve avere esattamente ${\displaystyle n_{i}}$ cicli di grandezza ${\displaystyle p^{i}}$. Quindi il numero di scelte per ${\displaystyle N}$ è esattamente

${\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}.}$

Questa dimostrazione è da accreditarsi a Nathan Fine.^[2]

Se ${\displaystyle p}$ è un numero primo e ${\displaystyle n}$ è un numero intero con ${\textstyle 1\leq n\leq p-1}$, allora il numeratore del coefficiente binomiale

${\displaystyle {\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}}$

è divisibile per ${\displaystyle p}$ mentre il denominatore non lo è. Quindi ${\displaystyle p}$ divide ${\displaystyle {\displaystyle {\tbinom {p}{n}}}}$. In termini di funzioni generatrici ordinarie questo significa che

${\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.}$

Continuando per induzione, abbiamo per ogni numero intero non negativo ${\displaystyle i}$ che

${\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}$

Ora indichiamo con ${\displaystyle m}$ un numero intero non negativo e con ${\displaystyle p}$ un numero primo. Scriviamo ${\displaystyle m}$ in base ${\displaystyle p}$ così che ${\displaystyle m=\sum _{i=0}^{k}m_{i}p^{i}}$ per qualche intero non negativo ${\displaystyle k}$ e per gli interi ${\displaystyle m_{i}}$ con ${\textstyle 0\leq m_{i}\leq p-1}$.

Allora

${\displaystyle {\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, ${\displaystyle n_{i}}$è la ${\displaystyle i}$-esima cifra della rappresentazione in base ${\displaystyle p}$ di ${\displaystyle n}$. Questo dimostra il teorema di Lucas.

• Teorema di Kummer
• Andrew Granville ha generalizzato il teorema di Lucas per il caso in cui ${\displaystyle p}$ è la potenza di un numero primo.^[3]

• (EN) Teorema di Lucas, in PlanetMath.
• Alternative proof of Lucas's theorem