Bài toán 18. Tìm tất cả các ước số nguyên tố $p$ của $A= 2^{2017}-1$, biết $p < 9000$.

Bài toán 18. Tìm tất cả các ước số nguyên tố $p$ của $A= 2^{2017}-1$, biết $p < 9000$.

Lời giải

Trước hết ta chứng minh bổ đề sau: Nếu $2^m-1$, $2^n-1$ đều chia hết cho số nguyên tố $p$, mà $n$ là số nguyên dương nhỏ nhất thì $m$ chia hết cho $n$. Chứng minh bổ đề. Giả sử $m=nt+r$ với $t$, $r$ là các số nguyên dương, $0\le r < n$. Ta có $$2^m-1= 2^{nt+r}-1= 2^r \left( 2^{nt}-1\right) + 2^r-1. \tag{1}$$ Vì $n$ là số nguyên dương nhỏ nhất nên $m\ge n$. Dựa vào hằng đẳng thức $$a^k-b^k = (a-b)\left( a^{k-1}+a^{k-2}b+ \cdots + b^{k-1}\right) \mathbin{\vdots} (a-b) \Rightarrow \left( 2^{nt}-1\right) \mathbin{\vdots} \left( 2^n-1\right).$$ Theo giả thiết $\left( 2^m-1\right) \mathbin{\vdots} p$ nên từ $(1)$ ta được $\left( 2^r-1\right) \mathbin{\vdots} p$.
Theo giả thiết $n$ là số nguyên dương nhỏ nhất mà $\left( 2^n-1\right) \mathbin{\vdots} p$, kết hợp với $0\le r < n$ suy ra $r=0$. Từ đó ta thu được $m=nt$. $(2)$
Từ $(2)$ suy ra $m \mathbin{\vdots} n$. Bổ đề được chứng minh.
Quay lại bài toán: Giả sử $p$ là ước nguyên tố của $A=2^{2017}-1$ với $p\le 9000$.
Chọn $m=2017$. Gọi $n$ là số nguyên dương nhỏ nhất mà $\left( 2^n-1\right) \mathbin{\vdots}p \Rightarrow p$ là số nguyên tố lẻ.
Theo bổ đề ta có $m=2017=nt$. Nhưng do $2017$ là số nguyên tố nên $n=2017$ ($n\neq 1$ vì nếu $n=1$ thì $2^n-1=1 \mathbin{\not\vdots} p$).
Do $p$ là số nguyên tố lẻ, nên theo định lí Fermat nhỏ ta có $\left( 2^{p-1}-1\right) \mathbin{\vdots}p$. $(3)$
Từ $(3)$ và áp dụng bổ đề với $m=p-1$, $n=2017$ ta có $p-1=2017t$. Vì $p$ là số nguyên tố lẻ nên $p=4034t_1+1$, với số nguyên dương $t_1$.
Do $p\le 9000$ nên $4034t_1+1 \le 9000$, suy ra $4034t_1 \le 8999$. $(4)$
Do $t_1$ nguyên dương nên từ $(4)$ suy ra $t_1$ có thể là $1$, $2$.

• Nếu $t_1=1\Rightarrow p=4034t_1+1=4035$ (không là số nguyên tố).
• Nếu $t_1=2 \Rightarrow p= 4034t_1+1=8069$ là số nguyên tố: thỏa mãn bài toán.

Tóm lại, chỉ có một ước nguyên tố $p\le 9000$ của $A=2^{2017}-1$ là số $8069$.