# Nâng bậc theo modulo $p$

(Sưu tầm)

Trong bài viết dưới đây mình sẽ trình bày lại một bổ đề liên quan đến nâng bậc đồng dư của đa thức theo modulo $p$.

**Bài toán**: Với mỗi đa thức $\displaystyle P( x)$ hệ số nguyên, chứng minh rằng tồn tại số nguyên dương $\displaystyle M$ đủ lớn sao cho tồn tại vô hạn số nguyên dương $\displaystyle n\in \mathbb{N}$ để thỏa mãn $\displaystyle v_{p}( P( n)) \leqslant M,\forall p\in \mathbb{P}$.

*Lời giải.*

Bài toán là một hệ quả rất hay của bổ đề Hensel. Cụ thể bài toán yêu cầu ta chứng minh rằng, tồn tại một hằng số $\displaystyle M$ để có vô số số $\displaystyle n$ thỏa mãn trong phân tích tiêu chuẩn của $\displaystyle P( n)$, tất cả các số mũ nguyên tố đều bé hơn $\displaystyle M$.

Ta nhắc lại bổ đề sau:

Cho $\displaystyle P( x)$ là một đa thức hệ số nguyên và bất khả quy, xét $\displaystyle q$ là một số nguyên tố cố định bất kỳ. Ký hiệu $\displaystyle a_{n}$ là số nguyên của phương trình đồng dư $\displaystyle p( x) \equiv 0\bmod q^{n}$. Chứng minh rằng tồn tại một số nguyên dương $\displaystyle M$ để dãy $\displaystyle \{a_{n}\}_{n\geqslant M}$ sẽ là dãy tuần hoàn.

Chứng minh kết quả trên như sau:

