2^k-1 ถ้ามันเป็นจำนวนเฉพาะนี่ก็คือ
Mersenne Prime นะครับ
กำหนดจำนวนเต็มบวก r และ s จะพบว่า
$2^{rs} -1 = (2^r-1)(2^{r(s-1)} + 2^{r(s-2)} + ... + 1)$
นั้นคือ ถ้า k เป็นจำนวนประกอบ (k=rs) แล้ว 2^k - 1 จะเป็นจำนวนประกอบ (แยก 2^r-1 ออกมาได้)
แล้วจากตรรกศาสตร์ ก็จะได้ว่า ถ้า 2^k - 1 ไม่เป็นจำนวนประกอบ (ก็คือเป็นจำนวนเฉพาะ) แล้ว k จะเป็นจำนวนเฉพาะ
สำหรับทำไมว่า $2^{rs} -1 = (2^r-1)(2^{r(s-1)} + 2^{r(s-2)} + ... + 1)$ ขอให้มองว่า 2^k-1 คือเลขฐานสองที่มีแต่ 1 เรียงกัน k ตัว ดังนั้น 2^(rs) -1 ก็จะเป็นฐานสองที่มีแต่ 1 เรียงกัน rs ตัว ถ้า "หั่นสับ" เลขฐานสองนั้นเป็นชิ้นๆ แต่ละชิ้นคือเลขฐานสองที่มีแต่ 1 ยาว r ตัว (ซึ่งเท่ากับ 2^r-1) ถ้าจะเอา 2^r-1 มาประกอบกลับคืนให้เป็น 2^(rs) -1 ก็ต้องเอา 2^r-1 มาเลื่อนบิตไปทางซ้ายที่ละ s แล้วบวกกัน
02 มีนาคม 2016, 19:03
