Cho đa thức hệ số nguyên $P(x)$ và số nguyên tố $p$, ta nói $P(x)$ là $p$-tốt nếu mọi số nguyên có thể thu được từ 0 sau hữu hạn các phép thay sau: thay $a$ bởi $P(a)$, hoặc thay $a$ bởi số nguyên $b$ (nếu tồn tại) sao cho $P(b)\equiv a(\mathrm{mod}p)$.

a) Hỏi có bao nhiêu đa thức 3-tốt có bậc 99 và mọi hệ số thuộc $\{1;2;\dots ;99\}$?

b) Chứng minh rằng với mọi đa thức hệ số nguyên $P(x)$ có bậc 2, tồn tại vô hạn số nguyên tố $p$ sao cho $P(x)$ không là $p$-tốt.

Lời giải.

a) Gọi $S$ là tập các số nguyên thu được từ 0.

$P(x)$ là đa thức 3-tốt $⟺S=\mathbb{Z}$.

Quy tắc sinh phần tử của tập $S$:

- (Quy tắc A): $u\in S⟹P(u)\in S$.
- (Quy tắc B): $v\in S$ và $P(u)\equiv v(\mathrm{mod}3)⟹u\in S$.

Nhận xét 1: Nếu $u\in S$ thì mọi số nguyên $x$ thỏa mãn $x\equiv u(\mathrm{mod}3)$ cũng thuộc $S$.

Chứng minh: Với $P(x)\in \mathbb{Z}[x]$, ta có tính chất cơ bản: $x\equiv u(\mathrm{mod}3)⟹P(x)\equiv P(u)(\mathrm{mod}3)$. Vì $u\in S\stackrel{\text{Quy ta˘ˊc A}}{\to }P(u)\in S$. Lại có $P(x)\equiv P(u)(\mathrm{mod}3)\stackrel{\text{Quy ta˘ˊc B}}{\to }x\in S$.

Nhận xét 1 cho thấy để $S=\mathbb{Z}$, tập $S$ chỉ cần chứa đủ 3 đại diện có số dư là $0,1,2$ khi chia cho 3.

Nhận xét 2: Có $3^3=27$ bộ số dư $(P(0),P(1),P(2))$ modulo 3.

Tập $S$ (xuất phát từ 0) không thể sinh ra toàn bộ $\mathbb{Z}⟺$ tập $\{0,1,2\}$ bị phân hoạch thành các tập con $X$ rời nhau thỏa mãn: $x\in X⟺P(x)\in X$.

Các trường hợp thất bại này bao gồm:

- Phân hoạch thành 3 tập $\{0\},\{1\},\{2\}$:

Vì $0\in \{0\}⟹P(0)\in \{0\}⟹P(0)\equiv 0(\mathrm{mod}3)$.

Vì $1\in \{1\}⟹P(1)\in \{1\}⟹P(1)\equiv 1(\mathrm{mod}3)$.

Vì $2\in \{2\}\Rightarrow P(2)\in \{2\}\Rightarrow P(2)\equiv 2(\mathrm{mod}3)$.

Suy ra: $P(x)\equiv x(\mathrm{mod}3),\forall x\in \{1,2,3\}$.

$\Rightarrow$ Có 1 trường hợp.

• Phân hoạch thành 2 tập $\{a\}$ và $\{b,c\}$ (với $\{a,b,c\}=\{0,1,2\}$):

Vì $a\in \{a\}\Rightarrow P(a)\in \{a\}\Rightarrow P(a)\equiv a(\mathrm{mod}3)$.

Vì $b\in \{b,c\}\Rightarrow P(b)\in \{b,c\}\Rightarrow P(b)\equiv b$ hoặc $P(b)\equiv c(\mathrm{mod}3)$.

Vì $c\in \{b,c\}\Rightarrow P(c)\in \{b,c\}\Rightarrow P(c)\equiv b$ hoặc $P(c)\equiv c(\mathrm{mod}3)$.

Có 3 cách chọn $a$. Với mỗi $a$, có $2^2=4$ cách chọn ảnh cho $P(b)$ và $P(c)$. Trừ đi 1 trường hợp $P(b)\equiv b,P(c)\equiv c$ (đã đếm ở trên). $\Rightarrow$ Có $3\times (4-1)=9$ trường hợp.

Suy ra số bộ $(P(0),P(1),P(2))$ thành công (thỏa mãn $S=\mathbb{Z}$) là: $27-1-9=17$.

Mặt khác, với $x\in \{1,2\}$, ta có $x^2\equiv 1(\mathrm{mod}3)\Rightarrow x^{lẻ}\equiv x$ và $x^{ch\widetilde{\stackrel{˘}{a}}n}\equiv 1(\mathrm{mod}3)$. Do đó:

$$P(x)\equiv c_0+\left(\sum _{klẻ}{c}_k\right)x+\left(\sum _{kch\widetilde{\stackrel{˘}{a}}n\ge 2}{c}_k\right)(\mathrm{mod}3)$$

Đặt $A=c_0$, $B={\sum }_{klẻ}{c}_k$ và $C={\sum }_{kch\widetilde{\stackrel{˘}{a}}n\ge 2}{c}_k$. Ta có hệ:

$$\{\begin{array}{l}P(0)\equiv A(\mathrm{mod}3)\\ P(1)\equiv A+B+C(\mathrm{mod}3)\\ P(2)\equiv A+2B+C\equiv A-B+C(\mathrm{mod}3)\end{array}$$

Hệ phương trình này xác định duy nhất bộ dư $(A,B,C)(\mathrm{mod}3)$ từ bộ $(P(0),P(1),P(2))$. Suy ra có đúng 17 bộ $(A,B,C)$ thỏa mãn.

Cuối cùng, ta đếm số cách chọn hệ số $c_k\in \{1,2,\dots ,99\}$. Tập này có 99 số, chia đều mỗi loại số dư 0, 1, 2 có 33 số. Với một bộ $(A,B,C)$ cố định:

• $c_0\equiv A(\mathrm{mod}3)$: Có 33 cách chọn.

• Tổng của 50 hệ số bậc lẻ $\equiv B(\mathrm{mod}3)$: Chọn 49 hệ số đầu tiên tùy ý (có $99^{49}$ cách). Hệ số cuối cùng bị buộc phải nhận một số dư duy nhất để tổng bằng $B$ (có 33 cách chọn giá trị thỏa mãn số dư đó). Nhóm này có $99^{49}\cdot 33$ cách.

• Tổng của 49 hệ số bậc chẵn $\equiv C(\mathrm{mod}3)$: Tương tự, chọn tùy ý 48 số đầu, số cuối bị cố định số dư. Nhóm này có $99^{48}\cdot 33$ cách.

Số lượng đa thức tạo thành cho một bộ $(A,B,C)$ là:

$$33\times (99^{49}\cdot 33)\times (99^{48}\cdot 33)=33^3\cdot 99^{97}$$

Tổng số đa thức 3-tốt là: $\boxed{17\cdot 33^3\cdot 99^{97}}$.

b) Đặt $\phi (r)=P(r)\mathrm{mod}p$. Với $u\in S$ (tập sinh từ 0), dãy lặp $u,\phi (u),{\phi }^2(u),\dots$ luôn tuần hoàn về một chu trình cố định - gọi là chu trình tối hạn của $u$; quy nạp trực tiếp trên hai quy tắc sinh của đề bài cho thấy mọi phần tử của $S$ có cùng chu trình tối hạn với 0. Nếu tồn tại hai chu trình tối hạn phân biệt, các điểm trên chu trình thứ hai không thuộc $S$, do đó $P$ không $p$-tốt.

Ta phát biểu và chứng minh các bổ đề sau:

Bổ đề 1

Nếu hàm số $f\in \mathbb{Z}[x]$ không là hàm hằng, thì có vô hạn số nguyên tố $p$ để phương trình $f(x)\equiv 0(\mathrm{mod}p)$ có nghiệm nguyên.

Chứng minh: Nếu $f(0)=0$ thì hiển nhiên $x=0$ là nghiệm với mọi $p$.

Giả sử $f(0)=c_0\ne 0$ và chỉ có hữu hạn $p_1,\dots ,p_k$ thỏa mãn, đặt $N=c_0{p}_1\cdots p_k$. Do các số hạng có bậc $\ge 1$ trong $f(Nt)$ đều chia hết cho $N$, ta có thể viết $f(Nt)$ dưới dạng $c_0(1+N.M(t))$ (với $t\in \mathbb{Z}$). Thừa số sau nguyên tố cùng nhau với mọi $p_i$, và ta có thể chọn $t$ đủ lớn để nó có giá trị tuyệt đối lớn hơn 1. Khi đó nó có ước nguyên tố mới $q\notin \{p_i\}$ — mâu thuẫn. Ta có điều phải chứng minh.

