Cho $p$ là một số nguyên tố bất kỳ. Chứng minh rằng tồn tại vô số số nguyên tố dạng $pk + 1$, với $k$ nguyên dương
Chứng minh tồn tại vô số số nguyên tố dạng $pk + 1$
#1
Đã gửi 01-08-2023 - 10:19
#2
Đã gửi 01-08-2023 - 16:09
Giả sử phản chứng rằng chỉ có một số hữu hạn các số nguyên tố như vậy, gọi chúng là $q_1,\ldots,q_r$. Xét các số nguyên dương $$N = p q_1\cdots q_r, \quad \text{và} \quad M = N^{p-1} + N^{p-2} + \cdots + 1 = \frac{N^p - 1}{N - 1}.$$ Vì $M > 1$ nên nó có một ước nguyên tố $q$ nào đó.
Một mặt, $M$ và $N$ nguyên tố cùng nhau nên $q \not \kern -.5pt | N$, hay $q \notin \{p, q_1,\ldots,q_r\}$.
Mặt khác, $q | M$ nên $q | N^p - 1$, hay $N^p \equiv 1 \pmod q$. Nói riêng, tồn tại số nguyên dương $h$ sao cho $N^h \equiv 1 \pmod q$. Theo nguyên lý sắp thứ tự tốt trong $\mathbb{N}$ thì tồn tại số nguyên dương $h$ nhỏ nhất sao cho $N^h \equiv 1 \pmod q$. Thực hiện phép chia Euclid $$p = ah + b, \qquad a \in \mathbb{N}, b \in \{0,1,\ldots,h-1\}.$$ Ta có $$1 \equiv N^p \equiv N^{ah+b} \equiv (N^h)^a \cdot N^b \equiv N^b \pmod q.$$ Theo định nghĩa của $h$ thì ta phải có $b = 0$ (vì nếu $b > 0$ thì $b$ là một số nguyên dương nhỏ hơn $h$ thỏa mãn $N^b \equiv 1 \pmod q$. Vậy $p = ah$, suy ra $h \in \{1,p\}$.
- Nếu $h = 1$ thì $N \equiv 1 \pmod q$, suy ra $$0 \equiv M \equiv N^{p-1} + N^{p-2} + \cdots + 1 \equiv 1 + 1 + \cdots + 1 \equiv p \pmod q,$$ hay $q | p$, suy ra $q = p$, mâu thuẫn.
- Nếu $h = p$, ta áp dụng định lý nhỏ Fermat, $N^{q-1} \equiv 1 \pmod q$. Lại thực hiện phép chia Euclid $q-1$ cho $h$ tương tự như trên, ta có $h | q-1$, hay $p | q-1$, hay $q$ có dạng $pk + 1$. Mà $q \notin \{q_1,\ldots,q_r\}$ và $q_1,\ldots,q_r$ là tất cả các số nguyên tố có dạng $pk+1$ theo giả thiết phản chứng, dẫn đến mâu thuẫn.
Tóm lại giả sử phản chứng là sai, nên có vô số số nguyên tố dạng $pk+1$.
Bài viết đã được chỉnh sửa nội dung bởi nmlinh16: 01-08-2023 - 16:11
- hxthanh, ThienDuc1101, Leonguyen và 2 người khác yêu thích
"Wir müssen wissen, wir werden wissen." - David Hilbert
#3
Đã gửi 02-08-2023 - 00:30
Bài này có thể sử dụng kỹ thuật trong chứng minh của Euclide cho định lý về sự vô hạn các số nguyên tố.
Thủ thuật là xét một ước nguyên tố bất kỳ $q$ của $a^p - 1$ ($a$ sẽ được chọn sau), khi đó $p$ chính là bậc của $a$ trong ${(Z/qZ)}^{*}$ (điều này là rõ ràng vì $p$ nguyên tố), do vậy $p \mid \varphi(q) = q - 1$, hay là $q = kp+1$.
Để chứng minh tính vô hạn, dùng phản chứng: giả sử chỉ có hữu hạn, gọi các số nguyên tố đó là $\{ q_1,q_2,\dots q_r \}$. Khi đó chọn $a$ sao cho $q_i \mid a$ với mọi $q_i$ (ví dụ $a = q_1 q_2 \dots q_r$). Do việc chọn ban đầu $q \mid a^p - 1$ nên $q \neq q_i$ với mọi $q_i$, điều này mâu thuẫn với giả thiết phản chứng.
Bài viết đã được chỉnh sửa nội dung bởi Konstante: 02-08-2023 - 13:07
- hxthanh và ThienDuc1101 thích
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh