Định Lý Euclid Về Số Nguyên Tố - Vườn Toán

Trang chủ » định Lý Euclid » Định Lý Euclid Về Số Nguyên Tố - Vườn Toán

Có thể bạn quan tâm

Trang

  • Trang nhà
  • Kỹ năng mềm
  • Giới thiệu

Định lý Euclid về số nguyên tố

Tiếp tục câu chuyện về số nguyên tố, hôm nay chúng ta sẽ chứng minh rằng tồn tại vô số các số nguyên tố. Đây chính là Định lý Euclid về số nguyên tố. Định lý này có một cách chứng minh rất là đơn giản, nhưng cách chứng minh này có lẽ là một trong những chứng minh hay nhất trong toán học. Chúng ta chứng minh tồn tại vô số số nguyên tố như sau. Giả sử rằng $p_1$, $p_2$, ..., $p_k$ là một dãy số nguyên tố. Chúng ta chỉ ra rằng chúng ta sẽ tìm được một số nguyên tố mới không nằm trong dãy số này. Từ đó suy ra sẽ phải có vô số các số nguyên tố. Để chỉ ra số nguyên tố mới, chúng ta xây dựng số $n = p_1 p_2 \dots p_k + 1$. Rõ ràng $n$ sẽ có một ước số nguyên tố $p$. Nhưng vì $n$ không chia hết cho các số nguyên tố $p_i$ ở trên nên ước số nguyên tố $p$ của $n$ sẽ là một số nguyên tố mới không nằm trong dãy số này. Tóm tại, cứ lấy bất kỳ một dãy số hữu hạn các số nguyên tố thì chúng ta lại tìm được một số nguyên tố mới, điều đó chứng tỏ sẽ có vô hạn các số nguyên tố. Cách chứng minh ở trên thật là hay. Chúng ta sẽ dùng phương pháp chứng minh này để giải một vài bài toán tương tự. Bài toán 1. Chứng minh rằng có vô số các số nguyên tố có dạng $4N+3$. Chúng ta biết rằng 2 là số nguyên tố chẵn duy nhất, còn tất cả các số nguyên tố còn lại là số nguyên tố lẻ. Một số nguyên tố lẻ thì hoặc là có dạng $4N+1$ hoặc là có dạng $4N+3$. Muốn chứng minh rằng có vô số các số nguyên tố có dạng $4N+3$, chúng ta lý luận tương tự như trên. Đó là với mọi dãy số nguyên tố $p_1$, $p_2$, ..., $p_k$ bất kỳ có dạng $4N+3$, chúng ta sẽ chỉ ra được một số nguyên tố mới không nằm trong dãy này và cũng có dạng $4N+3$. Chúng ta xây dựng số $n = 4 p_1 p_2 \dots p_k - 1$, số này có dạng $4N+3$. Số $n$ này sẽ phải có một ước số nguyên tố $p$ có dạng $4N+3$. Vì sao? Bởi vì $n$ là số lẻ lớn hơn 1, cho nên nếu $n$ không có ước số nguyên tố có dạng $4N+3$ thì tất cả các ước số nguyên tố của $n$ sẽ có dạng $4N+1$. Vậy $n$ sẽ là tích của các số có dạng $4N+1$. Nhưng mà chúng ta dễ dàng thấy rằng tích của các số có dạng $4N+1$ là một số có dạng $4N+1$. Cho nên $n$ cũng có dạng $4N+1$, và đây là điều vô lý. Như vậy $n$ sẽ có ước số nguyên tố $p$ có dạng $4N+3$. Tiếp theo, chúng ta thấy rằng vì $n$ không chia hết cho các số nguyên tố $p_i$ ở trên nên ước số nguyên tố $p$ của $n$ sẽ là một số nguyên tố mới không nằm trong dãy số này. Vậy coi như chúng ta đã tìm ra lời giải cho bài toán. Lời giải bài toán 1. Để chứng minh rằng tồn tại vô số các số nguyên tố có dạng $4N+3$, chúng ta sẽ chứng minh rằng, với mọi dãy số nguyên tố $p_1$, $p_2$, ..., $p_k$ có dạng $4N+3$, sẽ tồn tại một số nguyên tố khác cũng có dạng $4N+3$, và không nằm trong dãy số nguyên tố này. Thực vậy, lấy $n = 4 p_1 p_2 \dots p_k - 1$, số này có dạng $4N+3$. Đầu tiên chúng ta khẳng định rằng $n$ phải có một ước số nguyên tố có dạng $4N+3$. Đó là vì nếu tất cả các ước số nguyên tố của $n$ có dạng $4N+1$ thì $n$ sẽ là tích của các số có dạng $4N+1$, suy ra $n$ cũng có dạng $4N+1$, vô lý. Tóm lại, $n$ có ít nhất một ước số nguyên tố $p$ có dạng $4N+3$. Cuối cùng vì $n$ không chia hết cho các số nguyên tố $p_i$ nên $p \neq p_i$. Tóm tại, cứ lấy bất kỳ một dãy số hữu hạn các số nguyên tố có dạng $4N+3$ thì chúng ta lại tìm được một số nguyên tố mới cũng có dạng $4N+3$, do đó sẽ tồn tại vô số các số nguyên tố có dạng $4N+3$. $\blacksquare$ Bài toán 2. Chứng minh rằng tồn tại vô số các số nguyên tố có dạng $4N+1$. Làm theo phương pháp ở trên thì chúng ta sẽ chọn $n = 4 p_1 p_2 \dots p_k + 1$ và tìm cách chứng minh rằng $n$ sẽ có ước số nguyên tố có dạng $4N+1$. Tuy nhiên nhìn kỹ ra thì cách chứng minh này không ổn. Đó là vì tích của hai số có dạng $4N+3$ là số có dạng $4N+1$. Do đó có khả năng là $n$ là tích của hai số nguyên tố có dạng $4N+3$ và vì vậy $n$ sẽ không có ước số nguyên tố nào có dạng $4N+1$. Chúng ta phải tìm cách giải khác. Chúng ta sẽ dùng $n = 4 p_1^2 p_2^2 \dots p_k^2 + 1$. Để chứng minh $n$ có ước số nguyên tố có dạng $4N+1$, chúng ta sẽ dùng bổ đề sau. Bổ đề. Với mọi số tự nhiên $x$ thì $x^2 + 1$ không có ước nguyên tố có dạng $4N+3$. Để chứng minh bổ đề này, chúng ta sẽ sử dụng Định lý nhỏ Fermat. Các bạn có thể đọc thêm về Định lý nhỏ Fermat ở đây: "modulo - Phần 5". Theo định lý nhỏ Fermat thì với mọi số nguyên tố $p$ và với mọi số nguyên $a$ không chia hết cho $p$, $$a^{p-1} = 1 \pmod{p}.$$ Bây giờ chúng ta chứng minh bổ đề theo phương pháp phản chứng. Đó là, giả sử như $x^2+1$ có một ước số nguyên tố $p=4N+3$. Tức là $$x^2 = -1 \pmod{p}.$$ Từ đó chúng ta có $$x^{4N+2} = (x^2)^{2N+1} = (-1)^{2N+1} = -1 \pmod{p}.$$ Nhưng theo định lý nhỏ Fermat thì $$x^{4N+2} = 1 \pmod{p}.$$ Vậy $1=-1 \pmod{p}$, hay $2=0 \pmod{p}$. Đây là điều vô lý. Cho nên bổ đề đã được chứng minh. $\blacksquare$ Lời giải bài toán 2. Để chứng minh rằng tồn tại vô số các số nguyên tố có dạng $4N+1$, chúng ta sẽ chứng minh rằng, với mọi dãy số nguyên tố $p_1$, $p_2$, ..., $p_k$ có dạng $4N+1$, sẽ tồn tại một số nguyên tố khác cũng có dạng $4N+1$ và không nằm trong dãy số nguyên tố này. Thực vậy, lấy $n = 4 p_1^2 p_2^2 \dots p_k^2 + 1$. Vì $n$ có dạng $x^2+1$, nên theo bổ đề trên mà chúng ta vừa chứng minh, thì $n$ không có ước số nguyên tố có dạng $4N+3$. Vì $n$ là số lẻ nên toàn bộ các ước số nguyên tố của $n$ sẽ có dạng $4N+1$. Chúng ta lại dễ dàng thấy rằng không một số $p_i$ nào trong dãy số trên là ước số của $n$. Vì vậy chúng ta đã tìm được những số nguyên tố mới có dạng $4N+1$. Tóm tại, cứ lấy bất kỳ một dãy số hữu hạn các số nguyên tố có dạng $4N+1$ thì chúng ta lại tìm được một số nguyên tố mới cũng dạng $4N+1$, do đó sẽ có vô hạn các số nguyên tố có dạng $4N+1$. Chúng ta tạm dừng ở đây. Chỉ xin lưu ý là hai bài toán ở trên là hai trường hợp đặc biệt của một định lý tổng quát. Định lý này gọi là định lý Dirichlet về cấp số cọng. Định lý Dirichlet về cấp số cọng phát biểu như sau: nếu $a$ và $b$ là hai số nguyên tố cùng nhau thì sẽ tồn tại vô số các số nguyên tố có dạng $aN+b$. Hẹn gặp lại các bạn ở bài sau. Bài tập về nhà. 1. Chứng minh rằng tồn tại vô số các số nguyên tố có dạng $6N+1$. 2. Chứng minh rằng tồn tại vô số các số nguyên tố có dạng $6N+5$. 3. Thử chọn vài giá trị khác cho $a$ và $b$ rồi chứng minh rằng tồn tại vô số các số nguyên tố có dạng $aN+b$. Labels: arithmetic progression, cấp số cọng, Dirichlet theorem, Euclid theorem, Fẹcma, Fermat little theorem, number theory, Ơclít, prime number, số học, số nguyên tố Bài đăng Mới hơn Bài đăng Cũ hơn Trang chủ

