Thế nào là ước nguyên tố

Ước nguyên tố của một dãy nguyên

in Số Học | No comments

Rất nhiều vấn đề trong Số Học liên quan đến sự tồn tại vô hạn các số nguyên tố trong một dãy nguyên. Ví dụ như định lý Dirichlet, các số nguyên tố Fermat hay các số nguyên tố Mersene. Một vấn đề đơn giản hơn, đó là nói đến các ước nguyên tố của phần tử trong dãy. Bài viết này bàn về khái niệm ước nguyên tố của một dãy số nguyên, và tập các ước nguyên tố đó. Phạm vi bài viết là ở mức độ các bài toán sơ cấp, mặc dù vấn đề trong bài vẫn được nghiên cứu ở lý thuyết Số cao cấp.

1. Các quy ước và ký hiệu

Suốt bài viết này, tôi sử dụng các ký hiệu với ý nghĩa được quy ước thống nhất như sau:

1. $\gcd[a,\,b]$: Ước số chung lớn nhất của $a,\,b\in\mathbb Z$.
2. $m\nmid a$: Số nguyên $a$ không chia hết cho số nguyên $m$ [với $m\ne 0$].
3. $\left\lfloor {x} \right\rfloor$: Số nguyên lớn nhất không vượt quá số thực $x$ [phần nguyên của $x$].
4. $\varphi[m]$: Phi hàm Euler.
5. $v_p[m]$: Hàm định giá p-adic.
6. $\mathbb P$: Tập hợp chứa tất cả các số nguyên tố.

2. Các kiến thức cơ sở

Chúng ta quan tâm đến khái niệm sau.

Định nghĩa. Cho dãy số nguyên $\{a_n\}_{n\in\mathbb Z^+}$, số nguyên tố $p$ được gọi là ước nguyên tố của dãy khi và chỉ khi tồn tại chỉ số $m$ sao cho $p\mid a_m$.

Trong suốt bài viết này, với $\{a_n\}_{n\in\mathbb Z^+}$ là một dãy số nguyên thì tập hợp các ước nguyên tố của dãy $\{a_n\}_{n\in\mathbb Z^+}$ được ký hiệu là $\mathfrak P[a_n]$. Còn với một tập con $S$ của $\mathbb Z$ thì $\mathfrak P[S]$ được hiểu là tập các số nguyên tố là ước của một phần tử nào đó trong $S$.

Để minh họa cho định nghĩa nêu trên, ta xét một số ví dụ sau.

Ví dụ 1.Với dãy các luỹ thừa của 2 là $a_n=2^{n-1}$, khi đó chỉ có 2 là ước nguyên tố của dãy. Nói khác đi $\mathfrak P\left[2^{n-1}\right]=\{2\}.$

Ví dụ 2.Với dãy các luỹ thừa của 2 là $a_n=2^{n}-1$. Khi đó mọi ước nguyên tố của dãy là các số nguyên tố lẻ, nói khác đi $\mathfrak P\left[2^{n}-1\right]=\mathbb P\setminus\{2\}.$ Lý do là bởi vì $2\nmid \left[2^n-1\right]\;\forall\,n\in\mathbb Z^+$ và nếu $p$ là số nguyên tố lẻ thì theo định lý Fermat bé ta có\[p\mid\left[2^{p-1}-1\right].\]

Ví dụ 3.Xét dãy số nguyên sau đây$$a_n=2^n+3^n+6^n-1.$$Dễ kiểm tra rằng $6\mid a_2$, do vậy $2,\,3$ đều là các phần tử của $\mathfrak P\left[a_n\right]$, thêm nữa với $p\in\mathbb P\setminus\{2,\,3\}$ thì theo định lý Fermat bé ta có\[6{a_{p 2}} = {3.2^{p 1}} + {2.3^{p 1}} + {6^{p 1}} 6 \equiv 3 + 2 + 1 6 \equiv 0\pmod p.\]Điều đó cho thấy rằng $$\mathfrak P\left[a_n\right]=\mathbb P.$$ Bạn đọc hẳn nhận ra vấn đề với dãy số ở ví dụ này, chính là bài toán IMO 2005.

Ngoài khái niệm về ước nguyên tố của dãy nguyên và tập ước nguyên tố, để thuận tiện cho việc theo dõi bài viết. Tôi nhắc lại một vài định lý và bổ đề Số Học hay sử dụng ở đây.

