การทดสอบของลูคัส-เลห์เมอร์ (Lucas-Lehmer test) ทำงานอย่างไร?

สำหรับเลขชี้กำลังที่เป็นจำนวนเฉพาะ p ที่มากกว่าหรือเท่ากับ 3 ให้กำหนด S_0 = 4 และ S_i = S_(i-1)^2 - 2 โมดูโล M_p จำนวนแมร์เซน M_p = 2^p - 1 จะเป็นจำนวนเฉพาะก็ต่อเมื่อ S_(p-2) สอดคล้องกับ 0 โมดูโล M_p การทดสอบจะทำงานใน p-2 รอบ โดยแต่ละรอบจะเป็นการยกกำลังสองแบบโมดูลาเพียงครั้งเดียว

จำนวนเฉพาะแมร์เซนกับจำนวนสมบูรณ์ (Perfect Numbers) เกี่ยวข้องกันอย่างไร?

ทฤษฎีบทของยูคลิด-ออยเลอร์ระบุว่าจำนวนสมบูรณ์คู่ทุกจำนวนจะอยู่ในรูป 2^(p-1) คูณ (2^p - 1) โดยที่ 2^p - 1 เป็นจำนวนเฉพาะแมร์เซน ดังนั้นจำนวนเฉพาะแมร์เซนทุกจำนวนจะสร้างจำนวนสมบูรณ์คู่ได้เพียงหนึ่งจำนวน และจำนวนสมบูรณ์คู่ทุกจำนวนมาจากจำนวนเฉพาะแมร์เซน การมีอยู่ของจำนวนสมบูรณ์คี่หรือไม่นั้นยังคงเป็นหนึ่งในปัญหาเปิดที่เก่าแก่ที่สุดในวิชาคณิตศาสตร์

ทำไม M_p ถึงมีเลข 1 ติดกัน p ตัวในระบบเลขฐานสอง?

เลข 2^p ในระบบฐานสองคือเลข 1 ตามด้วยเลขศูนย์ p ตัว การลบออก 1 จะเปลี่ยนเลขศูนย์ p ตัวที่ตามหลังทั้งหมดให้กลายเป็นเลข 1 ดังนั้น 2^p - 1 ในระบบฐานสองจึงมีเลขหนึ่ง p ตัวพอดี ซึ่งเป็นลักษณะทางภาพที่ระบุความเป็นจำนวนแมร์เซนทุกจำนวน

ตัวตรวจสอบจำนวนเฉพาะแมร์เซน

ตรวจสอบว่า 2^p − 1 เป็นจำนวนเฉพาะแมร์เซนสำหรับเลขชี้กำลัง p ที่กำหนดหรือไม่ โดยใช้การทดสอบความแจ้งชัดของลูคัส-เลห์เมอร์ พร้อมการแสดงลำดับการทำซ้ำแบบเคลื่อนไหว การจำลองรูปแบบบิตฐานสอง การจับคู่เลขสมบูรณ์แบบยูคลิด-ออยเลอร์ และบริบททางประวัติศาสตร์ของจำนวนเฉพาะแมร์เซนทั้ง 52 จำนวนที่รู้จัก

เลือกเลขชี้กำลังที่มีชื่อเสียงเพื่อทดสอบ — แต่ละรายการรันในหน่วยมิลลิวินาที:

✦ $M_p$ ที่เป็นจำนวนเฉพาะ p = 13 p = 17 p = 31 p = 61 p = 127

✕ $M_p$ ที่เป็นจำนวนประกอบ p = 11 p = 23 p = 37 p = 67

⚡ ตัวเลขขนาดใหญ่ p = 521 p = 1279 p = 2281 p = 4253

เลขชี้กำลัง p ใน $M_p = 2^p - 1$

จำนวนเต็มบวกตั้งแต่ 1 ถึง 5,000 สำหรับเลขชี้กำลังที่ใหญ่กว่า โปรดใช้ซอฟต์แวร์เฉพาะทางเช่น Prime95

Embed ตัวตรวจสอบจำนวนเฉพาะแมร์เซน Widget

เกี่ยวกับ ตัวตรวจสอบจำนวนเฉพาะแมร์เซน

ยินดีต้อนรับสู่ ตัวตรวจสอบจำนวนเฉพาะแมร์เซน เครื่องมือแบบโต้ตอบที่จะทดสอบว่า $2^p - 1$ เป็น จำนวนเฉพาะแมร์เซน หรือไม่ สำหรับเลขชี้กำลัง $p$ ใดๆ ที่มีค่าสูงสุด 5,000 เครื่องมือนี้จะรัน การทดสอบความเป็นจำนวนเฉพาะของลูคัส-เลห์เมอร์ ที่มีชื่อเสียง แสดงร่องรอยการวนซ้ำแบบแอนิเมชันของความสัมพันธ์เวียนเกิด $S_i = S_{i-1}^2 - 2 \pmod{M_p}$, แสดงภาพรูปแบบบิตฐานสอง (ซึ่งเป็นลักษณะเฉพาะของจำนวนแมร์เซนทุกจำนวน) และเมื่อผลลัพธ์เป็นจำนวนเฉพาะ จะจับคู่กับจำนวนสมบูรณ์คู่ที่เกี่ยวข้องผ่าน ทฤษฎีบทของยูคลิด-ออยเลอร์

จำนวนเฉพาะแมร์เซนคืออะไร?

จำนวนแมร์เซน คือจำนวนที่อยู่ในรูป $M_p = 2^p - 1$ เมื่อ $M_p$ เป็นจำนวนเฉพาะในตัวมันเอง จะถูกเรียกว่า จำนวนเฉพาะแมร์เซน ชื่อนี้ตั้งเพื่อเป็นเกียรติแก่ มารีน แมร์เซน (Marin Mersenne, 1588-1648) นักบวชชาวฝรั่งเศสผู้รวบรวมกรณีแรกๆ และคาดการณ์ว่าเลขชี้กำลังใดบ้างที่ให้ค่าเป็นจำนวนเฉพาะจนถึง 257 แม้ว่ารายการดังกล่าวจะผิดไปบางส่วน แต่ก็ได้เป็นจุดเริ่มต้นของการวิจัยนานกว่าสามศตวรรษ

จำนวนเฉพาะแมร์เซน

$$M_p = 2^p - 1 \;\; \text{เป็นจำนวนเฉพาะ โดยที่ } p \text{ เองต้องเป็นจำนวนเฉพาะ}$$

จำนวนเฉพาะแมร์เซนชุดแรกๆ ตามลำดับ:

$M_2 = 3$
$M_3 = 7$
$M_5 = 31$
$M_7 = 127$
$M_{13} = 8{,}191$
$M_{17} = 131{,}071$
$M_{19} = 524{,}287$
$M_{31} = 2{,}147{,}483{,}647$ (ค้นพบโดยออยเลอร์ในปี 1772 — เป็นจำนวนเฉพาะที่ใหญ่ที่สุดที่รู้จักมานานถึง 104 ปี)

ณ ปี 2024 มี จำนวนเฉพาะแมร์เซนที่รู้จักแน่ชัด 52 จำนวน สถิติปัจจุบันคือ $M_{136{,}279{,}841}$ ค้นพบในเดือนตุลาคม 2024 โดยโครงการคำนวณแบบกระจาย GIMPS ซึ่งเป็นจำนวนที่มีเลขหลักทศนิยมถึง 41,024,320 หลัก

การทดสอบของลูคัส-เลห์เมอร์

สาเหตุที่จำนวนเฉพาะแมร์เซนครองอันดับในหนังสือบันทึกสถิติโลกมาโดยตลอด คือการทดสอบความเป็นจำนวนเฉพาะที่มีความเร็วสูงเป็นพิเศษซึ่งค้นพบโดย Édouard Lucas (1878) และทำให้ง่ายขึ้นโดย Derrick Lehmer (1930):

การทดสอบของลูคัส-เลห์เมอร์

$$S_0 = 4, \quad S_i = S_{i-1}^2 - 2 \pmod{M_p}$$

สำหรับจำนวนเฉพาะ $p \geq 3$: $\;M_p$ เป็นจำนวนเฉพาะ $\iff S_{p-2} \equiv 0 \pmod{M_p}$

การทดสอบนี้ต้องการการยกกำลังสองแบบโมดูลาเพียง $p-2$ ครั้ง — ซึ่งเป็นการดำเนินการทางบิตประมาณ $O(p^3)$ ด้วยการคูณแบบโรงเรียน หรือ $O(p^2 \log p \log\log p)$ ด้วย FFT เมื่อเทียบกับการทดสอบความเป็นจำนวนเฉพาะทั่วไปในตัวเลขที่มีขนาดเท่ากับ $M_p$ (หลายล้านหลัก) ซึ่งเป็นไปไม่ได้เลย ทางลัดของลูคัส-เลห์เมอร์นี้เองที่ทำให้การค้นหาจำนวนเฉพาะแมร์เซนเป็นไปได้

