Bài 3

Chứng minh rằng tồn tại vô hạn số nguyên dương

n

sao cho

n^2+1

có một ước nguyên tố lớn hơn

2n+\sqrt{2n}

Bước 1 trên 6: Chiến lược: cố định số nguyên tố p trước rồi tìm n phù hợp nhỏ hơn nó

Bước trước Bước tiếp

Hiểu nôm na

Thay vì đi tìm $n$ rồi hy vọng $n^2+1$ có ước nguyên tố lớn, ta đảo ngược cách tìm: chọn số nguyên tố $p$ trước, rồi dựng $n$ sao cho $p$ chia hết $n^2+1$ và $n$ đủ nhỏ để $p$ đã vượt $2n+\sqrt{2n}$ .

p \equiv 1 \pmod 8,\quad h=\lceil\sqrt p\rceil,\quad n\le\tfrac12(p-h),\ p\mid n^2+1 \implies p\ge 2n+\sqrt{2n}

Phân tích chi tiết

Cố định một số nguyên tố $p\equiv1\pmod8$ với $p\ge2013$ , và đặt $h=\lceil\sqrt p\rceil$ . Ta muốn tìm số nguyên dương $n\le\frac12(p-h)$ với $p\mid n^2+1$ . Nếu thành công, thì $p\ge 2n+h\ge 2n+\sqrt p$ ; vì $n\le\frac12(p-h)<\frac p2$ nên $2n<p$ , do đó $\sqrt{2n}<\sqrt p\le h$ , suy ra $p\ge2n+h>2n+\sqrt{2n}$ . Vậy chính $p$ là một ước nguyên tố của $n^2+1$ vượt quá $2n+\sqrt{2n}$ , đúng như yêu cầu.