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* trong \{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
*