ปัญหาชิงรางวัลข้อที่ 23: Number Theory once more

[warut]

จงพิสูจน์ว่า $$ 2^{2^n-1} -2^n-1 $$ เป็นจำนวนประกอบ สำหรับทุกจำนวนเต็ม $n>2$

[nooonuii]

To make life easier, I conjecture that

$\displaystyle{2^{2^n-1}-2^n-1}$ is divisible by $p$

where $p$ is the smallest prime divisor of $2^n-1$.

I can prove two special cases for this conjecture :

Case 1 : n is even. Then $\displaystyle{2^{2^n-1}-2^n-1}$ is divisible by $3$.
Case 2 : n is odd and $2^n-1$ is prime, i.e. a Mersenne prime. Then $\displaystyle{2^{2^n-1}-2^n-1}$ is divisible by $2^n-1$ by Fermat's Little Theorem.

Thus it remains to prove the case where n is odd and $2^n-1$ is composite.

[warut]

ข้อคาดเดาของคุณ nooonuii ไม่เป็นจริงครับ เช่น ในกรณีที่ $n=35$ เรามี $31$ เป็นตัวประกอบเฉพาะที่เล็กที่สุดของ $2^n-1$ แต่ $31$ หาร $ 2^{2^n-1} -2^n-1 $ เหลือเศษ $2$ ครับ

ผมยังไม่อยาก comment อะไรมากครับ เพราะเพิ่งจะโพสต์โจทย์ไป อาจจะมีบางคนที่ยังไม่เห็นโจทย์ด้วยซ้ำ

[nooonuii]

อ้าวเดาผิดนี่เอง มิน่าพิสูจน์ยังไงก็ไม่ออก

[warut]

เย็นนี้ประมาณทุ่มนึง ผมจะโพสต์ hint อันใหญ่สำหรับข้อนี้ให้ครับ คราวนี้รับรองมีคนทำได้แน่ๆ

ตอนนี้ขอบอกแต่เพียงว่า ข้อนี้ใช้แค่ elementary number theory จริงๆครับ พวก powerful theorems อย่างเรื่อง quadratic residues หรือแม้แต่ Fermat's Little Theorem นี่ไม่ต้องเอามาใช้เลย เพียงแต่มัน tricky หน่อย ถ้าไม่เห็น hint อาจคาดไม่ถึงว่าต้องไปทางนั้น

[warut]

Big hint: Show that $$ 2^r \, \| \, n+1 \quad \Rightarrow \quad 2^{2^r} + 1 \mid 2^{2^n-1} -2^n-1 $$ ใครไม่ทราบความหมายของสัญลักษณ์ $\|$ อ่านคำอธิบายของผมได้ในกระทู้นี้ครับ

[warut]

ผมคิดออกแล้วว่าจะ hint อะไรอีกดี hint นี้จะเป็นอันสุดท้ายของการแข่งขันนี้แล้วนะครับ จะไม่มีการ hint ใดๆเพิ่มอีก ไม่ว่าข้อนี้หรือข้อไหน ถ้าหลังจากให้เวลาพอสมควรแล้ว (ไม่น้อยกว่า 1 สัปดาห์แน่นอนครับ) ยังไม่มีใครตอบ ผมก็จะเฉลยล่ะนะ

ผมจะโพสต์ hint วันพรุ่งนี้ตอนประมาณทุ่มนึงนะครับ เดิมว่าจะใช้วิธีเพิ่มคะแนนให้กับข้อนี้ แต่คิดว่ามันคงจะไม่ช่วยอะไรได้มากนัก

แล้วพบกันใหม่วันพรุ่งนี้ครับ

[warut]

Last hint!

By repeated squaring, $$ a^{2^{\displaystyle{r}}} \equiv 1 \pmod m \quad \Rightarrow \quad a^{2^{\displaystyle{s}}} \equiv 1 \pmod m \quad \forall s \ge r $$

[warut]

เข้า winter break แล้ว ถ้าใครมีเวลาว่างก็ลองทำข้อนี้ดูหน่อยนะครับ ผมยังไม่อยากเฉลยข้อนี้เป็นของขวัญปีใหม่ง่ะ

[Necron]

จากโจทย์นะครับแยกเป็น2กรณีนะครับ
n=2a+1 nเป็นจำนวนคี่
ตามหลักของการพิสูจน์ให้แทน a=1ก่อน

2^22a+1-1-2^2a+1-1

แทนa=1

2^22(1)+1-1-2²⁽¹⁾⁺¹-1

=2⁷-2³-1
=119
119เป็นจำนวนเฉพาะ ประโยคนี้ไม่จริง

[nongtum]

ข้อความเดิมของคุณ Necron:
119เป็นจำนวนเฉพาะ ประโยคนี้ไม่จริง

$119=17\times7$

[warut]