Định lý Euler. Với $\varphi [m]$ là số các số nguyên dương không vượt quá $m$ và nguyên tố cùng nhau với $m$, khi đó\[a^{\varphi m}\equiv 1\pmod m.\]

Từ định lý Euler, ta có một hệ quả đáng chú ý sau đây.

Hệ quả.Cho $k$ số nguyên khác $0$ là $a_1,\,a_2,\,\ldots,\,a_k$ và một số nguyên dương $m>1$, khi đó tồn tại $N$ đủ lớn để\[a_i^{N+n\varphi[m]}\equiv a_i^N\pmod m\quad\forall\,i=\overline{1,\,k},\;n\in\mathbb Z^+.\]

Chứng minh.Giả sử ta có phân tích ra thừa số nguyên tố của $m$ là\[m = \prod\limits_{j = 1}^t {p_j^{{k_j}},\;{p_j} \in \mathbb P,\;{p_1} < {p_2} < \ldots < {p_t},\;{k_j} \in {\mathbb Z^ + }.} \]Giả sử $N=\max\left\{k_j:\;j=\overline{1,\,t}\right\}$, khi đó.

1. Nếu $p_j\nmid a_i$ thì từ $p_j^{k_j}\mid m$, vì phi hàm Euler có tính chất nhân tính nên $\varphi\left[p_j^{k_j}\right]\mid\varphi[m]$ sử dụng định lý Euler ta có\[a_i^{\varphi[m]}\equiv 1\pmod{p_j^{k_j}}.\]Từ đó mà có được\[a_i^{N+n\varphi[m]}\equiv a_i^N\pmod{p_j^{k_j}}.\]
2. Nếu $p_j\mid a_i$ thì do $N\ge k_j$ nên \[a_i^{N+n\varphi[m]}\equiv a_i^N\equiv 0\pmod{p_j^{k_j}}.\]

Từ $p_j^{k_j}\mid \left[a_i^{N+n\varphi[m]}- a_i^N\right]\;\forall\,j=\overline{1,\,t}$ để có $m\mid \left[a_i^{N+n\varphi[m]}- a_i^N\right]\;\forall\,i=\overline{1,\,k}$.

$\square$

Với số nguyên tố $p$ bất kỳ, ta có $\varphi[p]=p-1$. Vì vậy, trong trường hợp $m=p$ thì định lý Euler trở thành định lý sau đây.

Định lý Fermat bé.Với $p$ là số nguyên tố và $p\nmid a$, khi đó\[a^{p-1}\equiv 1\pmod p.\]

Định lý Trung Hoa về số dư. Với $m_1,\,m_2,\,\ldots ,\,m_n$ là các số nguyên dương đôi một nguyên tố cùng nhau còn $r_1,\,r_2,\,\ldots ,\,r_n$ là các số nguyên bất kỳ, khi đó tồn tại duy nhất $r\in\left\{0,\,1,\,\ldots ,\,m_1m_2\ldots m_k-1\right\}$ thỏa mãn hệ đồng dư sau\[r\equiv r_k\mod{m_k}\;\forall\,k=\overline{1,\,n}.\]

Những kiến thức cơ bản nêu trên là cần thiết để theo dõi các vấn đề ở mục tiếp theo, ngoài ra bạn đọc cần có những trang bị về định giá p-adic, bổ đề nâng bậc hay những kiến thức về cấp, căn theo modulo và thặng dư bậc hai để xử lý các bài tập đề nghị.

3. Một số vấn đề cơ bản

Định lý Schur.Cho đa thức hệ số nguyên $f[x]$ có bậc dương, khi đó tập các ước nguyên tố của dãy $a_n=f[n]$ là vô hạn.

Chứng minh.Giả sử ngược lại là tập tất cả các ước nguyên tố của dãy $a_n=f[n]$ chỉ là tập hữu hạn sau đây\[\mathfrak P\left[f_n\right]=\left\{ p_1,\,p_2,\,\ldots ,\,p_t \right\}.\]Do $f\in\mathbb Z[x]$ nên $f[x]=a_0+a_1x+\ldots +a_nx^n$, với $a_i\in\mathbb Z\,\forall\,i=\overline{1,\,n}$, ta xét hai trường hợp sau.

