Số học Olympic

Công thức Legendre là công cụ chuẩn để tính lũy thừa nguyên tố chính xác chia hết giai thừa và hệ số nhị thức, kết hợp với định lý Kummer nó giải thích chính xác hệ số nhị thức nào chia hết cho một số nguyên tố cho trước.

**Bước 1: Viết $v_p(n!)$ thành tổng theo từng thừa số.** Theo định nghĩa $n! = 1\cdot 2\cdots n$, nên $v_p(n!) = \sum_{k=1}^{n} v_p(k)$, tổng định giá $p$-adic của mọi số nguyên từ $1$ đến $n$.

**Bước 2: Viết lại mỗi $v_p(k)$ thành một phép đếm.** Với mỗi $k$, $v_p(k) = \sum_{i=1}^{\infty} [p^i \mid k]$ (dùng ký hiệu Iverson, $1$ nếu đúng, $0$ nếu sai), vì $k$ chia hết cho $p^i$ đúng với $v_p(k)$ giá trị $i$ (cụ thể $i=1,\dots,v_p(k)$).

Bước 3: Đổi thứ tự tổng. Thay vào, $v_p(n!) = \sum_{k=1}^n \sum_{i=1}^{\infty} [p^i \mid k] = \sum_{i=1}^{\infty} \sum_{k=1}^n [p^i \mid k]$, đổi thứ tự tổng kép (hữu hạn nên hợp lệ).

**Bước 4: Đếm trực tiếp bội của $p^i$.** Tổng trong $\sum_{k=1}^n [p^i \mid k]$ đếm có bao nhiêu số nguyên từ $1$ đến $n$ là bội của $p^i$, đúng bằng $\left\lfloor \frac{n}{p^i} \right\rfloor$ (các bội là $p^i, 2p^i, \dots, \lfloor n/p^i\rfloor \cdot p^i$).

Bước 5: Kết luận. Thay lại, $v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$, hữu hạn vì $\lfloor n/p^i \rfloor = 0$ khi $p^i > n$, hoàn tất chứng minh.

LTE biến câu hỏi khó về chia hết của hiệu hai lũy thừa cao thành số học đơn giản trên định giá, và là một trong những cách nhanh nhất giải bài toán Olympic hỏi lũy thừa lớn nhất của số nguyên tố chia hết biểu thức như $a^n-b^n$ hoặc chứng minh biểu thức đó không bao giờ (hay luôn luôn) chia hết cho một lũy thừa số nguyên tố nào đó.

**Bước 1: Quy về trường hợp $n=p$ nhờ tính nhân.** Viết $n = p^{v_p(n)} \cdot m$ với $p \nmid m$. Áp dụng lặp lại trường hợp $n=p$ (chứng minh dưới đây) cho $a^m, b^m$ thay $a,b$ cho thấy $v_p(a^n-b^n) = v_p((a^m)^{p^{v_p(n)}} - (b^m)^{p^{v_p(n)}}) = v_p(a^m-b^m) + v_p(n)$, nên chỉ cần chứng minh $v_p(a^m - b^m) = v_p(a-b)$ khi $p \nmid m$, và chứng minh bước cơ sở $v_p(a^p-b^p) = v_p(a-b)+1$.

Bước 2: Chứng minh bước cơ sở bằng khai triển nhân tử. Phân tích $a^p - b^p = (a-b)(a^{p-1}+a^{p-2}b+\cdots+b^{p-1})$. Ta cần chỉ ra nhân tử thứ hai $S = \sum_{j=0}^{p-1} a^{p-1-j}b^j$ có $v_p(S) = 1$.

**Bước 3: Chỉ ra $p \mid S$.** Vì $p \mid a-b$, ta có $a \equiv b \pmod p$, nên mỗi số hạng $a^{p-1-j}b^j \equiv b^{p-1-j}b^j = b^{p-1} \pmod p$. Cộng cả $p$ số hạng, $S \equiv p\cdot b^{p-1} \equiv 0 \pmod p$ (dùng $p \nmid b$), nên $p \mid S$.

**Bước 4: Chỉ ra $p^2 \nmid S$.** Viết $a = b + pt$ với $t$ nguyên (được vì $p\mid a-b$). Khai triển mỗi số hạng $a^{p-1-j}b^j = (b+pt)^{p-1-j}b^j \equiv b^{p-1-j}b^j + (p-1-j)pt\, b^{p-2-j}b^j \pmod{p^2}$ (khai triển nhị thức, bỏ số hạng có $p^2$ trở lên). Cộng qua $j=0,\dots,p-1$: các số hạng dẫn đầu cộng thành $p\,b^{p-1}$ như trước, và số hạng hiệu chỉnh cộng thành $pt\,b^{p-2}\sum_{j=0}^{p-1}(p-1-j) = pt\,b^{p-2}\cdot\frac{p(p-1)}{2}$, chia hết cho $p^2$ (vì $p$ lẻ, $\frac{p-1}{2}$ là số nguyên, nên hiệu chỉnh này là $p^2\cdot(\text{integer})$, tức $\equiv 0 \pmod{p^2}$). Vậy $S \equiv p\,b^{p-1} \pmod{p^2}$, và vì $p \nmid b$, $p\,b^{p-1}$ chia hết cho $p$ nhưng không cho $p^2$, cho $v_p(S)=1$.

Bước 5: Kết hợp. Từ Bước 2–4, $v_p(a^p-b^p) = v_p(a-b) + v_p(S) = v_p(a-b)+1$. Kết hợp với phép quy ở Bước 1 (và sự kiện $v_p(a^m-b^m)=v_p(a-b)$ khi $p\nmid m$, chứng minh tương tự vì khi đó $S \equiv m\,b^{m-1} \not\equiv 0 \pmod p$), quy nạp theo $v_p(n)$ cho $v_p(a^n-b^n) = v_p(a-b)+v_p(n)$ với mọi số nguyên dương $n$.