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.

Cho số nguyên tố p và bất kỳ số tự nhiên n, gọi ${\displaystyle \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 đó

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

trong đó ${\displaystyle \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 ${\displaystyle p^{i}>n}$, ta có ${\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =0}$. Nhờ đó, rút gọn công thức trên thành

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

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

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

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

Bởi ${\displaystyle 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 ${\displaystyle n!}$ cho mỗi bội của p trpng ${\displaystyle \{1,2,\dots ,n\}}$, tổng cộng có ${\displaystyle \textstyle \left\lfloor {\frac {n}{p}}\right\rfloor }$. Mỗi bội của ${\displaystyle p^{2}}$ cho thêm một nhân tử p, và tương tự như vậy, mỗi bội của ${\displaystyle 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 ${\displaystyle \nu _{p}(n!)}$.

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 ${\displaystyle s_{p}(n)}$ là tổng các chữ số trong khai triển cơ số p của n thì

${\displaystyle \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ó ${\displaystyle s_{2}(6)=1+1+0=2}$ nên

${\displaystyle \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ó ${\displaystyle s_{3}(6)=2+0=2}$ nên

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

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

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

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ì ${\displaystyle {\binom {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 ${\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, page 77
• Leonard Eugene Dickson, History of the Theory of Numbers, Volume 1, Carnegie Institution of Washington, 1919, page 263.

• Weisstein, Eric W., "Factorial" từ MathWorld.