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&nbsp;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}^{\infty} \left\lfloor \frac{n}{p^i} \right\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ó \textstyle \left\lfloor \frac{n}{p^i} \right\rfloor = 0. Nhờ đó, rút gọn công thức trên thành
:\nu_p(n!) = \sum_{i=1}^{L} \left\lfloor \frac{n}{p^i} \right\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{align}
\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{align}

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ó \textstyle \left\lfloor \frac{n}{p} \right\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à 610 = 1102, 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à 610 = 203, 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ì \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
:
\begin{align}
\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{align}

Ứ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ì \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 p^{-1/(p-1)}.

Tham khảo


, 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