Trước hết, ta chú ý đến gải thiết $\displaystyle P( x)$ là đa thức bất khả quy, thì khi đó $\displaystyle ( P( x) ,P'( x)) =1$ cho nên tồn tại các đa thức nguyên $\displaystyle a( x) ,b( x)$ để mà
\begin{equation*}
a( x) P( x) +b( x) P'( x) =c
\end{equation*}
với $\displaystyle c\in \mathbb{Z}$. Ta chọn $\displaystyle N$ đủ lớn để $\displaystyle 2^{N} >|c|$ thì khi đó nếu $\displaystyle p^{N} |P( x_{0})$ thì kéo theo $\displaystyle p^{N}\not{\mid } P'( x_{0})$.

Gọi $\displaystyle x_{1} ,x_{2} ,...,x_{m}$ là các nghiệm của phương trình đồng dư
\begin{equation*}
P( x) \equiv 0\ \bmod p^{N}
\end{equation*}

và các nghiệm này cũng thỏa mãn
\begin{equation*}
P'( x_{i})\not{\equiv } 0\bmod p^{N}
\end{equation*}

đúng theo điều kiện của định lý Hensel. Do đó, với mỗi $\displaystyle m\geqslant N$ thì mỗi nghiệm $\displaystyle x_{i}$ này sẽ sinh ra thêm được 1 nghiệm $\displaystyle x'_{i}$ duy nhất thỏa mãn
\begin{equation*}
x_{i} '\equiv x_{i}\bmod p^{N}
\end{equation*}

do các nghiệm này là hữu hạn và về mặt chỉ số là vô hạn, cho nên đến một lúc nào đó dãy sẽ tuần hoàn trở lại.

Như vậy, thực chất từ chứng minh của bài toán trên, ta đã có được rằng, tồn tại một hằng số $\displaystyle N$ sao cho với mỗi số nguyên tố $\displaystyle p$ và $\displaystyle m >N$ thì số nghiệm của phương trình
\begin{equation*}
p( x) \equiv 0\left(\bmod p^{m}\right)
\end{equation*}

sẽ có tối đa là $\displaystyle p^{N}$. Trong đó chú ý rằng điều kiện mà ta cần đó là $\displaystyle P( x)$ phải là một đa thức bất khả quy. Nhưng thực ra ta cũng chỉ cần xét $\displaystyle P( x)$ bất khả quy, trường hợp $\displaystyle P( x)$ khả quy thì ta chỉ việc chia $\displaystyle P$ thành các nhân tử bất khả quy rồi thực hiện tính toán trên đó. Chú ý rằng tính khả quy và bất khả quy ở đây được xét trên trường $\displaystyle \mathbb{Z}[ x]$.

Chọn $\displaystyle p_{1} ,p_{2} ,...,p_{k}$ là các số nguyên tố đầu tiên, thì như nhận xét trene, với mỗi $\displaystyle s\in \mathbb{N} ,s\geqslant N$ thì phương trình đồng dư
\begin{equation*}
P( x) \equiv 0\left(\bmod p^{s}\right)
\end{equation*}

có tối đa $\displaystyle p^{N}$ nghiệm. Bây giờ ta đếm số nguyên của phương trình $\displaystyle P( n) \equiv 0\bmod p_{i}^{s}$ với mỗi $\displaystyle 1\leqslant i\leqslant k$ và $\displaystyle 1\leqslant n\leqslant p_{k}$. Số nghiệm của phương trình này chính là $\displaystyle \varepsilon p_{k}$ trong đó
\begin{equation*}
\begin{aligned}
\varepsilon & :=\frac{p_{1}^{N}}{p_{1}^{s}} +\frac{p_{2}^{N}}{p_{2}^{s}} +\dotsc +\frac{p_{k}^{N}}{p_{k}^{s}}\\
& =\frac{1}{p_{1}^{s-N}} +\frac{1}{p_{2}^{s-N}} +\dotsc +\frac{1}{p_{k}^{s-N}}\\
& < \sum _{j=1}^{\infty }\frac{1}{p_{j}^{s-N}} \ \ \ \ (1).
\end{aligned}
\end{equation*}
vì chú ý rằng với $\displaystyle s$ đủ lớn thì số nghiệm của phương trình $\displaystyle P( n) \equiv 0\bmod p_{i}^{s}$ là một hằng số $\displaystyle C( p_{i})$ cho nên số nghiệm tối đa có thể có với mỗi $\displaystyle p_{i}$ sẽ là $\displaystyle \frac{C( p_{i}) p_{k}}{p_{i}^{s}}$ , tưởng tượng nôm na là ta chia $\displaystyle C( p_{i})$ thành $\displaystyle p_{i}^{s}$ khoảng chẳng hạn và do $\displaystyle p_{i}^{s} >C( p_{i})$ rất nhiều cho nên mỗi khoảng sẽ có độ dài bé hơn 1, cho nên khi lấy đến $\displaystyle p_{k}$ thì có tối đa như trên. Bây giờ, ta cần xem xét lại những giá trị nào không bị phụ thuộc vào $\displaystyle P$. Đầu tiên là $\displaystyle s$ cho nên ta có thể lấy $\displaystyle s\geqslant M$ đủ lớn để cho $\displaystyle \varepsilon < \frac{1}{2}$. Suy ra tồn tại $\displaystyle n\in \left[\frac{p_{k}}{2} ;p_{k}\right]$ sao cho $\displaystyle P( n)$ không là bội của $\displaystyle p_{i}^{M}$ và đồng thời cũng không là bội của bất cứ số nguyên tố $\displaystyle p >p_{k}$ nào vì ta có thể chọn $\displaystyle M\gg \deg P^{100}$ để mà
\begin{equation*}
P( n) < n^{M} < p^{M}
\end{equation*}
Tiếp đó ta cứ chọn $\displaystyle k$ lớn dần thì có $\displaystyle n$ cũng lớn dần theo và có được điều phải chứng minh. Chú ý rằng hằng số $\displaystyle M$ ở đây ta chọn là cố định.

Nếu $\displaystyle P$ là đa thức khả quy thì xét $\displaystyle P( x)$ có dạng
\begin{equation*}
P=P_{1} P_{2} ...P_{l}
\end{equation*}
trong đó $\displaystyle P_{i} \in \mathbb{Z}[ x]$ và đều bất khả quy. Thì ta chỉ cần chọn $\displaystyle \varepsilon < \frac{1}{2l}$ là được.

# Bonus: Số lớp thặng dư modulo $p$ của đa thức

**Bài toán**: Cho $\displaystyle p$ là một số nguyên tố và $\displaystyle f( x)$ là một đa thức hệ số nguyên với bậc $\displaystyle d\geqslant 1$. Giả sử rằng $\displaystyle f( 1) ,f( 2) ,...,f( p)$ cho ta đúng $\displaystyle k$ lớp thặng dư phân biệt theo modulo $\displaystyle p$ với $\displaystyle 1< k< p$. Chứng minh rằng ta có
\begin{equation*}
\frac{p-1}{d} \leqslant k-1\leqslant ( p-1)\left( 1-\frac{1}{d}\right)
\end{equation*}

*Lời giải.*
Trước hết ta chứng minh 2 bổ đề quan trọng sau

Bổ đề 1. Cho đa thức $\displaystyle h( x)$ hệ số nguyên có bậc $\displaystyle m< p-1$ thì khi đó với số nguyên tố $\displaystyle p$ bất kì ta có $\displaystyle p|h( 1) +h( 2) +...+h( p)$.

Thực chất bổ đề trên đến từ kết quả $\displaystyle p|1^{k} +2^{k} +...+( p-1)^{k}$ với $\displaystyle k$ không là bội hoặc ước của $\displaystyle p-1$

Bây giờ, trước khi qua bổ đề 2 ta hãy cùng chứng minh rằng $\displaystyle \frac{p-1}{d} \leqslant k-1$. Thật vậy, ta xét đa thức $\displaystyle g( x) =\prod _{i=1}^{k-1}( f( x) -u_{i})$ trong đó $\displaystyle u_{1} ,u_{2} ,...,u_{k}$ là các lớp thặng dư phân biệt từ $\displaystyle f( 1) ,f( 2) ,...,f( p)$. Ta có thể coi $\displaystyle \{f( 1) ,f( 2) ,...,f( p)\}$ là một đa tập chứa các thặng dư mod $\displaystyle p$. Tiếp theo ta có $\displaystyle g( x)$ sẽ cho ta một trong hai số dư là $\displaystyle 0$ hoặc $\displaystyle ( u_{k} -u_{1}) ...( u_{k} -u_{k-1})$ theo modulo $\displaystyle p$. Do đó $\displaystyle \sum _{i=1}^{p} g( i)$ không chia hết cho $\displaystyle p$ và điều này dẫn tới việc $\displaystyle \deg g\geqslant p-1$ hay $\displaystyle d( k-1) \geqslant p-1$ và ta có điều phải chứng minh.

Bây giờ ta sẽ đến với bổ đề 2.

Bổ đề 2. Xét $\displaystyle \{w_{1} ,w_{2} ,..,w_{s}\}$ là một đa tập( tức là có thể có một số phần tử bằng nhau) theo modulo $\displaystyle p$ với $\displaystyle s\leqslant p-1$. Thì khi ấy tập các lớp thặng dư xác định bởi $\displaystyle r_{j} :=w_{1}^{j} +w_{2}^{j} +...+w_{s}^{j}$ với $\displaystyle j=1,2,...,s$ là xác định duy nhất theo $\displaystyle \{w_{1} ,w_{2} ,..,w_{s}\}$.

Chứng minh như sau

Kết quả này thực chất đến từ một bổ đề khác về tổng lũy thừa của các số thực. Cụ thể trong bài này ta làm như sau. Giả sử phản chứng tồn tại hai tập $\displaystyle \{u_{1} ,u_{2} ,...,u_{s}\}$ và $\displaystyle \{w_{1} ,w_{2} ,...,w_{s}\}$ sao cho các số $\displaystyle r_{1} ,r_{2} ,...,r_{s}$ cho cùng các lớp thặng dư theo modulo $\displaystyle p$. Ta có thể loại đi các phần tử trùng nhau để cho hai tập $\displaystyle \{u_{i}\} \cap \{w_{i}\} =\emptyset$. Các số $\displaystyle r_{1} ,r_{2} ,...$ theo modulo $\displaystyle p$ được xác định duy nhất bởi các đa thức đối xứng
\begin{equation*}
\sigma _{0} =1,\sigma _{k} =\sum _{i_{1} < i_{2} < ...< i_{k}} w_{i_{1}} w_{i_{2}} ...w_{i_{k}}
\end{equation*}

suy ra từ đẳng thức
\begin{equation*}
k\sigma _{k} =\sum _{i=1}^{k}( -1)^{i-1} \sigma _{k-1} r_{i}
\end{equation*}

trong khi đó $\displaystyle ( -1)^{i} \sigma _{i}$ chính là hệ số trong đa thức $\displaystyle ( x-w_{1})( x-w_{2}) ...( x-w_{s})$ điều này chứng tỏ rằng các lớp thặng dư theo modulo $\displaystyle p$ của hai đa thức $\displaystyle P( X) =\prod ( X-u_{i})$ và $\displaystyle Q( x) =\prod ( X-w_{i})$ là phân biệt. Vậy giả sử phản chứng là sai và ta có điều phải chứng minh

Bây giờ quay lại bài toán, ta chứng minh $\displaystyle k-1\leqslant ( p-1)\frac{d-1}{d}$

Ta có multiset $\displaystyle \{f( 1) ,f( 2) ,...,f( p)\}$ có thể được viết lại thành
\begin{equation*}
A=(\{0,1,...,p-1\} \backslash \{w_{1} ,w_{2} ,...,w_{s}\}) \cup \{u_{1} ,u_{2} ,...,u_{s}\}
\end{equation*}
trong đó $\displaystyle w_{i}$ là các lớp thặng dư mà $\displaystyle f$ không nhận và $\displaystyle u_{i}$ là các thặng dư mà xuất hiện nhiều hơn một lần trong $\displaystyle \{f( 1) ,...,f( p)\}$

Ký hiệu $\displaystyle s:=p-ks\leqslant p-2$ và giả sử \ $\displaystyle k-1 >( p-1)\frac{d-1}{d}$ thì khi đó $\displaystyle ds< p-1$ suy ra ta có từ bổ đề 1 :
\begin{equation*}
\sum _{a\in A} a^{j} =\sum _{k=1}^{p}( f( k))^{j} \equiv 0(\bmod p)
\end{equation*}
với mọi $\displaystyle j=1,...,s$ nhưng ta lại có
\begin{equation*}
\sum _{a\in A} a^{j} \equiv \sum _{i=1}^{p} i^{j} +\sum _{i=1}^{s} w_{i}^{j} -\sum _{i=1}^{s} u_{i}^{j} ,j\leqslant p-2
\end{equation*}
suy ra $\displaystyle \{u_{1} ,u_{2} ,...,u_{s}) \equiv \{w_{1} ,w_{2} ,...,w_{s}\}$ nhưng đây là điều mâu thuẫn cho nên ta có điều phải chứng minh.