Number Theory Marathon

[nooonuii]

ข้อ $61$ $K_n$ ไม่จำเป็นต้องเป็นจำนวนเต็มใช่มั้ยครับ

ผมได้ $K_n=\dfrac{3y_n-x_n-2}{4}$

[owlpenguin]

ข้อ 59 ไม่ทราบว่า่แบบนี้ถูกไหมครับ

เนื่องจาก เมื่อ $n>1$ แล้ว $2\not |n!+1$
$\therefore ให้ n,k>1$

ถ้า $n!+1$ เป็นจำนวนเฉพาะ เราก็เลือก $((n!+1)-1)!+1=(n!)!+1$ ซึ่งจาก Wilson's Theorem จะได้ $(n!+1)|(n!)!+1$
$\therefore (n!+1,(n!)!+1)=n!+1>1$
แต่กรณีจะใช้ไม่ได้เมื่อ $n=2$

ถ้า $n!+1$ ไม่เป็นจำนวนเฉพาะ เราเลือกจำนวนเฉพาะ $p$ ที่ทำให้ $p|n!+1$ และ $p-1\not =n$
จาก Wilson's Theorem จะได้ $p|(p-1)!+1$
$\therefore (n!+1,(p-1)!+1)\geq p>1$
แต่กรณีนี้จะใช้ไม่ได้เมื่อ $n=4$

[warut_suk]

ข้อความเดิมเขียนโดยคุณ nooonuii

ข้อ $61$ $K_n$ ไม่จำเป็นต้องเป็นจำนวนเต็มใช่มั้ยครับ

ผมได้ $K_n=\dfrac{3y_n-x_n-2}{4}$

โทษทีครับ พิมพ์โจทย์ตกไป ต้องเป็นจำนวนเต็มบวกครับ (แก้ไขแล้ว)

ข้อความเดิมเขียนโดยคุณ owlpenguin

ถ้า $n!+1$ ไม่เป็นจำนวนเฉพาะ เราเลือกจำนวนเฉพาะ $p$ ที่ทำให้ $p|n!+1$ และ $p-1\not =n$

เลือกได้แน่หรือครับ

[warut]

ข้อความเดิมเขียนโดยคุณ warut_suk

59. จงแสดงว่ามีคู่ $(n,k)$ ของจำนวนเต็มบวกที่แตกต่างกัน เป็นอนันต์คู่ ซึ่งหรม.ของ $n!+1$ และ $k!+1$ มากกว่า $1$

แนวคิดข้อนี้ของผมคือ จาก Wilson's Theorem เรารู้ว่าจำนวนเฉพาะ $p$ หาร $(p-1)!+1$ ลงตัว ดังนั้นเราต้องการ $k\ne p-1$ ที่ $p\mid k!+1$ แต่หาแบบนี้ยาก ผมเลยคิดในมุมกลับแทน คือเลือกให้ $k=a$ แล้วเลือก $p$ เป็นตัวประกอบเฉพาะของ $a!+1$ โดยพยายามให้ $a\ne p-1$ ซึ่งทางหนึ่งก็คือ เลือก $a$ เป็นจำนวนคี่ที่มากกว่า $1$ ซึ่งจะทำให้มันมี parity ตรงข้ามกับ $p-1$

เมื่อเราได้คำตอบ $(p-1,a)$ มาอันนึงแล้ว เราสามารถสร้างคำตอบอันต่อไปได้โดยวิธีเดียวกัน แต่ที่สำคัญเราต้องแสดงว่า คำตอบใหม่นั้นไม่ซ้ำเดิม ซึ่งทางหนึ่งคือเลือก $k=p$ คำตอบใหม่ก็จะเป็น $(q-1,p)$ เมื่อ $q$ คือตัวประกอบเฉพาะของ $p!+1$ ซึ่งคำตอบใหม่นี้ไม่มีทางซ้ำเดิม เพราะ $p>a$ และ $q>p$ ครับ

ข้อความเดิมเขียนโดยคุณ warut_suk

60. จงแสดงว่ามีคู่ $(n,k)$ ของจำนวนเต็มบวกที่แตกต่างกัน เป็นอนันต์คู่ ซึ่งหรม.ของ $n!-1$ และ $k!-1$ มากกว่า $1$

