Bài viết này, viết về một kỹ năng cơ bản nhưng quan trọng ở trong Số Học. Đó là phép nâng bậc đồng dư. Nội dung bài viết bắt đầu từ một bài toán cũ kỹ và kinh điển, sau đó là sự khái quát hóa bài toán đó.

Mở đầu

Ở Số Học sơ cấp, một vấn đề cơ bản thường xuyên chúng ta phải xử lý, đó là xét số dư trong phép chia cho một số nguyên dương $m$ cho trước. Thường thì khi đối diện bài toán đó, trừ những trường hợp quá tầm thường, thì một ý tưởng rất bài bản là phân tích $m$ ra thừa số nguyên tố (hành vi đó được bảo kê nhờ định lý cơ bản của Số Học). Sau đó, bài toán quy về xét đồng dư theo các mod ${p^k}$, trong đó $p$ là ước nguyên tố của $m$ còn $k$ là số mũ của $p$ khi phân tích $m$ ra thừa số nguyên tố. Nếu ta xử lý được các vấn đề ở khâu đó, chúng ta sẽ có được câu trả lời ở mod $m$ nhờ ánh xạ phục dựng ở định lý CRT.

Vấn đề là, để xử lý theo mod $p^k$ như đã nói ở trên với $k>1$, một tư duy tự nhiên là đầu tiên ta phải xử lý được mod $p$ đã. Sau đó cần những kỹ năng, để nâng dần lên mod $p^2$, và lần hồi dần lên mod $p^k$.

Đại khái tư tưởng là vậy, và để tránh sự mông lung, ta cùng xem xét một ví dụ

Bài toán (Japan MO 1999). Cho $n$ là một số nguyên dương lớn hơn $1$. Chứng minh rằng luôn tồn tại số nguyên $x$ để $$v_3\left(x^3+17\right)=n.$$ Nhận xét. Bản chất bài toán là cần chỉ ra sự tồn tại của một dãy nguyên $\left(x_n\right)_{n\in\mathbb N^*}$ để $$v_3\left(x_n^3+17\right)=n+1,\;\forall\,n\in\mathbb{N}^.$$
Để ý rằng, dãy nguyên $\left(x_n\right)_{n\in\mathbb N^*}$ như vậy, trước tiên cần đảm thỏa điều kiện $$3\mid\left(x_n^3+1\right),\;\forall\,n\in\mathbb{N}^*.$$ Từ đó thấy ngay là với mỗi $n$ thì $x_n\equiv 1\pmod 3$, ta đặt $x_n=3t_n+1$ với $t_n\in\mathbb{Z}$, và quy về \[n + 1 = {v_3}\left( {{{\left( {3{t_n} + 1} \right)}^3} + 17} \right) = {v_3}\left( {9\left( {3t_n^3 + 3t_n^2 + {t_n} + 2} \right)} \right),\;\forall {\mkern 1mu} n \in \mathbb{N}^*.\]

Xét $f(x)=3x^3+3x^2+x+2$, đưa về việc chỉ ra sự tồn tại của dãy nguyên $\left(t_n\right)_{n\in\mathbb N^*}$ để $$v_3\left(f(t_n)\right)=n,\;\forall\,n\in\mathbb{N}.$$ Với $n=0$, ta chọn $t_0=0$, với $n=1$ ta chọn $t_1=4$, còn với $n=2$ ta chọn $t_2=1$ là xong. Bây giờ với $n$ là số nguyên dương nào đó ($n\ge 2$), giả sử đã sẵn có $t_n$ để $v_3\left(f\left(t_n\right)\right)=n$, ta cần xây dựng được số nguyên $t_{n+1}$ để $$v_3\left(f\left(t_ {n+1}\right)\right)=n+1.$$ Nếu điều đó xảy đến, thì phải có $$f\left(t_{n+1}\right)\equiv f\left(t_n\right)\equiv 0\pmod{3^n}.$$ Vì vậy, với để ý về tính chất của đa thức hệ số nguyên $f(x)$, ta sẽ chọn $t_{n+1}$ đảm bảo $$t_{n+1}\equiv t_n\pmod{3^n},\;(1).$$
Ta đặt $9t_{n}^2+6t_n+1=\lambda_n$ và có được biến đổi sau \[f\left( {{t_{n + 1}}} \right) = f\left( {{t_n}} \right) + 3\left(t_{n+1}-t_n\right)^2\left(t_{n+1}+2t_n+1\right)+ \left( {{t_{n + 1}} – {t_n}} \right)\lambda_n.\].

