ปัญหาชิงรางวัลข้อที่ 23: Number Theory once more
จงพิสูจน์ว่า $$ 2^{2^n-1} -2^n-1 $$ เป็นจำนวนประกอบ สำหรับทุกจำนวนเต็ม $n>2$
|
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. |
ข้อคาดเดาของคุณ nooonuii ไม่เป็นจริงครับ เช่น ในกรณีที่ $n=35$ เรามี $31$ เป็นตัวประกอบเฉพาะที่เล็กที่สุดของ $2^n-1$ แต่ $31$ หาร $ 2^{2^n-1} -2^n-1 $ เหลือเศษ $2$ ครับ
ผมยังไม่อยาก comment อะไรมากครับ เพราะเพิ่งจะโพสต์โจทย์ไป อาจจะมีบางคนที่ยังไม่เห็นโจทย์ด้วยซ้ำ |
อ้าวเดาผิดนี่เอง :laugh: มิน่าพิสูจน์ยังไงก็ไม่ออก :cry:
|
เย็นนี้ประมาณทุ่มนึง ผมจะโพสต์ hint อันใหญ่สำหรับข้อนี้ให้ครับ คราวนี้รับรองมีคนทำได้แน่ๆ
ตอนนี้ขอบอกแต่เพียงว่า ข้อนี้ใช้แค่ elementary number theory จริงๆครับ พวก powerful theorems อย่างเรื่อง quadratic residues หรือแม้แต่ Fermat's Little Theorem นี่ไม่ต้องเอามาใช้เลย เพียงแต่มัน tricky หน่อย ถ้าไม่เห็น hint อาจคาดไม่ถึงว่าต้องไปทางนั้น |
Big hint: Show that $$ 2^r \, \| \, n+1 \quad \Rightarrow \quad 2^{2^r} + 1 \mid 2^{2^n-1} -2^n-1 $$ ใครไม่ทราบความหมายของสัญลักษณ์ $\|$ อ่านคำอธิบายของผมได้ในกระทู้นี้ครับ
|
ผมคิดออกแล้วว่าจะ hint อะไรอีกดี hint นี้จะเป็นอันสุดท้ายของการแข่งขันนี้แล้วนะครับ จะไม่มีการ hint ใดๆเพิ่มอีก ไม่ว่าข้อนี้หรือข้อไหน ถ้าหลังจากให้เวลาพอสมควรแล้ว (ไม่น้อยกว่า 1 สัปดาห์แน่นอนครับ) ยังไม่มีใครตอบ ผมก็จะเฉลยล่ะนะ
ผมจะโพสต์ hint วันพรุ่งนี้ตอนประมาณทุ่มนึงนะครับ เดิมว่าจะใช้วิธีเพิ่มคะแนนให้กับข้อนี้ แต่คิดว่ามันคงจะไม่ช่วยอะไรได้มากนัก แล้วพบกันใหม่วันพรุ่งนี้ครับ :) |
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 $$ |
เข้า winter break แล้ว ถ้าใครมีเวลาว่างก็ลองทำข้อนี้ดูหน่อยนะครับ ผมยังไม่อยากเฉลยข้อนี้เป็นของขวัญปีใหม่ง่ะ :p
|
จากโจทย์นะครับแยกเป็น2กรณีนะครับ
n=2a+1 nเป็นจำนวนคี่ ตามหลักของการพิสูจน์ให้แทน a=1ก่อน 222a+1-1-22a+1-1 แทนa=1 222(1)+1-1-22(1)+1-1 =27-23-1 =119 119เป็นจำนวนเฉพาะ ประโยคนี้ไม่จริง |
อ้างอิง:
|
อ้างอิง:
อ้างอิง:
ให้จำนวนเต็ม $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 ชื่อดัง) เป็นคนให้ไว้ครับ |
Hint ที่ให้มาใหญ่จริงๆครับ ผมอ่านบรรทัดแรกอึ้งไปเลย ไม่นึกว่าไอเดียที่ตามมาจะง่ายขนาดนั้น แค่แสดงว่า $2^{2^r} + 1 \mid 2^{2^n} -1-(2^n+1)$ บวกสมบัติการหารลงตัวอีกนิดหน่อย คนที่คิดได้โดยไม่ใช้ hint คงจะทั้งเฉียบและอึดมากๆเลยล่ะครับ
แม้จะ็จบการแข่งแล้ว แต่หากคุณ warut มีโจทย์น่าสนใจแบบนี้อีกก็เอามาแบ่งกันทำบ้างนะครับ เชื่อว่าน่าจะเป็นประโยชน์ต่อหลายๆคนที่เข้ามาอ่าน |
ครับ ถ้าผมเจอโจทย์ที่น่าสนใจก็จะเอามาแปะให้ หวังว่าคงมีคนสนใจเอาไปคิดต่อ และตอบกลับกันมาบ้างเด้อ
|
ผมขอสารภาพครับว่า ผมไม่รู้เรื่องเลยแหะๆๆ ความรู้ทฤษฏีจำนวนน้อยนิดขอรับ เลยไม่รู้จะคิดยังไง ก็คิดจะศึกษานะครับ แต่เรื่องของเรื่องคือไม่ได้ใช้งานประจำ ทำให้ลืมครับ (ก็ต้องศึกษาของที่ใช้ประจำก่อนอิอิ :rolleyes: )
แต่ผมเชื่อว่าถ้ามีคนอ่านแล้วมีความรู้ในด้านนั้นพอจะหาคำตอบ และความเห็นมาเสนอได้ รับรองไม่มีพลาดครับ พี่ warut |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 17:55 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha