Bài toán 21.[IMO 1989] Chứng minh rằng với mỗi số nguyên dương $n$, ta có thể tìm được một tập gồm $n$ số nguyên dương liên tiếp sao cho không số nào trong chúng là lũy thừa của một số nguyên tố.

Bài toán 21.[IMO 1989] Chứng minh rằng với mỗi số nguyên dương $n$, ta có thể tìm được một tập gồm $n$ số nguyên dương liên tiếp sao cho không số nào trong chúng là lũy thừa của một số nguyên tố.

Lời giải

Ta chứng minh rằng tập hợp $$\Big\{ (2n+2)!+2; (2n+2)!+3; \ldots; (2n+2)!+n+1\Big\}$$ thỏa mãn yêu cầu bài toán. Ta thấy rằng $$(2n+2)!+2= 2 \cdot \left[ 1+ \dfrac{(2n+2)!}{2}\right].$$ Từ $\dfrac{(2n+2)!}{2} \equiv 0 \pmod{2}$, suy ra $1+ \dfrac{(2n+2)!}{2} \equiv 1 \pmod{2}$.
Vì vậy $(2n+2)!+2$ không thể là lũy thừa của một số nguyên tố vì nó có một ước chẵn và một ước lẻ. Bây giờ ta xét $$(2n+2)!+k = k \cdot \left[ 1+ \dfrac{(2n+2)!}{k}\right]$$ với $2\le k \le n+1$. Khi đó ta có $$(2n+2)! \equiv 0 \pmod{k} \Rightarrow \dfrac{(2n+2)!}{k} \equiv 0 \pmod{k} \Rightarrow 1+ \dfrac{(2n+2)!}{k} \equiv 1 \pmod{k}.$$ Nếu $(2n+2)!+k$ là lũy thừa của một số nguyên tố thì do $(2n+2)!+k$ chia hết cho $k$ nên nó là một lũy thừa của $k$. Nhưng điều này không xảy ra vì $1+ \dfrac{(2n+2)!}{k}$ không là lũy thừa của $k$. Vậy ta có điều phải chứng minh.
Ta có thể giải bài này theo cách sau:
Đặt $N=1+ \left[ (n+1)!\right]^2$. Ta sẽ chứng minh: Không có số nào trong $n$ số nguyên liên tiếp $N+1$, $N+2$, \ldots, $N+n$ là lũy thừa của một số nguyên tố.
Giả sử ngược lại $\exists k, m \in \mathbb{Z}$, $k \ge 1$, $1\le m \le n$ và số nguyên tố $p$ để $N+m=p^k$.
Ta có $(m+1) \Big| (n+1)!$ nên $(m+1) \Big| \left[ (n+1)!\right]^2+(m+1)=N+m=p^2$.
Do $1 < m+1 < N+m$ nên ta có $m+1=p^r$ với $0 < r < k$. Suy ra $p^{r+1} \Big| p^k=N+m$.
Mặt khác $p^{r+1} \Big| \left[ (n+1)!\right]^2=N-1$. Do đó $p^{r+1} \Big| (N+m)-(N-1)=p^r$. Điều này là không thể. Vậy ta có điều phải chứng minh.