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.

Enunț

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

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

unde $\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 $p^i>n$, are loc $\lfloor \frac{n}{p^i}\rfloor =0$. Aceasta reduce suma infinită de mai sus la

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

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

Exemplu

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

$\begin{array}{cc}{\nu }_2(6!)& =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{6}{2^i}\rfloor =\lfloor \frac{6}{2}\rfloor +\lfloor \frac{6}{4}\rfloor =3+1=4,\\ {\nu }_3(6!)& =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{6}{3^i}\rfloor =\lfloor \frac{6}{3}\rfloor =2,\\ {\nu }_5(6!)& =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{6}{5^i}\rfloor =\lfloor \frac{6}{5}\rfloor =1.\end{array}$

Demonstrație

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

Formă alternativă

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

${\nu }_p(n!)=\frac{n-s_p(n)}{p-1}.$

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

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

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

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

Demonstrație

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

$\begin{array}{cc}{\nu }_p(n!)& =\sum _{i=1}^{\ell }\lfloor \frac{n}{p^i}\rfloor \\ & =\sum _{i=1}^{\ell }(n_{\ell }{p}^{\ell -i}+\cdots +n_{i+1}p+n_i)\\ & =\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 }(n_j{p}^j-n_j)\\ & =\frac{1}{p-1}(n-s_p(n)).\end{array}$

Aplicații

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 $(\genfrac{}{}{0ex}{}{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ță $p^{-1/(p-1)}$.

Bibliografie

• Format:Citation
• Format:Citation, pagina 77
• Leonard Eugene Dickson, History of the Theory of Numbers, Volumul 1, Carnegie Institution of Washington, 1919, pagina 263.

Legături externe

• Format:MathWorld