Ủng hộ Vườn Toán trên facebook

Facebook

Lưu trữ Blog

  • ▼  2012 (36)
    • ▼  tháng 8 (5)
      • Bộ số Pitago
      • Định lý Wilson
      • Một vài bài toán về số nguyên tố
      • Định lý Euclid về số nguyên tố
      • Số nguyên tố

English Version

English Version

Bài toán kết nối facebook

Phép nhân thời đồ đá

Mắt Biếc Hồ Thu

Lục giác kỳ diệu

Định lý Pitago

1 = 2012 = 2013

Dãy số Fibonacci và một bài toán xếp hình

James vẽ hình

Câu hỏi của James

Hình vuông số chính phương kỳ diệu của Vianney!

Câu đố mẹo về đo lường

Công thức lượng giác Gauss cho 17-giác đều

Chào năm mới 2014

Chào năm mới 2015

Chào năm mới 2016

Không gian 4 chiều là gì?

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Ngày số Pi (2015)

Ngày số Pi (2016)

0.9999999... có bằng 1 không? (2015)

Hình tam giác

Bàn cờ vua và kim tự tháp

Dãy số

Dãy số - Phần 1

Dãy số - Phần 2

Dãy số - Phần 3

Dãy số - Phần 4

Dãy số - Phần 5

