Định lý Euclid–Euler

Bài này viết về định lý về số hoàn thiện và số nguyên tố Mersenne. Đối với định lý về sự tồn tại vô số số nguyên tố, xem Định lý Euclid.

Định lý Euclid–Euler là một định lý trong lý thuyết số liên hệ số hoàn thiện với số nguyên tố Mersenne. Định lý này phát biểu rằng một số chẵn là số hoàn thiện khi và chỉ khi nó có dạng 2^p−1(2^p − 1), trong đó 2^p − 1 là số nguyên tố. Nó được đặt tên theo hai nhà toán học Euclid và Leonhard Euler, là hai người đã lần lượt chứng minh được phần "khi" và "chỉ khi" của định lý.

Ví dụ về Định lý Euclid-Euler

Có giả thuyết cho rằng có vô số số nguyên tố Mersenne. Mặc dù vẫn chưa rõ giả thuyết này có chính xác hay không, nhưng theo định lý Euclid–Euler, nó tương đương với giả thuyết rằng có vô số số hoàn thiện chẵn. Tuy nhiên, cũng chưa rõ có tồn tại một số hoàn thiện lẻ hay không.

Phát biểu và ví dụ

Số hoàn thiện là một số tự nhiên có giá trị bằng tổng các ước thật sự của nó (ước thực sự của một số được định nghĩa là những số nhỏ hơn nó và chia hết nó, với số dư bằng không). Ví dụ, các ước thật sự của 6 là 1, 2 và 3, và ba số trên có tổng bằng 6, nên 6 là số hoàn thiện.

Số nguyên tố Mersenne là số nguyên tố có dạng M_p = 2^p − 1, nhỏ hơn 1 đơn vị so với lũy thừa của 2. Để một số dạng này là số nguyên tố thì p phải là số nguyên tố, nhưng không phải mọi số nguyên tố áp vào công thức trên đều cho giá trị là số nguyên tố Mersenne. Chẳng hạn, 2³ − 1 = 7 là số nguyên tố Mersenne, nhưng 2¹¹ − 1 = 2047 = 23 × 89 thì không phải.

Định lý Euclid–Euler phát biểu rằng một số tự nhiên chẵn là số hoàn thiện khi và chỉ khi nó có dạng 2^p−1M_p với M_p là số nguyên tố Mersenne. Số hoàn thiện 6 có được trong trường hợp p = 2 do 2²⁻¹M₂ = 2 × 3 = 6, và số nguyên tố Mersenne 7 thay vào dạng nói trên cho giá trị là số hoàn thiện 28.

Lịch sử

Euclid chứng minh được 2^p−1(2^p − 1) là số hoàn thiện chẵn khi 2^p − 1 là số nguyên tố. Đây là kết quả cuối cùng về lý thuyết số trong bộ Cơ sở của Euclid; các cuốn tiếp theo trong bộ sách này tập trung vào số vô tỉ, hình học không gian và tỷ lệ vàng. Euclid thể hiện kết quả này bằng cách phát biểu rằng nếu một cấp số nhân hữu hạn với số hạng đầu là 1 và công bội là 2 có tổng là số nguyên tố q, thì tổng này nhân cho số hạng cuối cùng t của dãy số này là một số hoàn thiện. Biểu diễn cụ thể đối với dãy số này thì tổng q của các số hạng là số nguyên tố Mersenne 2^p − 1 và số hạng cuối cùng của dãy t là lũy thừa của 2, 2^p−1. Euclid chứng minh qt là số hoàn thiện khi nhận thấy một cấp số nhân thứ hai, với số hạng đầu là q, công bội là 2 và có cùng số các số hạng, có tính tỷ lệ thuận với cấp số nhân ban đầu; do đó, vì tổng của dãy số ban đầu là q = 2t − 1 nên tổng của dãy số thứ hai là q(2t − 1) = 2qt − q, và tổng của cả hai dãy số cộng lại là 2qt, bằng hai lần số hoàn thiện giả thiết lúc đầu. Tuy nhiên, hai dãy số này lại không giao nhau và (do tính nguyên tố của q) vét kiệt tất cả các ước của qt, nên qt là một số có tổng các ước bằng 2qt, dẫn đến nó là số hoàn thiện.