1. Nếu $a_0=0$, khi đó $p\mid f[p]\,\forall\,p\in\mathbb P$ cho nên dãy $a_n$ nhận mọi số nguyên tố làm ước nguyên tố.
2. Nếu $a_0\ne 0$ với mỗi số nguyên dương $k$ đặt $kp_1p_2\ldots p_t=m_k$, ta có\begin{align*}
   f\left[ a_0m_k \right] &= {a_0} + {a_1}a_0m_k + \ldots + {a_n}a_0^n{m_k^n}\\
   &= {a_0}.\left[ 1 + {a_1}m_k + {a_2}{a_0}m_k^2 + \ldots + {a_n}a_0^{n 1}m_k^n\right].
   \end{align*}Đặt $g[x]=1+a_0a_1x+\ldots +a_0^{n-1}a_nx^n$ vì $\text{deg}[g]=\text{deg}[f]=n\in\mathbb Z^+$ cho nên phương trình $\left| g[x]\right| =1$ chỉ có hữu hạn nghiệm, tức là tồn tại $k\in\mathbb Z^+$ sao cho $\left| g\left[m_k\right]\right|>1$. Để ý rằng $g[x]\in\mathbb Z[x]$ nên giá trị $g\left[m_k\right]$ là một số nguyên và vì thế nó có ước nguyên tố $p$ nào đó. Rõ ràng $g\left[m_k\right]\equiv 1\pmod{m_k}$, cho nên\[\gcd \left[ g\left[m_k\right],\,m_k\right]=1.\] Điều này cũng dẫn đến $\gcd\left[m_k,\,p\right]=1$ cho nên $p\notin\mathfrak P\left[f_n\right]$, dẫn đến điều mâu thuẫn.

Vậy $\mathfrak P\left[f_n\right]$ là tập vô hạn.

$\square$

Dựa vào định lý Schur, chúng ta có thể giải quyết bài toán sau.

Bài toán 1.Cho các số nguyên dương $a,\,b$ với $a>b$, tìm tất cả các đa thức hệ số nguyên $P[x]$ thỏa mãn
\[P\left[ n \right]\mid \left[ {a^n b^n} \right]\quad\forall\,n\in\mathbb Z^+.\]

Lời giải.Ta xét hai trường hợp.

1. Nếu $\deg[P]>0$, khi đó theo định lý Schur sẽ tồn tại vô số ước nguyên tố $p$ của dãy $P[n]$. Giả sử $p$ là một ước nguyên tố bất kỳ như thế [với $p>a$] và $p\mid P[m]$ với $m\in\mathbb Z^+$, ta có\[p\mid\left[a^m-b^m\right].\]Mặt khác do $P[x]\in\mathbb Z[x]$ nên\[P[m+p]\equiv P[m]\equiv 0\pmod p.\]Từ đây ta lại có\[p\mid\left[a^{m+p}-b^{m+p}\right].\]Vì $p\nmid a,\,p\nmid b$ và $a^m\equiv b^m\pmod p$ nên kết hợp định lý Fermat bé ta có\[a^{m+p}-b^{m+p}\equiv a^m\left[a^p-b^p\right]\equiv a^m[a-b]\pmod p .\]Điều này kéo theo $p\mid [a-b]$, nhưng do $a-b$ là một số nguyên dương cố định cho nên nó không thể có vô số ước nguyên tố. Vậy nên trường hợp này không thể xảy ra.
2. Nếu $\deg[P]\le 0$, tức $P[x]$ là đa thức hằng thế thì $P[x]=d$ với $d=P[1]$ và là ước của $a-b$. Lúc đó do $[a-b]$ luôn là ước của $a^n-b^n$ với mọi số nguyên dương $n$ do đó trường hợp này thỏa.

Vậy, kết quả của bài toán là $P[x]=d\;\forall\,x\in\mathbb R$ với $d$ là một ước số bất kỳ của $a-b$.

$\square$

Kết quả của Schur ứng với lớp dãy số đặc biệt, đó là các dãy sinh ra từ các đa thức hệ số nguyên. Ở bài toán tiếp theo, chúng ta sẽ xử lý một bài toán về mục đích thì tương tự nhưng dãy số được cho phức tạp hơn chút xíu.

Bài toán 2.Chứng minh rằng $\mathfrak{P}\left[a_n\right]$ là vô hạn, với $$a_n=\left\lfloor \log\left[2017^n+1\right]\right\rfloor\quad\forall\,n\in\mathbb Z^+.$$

