ปัญหาชิงรางวัลข้อที่ 16: Prime of the form 2^n-777149?

[warut]

จงหาจำนวนเต็มบวก $n$ ที่น้อยที่สุดที่ทำให้ $2^n-777149$ เป็นจำนวนเฉพาะ

[nongtum]

ยังคิดไม่ออก แต่ลงเท่าที่คิดได้บางส่วนก่อนนะครับ

ให้ $m(n):=2^n-777149$
จาก $m(n)\equiv\cases{ -1\pmod3&,\ n\ คู่\cr 0\pmod3&,\ n\ คี่}$ และ $5|m(4k+2)$ จะได้ว่า $m(n)$ จะเป็นจำนวนเฉพาะได้เมื่อ $4|n$
จากการทดลองทดและคำนวณค่าใน mathematica จึงขอตั้งข้อสังเกตว่า $m(4k)$ ไม่เป็นจำนวนเฉพาะสำหรับ $k=1,\dots,50$

[R-Tummykung de Lamar]

ผมไล่ไปจนถึง k = 200 000 แล้ว ยังไม่เจอเลยครับ

ขอ hint ซักเล็กน้อยได้ปะครับ ไม่มีแนวทางเลย

[warut]

ต้องขออภัยเป็นอย่างสูงครับ ที่ช่วงนี้หายหน้าไปเลย

Hint: จริงๆแล้วมันไม่มีหรอกครับ จำนวนเฉพาะที่อยู่ในรูปนี้น่ะ ดังนั้นจุดสำคัญคือการแสดงว่า $2^n-777149$ เป็นจำนวนประกอบ สำหรับทุกจำนวนเต็มบวก $n$

ป.ล. (= Hint #2) แล้วระหว่างที่มองหาจำนวนเฉพาะอยู่นั้น ได้สังเกตเห็น pattern อะไรบ้างไหมครับ ถ้าไม่ได้ปล่อยให้คอมพิวเตอร์ทำแบบ blind mode ก็น่าจะเห็นอะไรบ้างนะครับ

[nongtum]

ต่อจากด้านบนนะครับ
ให้ $m'(a)=16^a-777149$ และ a,r,s เป็นจำนวนเต็ม จะแสดงข้อความต่อไปนี้
i) a=3r+1 => 7|m'(a)
ii) a=3r+2 => 13|m'(a)
iii) a=3r
$\qquad$a) a=9s+3 => 19|m'(a)
$\qquad$b) a=9s+6 => 73|m'(a)
$\qquad$c) a=9s => 37|m'(a)

พิสูจน์
i) $m'(a)\equiv2^{3r}\cdot2-2=8^r \cdot 2 -2\equiv2-2\equiv0\pmod7$
ii) $m'(a)\equiv3^{3r}\cdot9-9=27^r\cdot9-9\equiv9-9\equiv0\pmod{13}$
iii)
a) $m'(a)\equiv(-3)^{9s}(-27)-11\equiv(-8)^{3s}(-8)+8\equiv-8+8\equiv0\pmod{19}$
b) $m'(a)\equiv8^{3s}\cdot64-64\equiv64-64\equiv0\pmod{73}$
c) $m'(a)\equiv26^{3s}-1\equiv(-11)^{3s}-1\equiv1-1\equiv0\pmod{37}$
และเนื่องจาก m(n) ไม่เท่ากับ 3,5,7,13,19,37,73 ดังนั้น m(n) เป็นจำนวนประกอบทุกจำนวนเต็มบวก n ###

ปล: หากคำนวณสั้นไปนิด ต้องขอโทษด้วยนะครับ ไม่เข้าใจสามารถถามได้ครับ

[warut]

ถูกต้องแล้วคร้าบ (มีพิมพ์เลขตกไปนิดนึง ซึ่งผมแก้ให้แล้ว) คุณ nongtum รับไปอีก 5 คะแนน ทำให้ตอนนี้นำโด่งเลยครับ

เมื่อมีโอกาสผมจะมาเขียนความเห็นเพิ่มเติมอีกทีนะครับ

[warut]

มาอธิบายเพิ่มเติมต่อตามที่สัญญาไว้ครับ

ปรากฎการณ์แบบที่เห็นในข้อนี้ เค้าเรียกกันว่า "covering congruences" ครับ จำนวนที่อยู่ในรูป $2^n-777149$ จะมีตัวประกอบเป็นหนึ่งในสมาชิกของ "covering set" $\{ 3, 5, 7, 13, 19, 37, 73 \}$ เสมอ ดังนั้นมันจึงไม่มีโอกาสเป็นจำนวนเฉพาะเลย

ตัวอย่างอื่นๆก็เช่น จำนวนที่อยู่ในรูป $78557\cdot2^n+1$ หรือ $509203\cdot2^n-1$ ก็จะเป็นจำนวนประกอบเสมอเช่นกัน

เราเรียกจำนวนคี่บวก $k$ ที่ทำให้ $k \cdot 2^n +1$ เป็นจำนวนประกอบเสมอ ว่า Sierpinski number เพราะ Sierpinski ได้ค้นพบเป็นคนแรกในปี 1960 ตัวอย่างของ Sierpinski number ได้แก่ 78557, 271129, 271577, 322523, 327739

เราเรียกจำนวนคี่บวก $k$ ที่ทำให้ $k \cdot 2^n -1$ เป็นจำนวนประกอบเสมอ ว่า Riesel number เนื่องจาก Riesel ได้ค้นพบเป็นคนแรกในปี 1956 ตัวอย่างของ Riesel number ก็เช่น 509203, 762701, 777149, 790841, 992077

เป็นที่น่าสังเกตว่า ถึงแม้ปรากฎการณ์แบบนี้จะไม่ต้องใช้คณิตศาสตร์ชั้นสูงมาอธิบาย แต่เราก็เพิ่งค้นพบมันเมื่อไม่นานมานี้เอง ผมคิดว่าน่าจะเป็นเพราะไม่มีใครคาดคิดมาก่อนว่าจะมีค่า $k$ เช่นนั้นอยู่ เนื่องจากโดยสามัญสำนึกมันชวนให้เราคิดว่า ไม่ว่า $k$ จะเป็นจำนวนใด ก็น่าจะมีค่า $n$ ที่ทำให้ $k \cdot 2^n +1$ หรือ $k \cdot 2^n -1$ เป็นจำนวนเฉพาะได้เสมอ แม้ว่าอาจจะต้องหากันไปไกลสักหน่อยก็เถอะ