Giờ ta để ý rằng việc $v_3\left(f\left(t_{n+1}\right)\right)=n+1$, tương đương với có $u\in{1,\,2}$ để
$$f\left(t_{n+1}\right)\equiv 3^{n+1}u\pmod{3^{n+2}}.$$
Cho nên ta cần chọn được $t_{n+1}$ nguyên đảm bảo được điều đó và cả $(1)$. Cũng để ý rằng do đã sẵn có $v_3\left(f\left(t_n\right)\right)=n$, nên sẵn có $s\in\mathbb{Z},\,3\nmid s$ để khả diễn
$$f\left(t_n\right)=3^ns.$$
Vì $3^{n+2}\mid 3^{2n}\mid \left(t_{n+1}-t_n\right)^2$ do $(1)$ và việc $n\ge 2$, nên ta cần tìm $t_{n+1}$ thỏa mãn
\[{3^n}u \equiv {3^{n+1}}s + \left( {{t_{n + 1}} – {t_n}} \right){\lambda_n}\pmod{3^{n+2}}.\] Hãy tạm từ chối cái đòi hỏi rắc rối của đồng dư trên, thay vào đó, ta hãy tưởng tưởng là phải giải phương trình bậc nhất (ẩn $x$ ở trên $\mathbb{R}$) sau \[{3^{n+1}}u = {3^n}s + \left( {x – {t_n}} \right){\lambda _n}.\] Thì rõ ràng quá đơn giản phỏng ạ? Bởi vì nếu như là $\lambda_n\ne 0$, ta có luôn \[x = {t_n} + \left( {{3^{n + 1}}u – {3^n}s} \right)\lambda _n^{ – 1}.\]Cái nghiệm ngon ăn được lôi cổ ra ngay đó, là bởi vì mọi phần tử khác $0$ ở trên $\mathbb R$ đều có một nghịch đảo (khả nghịch). Bây giờ, ta quay về đồng dư dở dang phía trên, và để ý \[\gcd \left( {{\lambda _n},{\mkern 1mu} 3} \right) = \gcd \left( {9t_n^2 + 6{t_n} + 1,{\mkern 1mu} 3} \right) = \gcd \left( {3,{\mkern 1mu} 1} \right) = 1.\]
Vậy, $\gcd\left(\lambda_n,\,3^{n+2}\right)=1$, và do đó sẽ tồn tại $\gamma\in\mathbb Z$ để $\lambda_n\gamma\equiv 1\pmod{3^{n+1}}$. Đến đây chọn $$t_{n+1}=t_n+\left( {{3^{n + 1}}u – {3^n}s} \right)\gamma.$$ Để ý là $(1)$ cũng tự được thỏa mãn nhờ cách chọn đó

Từ những phân tích-nhận xét như đã, ta có lời giải cho bài toán như sau

