Identità di Legendre-de Polignac

In teoria dei numeri, l'identità di Legendre-de Polignac (o anche solo identità di Legendre), da Adrien-Marie Legendre e Alphonse de Polignac, fornisce l'esponente della maggiore potenza di un numero primo $p$ che divide il fattoriale $n!,$ dove $n\geq 1$ è un intero.

L'identità

Per ogni $p$ numero primo e ogni $n$ intero positivo, con $v_{p}(n)$ indica l'esponente della maggiore potenza di un numero primo $p$ che divide $n$ (la valutazione p-adica di $n$). Allora

$\upsilon _{p}(n!)=\sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor ,$

dove $\left\lfloor x\right\rfloor$ rappresenta la parte intera di $x.$ Per ogni $j$ tale che $p^{j}>n$, si ha $\left\lfloor {\frac {n}{p^{j}}}\right\rfloor =0.$

A ciò segue la disuguaglianza

${\displaystyle \upsilon _{p}(n!)\leq {\frac {n}{p-1}}}.$

Esempio

Per $n=6,$ si ha ${\displaystyle 6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}}$. Gli esponenti ${\displaystyle \nu _{2}(6!)=4,\nu _{3}(6!)=2}$ e ${\displaystyle \nu _{5}(6!)=1}$ possono essere ottenuti dalla identità di Legendre in questo modo:

${\displaystyle {\begin{aligned}\nu _{2}(6!)&=\sum _{j=1}^{\infty }\left\lfloor {\frac {6}{2^{j}}}\right\rfloor =\left\lfloor {\frac {6}{2}}\right\rfloor +\left\lfloor {\frac {6}{4}}\right\rfloor =3+1,\\[3pt]\nu _{3}(6!)&=\sum _{j=1}^{\infty }\left\lfloor {\frac {6}{3^{j}}}\right\rfloor =\left\lfloor {\frac {6}{3}}\right\rfloor =2,\\[3pt]\nu _{5}(6!)&=\sum _{j=1}^{\infty }\left\lfloor {\frac {6}{5^{j}}}\right\rfloor =\left\lfloor {\frac {6}{5}}\right\rfloor =1.\end{aligned}}}$

Dimostrazione

Essendo $n!$ il prodotto degli interi da $1$ a $n,$ otteniamo almeno un fattore di $p$ in $n!$ per ogni multiplo di $p$ in ${\displaystyle \{1,2,\ldots ,n\}},$ che sono in numero pari a ${\textstyle \left\lfloor {\frac {n}{p}}\right\rfloor }$. Ogni multiplo di $p^{2}$apporta un ulteriore fattore di $p,$ ogni multiplo di $p^{3}$ apporta ancora un altro fattore di $p,$ ecc. La somma del numero di questi fattori produce la somma infinita per $v_{p}(n!)$.

Forma alternativa

Si può riformulare l'identità di Legendre-de Polignac in termini dell'espansione in base $p$ di $n.$ Con ${\displaystyle s_{p}(n)}$ si denota la somma delle cifre dell'espansione in base $p$ di $n.$ Allora

${\displaystyle \nu _{p}(n!)={\frac {n-s_{p}(n)}{p-1}}}.$

Esempio

Scrivendo $n=6$ in binario come $6_{10}=110_{2},$ abbiamo che ${\displaystyle s_{2}(6)=1+1+0=2}$ e quindi

${\displaystyle \nu _{2}(6!)={\frac {6-2}{2-1}}=4.}$

Similmente, scrivendo $n=6$ in ternario come $6_{10}=20_{3},$ abbiamo che ${\displaystyle s_{3}(6)=2+0=2}$ e quindi

${\displaystyle \nu _{3}(6!)={\frac {6-2}{3-1}}=2.}$

Dimostrazione

Scrivendo $n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}$ in base $p$ si ottiene che $\textstyle \left\lfloor {\frac {n}{p^{j}}}\right\rfloor =n_{\ell }p^{\ell -j}+\cdots +n_{j+1}p+n_{j}.$ Allora

${\begin{aligned}\nu _{p}(n!)&=\sum _{j=1}^{\ell }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \\&=\sum _{j=1}^{\ell }\left(n_{\ell }p^{\ell -j}+\cdots +n_{j+1}p+n_{j}\right)\\&=\sum _{j=1}^{\ell }\sum _{i=j}^{\ell }n_{i}p^{i-j}\\&=\sum _{i=1}^{\ell }\sum _{j=1}^{i}n_{i}p^{i-j}\\&=\sum _{i=1}^{\ell }n_{i}\cdot {\frac {p^{i}-1}{p-1}}\\&=\sum _{i=0}^{\ell }n_{i}\cdot {\frac {p^{i}-1}{p-1}}\\&={\frac {1}{p-1}}\sum _{i=0}^{\ell }\left(n_{i}p^{i}-n_{i}\right)\\&={\frac {1}{p-1}}\left(n-s_{p}(n)\right).\end{aligned}}$

Applicazioni

L'identità di Legendre-de Polignac è utilizzata per dimostrare il teorema di Kummer. Può anche essere utilizzata per dimostrare che se $n$ è un intero positivo, allora $4$ divide ${\binom {2n}{n}}$ se e solo se $n$ non è una potenza di $2.$

Segue all'identità di Legendre-de Polignac che la funzione esponenziale p-adica ha raggio di convergenza $p^{-1/(p-1)}$.

Bibliografia

• Tom M. Apostol (1976): Introduction to Analytic Number Theory, Springer, (Chapter 3.11)
• Legendre, A. M. (1830), Théorie des Nombres, Paris: Firmin Didot Frères
• Moll, Victor H. (2012), Numbers and Functions, American Mathematical Society, ISBN 978-0821887950, MR 2963308, page 77
• Leonard Eugene Dickson, History of the Theory of Numbers, Volume 1, Carnegie Institution of Washington, 1919, page 263.

Voci correlate

• Fattorizzazione
• Fattoriale
• Parte intera
• Valutazione p-adica
• Base-p