Mathlink Contest ครั้งที่ 5 รอบที่ 1 ข้อ 2

[gools]

หาจำนวนเต็มบวก \(n\ge5\) ทั้งหมดที่มีคุณสมบัติดังนี้ เศษของ \(n\) เมื่อหารด้วยจำนวนเฉพาะทุกตัวที่น้อยกว่า \(\frac{n}{2}\) จะมีค่าเป็นจำนวนคี่เสมอ

Edit: แก้ไขโจทย์เล็กน้อยครับ

[warut]

เมื่อ $n\le31$ เราจะพบว่ามี $n=5,7,13,31$ เป็นคำตอบ

ต่อไปเป็นการพิสูจน์ (โดยใช้ contradiction) ว่าเมื่อ $n>31$ แล้วจะไม่มี $n$ ที่มีสมบัติตามที่ต้องการ

สมมติว่ามี $n$ อย่างว่า

เราจะได้ว่า

$n\equiv1\pmod2$
$n\equiv1\pmod3$
$n\equiv1,3\pmod5$

นั่นคือ $n\equiv1,13\pmod{30}$

จะเห็นว่า $3\mid n-4$

ถ้า $n-4$ มีตัวประกอบเฉพาะอื่นนอกจาก 3 สมมติว่าคือ $p$ เราจะได้ว่า $5\le p\le(n-4)/3<n/2$ และ $n$ หารด้วย $p$ เหลือเศษ 4 ทำให้ขัดแย้งกับสมบัติของ $n$ ที่เรากำหนดไว้ เราจึงสรุปได้ว่า $n-4$ จะต้องอยู่ในรูป $3^r,\,r>3$

กรณีที่ 1: $n\equiv1\pmod{30}$

จะเห็นว่า $5\mid n-6$ แต่ $3\!\not|\,n-6$ เพราะ $3\mid n-4=(n-6)+2$

ดังนั้นถ้า $n-6$ มีตัวประกอบเฉพาะอื่นนอกจาก 5 สมมติว่าคือ $p$ เราจะได้ว่า $7\le p\le(n-6)/5<n/2$ และ $n$ หารด้วย $p$ เหลือเศษ 6 ทำให้ขัดแย้งกับสมบัติของ $n$ ที่เรากำหนดไว้ เราจึงสรุปได้ว่า $n-6$ จะต้องอยู่ในรูป $5^s,\,s>2$

จากที่ $n\equiv1\pmod3$ และ $n-6=5^s$ เราจึงได้ว่า $s=2b,\, b\in\mathbb N$

จะเห็นว่า $3\mid n-10$ แต่ $3^2\!\not|\,n-10$ เพราะ $3^2\mid n-4=(n-10)+6$

$5\!\not|\,n-10$ เพราะ $5\mid n-6=(n-10)+4$

ถ้า $n-10$ มีตัวประกอบเฉพาะ $p$ โดยที่ $11\le p\le(n-10)/3<n/2$ เราจะได้ว่า $n$ หารด้วย $p$ แล้วเหลือเศษ 10 ทำให้ขัดแย้งกับสมบัติของ $n$ ที่เรากำหนดไว้ ดังนั้น $n-10$ จะต้องอยู่ในรูป $3\cdot7^t,\, t>1$

ดังนั้น $4= (n-6)-(n-10)= 5^{2b}-3\cdot7^t$

นั่นคือ $3\cdot7^t=(5^b-2)(5^b+2)$

จะเห็นว่า 7 หารทั้ง $5^b-2$ และ $5^b+2$ ลงตัวพร้อมกันไม่ได้ เพราะ $7\!\not|\,4=(5^b+2)-(5^b-2)$

ถ้า $5^b-2=1$ และ $5^b+2=3\cdot7^t$ จะได้ $3\cdot7^t=5$ จึงเป็นไปไม่ได้

ถ้า $5^b-2=3$ และ $5^b+2=7^t$ จะได้ $7^t=7$ แต่ $t>1$ จึงเป็นไปไม่ได้เช่นกัน

ดังนั้นในกรณีที่ 1 นี้จึงไม่มี $n>31$ ที่มีสมบัติตามต้องการอยู่

กรณีที่ 2: $n\equiv13\pmod{30}$

จะเห็นว่า $5\mid n-8$ แต่ $3\!\not|\,n-8$ เพราะ $3\mid n-4=(n-8)+4$

และจะเห็นว่า $3\mid n-10$ แต่ $3^2\!\not|\,n-10$ เพราะ $3^2\mid n-4=(n-10)+6$

$5\!\not|\,n-10$ เพราะ $5\mid n-8=(n-10)+2$

ถ้า $n-10$ มีตัวประกอบเฉพาะ $p$ โดยที่ $11\le p\le(n-10)/3<n/2$ เราจะได้ว่า $n$ หารด้วย $p$ แล้วเหลือเศษ 10 ทำให้ขัดแย้งกับสมบัติของ $n$ ที่เรากำหนดไว้ ดังนั้น $n-10$ จะต้องอยู่ในรูป $3\cdot7^t,\, t>1$

แสดงว่า $7\!\not|\,n-8$ เพราะ $7\mid n-10=(n-8)-2$

ดังนั้นถ้า $n-8$ มีตัวประกอบเฉพาะอื่นนอกจาก 5 สมมติว่าคือ $p$ เราจะได้ว่า $11\le p\le(n-8)/5<n/2$ และ $n$ หารด้วย $p$ เหลือเศษ 8 ทำให้ขัดแย้งกับสมบัติของ $n$ ที่เรากำหนดไว้ เราจึงสรุปได้ว่า $n-8$ จะต้องอยู่ในรูป $5^s,\, s>2$