Dãy số - Phần 6

Dãy số - Phần 7

Dãy số - Phần 8

Dãy số - Phần 9

Đại số

Tam giác Pascal

Quy nạp

Quy nạp II

Quy nạp III

Nhị thức Newton

1 = 2012 = 2013

Đa thức nội suy Newton

Đa thức nội suy Lagrange

Chứng minh Định lý Wilson bằng công thức nội suy

Tổng luỹ thừa

Số phức

Số phức

Công thức Moivre

Lượng giác

Công thức lượng giác cho góc bội

Công thức lượng giác Gauss cho 17-giác đều

Ngày số Pi (2016)

Radian là gì?

Số học

modulo - Phần 1

modulo - Phần 2

modulo - Phần 3

modulo - Phần 4

modulo - Phần 5

modulo - Phần 6

Số nguyên tố

Định lý Euclid về số nguyên tố

Một vài bài toán về số nguyên tố

Định lý Wilson

Bộ số Pitago

Modulo cho số hữu tỷ

Modulo cho số hữu tỷ II

Chứng minh lại định lý Wilson

Bổ đề Bezout

Thuật toán Euclid

Tổng luỹ thừa

Tổng luỹ thừa và định lý Wolstenholme

Câu đố mẹo về đo lường

Dựng đa giác đều 15 cạnh

Bò đi con bọ cạp!

Liên phân số Fibonacci

Hằng đẳng thức Pitago

Hình vuông số kỳ diệu của Euler

Tổ hợp

Bài toán kết nối facebook

Dãy số Fibonacci và một bài toán xếp hình

Hằng đẳng thức về dãy số Fibonacci

Dãy số Fibonacci và tam giác Pascal

Hình học

Định lý Pitago

Định lý đường cao tam giác vuông

Định lý Morley

Phương tích

Trục đẳng phương và tâm đẳng phương

Định lý Ceva và Định lý Menelaus

Lục giác kỳ diệu

Định lý Pascal

Định lý Pappus

Cánh bướm Pascal

Bài toán con bướm

Định lý Ngôi Sao Do Thái

Hãy xem xét trường hợp đặc biệt

Bài toán về tìm khoảng cách ngắn nhất và một tính chất của hình elíp

Điểm Fermat của hình tam giác

Điểm Fermat của hình tam giác II

Dựng hình

Dựng hình bằng thước và compa

Bài toán chia hình tứ giác

Dựng hình ngũ giác đều

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Định lý đường cao tam giác vuông

Thuật toán dựng hình

Công thức lượng giác Gauss cho 17-giác đều

Dựng hình chỉ bằng compa

Dùng compa chia đều đoạn thẳng

Giải tích

Ngày số Pi 2015

Chuỗi Taylor

Tổng nghịch đảo bình phương

Giúp bé thông minh

Xì-tin năng động

BBC - Học tiếng Anh Du học Hoa kỳ Học Bổng Hoa Kỳ VOA - Học tiếng Anh

Tạp chí toán học

Kỹ năng mềm

Tạo lập tài khoản google

Cách tạo blog toán học

Học toán trên Wolfram

Dịch tài liệu toán học

Viết văn bản toán học PDF trực tuyến bằng LaTeX

Chia xẻ tài liệu toán học trên Google Drive

Từ khóa » định Lý Euclid