ข้อความเดิมของคุณ warut:
จงพิสูจน์ว่า $$ 2^{2^n-1} -2^n-1 $$ เป็นจำนวนประกอบ สำหรับทุกจำนวนเต็ม $n>2$

ข้อความเดิมของคุณ warut:
Big hint: Show that $$ 2^r \, \| \, n+1 \quad \Rightarrow \quad 2^{2^r} + 1 \mid 2^{2^n-1} -2^n-1 $$ ใครไม่ทราบความหมายของสัญลักษณ์ $\|$ อ่านคำอธิบายของผมได้ในกระทู้นี้ครับ

ถึงเวลาเฉลยแล้วครับ

ให้จำนวนเต็ม $n\ge3$ และ $n+1=k\cdot2^r$, โดยที่ $k$ เป็นจำนวนคี่ และ $r\ge0$ เป็นจำนวนเต็ม

เนื่องจาก $$2^{2^r} \equiv -1 \pmod{2^{2^r} + 1} \quad (\star) $$ ดังนั้น โดยการยกกำลังสองซ้ำไปเรื่อยๆ เราจะพบว่า $$2^{2^t} \equiv 1 \pmod{2^{2^r} + 1}$$ สำหรับทุกจำนวนเต็ม $t>r$

นั่นแสดงว่า $$2^{2^n} \equiv 1 \pmod{2^{2^r} + 1}$$ เพราะเมื่อ $n\ge3$ แล้ว $n=k\cdot2^r-1>r$

จาก $(\star)$ เราจะได้ว่า $$2^{n+1}=2^{k\cdot2^r} \equiv (-1)^k \equiv -1\pmod{2^{2^r} + 1} $$ ดังนั้น $$ 2(2^{2^n-1} -2^n-1) = 2^{2^n}-2^{n+1}-2 \equiv 1-(-1)-2 \equiv 0 \pmod{2^{2^r} + 1} $$ แต่ $2^{2^r} + 1$ เป็นจำนวนคี่ แสดงว่า $2^{2^r} + 1 \mid 2^{2^n-1}-2^n-1$ และเนื่องจาก $2^{2^r} + 1 < 2^{2^n-1}-2^n-1$ เราจึงได้ว่า $2^{2^n-1}-2^n-1$ เป็นจำนวนประกอบเมื่อ $n$ เป็นจำนวนเต็มที่มากกว่า 2 ตามต้องการครับ

ไม่ยากใช่ไหมครับ แต่ถ้าใครทำไม่ได้ก็ไม่ต้องเสียใจนะครับ เพราะผมคิดว่า number theorists ส่วนใหญ่ก็ทำไม่ได้ (เห็นนิ่งเงียบ แต่ทีโจทย์เกี่ยวกับ elliptic curve ยากๆเห็นแย่งตอบกันใหญ่เลย แปลกดีครับ) ผมทำข้อนี้ได้ก็เพราะ big hint ซึ่ง Schoof (number theorist ชื่อดัง) เป็นคนให้ไว้ครับ

[nongtum]

Hint ที่ให้มาใหญ่จริงๆครับ ผมอ่านบรรทัดแรกอึ้งไปเลย ไม่นึกว่าไอเดียที่ตามมาจะง่ายขนาดนั้น แค่แสดงว่า $2^{2^r} + 1 \mid 2^{2^n} -1-(2^n+1)$ บวกสมบัติการหารลงตัวอีกนิดหน่อย คนที่คิดได้โดยไม่ใช้ hint คงจะทั้งเฉียบและอึดมากๆเลยล่ะครับ

แม้จะ็จบการแข่งแล้ว แต่หากคุณ warut มีโจทย์น่าสนใจแบบนี้อีกก็เอามาแบ่งกันทำบ้างนะครับ เชื่อว่าน่าจะเป็นประโยชน์ต่อหลายๆคนที่เข้ามาอ่าน

[warut]

ครับ ถ้าผมเจอโจทย์ที่น่าสนใจก็จะเอามาแปะให้ หวังว่าคงมีคนสนใจเอาไปคิดต่อ และตอบกลับกันมาบ้างเด้อ

[M@gpie]

ผมขอสารภาพครับว่า ผมไม่รู้เรื่องเลยแหะๆๆ ความรู้ทฤษฏีจำนวนน้อยนิดขอรับ เลยไม่รู้จะคิดยังไง ก็คิดจะศึกษานะครับ แต่เรื่องของเรื่องคือไม่ได้ใช้งานประจำ ทำให้ลืมครับ (ก็ต้องศึกษาของที่ใช้ประจำก่อนอิอิ )
แต่ผมเชื่อว่าถ้ามีคนอ่านแล้วมีความรู้ในด้านนั้นพอจะหาคำตอบ และความเห็นมาเสนอได้ รับรองไม่มีพลาดครับ พี่ warut