ให้ $n=1$ และ $k>2$ เราจะได้ $\gcd(n!-1,k!-1)=k!-1>1$ ครับ

[warut_suk]

ข้อความเดิมเขียนโดยคุณ warut

แนวคิดข้อนี้ของผมคือ จาก Wilson's Theorem เรารู้ว่าจำนวนเฉพาะ $p$ หาร $(p-1)!+1$ ลงตัว ดังนั้นเราต้องการ $k\ne p-1$ ที่ $p\mid k!+1$ แต่หาแบบนี้ยาก ผมเลยคิดในมุมกลับแทน คือเลือกให้ $k=a$ แล้วเลือก $p$ เป็นตัวประกอบเฉพาะของ $a!+1$ โดยพยายามให้ $a\ne p-1$ ซึ่งทางหนึ่งก็คือ เลือก $a$ เป็นจำนวนคี่ที่มากกว่า $1$ ซึ่งจะทำให้มันมี parity ตรงข้ามกับ $p-1$

เมื่อเราได้คำตอบ $(p-1,a)$ มาอันนึงแล้ว เราสามารถสร้างคำตอบอันต่อไปได้โดยวิธีเดียวกัน แต่ที่สำคัญเราต้องแสดงว่า คำตอบใหม่นั้นไม่ซ้ำเดิม ซึ่งทางหนึ่งคือเลือก $k=p$ คำตอบใหม่ก็จะเป็น $(q-1,p)$ เมื่อ $q$ คือตัวประกอบเฉพาะของ $p!+1$ ซึ่งคำตอบใหม่นี้ไม่มีทางซ้ำเดิม เพราะ $p>a$ และ $q>p$ ครับ

ทำได้ดีมากๆเลยครับ แนวคิดดีมาก และยังรอบคอบด้วย (ซึ่งหลายๆคนอาจจะไม่)

ส่วนข้อ 60 ขอคำตอบที่ $n,k$ ไม่เป็น 1 ละกันนะครับ

เพิ่มโจทย์สักหน่อย

62. สำหรับจำนวนเต็มบวก $n$ แต่ละตัว จงหาหรม.ของ $n!+1$ และ $(n+1)!$

63. ให้ $p$ เป็นจำนวนเฉพาะ และ $a,n$ เป็นจำนวนเต็มบวก โดยที่ $2^p+3^p=a^n$ จงหาค่า $n$ ที่เป็นไปได้ทั้งหมด

64. ให้ $a$ เป็นจำนวนเต็ม และ $x,y$ เป็นจำนวนเต็มบวก นิยาม $z_a(x,y)=\frac{x^2+y^2+a}{xy}$

(a) จงแสดงว่ามี $a$ เป็นอนันต์ตัว ซึ่ง $z_a(x,y)$ เป็นจำนวนเต็ม สำหรับ $(x,y)$ เป็นอนันต์คู่

(b) จงหา $a$ ทั้งหมด ซึ่งเซต $E(a)$ ของค่า $z_a(x,y)$ ทั้งหมดที่เกิดขึ้น เป็นเซตจำกัด

[warut]

ข้อความเดิมเขียนโดยคุณ warut_suk

ส่วนข้อ 60 ขอคำตอบที่ $n,k$ ไม่เป็น 1 ละกันนะครับ

น่าจะใช้ความจริงที่ว่า $(p-2)!\equiv1\pmod p$ เมื่อ $p$ เป็นจำนวนเฉพาะ ร่วมกับเทคนิคแบบที่ผมทำในข้อ 59. จัดการได้ครับ

[owlpenguin]

ข้อความเดิมเขียนโดยคุณ warut_suk

...เลือกได้แน่หรือครับ

