Công thức Legendre

Trong toán học, Công thức Legendre là biểu thức tính số mũ của lũy thừa lớn nhất của số nguyên tố p mà là ước của  n!. Công thức được đặt tên theo nhà toán học Adrien-Marie Legendre. Đôi khi nó cũng được gọi là công thức de Polignac, theo tên của Alphonse de Polignac.

Phát biểu

Cho số nguyên tố p và bất kỳ số tự nhiên n, gọi ${\nu }_p(n)$ là số mũ của lũy thừa lớn nhất p mà là ước của n (tức là định giá p-adic của n). Khi đó

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

trong đó $\lfloor x\rfloor$ là hàm lấy phần nguyên. Mặc dù tổng ở vế phải có vô hạn số phần tử, cho bất kỳ giá trị của n và p, nó vẫn chỉ có hữu hạn số phần tử khác không, lý do như sau: lấy các giá trị i đủ lớn sao cho $p^i>n$, ta có $\lfloor \frac{n}{p^i}\rfloor =0$. Nhờ đó, rút gọn công thức trên thành

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

trong đó $L=\lfloor {\log }_{p}n\rfloor$.

Ví dụ

Xét n = 6, ta có $6!=720=2^4\cdot 3^2\cdot 5^1$. Các số mũ ${\nu }_2(6!)=4,{\nu }_3(6!)=2$ và ${\nu }_5(6!)=1$ có thể tính bằng công thức Legendre như sau:

$\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}$

Chứng minh

Bởi $n!$ là tích của các số nguyên dương từ 1 đến n, ta thu được ít nhất một p trong $n!$ cho mỗi bội của p trpng $\{1,2,\dots ,n\}$, tổng cộng có $\lfloor \frac{n}{p}\rfloor$. Mỗi bội của $p^2$ cho thêm một nhân tử p, và tương tự như vậy, mỗi bội của $p^3$ cho thêm một nhân tử p, tiếp diễn như vậy cho các lũy thừa sau. Cộng tất cả số này sẽ thu về được công thức tổng vô hạn cho ${\nu }_p(n!)$.

Dạng khác

Ta cũng có thể viết lại công thức Legendre thành khai triển cơ số p của n. Gọi $s_p(n)$ là tổng các chữ số trong khai triển cơ số p của n thì

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

Ví dụ chẳng hạn, n = 6 trong hệ nhị phân được viết là 6₁₀ = 110₂, ta có $s_2(6)=1+1+0=2$ nên

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

Tương tự, n = 6 trong hệ tam phân được viết là 6₁₀ = 20₃, ta có $s_3(6)=2+0=2$ nên

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

Chứng minh

Viết $n=n_{\ell }{p}^{\ell }+\cdots +n_{1}p+n_0$ trong hệ cơ số p. Vì $\lfloor \frac{n}{p^i}\rfloor =n_{\ell }{p}^{\ell -i}+\cdots +n_{i+1}p+n_i$, và do vậy

$\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}$

Ứng dụng

Công thức Legendre được dùng để chứng minh định lý Kummer. Dưới trường hợp đặc biệt, nó có thể dùng để chứng minh rằng nếu n là số nguyên dương thì $(\genfrac{}{}{0ex}{}{2n}{n})$ chia hết cho 4 khi và chỉ khi n không phải lũy thừa của 2.

Suy ra được từ công thức Legendre rằng hàm mũ p-adic có bán kính hội tụ bằng với $p^{-1/(p-1)}$.

Tham khảo

• Bản mẫu:Citation
• Bản mẫu:Citation, page 77
• Leonard Eugene Dickson, History of the Theory of Numbers, Volume 1, Carnegie Institution of Washington, 1919, page 263.

Liên kết ngoài

• Bản mẫu:MathWorld