Teorema di Lucas

In teoria dei numeri, il teorema di Lucas fornisce il resto che si ottiene dividendo il coefficiente binomiale $(\binom{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.^[1]

Formulazione

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

$(\binom{m}{n}) \equiv \prod_{i = 0}^{k} (\binom{m_{i}}{n_{i}}) (\mod p),$

dove

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

e

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

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

Conseguenza

Un coefficiente binomiale $(\binom{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 $(\binom{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}}) (\mod 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 $1 \leq n \leq p - 1$ , allora il numeratore del coefficiente binomiale

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

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

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

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

$(1 + X)^{p^{i}} \equiv 1 + X^{p^{i}} (\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 \leq m_{i} \leq p - 1$ .

Allora

$\begin{matrix} \sum_{n = 0}^{m} (\binom{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} (\sum_{n_{i} = 0}^{m_{i}} (\binom{m_{i}}{n_{i}}) X^{n_{i} p^{i}}) \\ = \prod_{i = 0}^{k} (\sum_{n_{i} = 0}^{p - 1} (\binom{m_{i}}{n_{i}}) X^{n_{i} p^{i}}) = \sum_{n = 0}^{m} (\prod_{i = 0}^{k} (\binom{m_{i}}{n_{i}})) X^{n} (\mod p), \end{matrix}$

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

Note

↑
* Template:Cita pubblicazione (part 1);
- Template:Cita pubblicazione (part 2);
- Template:Cita pubblicazione (part 3)
↑ Template:Cita pubblicazione
↑ Template:Cita pubblicazione

Collegamenti esterni

[1] * Template:Cita pubblicazione (part 1);
Template:Cita pubblicazione (part 2);

Template:Cita pubblicazione (part 3)

[2] Template:Cita pubblicazione (part 2);

[3] Template:Cita pubblicazione (part 3)

[2] Template:Cita pubblicazione

[3] Template:Cita pubblicazione

[1]

[2]

[3]

Teorema di Lucas

Indice

Formulazione

Conseguenza

Dimostrazioni

Ragionamento in combinatoria

Dimostrazione basata su funzioni generatrici

Variazioni e generalizzazioni

Note

Collegamenti esterni

Menu di navigazione

Teorema di Lucas

Formulazione

Conseguenza

Dimostrazioni

Ragionamento in combinatoria

Dimostrazione basata su funzioni generatrici

Variazioni e generalizzazioni

Note

Collegamenti esterni

Menu di navigazione

Ricerca