ต้องขอโทษด้วยครับ พอดีตอนนั้นสะเพร่าไป... ขอแก้ตัวละกันนะครับ
62. แบ่ง $n+1$ เป็น 2 กรณีดังนี้
i)$n+1$ ไม่เป็นจำนวนเฉพาะ
1)$n+1=4$ จะได้ $(n!+1,(n+1)!)=1$
2)$n+1>4$ ซึ่งจะได้ $(n+1)|n!$ และจาก $k|n!$ ทุก $k=1,2,...,n$, $\therefore (n!+1,k)=1$ ทุก $k=1,2,...,n+1$
$\therefore (n!+1,(n+1)!)=(n!+1,(1)(2)...(n+1))=1$
ii)$n+1$ เป็นจำนวนเฉพาะ
จาก $k|n!$ ทุก $k=1,2,...,n$ $\therefore (n!+1,k)=1$ ทุก $k=1,2,...,n$
และจาก Wilson's Theorem, ได้ว่า $(n+1)|n!+1$
$\therefore (n!+1,(n+1)!)=(n!+1,n+1)$ ($\because (n!+1,k)=1$ ทุก $k=1,2,...,n$)
$=n+1$ ($\because (n!+1,n+1)=n+1$)

ดังนั้นสรุปได้ว่า
$(n!+1,(n+1)!)=\cases{1 & , n+1 ไม่เป็นจำนวนเฉพาะ \cr n+1 & , n+1 เป็นจำนวนเฉพาะ}$

[warut_suk]

แนวคิดเยี่ยมทั้งสองข้อเลยครับ

[warut]

ข้อความเดิมเขียนโดยคุณ warut_suk

61. พิจารณาลำดับที่นิยามโดย $x_{n+1}=2x_n+3y_n, y_{n+1}=x_n+2y_n$ โดยที่ $x_1=2,y_1=1$ จงแสดงว่าสำหรับทุก $n\geq 1$ มีจำนวนเต็มบวก $K_n$ ซึ่ง $x_{2n+1}=2(K_n^2+(K_n+1)^2)$

โจทย์ข้อนี้ดีอย่าง คือสามารถใช้กำลังเข้าหักหาญเอาคำตอบได้ ไม่เหมือนกับข้อ 59-60 แต่โจทย์ที่ brute force ได้ก็มีข้อเสียคือ เรามักไม่สนใจว่าจะทำได้หรือไม่ แต่ไปสนใจว่าจะหาวิธีทำสวยๆได้ยังไง Carl Pomerance (number theorist ที่มีชื่อเสียงมากที่สุดคนนึงในยุคปัจจุบัน) เคยเขียนเล่าให้ฟังว่า เขาเคยได้รับโจทย์ในการแข่งขันข้อนึง เป็นโจทย์ให้แยกตัวประกอบจำนวนเต็ม ซึ่งถ้าใช้ trial division ธรรมดาก็คงทำได้แล้วล่ะ แต่ในเมื่อโจทย์ออกมาในลักษณะอย่างนี้ เขาคิดว่ามันต้องมีวิธีฉลาดๆในการทำแน่ จึงเสียเวลามองหาวิธีอยู่นาน จนกระทั่งเวลาใกล้หมด ก็ยังทำไม่ได้ เลยตัดสินใจกลับมาใช้ trial division แต่ก็สายเกินไปแล้ว...

สำหรับวิธีใช้กำลังที่ผมว่านั้น คือทำตรงๆดังนี้ครับ

จากที่โจทย์ให้ เราจะได้ว่า $$x_{n+2} = 2x_{n+1} +3y_{n+1} = 2x_{n+1} +3(x_n+2y_n) = 2x_{n+1} +3x_n +6y_n$$ เมื่อรวมกับ $x_{n+1}=2x_n+3y_n$ เราจึงได้ว่า $$x_{n+2} = 4x_{n+1} -x_n$$ โดยที่ $x_1=2$ และ $x_2=7$

แก้ difference equation อันนี้ เราได้ $$x_n= \frac12 (a^n + a^{-n}) $$ เมื่อ $a=2+\sqrt3$

จาก $$x_{2n+1}= 2(K_n^2+(K_n+1)^2) = (2K_n+1)^2+1$$ และ $$x_{2n+1}-1 = \frac12 (a^{2n+1} + a^{-(2n+1)} - 2) = \frac12 (a^{n+1/2} - a^{-(n+1/2)} )^2$$ ดังนั้น $$K_n= \frac{(1+\sqrt3)}{4} a^n + \frac{(1-\sqrt3)}{4} a^{-n} -\frac12 $$ เพราะ $\sqrt a= \dfrac{1+\sqrt3}{\sqrt2} $