Bổ đề 2

Cho $f\in \mathbb{Z}[x]$ là hàm số bậc 2 có $\Delta B^2-4AC\ne 0$. Khi đó có vô hạn số nguyên tố $p$ để phương trình $f(x)\equiv 0(\mathrm{mod}p)$ có hai nghiệm phân biệt.

Chứng minh: Theo Bổ đề 1, có vô hạn $p$ để $f$ có một nghiệm $x_0\mathrm{mod}p$. Ta loại bỏ hữu hạn giá trị $p\mid A\Delta$. Vì $p\nmid A$ và $x_0$ là nghiệm, phép chia đa thức trong ${\mathbb{F}}_p[x]$ cho ta $f(x)\equiv A(x-x_0)(x-x_1)(\mathrm{mod}p)$ với $x_1\in {\mathbb{F}}_p$ nào đó; theo hệ thức Viète ta được $x_0+x_1\equiv -B/A(\mathrm{mod}p)$

Giả sử $x_1\equiv x_0(\mathrm{mod}p)$, khi đó $2x_0\equiv -B/A\Rightarrow 2A{x}_0+B\equiv 0(\mathrm{mod}p)$. Mà $4A\cdot f(x)=(2Ax+B{)}^2-\Delta$, thay $x=x_0$ ta có được $\Delta \equiv 0(\mathrm{mod}p)$ — vô lí. Ta có điều phải chứng minh.

Trở lại bài toán, đặt $Q(x)=P(x)-x=a{x}^2+(b-1)x+c$, $\Delta =(b-1{)}^2-4ac$.

Ta thấy $Q(x)\equiv 0(\mathrm{mod}p)⟺P(x)\equiv x(\mathrm{mod}p)$, do đó các nghiệm của $Q(x)$ chính là các điểm bất động của hàm $\phi$ kể trên. Xét 2 trường hợp:

- $\Delta \ne 0$. Theo Bổ đề 2, có vô hạn số nguyên tố $p$ để $Q$ có 2 nghiệm phân biệt $x_1\ne x_2$ sao cho $Q(x_1)\equiv Q(x_2)\equiv 0(\mathrm{mod}p)$. Đa thức $P(x)$ có 2 điểm bất động, và do đó nó không $p$-tốt.

- $\Delta =0$. Lúc này $Q(x)=a(x-r{)}^2$ với $r=\frac{1-b}{2a}\in \mathbb{Q}$. Với $p\nmid 2a$, đặt $y=x-r$ ta được $\phi (y)=a{y}^2+y\mathrm{mod}p$ với điểm bất động duy nhất là $y=0$.

Ta tính được $\phi (\phi (y))-y=a{y}^2(a^2{y}^2+2ay+2)$. Xét $H(y)=a^2{y}^2+2ay+2\in \mathbb{Z}[y]$ có $\Delta =-4a^2\ne 0$ (vì $a\ne 0$), áp dụng Bổ đề 2 cho thấy có vô hạn số nguyên tố $p$ sao cho $H$ có 2 nghiệm phân biệt $y_1\ne y_2$ và đều khác 0 (theo hệ thức Viète thì $y_1{y}_2=\frac{2}{a^2}\ne 0$).

Với modulo các số nguyên tố $p$ kể trên, ta có $\phi (\phi (y))\equiv y$ nên $\phi (\phi (\phi (y)))\equiv \phi (y)$, nên $\phi (y)$ cũng là một trong các nghiệm $\{0;y_1;y_2\}$ của phương trình $\phi (\phi (y))-y\equiv 0(\mathrm{mod}p)$.

Mà $\phi (y_1)\ne y_1$ (do $y_1$ không bất động) và $\phi (y_1)\ne 0$ (khi đó $\phi (\phi (y_1))\equiv 0\ne y_1$), ta bắt buộc có $\phi (y_1)\equiv y_2$, và chứng minh tương tự ta có $\phi (y_2)\equiv y_1$.

Như vậy, tồn tại chu trình có độ dài 2 là $\{y_1;y_2\}$ khác 0 và phân biệt với điểm bất động $\{0\}$, suy ra $P(x)$ có 2 chu trình tối hạn và do đó $P$ không $p$-tốt.

Bài toán đã được giải quyết.