Teorema di Lucas

In teoria dei numeri, il teorema di Lucas fornisce il resto che si ottiene dividendo il coefficiente binomiale $(\genfrac{}{}{0ex}{}{m}{n})$ per un numero primo $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:

$(\genfrac{}{}{0ex}{}{m}{n})\equiv \prod _{i=0}^k(\genfrac{}{}{0ex}{}{m_i}{n_i})(\mathrm{mod}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 $(\genfrac{}{}{0ex}{}{m}{n})=0$ se $n>m$.

Conseguenza

Un coefficiente binomiale $(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{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(\genfrac{}{}{0ex}{}{m_i}{n_i})(\mathrm{mod}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\le n\le p-1$, allora il numeratore del coefficiente binomiale

$(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{p}{n})$. In termini di funzioni generatrici ordinarie questo significa che

$(1+X{)}^p\equiv 1+X^p(\mathrm{mod}p).$

Continuando per induzione, abbiamo per ogni numero intero non negativo $i$ che

$(1+X{)}^{p^i}\equiv 1+X^{p^i}(\mathrm{mod}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\le m_i\le p-1$.

Allora

$\begin{array}{cc}\sum _{n=0}^m(\genfrac{}{}{0ex}{}{m}{n})X^n& =(1+X{)}^m=\prod _{i=0}^k{((1+X{)}^{p^i})}^{m_i}\\ & \equiv \prod _{i=0}^k{(1+X^{p^i})}^{m_i}=\prod _{i=0}^k\left(\sum _{n_i=0}^{m_i}(\genfrac{}{}{0ex}{}{m_i}{n_i})X^{n_i{p}^i}\right)\\ & =\prod _{i=0}^k\left(\sum _{n_i=0}^{p-1}(\genfrac{}{}{0ex}{}{m_i}{n_i})X^{n_i{p}^i}\right)=\sum _{n=0}^m\left(\prod _{i=0}^k(\genfrac{}{}{0ex}{}{m_i}{n_i})\right)X^n(\mathrm{mod}p),\end{array}$

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.

Collegamenti esterni

• Template:PlanetMath
• Alternative proof of Lucas's theorem