ปัญหาชิงรางวัลข้อที่ 1: Primes of the form n^n+1

[warut]

จงหาจำนวนเต็มบวก \(n\) ที่น้อยที่สุดที่ปัจจุบันเรายังไม่ทราบว่า \(n^n+1\) เป็นจำนวนเฉพาะหรือจำนวนประกอบ

[nongtum]

ที่จะแสดงต่อไปนี้เป็นแค่ข้อสันนิษฐานหนึ่งในหลายกรณีที่เป็นไปได้(n อาจไม่น้อยที่สุด) คิดว่าอาจช่วยหลายๆคนที่นั่งคิดข้อนี้เหมือนกัน

ก่อนอื่นสังเกตว่าหาก n เป็นเลขคี่ จะได้ 2|nⁿ+1 และสำหรับจำนวนเต็มบวก k ใดๆ p^3k+1=(p^k+1)(p^2k-p^k+1) ดังนั้นเหลือกรณี $n=6k\pm2$ ที่ต้องพิจารณา
เราทราบว่าจำนวนในรูป $2^m+1, m\in\mathbb{N}$ อาจจะเป็น Fermat Prime เมื่อ $m=2^n$ และจาก $2^n\equiv\pm2\pmod{6}$ จะได้ว่า Fermat prime เข้ากรณีที่เรากำลังหาพอดีหาก $n=2^r,\ r\in\mathbb{N}$ และ $\exists s\in\mathbb{N}:r=2^s$
ด้วยเหตุผลดังกล่าวและจากข้อมูลที่ได้ในหน้านี้เราทราบว่าสำหรับ s=1,2,3,4,5: $F_3$ (n=4), $F_{6}$ (n=16), $F_{11}$ (n=256), $F_{20}$ (n=2¹⁶), $F_{37}$ (n=2³²) มีตัวประกอบหรือไม่ ผมจึงขอสันนิษฐานว่า $F_{70}={(2^{64})}^{(2^{64})}+1$ (s=6) หรือ n=2⁶⁴ เป็นค่า n ที่น้อยที่สุด(สำหรับ Fermat number)ที่เรายังบอกไม่ได้ว่า nⁿ+1 เป็นจำนวนเฉพาะหรือไม่ (ชักไม่แน่ใจตัวเองว่าคิดถูกไหม)

EDIT: มาแก้แคส่วนสมมติฐาน ส่วนวิธีทำน้อง gools แสดงไปแล้ว

[warut]

เยี่ยมครับ คุณ nongtum เริ่มทำให้ข้อนี้มีแสงสว่างแล้ว แม้จะยังไม่ตรงทางเป๊ะๆ แต่คงทำให้หลายๆคนได้แนวคิดไปไม่น้อยเลยครับ

[gools]

$(2^{64})^{2^{64}}$ หรือเปล่าครับ ส่วนที่มาก็มาจากหน้านี้ครับ http://mathworld.wolfram.com/Sierpin...FirstKind.html

[warut]

ไอ้หยา ไม่ยักกะรู้ว่ามีเพจสำหรับเรื่องนี้อยู่โดยเฉพาะ แถมผมยังไม่รู้ด้วยว่าจำนวนแบบนี้เค้าเรียกกันว่า Sierpinski Number of the First Kind

แต่ว่าผมถามหา \(n\) นะครับ ไม่ใช่ \(n^n\) แล้วก็สิ่งที่สำคัญที่ผมต้องการคือการพิสูจน์ว่า \(n\) ควรจะอยู่ในรูปใดถึงจะทำให้ \(n^n+1\) มีโอกาสเป็นจำนวนเฉพาะได้ ไม่ยากครับ ง่ายกว่าปัญหาชิงรางวัลข้อที่ 5 มากๆ ใช้ความรู้แค่ ม.ปลายพื้นๆเอง

[gools]

วิธีแสดงก็เหมือนพี่ nongtum ครับ

จะเห็นได้ว่าจำนวนที่อยู่ในรูป $n^n+1$ เป็นจำนวนเฉพาะแล้ว $n$ จะเป็นจำนวนคู่
ให้ $n=2^ka$ เมื่อ $a$ เป็นจำนวนเต็มคี่ที่ไม่เป็นลบและ $k$ เป็นจำนวนเต็มที่ไม่เป็นลบ
เนื่องจาก
\[(2^ka)^{2^ka}+1=((2^ka)^{2^k})^a+1=((2^ka)^{2^k}+1)[((2^ka)^{2^k})^{a-1}-...]\]
ดังนั้น $a=1$
เราจะได้ว่า $n^n+1=(2^k)^{2^k}+1=2^{k2^k}+1=(2^{2^k})^k+1$
ถ้า $k$ มีเลขคี่ที่มากกว่า $1$ เป็นตัวประกอบแล้วเราจะสามารถแยกตัวประกอบต่อไปได้อีก
ดังนั้น $k$ เป็นจำนวนอยู่ในรูป $2^i$ เมื่อ $i$ เป็นจำนวนเต็มที่ไม่เป็นลบ
ดังนั้น $(2^{2^k})^k+1=(2^{2^{2^{i}}2^i})+1=(2^{2^{2^{i}+i}})+1$
ดังนั้น $n^n+1$ เป็นจำนวนเฉพาะแล้วต้องเป็นจำนวนของแฟร์มาต์ด้วย
เนื่องจากมีการพบตัวประกอบของ $(2^{2^{5}})^{2^{2^{5}}}+1=(2^{2^{37}})+1$ แล้ว ดังนั้นจำนวนเต็มบวก $n$ ที่น้อยที่สุดที่ปัจจุบันเรายังไม่ทราบว่า $n^n+1$ เป็นจำนวนเฉพาะหรือจำนวนประกอบคือ $2^{2^{6}}$

[warut]

น้อง gools ตอบได้ถูกต้องสมบูรณ์แล้วครับ รับไปอีก 5 คะแนน ส่วนคุณ nongtum ผู้ชี้ทางสว่าง ได้ไปอีก 2 คะแนนครับ