Lời giải.Giả sử $\mathfrak{P}\left[a_n\right]$ chỉ là hữu hạn. Ta lấy ra $5$ số nguyên tố $p_i\notin \mathfrak{P}\left[a_n\right]$, theo CRT sẽ tồn tại $5$ số nguyên dương liên tiếp $N+1,\,N+2,\,\ldots ,\,N+5$ sao cho\[{p_k}\mid \left[ {N + k} \right]\;\forall {\mkern 1mu} k = \overline{1,\,5}.\]Giờ gọi $m$ là chỉ số lớn nhất sao cho $a_m\le N+1$, khi đó $a_{m+1}>N+1$ và vì \[1 < {a_{m + 1}} {a_m} = \left\lfloor {\log \left[ {{{2017}^{m + 1}} + 1} \right]} \right\rfloor \left\lfloor {\log \left[ {{{2017}^m} + 1} \right]} \right\rfloor < 5.\] Cho nên ta có được\[\left\{ {{a_m};{\mkern 1mu} {a_{m + 1}}} \right\} \cap \left\{ {N + 1,{\mkern 1mu} N + 2,{\mkern 1mu} \ldots ,{\mkern 1mu} N + 5} \right\} \ne \emptyset .\]Từ đây thấy sẽ tồn tại số nguyên tố $p\notin \mathfrak{P}\left[a_n\right]$ thoả $p\mid a_ma_{m+1}$, và điều đó mâu thuẫn với giả sử ban đầu của chúng ta.

$\square$

Bài toán trên, chỉ là hệ quả của bài toán sau đây [ứng với $d=5$]. Và lời giải là hoàn toàn tương tự.