ทำไม p ต้องเป็นจำนวนเฉพาะ?

ถ้า $p = a \cdot b$ โดยที่ $a, b > 1$ เอกลักษณ์คลาสสิกจะแสดงให้เห็นว่า $2^a - 1$ จะหาร $2^{ab} - 1$ ลงตัว:

เอกลักษณ์การแยกตัวประกอบ

$$2^{ab} - 1 = (2^a - 1)\left(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1\right)$$

ดังนั้นหากเลขชี้กำลังเป็นจำนวนประกอบ $M_p$ จะเป็นจำนวนประกอบโดยอัตโนมัติ แต่ในทางกลับกันไม่เป็นจริง: การที่ $p$ เป็นจำนวนเฉพาะ ไม่ได้รับประกัน ว่า $M_p$ จะเป็นจำนวนเฉพาะ ตัวอย่างเช่น $p = 11$ เป็นจำนวนเฉพาะแต่ $M_{11} = 2047 = 23 \times 89$

จำนวนเฉพาะแมร์เซนและจำนวนสมบูรณ์ (ยูคลิด-ออยเลอร์)

ยูคลิดสังเกตเห็นเมื่อประมาณ 300 ปีก่อนคริสตกาลว่าถ้า $2^p - 1$ เป็นจำนวนเฉพาะ แล้ว $2^{p-1}(2^p - 1)$ จะเป็น จำนวนสมบูรณ์ — ซึ่งเป็นจำนวนที่มีค่าเท่ากับผลรวมของตัวหารแท้ของมัน ต่อมาออยเลอร์ได้พิสูจน์ในทางกลับกันว่า: จำนวนสมบูรณ์คู่ทุกจำนวนเกิดขึ้นในรูปแบบนี้

ทฤษฎีบทของยูคลิด-ออยเลอร์

$$N \text{ เป็นจำนวนสมบูรณ์คู่} \iff N = 2^{p-1}(2^p - 1),\;\; 2^p - 1 \text{ เป็นจำนวนเฉพาะ}$$

ดังนั้นการค้นพบจำนวนเฉพาะแมร์เซนใหม่จะสร้างจำนวนสมบูรณ์ใหม่ขึ้นมาทันที จำนวนสมบูรณ์คู่สี่ตัวแรกคือ 6, 28, 496 และ 8128 ซึ่งเป็นที่รู้จักมาตั้งแต่สมัยโบราณ ส่วนเรื่องที่ว่ามีจำนวนสมบูรณ์ คี่ อยู่หรือไม่นั้น ยังคงเป็นปัญหาที่ยังแก้ไม่ได้มานานกว่า 2,300 ปี

รูปแบบบิตฐานสอง

จำนวนแมร์เซนทุกจำนวนมีการแสดงผลในระบบฐานสองที่สะอาดตาเป็นเอกลักษณ์: $2^p$ ในระบบฐานสองคือ $1$ ตามด้วยเลขศูนย์ $p$ ตัว ดังนั้น $2^p - 1$ จะเป็นเลข 1 ติดกัน $p$ ตัวพอดี:

M_5 = 2^5 − 1 = 11111₂ = 31

M_7 = 2^7 − 1 = 1111111₂ = 127

นี่คือสาเหตุที่เครื่องมือแสดงภาพแต่ละบิตเป็นแผ่นป้ายแยกกัน — รูปแบบบิตนี้เป็นเครื่องหมายทางภาพของจำนวนแมร์เซน ไม่ว่าจำนวนนั้นจะเป็นจำนวนเฉพาะหรือไม่ก็ตาม

วิธีใช้เครื่องคำนวณนี้

ป้อนเลขชี้กำลัง $p$: จำนวนเต็มบวกตั้งแต่ 1 ถึง 5,000
คลิก ตรวจสอบ (Check): เครื่องมือจะตรวจสอบก่อนว่า $p$ เป็นจำนวนเฉพาะหรือไม่ หากไม่ใช่ จะอธิบายว่าทำไม $M_p$ จึงต้องเป็นจำนวนประกอบ
สำหรับ p ที่เป็นจำนวนเฉพาะ: ความสัมพันธ์เวียนเกิดของลูคัส-เลห์เมอร์จะรัน $p - 2$ รอบโมดูโล $M_p$
สำรวจผลลัพธ์: แถบคำตัดสิน, ร่องรอยการวนซ้ำ 6 แถว (พร้อมเครื่องหมาย "..." สำหรับขั้นตอนที่ละไว้ในกรณี p ขนาดใหญ่), รูปแบบฐานสิบและฐานสองของ $M_p$ และการจับคู่จำนวนสมบูรณ์ของยูคลิด-ออยเลอร์เมื่อทำได้

