✨Định lý Euclid

Định lý Euclid là một tuyên bố cơ bản trong lý thuyết số khẳng định rằng có vô số số nguyên tố. Nó đã được Euclid chứng minh đầu tiên trong tác phẩm Cơ sở của ông. Có một số cách chứng minh khác nữa cho định lý này.

Chứng minh của Euclid

Euclid đưa ra một chứng minh được công bố trong tác phẩm Cơ sở của ông (Quyển IX, Mục 20), được diễn giải ở đây.

Xem xét bất kỳ danh sách hữu hạn của số nguyên tố p₁,   p₂,  ...,   p_n. Cần chỉ ra rằng ít nhất một số nguyên tố bổ sung không có trong danh sách này có tồn tại. Đặt P là tích của tất cả các số nguyên tố trong danh sách: P = p₁p₂... p_n. Cho q = P+1. Thì q hoặc là số nguyên tố hoặc không phải là số nguyên tố:

• Nếu q là số nguyên tố, vậy có ít nhất một số nguyên tố nữa không có trong danh sách.
• Nếu q không phải là số nguyên tố thì tồn tại một thừa số nguyên tố p là ước của q. Nếu số p này nằm trong danh sách số nguyên tố, thì nó sẽ là ước của P (vì P là tích của mọi số nguyên tố trong danh sách); nhưng p cũng là ước của P + 1  = q, như vừa nêu. Nếu p là ước số của cả P và q, thì p cũng phải là ước số của hiệu số chênh lệch của hai số đó là (P + 1) - P nghĩa là p là ước số của 1. Vì không có số nguyên tố nào là ước số của 1, p không thể có trong danh sách. Điều này có nghĩa là có ít nhất một số nguyên tố tồn tại ngoài những số trong danh sách.

Điều này chứng tỏ rằng đối với mọi danh sách hữu hạn của các số nguyên tố đều có một số nguyên tố không có trong danh sách. Trong tác phẩm gốc, vì Euclid không có cách viết một danh sách các số nguyên tố tùy ý, ông đã sử dụng một phương pháp mà ông thường xuyên áp dụng, đó là phương pháp ví dụ khái quát. Cụ thể, ông chỉ chọn ba số nguyên tố và sử dụng phương pháp chứng minh chung đã nêu ở trên, chứng tỏ rằng ông ta luôn có thể tìm thấy một số nguyên tố bổ sung. Euclid có lẽ giả định rằng độc giả của ông tin chắc rằng phép chứng minh tương tự sẽ cũng đúng, bất kể có bao nhiêu số nguyên tố được chọn lúc ban đầu.

Euclid thường được mô tả một cách sai lầm rằng đã chứng minh kết quả này bằng mâu thuẫn bắt đầu với giả định rằng tập hữu hạn ban đầu được xem có chứa tất cả các số nguyên tố, mặc dù nó thực sự là một chứng minh bằng cách xét tất cả các trường hợp, một phương pháp chứng minh trực tiếp. Nhà triết học Torkel Franzén, trong một cuốn sách về logic, đã nói, "Chứng minh của Euclid rằng có vô số số nguyên tố không phải là một chứng minh gián tiếp [... ] Cách chứng minh của ông đôi khi được coi là một chứng minh gián tiếp bằng cách thay thế nó bằng giả định 'Giả sử là tất cả các số nguyên tố'. Tuy nhiên, vì giả định này thậm chí không được sử dụng trong phép chứng minh của ông, nên việc thay thế câu giả định như trên là vô nghĩa. "

Biến thể

Một số biến thể của chứng minh của Euclid tồn tại như sau:

Giai thừa n! của một số nguyên dương n chia hết cho mọi số nguyên từ 2 đến n, vì nó là tích của tất cả các số này. Do đó, không chia hết cho bất kỳ số nguyên nào từ 2 đến n, (nó cho số dư là 1 khi chia cho mỗi số nguyên). Do đó là số nguyên tố hoặc chia hết cho số nguyên tố lớn hơn n. Trong cả hai trường hợp, với mỗi số nguyên dương n, có ít nhất một số nguyên tố lớn hơn n. Kết luận là số lượng các số nguyên tố là vô hạn.