จากที่ $n\equiv3\pmod5$ และ $n-4=3^r$ เราจึงได้ว่า $r=4a+2,\, a\in\mathbb N$

ดังนั้น $4= (n-4)-(n-8)= 3^{4a+2}-5^s$

นั่นคือ $5^s= (3^{2a+1}-2) (3^{2a+1}+2)$

จะเห็นว่า 5 หารทั้ง $3^{2a+1}-2$ และ $3^{2a+1}+2$ ลงตัวพร้อมกันไม่ได้ เพราะ $5\!\not|\,4=(3^{2a+1}+2)-(3^{2a+1}-2)$

ถ้า $3^{2a+1}-2=1$ และ $3^{2a+1}+2=5^s$ จะได้ $5^s=5$ แต่ $s>2$ จึงเป็นไปไม่ได้

ดังนั้นในกรณีที่ 2 นี้จึงไม่มี $n>31$ ที่มีสมบัติตามต้องการอยู่เช่นกัน

ป.ล. ในบรรดาโจทย์ elementary number theory (ที่พอจะเชื่อถือได้) ที่เอามาแปะที่นี่ ผมว่าข้อนี้ยากสุดแล้วล่ะ ถ้าคุณ gools มีเฉลยช่วยกรุณาแสดงให้ดูหรือ link ให้ด้วยนะครับ

ป.ล.2 เจอแล้วว่าโจทย์ต้นฉบับอยู่ที่นี่ แต่ยังหาเฉลยไม่เจอครับ

[warut]

ผมขอแปะ ตารางสรุปรูปแบบ/สมบัติของ $n,n-2,\dots,n-10$ ทั้งหมดที่ผมคิดได้ (บางอันอาจไม่ได้ใช้ในการพิสูจน์) ที่นำทางผมไปสู่การพิสูจน์ข้างบนนะครับ เพราะเกรงว่าต่อไปผมเองก็อาจจะลืมไปเหมือนกัน ว่าทำไมผมถึงคิดว่าควรพิสูจน์แบบนั้น และอาจช่วยให้คนที่สนใจการพิสูจน์ของผม (จะมีมั้ยน้า ) เข้าใจแนวคิดได้ดีขึ้นด้วยครับ $$ \begin{array}{lcc} & n\equiv1\pmod{30} & n\equiv13\pmod{30} \\ n\quad & \text{prime} & \text{prime} \\ n-2\quad & \text{prime} & \text{prime} \\ n-4\quad & 3^{4a+3} & 3^{4a+2} \\ n-6\quad & 5^{2b} & \text{prime} \\ n-8\quad & \text{prime} & 5^{2b+1} \\ n-10\quad & 3\cdot7^{4c+1} & 3\cdot7^{4c} \end{array} $$

[warut]

เมื่อวานผมได้คำตอบของโจทย์ข้อนี้มา 2 อันจากที่นี่

อันของ Daniel Gutekunst คิดว่าผิด เพราะอ้างว่า "For $n\ge34$ there is always a prime number with $\frac14 n <p< \frac13 n$." โดยไม่พิสูจน์หรือบอกแหล่งอ้างอิง

แต่บทพิสูจน์ของ pengshi ทำให้ผมต้องลงเสียเวลาลง MiKTeX เพราะเขาใช้ไฟล์ .dvi แต่ก็คุ้มครับ การพิสูจน์ของเขาไม่มีที่ผิด และคล้ายกับของผมมาก ที่ต่างกันอย่างนึงคือ เขาใช้เวลาคิดแป๊ปเดียว แต่ผมใช้เวลาเป็นปี

เฉลยของ pengshi มี 3 ส่วน เพื่อความสะดวก ผมจะเอาแต่ละส่วนมาแปะให้ดูกัน

ช่วงแรก การพิสูจน์ของเขาจะเหมือนกับของผมครับ
.

[warut]

ในช่วงกลางของการพิสูจน์ของ pengshi ก็คือกรณีที่ 1 ของผม แต่ว่าเขาจะเข้าชนตรงๆเลย โดยการแก้สมการ diophantine: $3^a-2=5^b$ ผมก็คิดจะทำอย่างนี้อยู่เหมือนกัน โดยพยายามค้นหาคำตอบของสมการนี้ในหนังสือเท่าที่ผมมีอยู่ แต่หาไม่เจอ เลยต้องหลบ เพราะคาดว่ามันต้องยากมากๆ และผมคงทำไม่ได้แน่ๆ นั่นคือสาเหตุที่ผมต้องพิจารณาลงไปจนถึง $n-10$ ซึ่งก็ช่วยให้ง่ายขึ้นเยอะ ถ้าใครได้อ่านการพิสูจน์ของ pengshi อย่างละเอียด จะต้องทึ่งมากๆ สังเกตจากการเลือกใช้ moduli ต่างๆ โดยเฉพาะอันที่ใช้ modulo 271 นี่ ทำให้ผมเชื่อว่า ถ้าเขาคิดเอง ไม่ได้นำเอาการพิสูจน์อันนี้มาจากหนังสือ คงต้องใช้ computer search เพื่อหา modulus ที่เหมาะสมแน่ๆเลยครับ
.

[warut]

ในช่วงท้าย (ซึ่งก็คือกรณีที่ 2 ของผม) pengshi จะใช้ผลจากการแก้สมการ diophantine: $3^a-2=5^b$ ในช่วงกลางมาช่วยอีก ทำให้เขาไม่ต้องพิจารณาลงไปลึกถึง $n-10$ อย่างผม แต่นั่นทำให้เขาไม่มีโอกาสได้รู้ว่า จริงๆแล้ว $n-8$ ไม่มี 7 เป็นตัวประกอบอยู่ ซึ่งนั่นจะทำให้ทุกอย่างง่ายขึ้นมากครับ
.