จำนวนเฉพาะแมร์เซน 12 ลำดับแรกที่รู้จัก

ลำดับที่	เลขชี้กำลัง $p$	$M_p = 2^p - 1$	จำนวนหลัก	ผู้ค้นพบ
1	2	3	1	สมัยโบราณ
2	3	7	1	สมัยโบราณ
3	5	31	2	สมัยโบราณ
4	7	127	3	สมัยโบราณ
5	13	8,191	4	1456 (ไม่ระบุนาม)
6	17	131,071	6	1588 Cataldi
7	19	524,287	6	1588 Cataldi
8	31	2,147,483,647	10	1772 Euler
9	61	2.3 × 10^18	19	1883 Pervushin
10	89	6.2 × 10^26	27	1911 Powers
11	107	1.6 × 10^32	33	1914 Powers
12	127	1.7 × 10^38	39	1876 Lucas

โครงการ GIMPS

Great Internet Mersenne Prime Search (GIMPS) เริ่มต้นขึ้นในปี 1996 โดย George Woltman เป็นโครงการคำนวณแบบกระจายที่อาสาสมัครร่วมบริจาคเวลาของ CPU เพื่อรันการทดสอบลูคัส-เลห์เมอร์ในเลขชี้กำลังที่คาดว่าจะเป็นจำนวนเฉพาะ ณ ปี 2024 จำนวนเฉพาะแมร์เซนทุกจำนวนตั้งแต่ M_35 = M_{1398269} (1996) เป็นต้นมา ถูกค้นพบโดย GIMPS การทดสอบลูคัส-เลห์เมอร์เพียงครั้งเดียวที่ขีดจำกัดปัจจุบัน (เลขชี้กำลังใกล้ $10^8$) ต้องใช้การคำนวณผ่าน GPU นานหลายสัปดาห์

ข้อเท็จจริงที่น่าสนใจเกี่ยวกับจำนวนเฉพาะแมร์เซน

$M_{31} = 2{,}147{,}483{,}647$ เป็นจำนวนเต็มแบบมีเครื่องหมายขนาด 32 บิตที่ใหญ่ที่สุด — คือค่า $\texttt{INT\_MAX}$ ที่มีชื่อเสียงในภาษา C นี่ไม่ใช่เรื่องบังเอิญ ค่านี้มาจากข้อเท็จจริงที่ว่า $M_{31}$ เป็นจำนวนเฉพาะ จึงเป็นขอบเขต "ก่อนที่เลขจะเกิน" (overflow) ตามธรรมชาติ
มีช่องว่างที่ขนาดไม่แน่นอนระหว่างจำนวนเฉพาะแมร์เซนลำดับถัดๆ ไป เราไม่รู้ว่ามีจำนวนเฉพาะแมร์เซน เป็นอนันต์ หรือไม่ — ข้อคาดการณ์ของ Lenstra-Pomerance-Wagstaff คาดว่ามี โดยเติบโตในอัตราประมาณ $e^\gamma \log_2 p$
ในปี 2008 Electronic Frontier Foundation มอบรางวัล 100,000 ดอลลาร์สหรัฐให้แก่ผู้ค้นพบจำนวนเฉพาะที่มี 10 ล้านหลักเป็นคนแรก รางวัลตกเป็นของทีม GIMPS จาก UCLA สำหรับ $M_{43112609}$ ปัจจุบันยังมีรางวัล 150,000 ดอลลาร์สหรัฐสำหรับการค้นพบจำนวนเฉพาะ 100 ล้านหลักคนแรก
$M_{31}$ ปรากฏอยู่บนธนบัตรที่ระลึก 100 รูเบิลของรัสเซียปี 1811 เพื่อเป็นเกียรติแก่การค้นพบของออยเลอร์ — เป็นหนึ่งในจำนวนเฉพาะไม่กี่จำนวนที่เคยพิมพ์ลงบนเงินตรา
เนื่องจากจำนวนเฉพาะแมร์เซนทุกจำนวนให้จำนวนสมบูรณ์ออกมา มนุษยชาติจึงมี จำนวนสมบูรณ์คู่เพียง 52 จำนวน ในบันทึก (เท่ากับจำนวนเฉพาะแมร์เซนที่รู้จัก 52 จำนวน)

คำถามที่พบบ่อย

จำนวนเฉพาะแมร์เซนคืออะไร?

