Teorema di Lucas

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

In teoria dei numeri, il teorema di Lucas fornisce il resto che si ottiene dividendo il coefficiente binomiale per un numero primo in termini dell'espansione in base dei numeri interi e .

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

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

dove

e

sono rispettivamente le espansioni in base di e di . Questo utilizza la convenzione che se .

Un coefficiente binomiale è divisibile per un numero primo se e solo se almeno una delle cifre in base di è maggiore della cifra corrispondente di .

Dimostrazioni

[modifica | modifica wikitesto]

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

[modifica | modifica wikitesto]

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

Dimostrazione basata su funzioni generatrici

[modifica | modifica wikitesto]

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

Se è un numero primo e è un numero intero con , allora il numeratore del coefficiente binomiale

è divisibile per mentre il denominatore non lo è. Quindi divide . In termini di funzioni generatrici ordinarie questo significa che

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

Ora indichiamo con un numero intero non negativo e con un numero primo. Scriviamo in base così che per qualche intero non negativo e per gli interi con .

Allora

dove nel prodotto finale, è la -esima cifra della rappresentazione in base di . Questo dimostra il teorema di Lucas.

Variazioni e generalizzazioni

[modifica | modifica wikitesto]
  1. ^ * Edouard Lucas, Théorie des Fonctions Numériques Simplement Périodiques, in American Journal of Mathematics, vol. 1, n. 2, 1878, pp. 184–196, DOI:10.2307/2369308, JSTOR 2369308, MR 1505161. (part 1);
  2. ^ Nathan Fine, Binomial coefficients modulo a prime, in American Mathematical Monthly, vol. 54, 1947, pp. 589–592, DOI:10.2307/2304500.
  3. ^ Andrew Granville, Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers (PDF), in Canadian Mathematical Society Conference Proceedings, vol. 20, 1997, pp. 253–275, MR 1483922 (archiviato dall'url originale il 2 febbraio 2017).

Collegamenti esterni

[modifica | modifica wikitesto]