Formula lui Legendre

În matematică, formula lui Legendre oferă o expresie pentru exponentul celei mai mari puteri a unui număr prim p care divide factorialul n!. Este numită după Adrien-Marie Legendre, dar este cunoscută uneori și ca formula lui de Polignac, după Alphonse de Polignac.

Pentru orice număr prim p și orice număr întreg pozitiv n, fie ${\displaystyle \nu _{p}(n)}$ exponentul celei mai mari puteri a lui p care divide n (adică valuarea p-adică a lui n). Atunci

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

unde ${\displaystyle \lfloor x\rfloor }$ este funcția parte întreagă. Deși suma din membrul drept este o sumă infinită, pentru orice valori particulare ale lui n și p ea are doar un număr finit de termeni nenuli: pentru orice i suficient de mare încât ${\displaystyle p^{i}>n}$, are loc ${\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =0}$. Aceasta reduce suma infinită de mai sus la

${\displaystyle \nu _{p}(n!)=\sum _{i=1}^{L}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ,}$

unde ${\displaystyle L=\lfloor \log _{p}n\rfloor }$.

Pentru ${\displaystyle n=6}$ avem ${\displaystyle 6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}}$. Exponenții ${\displaystyle \nu _{2}(6!)=4,\nu _{3}(6!)=2}$ și ${\displaystyle \nu _{5}(6!)=1}$ pot fi calculați cu ajutorul formulei lui Legendre după cum urmează:

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

Cum ${\displaystyle n!}$ este produsul numerelor întregi de la ${\displaystyle 1}$ la ${\displaystyle n}$, obținem cel puțin un factor al lui ${\displaystyle p}$ în ${\displaystyle n!}$ pentru fiecare multiplu al lui ${\displaystyle p}$ din ${\displaystyle \{1,2,\dots ,n\}}$, aceștia fiind în total${\displaystyle \textstyle \left\lfloor {\frac {n}{p}}\right\rfloor }$. Fiecare multiplu de ${\displaystyle p^{2}}$ contribuie cu un factor ${\displaystyle p}$ suplimentar, fiecare multiplu de ${\displaystyle p^{3}}$ contribuie cu încă un factor ${\displaystyle p}$ etc. Adunând numărul acestor factori se obține suma infinită pentru ${\displaystyle \nu _{p}(n!)}$.

Formula lui Legendre poate fi rescrisă în funcție de termenii reprezentării lui n în baza p. Fie ${\displaystyle s_{p}(n)}$ suma cifrelor din reprezentarea în baza p a lui n; atunci

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

De exemplu, scriindu-l pe n = 6 în baza 2 ca 6₁₀ = 110₂, avem ${\displaystyle s_{2}(6)=1+1+0=2}$ și, deci,

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

În mod similar, scriindu-l pe 6 în baza 3 ca 6₁₀ = 20₃, avem ${\displaystyle s_{3}(6)=2+0=2}$ și, deci,

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

Se scrie ${\displaystyle n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}}$ în baza p. Atunci ${\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}}$ și, prin urmare,

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

Formula lui Legendre poate fi folosită pentru a demonstra teorema lui Kummer. Ca un caz particular, poate fi folosită pentru a demonstra că dacă n este un număr întreg pozitiv, atunci 4 divide ${\displaystyle {\binom {2n}{n}}}$ dacă și numai dacă n nu este o putere a lui 2.

Din formula lui Legendre rezultă că funcția exponențială p-adică are raza de convergență ${\displaystyle p^{-1/(p-1)}}$.

• 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 , pagina 77
• Leonard Eugene Dickson, History of the Theory of Numbers, Volumul 1, Carnegie Institution of Washington, 1919, pagina 263.

• Eric W. Weisstein, Factorial la MathWorld.