คำนวณย้อนกลับหา linear recurrence relation เราจะพบว่า $$K_{n+2} =4K_{n+1} -K_n +1$$ โดยที่ $K_0=0$ และ $K_1=2$

โดย induction เรารู้ว่า $K_{n+1}>K_n$ ดังนั้น $\{K_n\}_{n\ge1}$ จึงเป็นลำดับของจำนวนเต็มบวก ตามที่โจทย์ต้องการครับ

สำหรับวิธีทำเจ๋งๆของข้อนี้ หรือวิธีทำของข้อที่เหลือ (ข้อ 64. ดูท่าทางน่าสนใจมาก) คงต้องปล่อยให้เป็นหน้าที่ของคนอื่นๆแล้วล่ะครับ

[owlpenguin]

63.
พิจารณา $2^x,3^x\pmod{25}$
$\bmatrix{x\equiv & 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\pmod{25} \\ 2^x\equiv & 1&2&4&8&16&7&14&3&6&12&24&23&21&17&9&18&11&22&19&13\pmod{25}\\ 3^x\equiv & 1&3&9&2&6&18&4&12&11&8&24&22&16&23&19&7&21&13&14&17\pmod{25}\\ \therefore 2^x+3^x\equiv & 2&5&13&10&22&0&18&15&17&20&23&20&12&15&3&0&7&10&8&5\pmod{25}}$
ดังนั้นถ้า $n>1$ แล้ว $x\equiv 5,15\pmod{20}\rightarrow x\equiv 5\pmod{10}$ ซึ่งจำนวนเฉพาะทั้งหมดที่ลงท้ายด้วย $5$ มี $5$ เพียงตัวเดียวเท่านั้น และจาก $2^5+3^5=275=5^2\times 11$

$\therefore n=1$ เท่านั้น

[nooonuii]

ข้อความเดิมเขียนโดยคุณ warut

โจทย์ข้อนี้ดีอย่าง คือสามารถใช้กำลังเข้าหักหาญเอาคำตอบได้ ไม่เหมือนกับข้อ 59-60 แต่โจทย์ที่ brute force ได้ก็มีข้อเสียคือ เรามักไม่สนใจว่าจะทำได้หรือไม่ แต่ไปสนใจว่าจะหาวิธีทำสวยๆได้ยังไง Carl Pomerance (number theorist ที่มีชื่อเสียงมากที่สุดคนนึงในยุคปัจจุบัน) เคยเขียนเล่าให้ฟังว่า เขาเคยได้รับโจทย์ในการแข่งขันข้อนึง เป็นโจทย์ให้แยกตัวประกอบจำนวนเต็ม ซึ่งถ้าใช้ trial division ธรรมดาก็คงทำได้แล้วล่ะ แต่ในเมื่อโจทย์ออกมาในลักษณะอย่างนี้ เขาคิดว่ามันต้องมีวิธีฉลาดๆในการทำแน่ จึงเสียเวลามองหาวิธีอยู่นาน จนกระทั่งเวลาใกล้หมด ก็ยังทำไม่ได้ เลยตัดสินใจกลับมาใช้ trial division แต่ก็สายเกินไปแล้ว...

สำหรับวิธีใช้กำลังที่ผมว่านั้น คือทำตรงๆดังนี้ครับ

จากที่โจทย์ให้ เราจะได้ว่า $$x_{n+2} = 2x_{n+1} +3y_{n+1} = 2x_{n+1} +3(x_n+2y_n) = 2x_{n+1} +3x_n +6y_n$$ เมื่อรวมกับ $x_{n+1}=2x_n+3y_n$ เราจึงได้ว่า $$x_{n+2} = 4x_{n+1} -x_n$$ โดยที่ $x_1=2$ และ $x_2=7$

แก้ difference equation อันนี้ เราได้ $$x_n= \frac12 (a^n + a^{-n}) $$ เมื่อ $a=2+\sqrt3$