Lời giải. Xét đa thức hệ số nguyên $f(t)=3t^3+3t^2+t+2$, ta sẽ chứng minh là tồn tại dãy nguyên $\left(t_n\right)_{n\in\mathbb N^*}$ để với mỗi số tự nhiên $n$ ta lại có $$v_3\left(f\left(t_n\right)\right)=n.$$ Thật vậy, với $n=0$ ta chọn $t_0=0$, với $n=1$ ta chọn $t_1=4$, còn với $n=2$ ta chọn $t_2=1$ là xong. Bây giờ với $n$ là số nguyên dương nào đó ($n\ge 2$), giả sử như ta đã sẵn có một số nguyên $t_n$ để $v_3\left(f\left(t_n\right)\right)=n$, xét $\lambda_n=9t_n^2+6t_n+1$ có $\lambda_n\equiv 1\pmod 3$ nên có được $$\gcd\left(\lambda_n,\,3^{n+2}\right)=1.$$ Vậy, sẽ tồn tại $\gamma\in\mathbb Z$ là nghịch đảo mod $3^{n+2}$ của $\lambda_n$, tức là xảy đến đồng dư $$\lambda_n\gamma\equiv 1\pmod{3^{n+2}}.$$ Bây giờ ta đi chọn $$t_{n+1}=t_n+\gamma\left(3^{n+1}-f\left(t_n\right)\right) .$$
Thì vì $v_3\left(f\left(t_n\right)\right)=n$ nên $3^n\mid f\left(t_n\right)$, kéo theo
$$t_{n+1}\equiv t_n\pmod{3^n},\;(1).$$
Lại để ý \[f\left( {{t_{n + 1}}} \right) = f\left( {{t_n}} \right) + 3\left(t_{n+1}-t_n\right)^2\left(t_{n+1}+2t_n+1\right)+ \left( {{t_{n + 1}} – {t_n}} \right){\lambda n},\;(2).\] Nên từ $(1)$ và $n\ge 2$ ta có $3^{n+2}\mid 3^{2n}\mid\left(t_{n+1}-t_n\right)^2$ kết hợp với $(2)$ cho ta
$$f\left(t_{n+1}\right)\equiv f\left(t_n\right)+\lambda_n\gamma \left(3^{n+1}-f\left(t_n\right)\right)\equiv 3^{n+1}\pmod{3^{n+2}}.$$
Điều đó dẫn đến là $v_3\left(f\left(t_{n+1}\right)\right)=n+1$. Và từ đó, khẳng định phía đầu lời giải đúng theo nguyên lý quy nạp. Lúc này cứ với mỗi số nguyên dương $n\ge 2$, ta chọn
$$x_n=3t_{n-2}+1.$$
Để mà thấy $x_n\in\mathbb Z$ và đồng thời
$$v_3\left(x_n^3+17\right)=v_3\left(9f\left(t_{n-2}\right)\right)=2+v_3\left(f\left(t_{n-2}\right)\right)=2+(n-2)=n.$$
Cho ta hoàn tất lời giải bài toán.

$\blacksquare$

Men tựa theo con đường tìm kiếm lời giải ở phần đầu, với những nhận xét nảy chồi như đã, chúng ta sẽ khái quát hóa bài toán ở phần sau đây.

Tổng quát bài Japan MO 1999

Từ quá trình xử lý bài Japan MO 1999 như đã, ta thấy rằng hoàn toàn có thể thay thế cái đa thức $3x^3+3x^2+x+2$ bởi một đa thức có hệ số nguyên $f(x)$, thay $3$ bởi một số nguyên tố $p$ nào đó. Cốt sao chúng cần thỏa mãn là tồn tại một số nguyên $a$ để $v_p\left(f(a)\right)\ge 2$ và đồng thời $p\nmid f^\prime(a)$. Cụ thể, đó là bài toán như sau đây

Bài toán. Cho $p$ là một số nguyên tố, $a$ là một số nguyên còn $f$ là một đa thức hệ số nguyên thỏa mãn điều kiện $p\nmid f^\prime (a)$ đồng thời $v_p\left(f(a)\right)=m$ với $m\ge 2$. Chứng minh rằng, tồn tại dãy số nguyên $\left(x_n\right)_{n\in\mathbb N}$ để với mỗi số nguyên dương $n$ thỏa mãn $n\ge m$ ta lại có $$v_p\left(f\left(x_n\right)\right)=n.$$

Trước khi xử lý bài toán này, ta cần đến bổ đề sau

Bổ đề. Cho $P$ là một đa thức hệ số nguyên, $m$ là số nguyên dương còn $a$ là một số nguyên, khi đó cứ với mỗi số nguyên $x$ thỏa mãn $x\equiv a\pmod m$ ta lại có $$P(x)\equiv P(a)+\left(x-a\right)P^\prime(a)\pmod{m^2}.$$ Chứng minh. Bởi vì đa thức là tổng của các đơn thức, và phép lấy đạo hàm là phép tuyến tính, cho nên thực ra ta chỉ cần chứng minh với trường hợp $P(x)=x^n$, trong đó $n$ là số nguyên dương, nói khác đi ta cần chỉ ra
$$x^n\equiv a^n+na^{n-1}(x-a)\pmod{m^2}.$$
Giờ để ý đẳng thức $x^n\equiv a^n+na^{n-1}(x-a)+(x-a)\lambda$, trong đó thì \[\lambda = – n{a^{n – 1}} + \sum\limits_{0 \le j \le n – 1} {{x^j}{a^{n – 1 – j}}} .\] Nên lại có \[\lambda = \sum\limits_{0 \le j \le n – 1} {\left( {{x^j}{a^{n – 1 – j}} – {a^n}} \right)} = \sum\limits_{0 \le j \le n – 1} {\left( {{x^j} – {a^j}} \right){a^{n – 1 – j}}} .\]
Vậy $\lambda$ có nhân tử $x-a$, nhân tử đó khả ước $m$ do giả thiết, cho ta hoàn tất chứng minh.

$\square$

Bây giờ ta đi đến lời giải bài toán tổng quát đã nêu

Lời giải. Sẵn chọn luôn được là $x_m=a$, bây giờ giả sử với số nguyên dương $n$ nào đó thỏa mãn $n\ge m$, đã sẵn chọn được số nguyên $x_n$ để
$$x_n\equiv a\pmod p,\; v_p\left(f\left(x_n\right)\right)=n.$$
Bởi vì đạo hàm của một đa thức hệ số nguyên, cũng ắt là đa thức hệ số nguyên, cho nên $$f^\prime\left(x_n\right)\equiv f^\prime(a)\pmod p.$$
Từ đây có $\gcd\left(f^\prime\left(x_n\right),\,p\right)=1$, cho nên tồn tại số nguyên $\lambda$ để $$\gamma f^\prime\left(x_n\right)\equiv 1\pmod{p^{2n}}.$$ Giờ ta chọn $$x_{n+1}=x_n+\left(p^{n+1}-f\left(x_n\right) \right)\gamma.$$ Thì vì là $v_p\left(f\left(x_n\right)\right)=n$ hệ dẫn đến $p^n\mid f\left(x_n\right)$, cho ta $$x_{n+1}\equiv x_n\pmod{p^n}.$$ Áp dụng bổ đề phía trên, ta có \[\begin{align*} f\left( {{x_{n + 1}}} \right) &\equiv f\left( {{x_n}} \right) + \left( {{x_{n + 1}} – {x_n}} \right){f^\prime }\left( {{x_n}} \right)\pmod{p^{2n}}\\ &\equiv f\left( {{x_n}} \right) + \left( {{p^{n + 1}} – f\left( {{x_n}} \right)} \right)\gamma {f^\prime }\left( {{x_n}} \right)\pmod{p^{2n}}\\ &\equiv {p^{n + 1}}\pmod{p^{2n}}. \end{align*}\]

Mà $n\ge 2$ nên $p^{n+2}\mid p^{2n}$, từ đó có
\[f\left( {{x_{n + 1}}} \right) \equiv {p^{n + 1}}\pmod{p^{n+2}}.\] Cho ta $v_p\left(f\left(x_{n+1}\right)\right)=n+1$. Và như thế, theo nguyên lý quy nạp, ta có được điều phải chứng minh.

$\blacksquare$