✨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 $\backslash 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 đó :$\backslash nu$p(n!) = \sum{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor, trong đó $\backslash lfloor\; x\; \backslash 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ó $\backslash textstyle\; \backslash left\backslash lfloor\; \backslash frac\{n\}\{p^i\}\; \backslash right\backslash rfloor\; =\; 0$. Nhờ đó, rút gọn công thức trên thành :$\backslash nu$p(n!) = \sum{i=1}^{L} \left\lfloor \frac{n}{p^i} \right\rfloor \, , trong đó $L\; =\; \backslash lfloor\; \backslash log\_\{p\}\; n\; \backslash rfloor$.

Ví dụ

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

: $\backslash begin\{align\}\; \backslash 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] \nu3(6!) & = \sum{i=1}^\infty \left\lfloor \frac 6 {3^i} \right\rfloor = \left\lfloor \frac 6 3 \right\rfloor = 2, \[3pt] \nu5(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,\; \backslash dots,\; n\}$, tổng cộng có $\backslash textstyle\; \backslash left\backslash lfloor\; \backslash frac\{n\}\{p\}\; \backslash right\backslash 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 $\backslash 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ì

:$\backslash nu\_p(n!)\; =\; \backslash 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 :$\backslash nu\_2(6!)\; =\; \backslash 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 :$\backslash nu\_3(6!)\; =\; \backslash frac\{6\; -\; 2\}\{3\; -\; 1\}\; =\; 2.$

Chứng minh

Viết $n\; =\; n\_\backslash ell\; p^\backslash ell\; +\; \backslash cdots\; +\; n\_1\; p\; +\; n\_0$ trong hệ cơ số p. Vì $\backslash textstyle\; \backslash left\backslash lfloor\; \backslash frac\{n\}\{p^i\}\; \backslash right\backslash rfloor\; =\; n$\ell p^{\ell-i} + \cdots + n{i+1} p + n_i, và do vậy :$\backslash begin\{align\}\; \backslash 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 + ni\right) \ &= \sum{i=1}^{\ell} \sum_{j=i}^{\ell} nj p^{j-i} \ &= \sum{j=1}^{\ell} \sum_{i=1}^{j} nj p^{j-i} \ &= \sum{j=1}^{\ell} nj \cdot \frac{p^j - 1}{p - 1} \ &= \sum{j=0}^{\ell} nj \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ì $\backslash 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)\}$.