Bài toán 3.Cho $d$ là một số nguyên dương lớn hơn 1, dãy số nguyên $\left\{a_n\right\}_{n\in\mathbb Z^+}$ tăng ngặt và thỏa mãn\[a_{n+1}-a_nN_0$ nên với $a_m=\max\mathfrak A_n$ ta có\[a_{N_0}\le{a_m} < {a_{m 1}} + {m^k} \sqrt[{k + 1}]{{n {a_{{N_0}}}}}-1\quad\forall\,n>M.\]
Với giả thiết phản chứng ở trên thì $\mathfrak A_n\subset\mathfrak P_n\quad\forall\,n>M$, tức là có\[\frac{{\sqrt[{k + 1}]{{n {a_{{N_0}}}}}}-1}{\left[{1 + {{\log }_2}n}\right]^t} < \frac{{\left| {{\mathfrak A_n}} \right|}}{{\left| {{\mathfrak P_n}} \right|}} < 1\quad\forall\,n>M.\]Lấy giới hạn ở vô cùng, cho ta điều vô lý. Vậy, $\mathfrak P\left[a_n\right]$ phải là tập vô hạn.

$\square$

Bây giờ là một bài toán xét kỹ thì cùng bản chất, mặc dù đọc qua yêu cầu thì cảm thấy khác biệt với các bài toán trên.

Bài toán 5.Cho các số nguyên dương $m$ và $n$, chứng minh rằng luôn tồn tại số nguyên dương $k$ sao cho $2^k-m$ có ít nhất $n$ ước nguyên tố phân biệt.

[China TST, 2006]

Lời giải.Giả sử với mọi số nguyên dương $k$ số ước nguyên tố của $2^k-m$ đều nhỏ hơn $n$, ta giả sử $K$ là số thỏa $2^K-m$ có nhiều ước nguyên tố nhất. Và phân tích ra thừa số nguyên tố của $2^K-m$ là\[{2^K} m = p_1^{{k_1}}p_2^{{k_2}} \ldots p_t^{{k_t}}.\]Đặt $M=p_1^{{1+k_1}}p_2^{{1+k_2}} \ldots p_t^{{1+k_t}}$, thế thì với $k$ đủ lớn ta có được\[{2^{K + k\varphi \left[ {M} \right]}} m \equiv {2^K} m\pmod M.\]Tức là ${2^{K + k\varphi \left[ {M} \right]}}-m$ chia hết cho $2^K-m$, nên ${2^{K + k\varphi \left[ {M} \right]}}-m$ nhận mọi ước nguyên tố của $2^K-m$ làm ước nguyên tố. Nhưng do vai trò của $K$ nên ${2^{K + k\varphi \left[ {M} \right]}}-m$ cũng chỉ được phép có đúng bấy nhiêu ước nguyên tố, đồng thời do $v_{p_i}[M]=v_{p_i}\left[2^K-m\right]+1\;\forall\,i=\overline{1,\,t}$ nên $$v_{p_i}\left[2^{K + k\varphi \left[ {M} \right]}-m\right] =v_{p_i}\left[2^K-m\right]\quad\forall\,i=\overline{1,\,t}.$$ Từ đó dẫn đến điều vô lý là\[{2^{K + k\varphi \left[ {M} \right]}} m = {2^K} m\quad\forall\,k\in\mathbb Z^+.\]

$\square$

Bằng kỹ thuật tương tự, ta dễ dàng có được lời giải cho bài toán sau.

Bài toán 6.Cho $a,\,b,\,c$ là các số nguyên thỏa $ac\ne 0$ và $b>1$. Xét dãy số $f_n=ab^n+c\;\forall\,n\in\mathbb Z^+$. Chứng minh rằng $\mathfrak P\left[f_n\right]$ là tập vô hạn.

Tôi không trình bày lời giải chi tiết cho bài toán này, thay cho việc đó tôi nêu ra và xử lý kết quả khá mạnh sau của Polya.

Định lý Polya.Giả sử $a_1,\,a_2,\,\ldots ,\,a_m$ là các số nguyên dương phân biệt, $0 < a_1< a_2< \ldots < a_m$ và $P_1[x],\, P_2[x],\,\ldots ,\, P_m[x]$ là các đa thức hệ số nguyên khác đa thức 0. Khi đó dãy số nguyên cho bởi công thức dưới đây, sẽ có vô hạn ước nguyên tố$$f_n=a_1^nP_1[n]+a_2^nP_2[n]+ \ldots +a_m^nP_m[n]\quad\forall\,n\in\mathbb Z^+.$$

Lời giải.Không mất tính tổng quát, ta giả sử hệ số bậc cao nhất của $P_m[x]$ là dương. Giả sử rằng $\mathfrak P\left[f_n\right]$ là tập hữu hạn, cụ thể\[\mathfrak P\left[f_n\right]=\left\{p_1,\,p_2,\,\ldots,\,p_t\right\}.\]Rõ ràng là $\lim f_n=+\infty$, cho nên tồn tại $N_0$ đủ lớn sao cho $f_{N_0}>1$ và đồng thời với số nguyên dương $m$ cho trước ta sẽ có\[a_i^{N_0+n\varphi[m]}\equiv a_i^{N_0}\pmod m.\]
Giả sử ta có phân tích ra thừa số nguyên tố của $f_{N_0}$ là\[{f_{{N_0}}} = p_1^{{k_1}}p_2^{{k_2}} \ldots p_t^{{k_t}};\;k_i\in\mathbb N.\]
Đặt $M=p_1^{{1+k_1}}p_2^{{1+k_2}} \ldots p_t^{{1+k_t}}$ và $M=p_1^{{2+k_1}}p_2^{{2+k_2}} \ldots p_t^{{2+k_t}}$, thế thì\[\varphi \left[ {M} \right] = M\prod\limits_{1 \le i \le t} {\left[ {{p_i} 1} \right]} = {p_1}{p_2} \ldots {p_t}\varphi[M].\] Điều đó kết hợp với $P_i[x]\in\mathbb Z[x]$ để thấy với mọi số nguyên dương $n$ ta có\[{f_{{N_0} + n\varphi \left[ M \right]}} = \sum\limits_{1 \le j \le m} {a_j^{{N_0} + n\varphi \left[ M \right]}{P_j}\left[ {{N_0} + n\varphi \left[ M \right]} \right]} \equiv \sum\limits_{1 \le j \le m} {a_j^{{N_0}}{P_j}\left[ {{N_0}} \right] \equiv {f_{{N_0}}}} \pmod{M}.\]Do $v_{p_i}\left[M\right]=1+v_{p_i}\left[f_{N_0}\right]\;\forall\,i=\overline{1,\,t}$, nên từ đó có được\[{v_{{p_i}}}\left[ {{f_{{N_0} + n\varphi \left[ M \right]}}} \right] = {v_{{p_i}}}\left[ {{f_{{N_0}}}} \right]\quad\forall\,i=\overline{1,\,t},\;\forall\,n\in\mathbb Z^+.\]
Điều đó cho thấy rằng\[\lim {f_{{N_0} + n\varphi \left[ M \right]}} = {f_{{N_0}}}.\]Kết quả vừa rút ra, trái với nhận xét từ ban đầu của chúng ta là $\lim f_n=+\infty$.

Vậy, $\mathfrak P\left[f_n\right]$ phải là tập vô hạn.

$\square$

Ta quan tâm đến một vấn đề khác liên quan đến kết quả của Polya nêu trên, đó là: Với dãy $f_n$ xác định như thế thì liệu số ước nguyên tố của một phần tử của dãy có bị giới hạn hay không? Cụ thể là nếu ta cố định một số nguyên dương $k$, thì có tồn tại hay không một chỉ số $m$ để $f_m$ có ít nhất $k$ ước nguyên tố phân biệt.

Bài toán 7.Giả sử $a_1,\,a_2,\,\ldots ,\,a_m$ là các sô nguyên dương phân biệt, và
$P_1[x],\, P_2[x],\,\ldots ,\, P_m[x]$ là các đa thức hệ số nguyên khác đa thức 0. Xét dãy số nguyên cho bởi công thức$$f_n=a_1^nP_1[n]+a_2^nP_2[n]+ \ldots +a_m^nP_m[n]\quad\forall\,n\in\mathbb Z^+.$$Chứng minh rằng, với $k$ là số nguyên dương cho trước, luôn tồn tại $m\in\mathbb Z^+$ sao cho $f_m$ có ít nhất $k$ ước nguyên tố phân biệt.

Lời giải.Nếu không tồn tại $m\in\mathbb Z^+$ sao cho $f_m$ có ít nhất $k$ ước nguyên tố phân biệt, thì mọi phần tử của dãy $f_n$ đều có hữu hạn ước nguyên tố. Ta giả sử $K$ là số thỏa $f_K$ có nhiều ước nguyên tố nhất. Và phân tích ra thừa số nguyên tố của $f_K$ là\[{f_K} = p_1^{{k_1}}p_2^{{k_2}} \ldots p_t^{{k_t}}.\]Lại đặt $M=p_1^{{1+k_1}}p_2^{{1+k_2}} \ldots p_t^{{1+k_t}}$ và $M=p_1^{{2+k_1}}p_2^{{2+k_2}} \ldots p_t^{{2+k_t}}$, để với $n$ đủ lớn ta có\[{f_{K + n\varphi \left[ {M} \right]}} \equiv {f_K}{\pmod M}.\]Từ đây có $f_K\mid {f_{K + n\varphi \left[ {M} \right]}}$ và bởi vậy ${f_{K + n\varphi \left[ {M} \right]}}$ cũng có $t$ ước nguyên tố là các ước nguyên tố của $f_K$. Nhưng do vai trò của $K$ nên ${f_{K + n\varphi \left[ {M} \right]}}$ cũng chỉ có bấy nhiêu ước nguyên tố. Đồng thời do $v_{p_i}[M]=1+v_{p_i}\left[f_K\right]$ và ${f_{K + n\varphi \left[ {M} \right]}} \equiv {f_K}{\pmod M}$ nên với mọi $n$ đủ lớn ta sẽ có\[v_{p_i}\left[{f_{K + n\varphi \left[ {M} \right]}}\right]=v_{p_i}\left[f_K\right]\quad\forall\,i=\overline{1,\,t}.\]
Điều này kéo theo dãy con $\left\{{f_{K + n\varphi \left[ {M} \right]}}\right\}_{n\in\mathbb Z^+}$ là dãy dừng và nó mâu thuẫn với việc $\lim f_n=+\infty.$

$\square$

Bây giờ, ta xét đến một bài toán olympic ứng dụng trực tiếp kết quả của Polya ở trên.

Bài toán 8.Cho $m,\,n$ là các số nguyên dương. Chứng minh rằng tồn tại vô hạn các cặp số nguyên dương $[a;\,b]$ sao cho $ [a+b]\mid \left[am^{a}+bn^{b}\right]$ và $\gcd[a,\,b]=1$.

[China MO, 2011]

Lời giải.Nếu $m=n=1$ thì bài toán cực kỳ là tầm thường, bởi vì nếu điều đó xảy ra ta có thể chọn $b=1$ còn $a$ tùy ý. Vì thế, ta có thể giả sử $n>1$ và xét dãy số xác định như sau \[a_k=[mn]^k-n\quad\forall\,k\in\mathbb Z^+.\]Theo bài toán trên thì $\mathfrak P\left[a_k\right]$ là tập vô hạn, như vậy ta có thể lấy ra vô số các số nguyên tố $p$ từ $\mathfrak P\left[a_k\right]$ thỏa mãn $p>m+n$ đồng thời khi đó tồn tại $k_p$ sao cho $p\mid a_{k_p}$, tức là\[[mn]^{k_p}\equiv n\pmod p.\]Bởi vì $0 {\left[ {a + b} \right]^2}.\]
Nhưng $p\mid [a+b]$ do đó từ $a+b\ge p$ mà có điều mâu thuẫn là\[a^p+b^p>p[a+b].\]