จำนวนเฉพาะแมร์เซนคือจำนวนเฉพาะที่อยู่ในรูป $2^p - 1$ โดยที่ $p$ เป็นจำนวนเฉพาะเช่นกัน ลำดับแรกๆ คือ 3, 7, 31, 127 และ 8,191 ณ ปี 2024 มีจำนวนเฉพาะแมร์เซนที่รู้จัก 52 จำนวน จำนวนที่ใหญ่ที่สุดที่รู้จัก ($M_{136{,}279{,}841}$) เป็นจำนวนเฉพาะแมร์เซนที่มีความยาวมากกว่า 41 ล้านหลัก

การทดสอบของลูคัส-เลห์เมอร์ทำงานอย่างไร?

สำหรับเลขชี้กำลังที่เป็นจำนวนเฉพาะ $p \geq 3$ ให้กำหนด $S_0 = 4$ และ $S_i = S_{i-1}^2 - 2 \pmod{M_p}$ จำนวนแมร์เซน $M_p = 2^p - 1$ จะเป็นจำนวนเฉพาะก็ต่อเมื่อ $S_{p-2} \equiv 0 \pmod{M_p}$ การทดสอบทำงานใน $p - 2$ รอบ โดยแต่ละรอบจะเป็นการยกกำลังสองแบบโมดูลาเพียงครั้งเดียว

ทำไม p ต้องเป็นจำนวนเฉพาะ?

ถ้า $p = ab$ โดยที่มีตัวประกอบทั้งคู่มากกว่า 1 แล้ว $2^p - 1$ จะหารลงตัวด้วย $2^a - 1$ (และด้วย $2^b - 1$) ดังนั้น $M_p$ จึงเป็นจำนวนประกอบ ในทางกลับกัน p ที่เป็นจำนวนเฉพาะไม่ได้หมายความว่า $M_p$ จะต้องเป็นจำนวนเฉพาะเสมอไป ตัวอย่างเช่น $p = 11$ เป็นจำนวนเฉพาะแต่ $M_{11} = 2047 = 23 \times 89$ เป็นจำนวนประกอบ

จำนวนเฉพาะแมร์เซนกับจำนวนสมบูรณ์เกี่ยวข้องกันอย่างไร?

ทฤษฎีบทของยูคลิด-ออยเลอร์ระบุว่าจำนวนสมบูรณ์คู่ทุกจำนวนจะอยู่ในรูป $2^{p-1}(2^p - 1)$ โดยที่ $2^p - 1$ เป็นจำนวนเฉพาะแมร์เซน ดังนั้นจำนวนเฉพาะแมร์เซนทุกจำนวนจะสร้างจำนวนสมบูรณ์คู่ได้หนึ่งจำนวน และจำนวนสมบูรณ์คู่ทุกจำนวนมาจากจำนวนเฉพาะแมร์เซน การมีอยู่ของจำนวนสมบูรณ์คี่หรือไม่นั้นยังคงเป็นหนึ่งในปัญหาเปิดที่เก่าแก่ที่สุดในวิชาคณิตศาสตร์

ทำไม $M_p$ ถึงมีเลข 1 ติดกัน $p$ ตัวในระบบฐานสอง?

เลข $2^p$ ในระบบฐานสองคือ 1 ตามด้วยเลขศูนย์ $p$ ตัว การลบออก 1 จะเปลี่ยนเลขศูนย์ที่ตามหลังทั้ง $p$ ตัวให้กลายเป็นเลข 1 ดังนั้น $2^p - 1$ ในระบบฐานสองจึงมีเลขหนึ่ง $p$ ตัวพอดี — ซึ่งเป็นลักษณะทางภาพที่เป็นเอกลักษณ์ของจำนวนแมร์เซนทุดจำนวน ไม่ว่าจะเป็นจำนวนเฉพาะหรือจำนวนประกอบ

เครื่องมือนี้นักเลขชี้กำลังที่ใหญ่ที่สุดได้เท่าไหร่?

เครื่องมือนี้นักทดสอบเลขชี้กำลังได้สูงสุดถึง 5,000 เพื่อให้การวนซ้ำของลูคัส-เลห์เมอร์เสร็จสิ้นภายในคำขอผ่านเว็บตามปกติ สำหรับเลขชี้กำลังที่ใหญ่กว่า (รวมถึงแนวหน้าของ GIMPS ที่ใกล้เคียง $10^8$) จำเป็นต้องใช้ซอฟต์แวร์เฉพาะทางเช่น Prime95 เนื่องจากหนึ่งการทดสอบอาจใช้เวลานานหลายสัปดาห์บน GPU สมัยใหม่