Hơn một thiên niên kỷ sau Euclid, Alhazen khoảng năm 1000 sau Công nguyên đưa ra giả thuyết rằng mọi số hoàn thiện chẵn đều có dạng 2^p−1(2^p − 1) với 2^p − 1 là số nguyên tố, nhưng ông không thể chứng minh được giả thuyết đó. Phải đến thế kỷ 18, hơn 2000 năm sau Euclid, Leonhard Euler mới chứng minh được rằng công thức 2^p−1(2^p − 1) luôn cho giá trị là số hoàn thiện chẵn. Như vậy, tồn tại mối liên hệ một–một giữa số hoàn thiện chẵn và số nguyên tố Mersenne; mỗi số nguyên tố Mersenne cho một số hoàn thiện chẵn tương ứng, và ngược lại. Từ sau chứng minh của Euler, nhiều nhà toán học đã xuất bản các cách chứng minh khác cho định lý Euclid–Euler như Victor-Amédée Lebesgue, Robert Daniel Carmichael, Leonard Eugene Dickson, John Knopfmacher và Wayne L. McDaniel. Đặc biệt, chứng minh của Dickson đã được nhắc đến phổ biến trong sách giáo khoa.

Định lý này nằm trong danh sách web "top 100 định lý toán học", có từ năm 1999, mà về sau được Freek Wiedijk sử dụng làm kiểm chuẩn để kiểm tra độ mạnh của các trình hỗ trợ chứng minh định lý khác nhau. Tính đến năm 2021, phần chứng minh của định lý Euclid–Euler đã được định hình tại 5 trên 10 trình hỗ trợ mà Wiedijk theo dõi.

Chứng minh

Chứng minh của Euler là một chứng minh ngắn và dựa trên cơ sở rằng hàm tổng các ước σ là hàm nhân tính, nghĩa là nếu a và b là hai số nguyên tố cùng nhau thì σ(ab) = σ(a)σ(b). Để công thức này chính xác, tổng các ước của một số phải tính cả số hạng là chính số đó chứ không chỉ tính các ước thật sự của nó. Một số được coi là hoàn thiện khi và chỉ khi tổng các ước của nó bằng hai lần số đó.

Điều kiện đủ

Phần đầu tiên của định lý (phần đã được Euclid chứng minh) được suy ra từ tính nhân tính: mỗi số nguyên tố Mersenne tương ứng với một số hoàn thiện chẵn được tạo thành. Khi 2^p − 1 là số nguyên tố thì

$\sigma (2^{p-1}(2^{p}-1))=\sigma (2^{p-1})\sigma (2^{p}-1).$

Các ước của 2^p−1 là 1, 2, 4, 8, ..., 2^p−1, tạo thành một cấp số nhân với tổng là 2^p − 1. Vì 2^p − 1 là số nguyên tố nên nó chỉ có hai ước là 1 và chính nó, và do đó, tổng các ước của nó là 2^p.

Kết hợp lại, ta có:

${\begin{aligned}\sigma (2^{p-1}(2^{p}-1))&=\sigma (2^{p-1})\sigma (2^{p}-1)\\&=(2^{p}-1)(2^{p})\\&=2(2^{p-1})(2^{p}-1).\end{aligned}}$

Do đó, 2^p−1(2^p − 1) là số hoàn thiện.

Điều kiện cần

Ngược lại, giả sử tồn tại một số hoàn thiện chẵn được phân tích một phần dưới dạng 2^kx, với x là số lẻ. Để 2^kx là số hoàn thiện thì tổng các ước của nó phải bằng hai lần số đó:

$2^{k+1}x=\sigma (2^{k}x)=(2^{k+1}-1)\sigma (x).$

(∗)

Thừa số lẻ 2^k+1 − 1 ở vế phải của (∗) có giá trị nhỏ nhất là 3, và nó phải là ước của x, thừa số lẻ duy nhất ở vế trái, nên y = x/(2^k+1 − 1) là một ước thật sự của x. Chia cả hai vế của (∗) cho thừa số chung 2^k+1 − 1 và xem xét các ước số x và y đã biết của x, ta được

$2^{k+1}y=\sigma (x)=x+y+{}$các ước số khác${}=2^{k+1}y+{}$các ước số khác.

Để đẳng thức trên đúng thì không thể tồn tại một ước số nào khác. Do đó, y phải bằng 1, và x phải là một số nguyên tố dạng 2^k+1 − 1.