Như vậy, $\Phi_p$ luôn phải có một ước nguyên tố $q$ lẻ và $q\ne p$, để ý rằng $\Phi_p\mid\left[a^p+b^p\right]$ mà ta có điều cần chứng minh.

$\square$

Từ lời giải bài toán trên, ta thấy từ dãy $f_n=a^n+b^n$ có thể trích ra một dãy con $f_{p^n}$ có vô hạn ước nguyên tố. Cũng cần nói thêm rằng, bài toán trên là một phiên bản của định lý Zsigmondy nổi tiếng. Nhưng chuyện đó bàn sau, giờ ta đến với một bài toán khác như sau.

Bài toán 10.Cho $m$ và $k$ là các số nguyên dương cho trước với $m$ lẻ, chứng minh rằng luôn tồn tại $n$ sao cho $m^n+n^m$ có ít nhất $k$ ước nguyên tố phân biệt.

[Romania TST, 2014]

Lời giải.Lấy ra một số nguyên tố $p$ lớn hơn $m+2$ bất kỳ và xét $n=mp^{2.3^k}$, ta có\[{n^m} + {m^n} = {m^m}\left[ {{m^{m\left[ {{p^{{{2.3}^k}}} 1} \right]}} + {p^{{3^k}.2m}}} \right] = {m^m}\left[ {{m^{m\left[ {\frac{{{p^{{{2.3}^k}}} 1}}{{{3^k}}}} \right]{{.3}^k}}} + {p^{{3^k}.2m}}} \right].\]Giờ để ý rằng do $p>3$ nên $3\mid\left[p^2-1\right]$ và vì thế\[v_3\left[p^{2.3^k}-1\right]=v_3[p^2-1]+k>k.\]Tức là $\dfrac{p^{2.3^k}-1}{3^k}\in\mathbb Z^+$, nên nếu đặt $m^{m\left[\frac{p^{2.3^k}-1}{3^k}\right]}=a,\,p^{2m}=b$ thì $a,\,b\in\mathbb Z^+$ thỏa $\gcd [a,\,b]=1$ tất nhiên $a+b>3$, đồng thời\[{n^m} + {m^n} = m^m\left[{a^{{3^k}}} + {b^{3^k}}\right].\]Theo bài toán phía trên thì tồn tại $k$ số nguyên tố phân biệt $p_1,\,p_2,\,\ldots ,\,p_k$ sao cho \[p_j\mid\left[{a^{{3^j}}} + {b^{3^j}}\right],\;p_j\nmid\left[{a^{{3^i}}} + {b^{3^i}}\right]\quad\forall\,j=\overline{1,\,k},\;\forall\,i=\overline{0,\,j-1}.\]
Rõ ràng $n^m+m^n$ có $k$ ước nguyên tố phân biệt là $p_1,\,p_2,\,\ldots ,\,p_k$.