จาก $$x_{2n+1}= 2(K_n^2+(K_n+1)^2) = (2K_n+1)^2+1$$ และ $$x_{2n+1}-1 = \frac12 (a^{2n+1} + a^{-(2n+1)} - 2) = \frac12 (a^{n+1/2} - a^{-(n+1/2)} )^2$$ ดังนั้น $$K_n= \frac{(1+\sqrt3)}{4} a^n + \frac{(1-\sqrt3)}{4} a^{-n} -\frac12 $$ เพราะ $\sqrt a= \dfrac{1+\sqrt3}{\sqrt2} $

คำนวณย้อนกลับหา linear recurrence relation เราจะพบว่า $$K_{n+2} =4K_{n+1} -K_n +1$$ โดยที่ $K_0=0$ และ $K_1=2$

โดย induction เรารู้ว่า $K_{n+1}>K_n$ ดังนั้น $\{K_n\}_{n\ge1}$ จึงเป็นลำดับของจำนวนเต็มบวก ตามที่โจทย์ต้องการครับ

สำหรับวิธีทำเจ๋งๆของข้อนี้ หรือวิธีทำของข้อที่เหลือ (ข้อ 64. ดูท่าทางน่าสนใจมาก) คงต้องปล่อยให้เป็นหน้าที่ของคนอื่นๆแล้วล่ะครับ

คุณ warut ใช้วิธีเดียวกับผมเลยครับ

แต่ผมคำนวณผิดที่ไหนซักแห่งก็เลยเลิกคิดไปแล้ว

ผมหา $x_n,y_n$ โดยตั้งสมการแบบนี้ครับ

$\pmatrix{x_{n+1}\\ y_{n+1}} = \pmatrix{2 & 3 \\ 1 & 2}\pmatrix{x_n \\ y_n}$

$~~~~~~~~~~~=\pmatrix{2 & 3 \\ 1 & 2}^n\pmatrix{x_1 \\ y_1}$

จากนั้นก็ใช้ linear algebra ล้วนๆ

ป.ล. คุณ warut หายยุ่งแล้วใช่มั้ยครับ

เห็นโจทย์ทฤษฎีจำนวนยากๆทีไรคิดถึงคุณ warut ทุกทีเลย

[square1zoa]

ข้อ 62 ใช้Euclidean algorithm ไม่ได้เหรอครับ เพราะตอนหาได้เศษเป็น $n+1$

[warut]

ข้อความเดิมเขียนโดยคุณ nooonuii

ป.ล. คุณ warut หายยุ่งแล้วใช่มั้ยครับ

เห็นโจทย์ทฤษฎีจำนวนยากๆทีไรคิดถึงคุณ warut ทุกทีเลย

ยังยุ่งฮะ แต่เป็นเรื่องไม่เป็นเรื่องทั้งน้าน

เดี๋ยวนี้โจทย์ที่นี่ยากจริงๆครับ เห็นแล้วท้อ (คงความรู้สึกเดียวกับที่น้องๆเห็นโจทย์ Warm Up ของคุณ passer-by ซึ่งผมก็ทำไม่ค่อยได้เหมือนกัน ) อย่างข้อ 64b ข้างบนนั่นผมดูแล้วยังไม่เห็นจะมีทางทำยังไงได้เลย

[Platootod]

ข้อความเดิมเขียนโดยคุณ dektep

55. $2551^{2008}+2008^{2551} \equiv 2 (mod 3)$ จึงไม่เป็นกำลังสองสมบูรณ์

ทำไม$\equiv 2 (mod 3)$จึงไม่เป็นกำลังสองสมบูรณ์
ผมไม่เข้าใจครับ(ผมความรู้ไม่ถึงครับแต่จะเป็นประโยชน์มากครับถ้านำแนวคิดข้อนี้ไปพิสูจน์ข้ออื่นๆครับ)

[nooonuii]

ข้อความเดิมเขียนโดยคุณ Platootod

ทำไม$\equiv 2 (mod 3)$จึงไม่เป็นกำลังสองสมบูรณ์
ผมไม่เข้าใจครับ(ผมความรู้ไม่ถึงครับแต่จะเป็นประโยชน์มากครับถ้านำแนวคิดข้อนี้ไปพิสูจน์ข้ออื่นๆครับ)

$a^2 \equiv 0,1\pmod{3}$ เท่านั้นครับ