$\square$

Nhận xét.Bài toán này hoàn toàn có thể xử lý như ở các bài China TST 2006 [bài toán 6] và kết quả của Polya [bài toán 8]. Tôi xử lý bằng cách trên, để muốn nhấn mạnh ý nghĩa của bài toán 10, đó là một kết quả khá hay và nó có vai trò trong nhiều bài toán khó.

Để kết thúc phần này, tôi xin đưa ra kết quả cực mạnh sau của Hiroshi Kobayashi. Một kết quả, mà theo tôi biết là chưa có chứng minh sơ cấp.

Định lý Kobayashi. Cho $S$ là một tập vô hạn các số nguyên dương thỏa mãn $\mathfrak P[S]$ là hữu hạn, khi đó với mọi hằng số nguyên $c$ khác $0$ ta có $\mathfrak P[S+c]$ là tập vô hạn, với\[S+c=\{s+c:\;s\in S\}.\]

Ở phần tiếp sau đây, là các bài toán để các bài toán luyện tập.

4. Bài tập

1. Tìm tất cả các đa thức hệ số nguyên $P[x]$ sao cho
\[\gcd \left[ {P\left[ n \right],\,P\left[ {{2017^n}} \right]} \right] = 1\quad\forall\, n \in\mathbb Z^+ .\]

2. Cho các số nguyên dương $k,\,m$ và đa thức hệ số nguyên $P[x]$ có bậc dương, chứng minh rằng tồn tại $n\in\mathbb Z^+$ sao cho mỗi giá trị $P[n],\,P[n+1],\,\ldots ,\,P[n+m]$ đều có ít nhất $k$ ước số nguyên tố phân biệt.

3. Cho $P[x]$ là đa thức hệ số nguyên bất khả quy trên $\mathbb Q[x]$ có bậc dương, chứng minh rằng tồn tại vô số số nguyên tố $p$ sao cho với mỗi $p$ như thế sẽ tồn tại $n\in\mathbb Z^+$ thỏa mãn $$v_p\left[P[n]\right]=1.$$

4. Cho $f[x]$ là một đa thức hệ số thực và số nguyên dương $k$, biết rằng với số nguyên dương $n$ bất kỳ đều tồn tại $m\in\mathbb N$ sao cho $f[n]=m^k$. Chứng minh rằng tồn tại đa thức hệ số hữu tỷ $P[x]$ sao cho\[f[x]=P^k[x].\]

5. Cho trước số nguyên dương $k$ và đa thức hệ số nguyên $P[x]$ có bậc dương, chứng minh rằng tồn tại vô số số nguyên tố $p$ sao cho phương trình đồng dư $P[x]\equiv 0\pmod{p^k}$ có nghiệm.

6. Cho trước số nguyên dương $a$ không là số chính phương, chứng minh rằng tồn tại vô số số nguyên tố $p$ lẻ thỏa mãn\[{a^{\frac{{p 1}}{2}}} \equiv 1\pmod p.\]

7. Cho các số nguyên dương $a$ và $b$ với $a>1$, xét dãy số\[f_n=a^{\varphi[n]}+b.\]

a. Chứng minh rằng $\mathfrak P\left[f_n\right]$ là tập vô hạn.

b. Chứng minh rằng $\mathbb P\setminus\mathfrak P\left[f_n\right]$ cũng là tập vô hạn.

8. Chứng minh rằng $\mathfrak P\left[f_n\right]$ là tập vô hạn, với\[{f_n} = \left\lfloor {{3^{{2^{\log n}}}}} \right\rfloor\quad\forall\,n\in\mathbb Z^+. \]

9 [Iran TST, 2009]. Cho trước số nguyên dương $a$, xét dãy $f_n=2^{2^n}+a$. Chứng minh rằng $\mathfrak P\left[f_n\right]$ là tập vô hạn.}

10. Với mỗi số nguyên dương $m$, ký hiệu $p[m]$ là ước nguyên tố lớn nhất của $m^2+2018$. Chứng minh rằng tồn tại vô số số nguyên dương $n$ sao cho $p[n]2$], xét dãy số $f_n=a^{n+1}+1$. Chứng minh rằng với mỗi số nguyên dương $m$, tồn tại số nguyên tố $p$ là ước của $f_m$ và $p>2m$.

12. Tìm tất cả các đa thức hệ số nguyên $P[x]$ và hằng số $k$ sao cho với mọi số nguyên dương $n$ thì $2^nP[n]+k$ luôn là số chính phương.

13. Cho $m$ là một số nguyên dương, chứng minh rằng tồn tại vô số số nguyên dương $n$ sao cho\[7^m\mid\left[3^n+5^n+6^n\right].\]

14 [IMO SL, 2014].Cho số nguyên dương $c$, xét dãy $a_n$ được xác định bởi công thức truy hồi như sau $a_1=c$ và\[{a_{n + 1}} = a_n^3 4ca_n^2 + 5{c^2}{a_n} + c\quad\forall\,n\in\mathbb Z^+.\] Chứng minh rằng với mọi $n>1$ sẽ tồn tại số nguyên tố $p$ sao cho $p\mid a_n$ và $p\nmid a_i\;\forall\,i