Number Theory Marathon

[Mastermander]

กระทู้ตื่นครับ

.

วันนี้เงียบจัง

[nongtum]

ไหนๆกระทู้ก็ถูกขุดมาแล้ว ใครคิดข้อของคุณ pheeradej (นับเป็นข้อ 34) ออกช่วยมาแสดงวิธีทำหน่อยครับ ผมยังคิดไม่ออกครับ...

แถมโจทย์ ไม่รู้เคยถามไปหรือยัง:

35. จงแสดงว่าส่วนที่เป็นจำนวนเต็มของ $(5+\sqrt{21})^n+1$ หารด้วย $2^n$ ลงตัว

ปล. ผมว่าข้อนี้มันแปลกๆนะ เพราะผมลองทดแล้วมันไม่จริงเมื่อ $n=2$ แต่เฉลยมันกลับเป็นคนละเรื่อง เลยอยากให้ช่วยดูกันหน่อย

[warut]

โจทย์แนวข้อ 35. ถ้าจำไม่ผิดเล่นกันไปหลายครั้งแล้วนะครับ วิธีทำก็ใช้วิธีมาตรฐานคือ linear recurrence relation ครับ

กรณีที่ $n=2$ ก็เป็นจริงครับ $$ \lfloor (5 + \sqrt{21} )^2 +1 \rfloor = 92 = 2^2 \cdot 23 $$

ให้ $ a_1 = 10, a_2 = 92 $ และสำหรับ $ n \ge 3 $ ให้ $$ a_n = 10a_{n-1} - 4a_{n-2} $$ แก้ difference equation แล้วจะพบว่า สำหรับทุก $ n \in \mathbb N , $ $$ a_n = (5 + \sqrt{21} )^n + (5 - \sqrt{21} )^n $$ เนื่องจาก $ 0 < (5 - \sqrt{21} )^n < 1 $ และ $ a_n $ เป็นจำนวนเต็มบวกเสมอ ดังนั้น $$ a_n = \lfloor (5 + \sqrt{21} )^n +1 \rfloor $$ และจากที่ $ a_n = 2 (5a_{n-1} - 2a_{n-2}) $ เราจึงสามารถพิสูจน์ได้ว่า $ 2^n \mid a_n $ โดยใช้ induction ครับ

[warut]

ข้อความเดิมของคุณ Pheeradej:
34. จงหาคู่อันดับ (m,n) เป็นจำนวนเต็มบวกทั้งหมด ที่ทำให้ (n³+1)/(mn-1) เป็นจำนวนเต็มบวก

โจทย์ข้อนี้ดูเหมือนพวกโจทย์โอลิมปิกเลย ถ้าทราบที่มาของโจทย์อาจจะช่วยให้ง่ายขึ้นก็เป็นได้นะครับ โจทย์ของน้อง Pheeradej แต่ละข้อนี่โหดๆทั้งนั้น ครั้งก่อนก็ทำผมเดี้ยงไปทีนึงแล้วเหมือนกัน

[warut]

วิธีทำข้อ 34. ของผมครับ

เนื่องจาก $$ 1 \equiv mn \equiv m^3n^3 \pmod{mn-1} $$ ดังนั้น $$ m^3+1 \equiv m^3+m^3n^3 \equiv m^3(n^3+1) \pmod{mn-1} $$ นั่นแสดงว่า $$ mn-1 \mid n^3+1 \quad \Rightarrow \quad mn-1 \mid m^3+1 $$ แปลว่า ถ้า $ (m,n) = (a,b) $ เป็นคำตอบของโจทย์แล้ว $ (m,n) = (b,a) $ ก็จะเป็นคำตอบด้วย

ถ้า $n=1$ เราได้ $m=2,3$ เป็นคำตอบ
ถ้า $n=2$ เราได้ $m=1,2,5$ เป็นคำตอบ
ถ้า $n=3$ เราได้ $m=1,5$ เป็นคำตอบ
ถ้า $n=4$ จะไม่มีคำตอบ
ถ้า $n=5$ เราได้ $m=2,3$ เป็นคำตอบ

ต่อไปเป็นการพิสูจน์ว่า ถ้า $n>5$ แล้วจะไม่มีคำตอบ ซึ่งเราจะใช้ contradiction ในการพิสูจน์

สมมติให้มี $n_0>5$ เป็นจำนวนเต็มบวกที่น้อยที่สุดที่ทำให้โจทย์มีคำตอบเมื่อ $n=n_0$
ในกรณีนี้เราจะได้คำตอบที่มี $m \ge n_0$ ด้วย ไม่อย่างนั้นมันจะไปขัดแย้งกับข้อสมมติเรื่องน้อยที่สุดข้างต้น

เราสามารถแสดงได้ว่าไม่มีคำตอบในกรณีที่ $m=n_0$ เนื่องจากเมื่อ $n_0>5$ แล้ว $ n_0^2-1 \! \not| \; n_0^3+1 $ และไม่มีคำตอบในกรณีที่ $m=n_0+1 $ เช่นกัน เนื่องจากเมื่อ $n_0>5$ แล้ว $ n_0(n_0+1) -1 \! \not| \; n_0^3+1 $

ดังนั้น $ m \ge n_0+2 $

ถ้า $ mn_0-1 \mid n_0^3+1 $ แสดงว่าจะต้องมีจำนวนเต็มบวก $k$ ที่ทำให้ $ n_0^3+1 = k(mn_0-1) =kmn_0-k $
เราจึงได้ว่า $k \equiv -1 \pmod{n_0} $ นั่นคือ $k \ge n_0-1 $

ดังนั้น $$ k(mn_0-1) \ge (n_0-1)((n_0+2)n_0-1) = n_0^3 + n_0^2 - 3n_0 +1 > n_0^3+1 $$ จึงเกิดข้อขัดแย้งขึ้นครับ

[Timestopper_STG]

เห็นว่ากระทู้นี้ไม่มีโจทย์เหลืออยู่งั้นผมขอแจมด้วยคนนะครับ
36.จงแสดงว่ามีจำนวนนับ$n$อยู่อย่างไม่จำกัดที่ทำให้
ระหว่าง$n^2$กับ$(n+1)^2$มีจำนวนเฉพาะอยู่มากกว่า1ตัว

[warut]

ข้อ 36. ผมพิสูจน์โดย contradiction ครับ

ให้ $\pi(x)$ แทนจำนวนของจำนวนเฉพาะบวกทั้งหมดที่ $\le x$

สมมติว่ามีจำนวนนับ $n$ ที่ระหว่าง $n^2$ กับ $(n+1)^2$ มีจำนวนเฉพาะอยู่มากกว่า 1 ตัว อยู่เป็นจำนวนจำกัด

ดังนั้นเราจะได้ว่า มีค่าคงที่ $c$ ที่ทำให้ $ \pi(n^2) \le n+c $ สำหรับทุกจำนวนนับ $n$

จาก Prime Number Theorem เรารู้ว่า $$ \lim_{x \to \infty} \frac{\pi(x)\ln x}{x} =1 $$ แต่ในที่นี้เราพบว่า $$ \lim_{n \to \infty} \frac{\pi(n^2) \ln n^2}{n^2} \le \lim_{n \to \infty} \frac{(n + c) \ln n^2}{n^2} = 0 $$ จึงเกิดข้อขัดแย้งขึ้นครับ

[Timestopper_STG]

ครับ...ส่วนวิธีทำข้อของผมแบบคร่าวๆนะครับคือเปรียบเทียบอนุกรมอนันต์2อัน
เรารู้ว่า$\displaystyle{\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}}\;converges\;$แต่ผลรวมของส่วนกลับของจำนวนเฉพาะ$diverges $
ซึ่งจะเห็นว่าจำนวนที่เป็นกำลัง2สมบูรณ์ไม่มีทางเป็นจำนวนเฉพาะครับ
พอกลับเศษเป็นส่วนก็จะได้ว่ามีช่วงที่มีแบบดังกล่าวที่มีจนวนเฉพาะอยู่มากกว่า1ตัว
ทีนี้ถ้าช่วงเหล่านี้มีเป็นจำนวนจำกัดผลต่างก็จะเป็นจำนวนจริงซึ่งจะได้ว่า
อนุกรมที่เป็นส่วนกลับของจำนวนเฉพาะนั่นจะลู่เข้าแต่จริงๆมันลู่ออกเลยได้ครับ

[nooonuii]

เพิ่งได้การบ้านมาครับ ให้พิสูจน์ special case ของ Dirichlet's Prime Number Theorem ซึ่งผมพิสูจน์โดยใช้ cyclotomic polynomial เลยอยากรู้ว่ามีวิธีพิสูจน์แบบ elementary รึเปล่าครับ

37. ให้ $n$ เป็นจำนวนนับ จงพิสูจน์ว่ามีจำนวนเฉพาะเป็นจำนวนอนันต์ในรูป $an+1$

[warut]

ข้อความเดิมของคุณ Timestopper_STG:
ครับ...ส่วนวิธีทำข้อของผมแบบคร่าวๆนะครับคือเปรียบเทียบอนุกรมอนันต์2อัน
เรารู้ว่า$\displaystyle{\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}}\;converges\;$แต่ผลรวมของส่วนกลับของจำนวนเฉพาะ$diverges $
ซึ่งจะเห็นว่าจำนวนที่เป็นกำลัง2สมบูรณ์ไม่มีทางเป็นจำนวนเฉพาะครับ
พอกลับเศษเป็นส่วนก็จะได้ว่ามีช่วงที่มีแบบดังกล่าวที่มีจนวนเฉพาะอยู่มากกว่า1ตัว
ทีนี้ถ้าช่วงเหล่านี้มีเป็นจำนวนจำกัดผลต่างก็จะเป็นจำนวนจริงซึ่งจะได้ว่า
อนุกรมที่เป็นส่วนกลับของจำนวนเฉพาะนั่นจะลู่เข้าแต่จริงๆมันลู่ออกเลยได้ครับ

อ๋อ... ผมว่าผมเข้าใจแนวคิดของคุณ Timestopper_STG แล้วล่ะ เป็นวิธีที่เหนือชั้นกว่าของผมมากเลยครับ เพราะไม่ต้องไปพึ่งทฤษฎีชั้นสูงอย่าง Prime Number Theorem ใช้ความรู้พื้นๆก็เอาอยู่แล้ว

ถ้าผมเขียนการพิสูจน์ตามสไตล์ของผม แต่ใช้แนวคิดของคุณ Timestopper_STG ก็จะได้ออกมาดังนี้ครับ

ให้ $p_n$ แทนจำนวนเฉพาะตัวที่ $n$

สมมติว่าข้อความที่ต้องการพิสูจน์เป็นเท็จ นั่นคือมีจำนวนนับ $m$ ที่เมื่อ $n \ge m$ แล้วระหว่าง $n^2$ กับ $(n+1)^2$ มีจำนวนเฉพาะอยู่ไม่เกิน 1 ตัว

ถ้า $p_k > m^2$ แล้วเราจะได้ว่า $$ \begin{array}{rcl} p_{k+1} & > & (m+1)^2 \\ p_{k+2} & > & (m+2)^2 \\ & \vdots & \\ p_{k+i} & > & (m+i)^2 \end{array} $$ นั่นคือ $p_n > (n+c)^2$ เมื่อ $n \ge k$ และ $c = m-k$ เป็นค่าคงที่

ดังนั้นเราจึงได้ว่า $$ \sum_{n=1} ^\infty \frac{1}{p_n} \; \le \; \sum_{n=1} ^{k-1} \frac{1}{p_n} + \sum_{n=k} ^\infty \frac{1}{(n+c)^2} \; < \; \infty $$ ซึ่งขัดแย้งกับความจริงที่ว่า อนุกรมของส่วนกลับของจำนวนเฉพาะนั้นลู่ออก

หมายเหตุ เวลาเขียนภาษาอังกฤษธรรมดา ให้เอาไว้นอก LaTeX ครับ

ข้อความเดิมของคุณ Timestopper_STG:
36.จงแสดงว่ามีจำนวนนับ$n$อยู่อย่างไม่จำกัดที่ทำให้
ระหว่าง$n^2$กับ$(n+1)^2$มีจำนวนเฉพาะอยู่มากกว่า1ตัว

จะเห็นว่าโจทย์ข้อนี้ ถ้าเปลี่ยนจาก "ยกกำลังสอง" เป็น "ยกกำลัง $1+ \epsilon$ " เมื่อ $\epsilon$ เป็นจำนวนจริงบวกใดๆ และเปลี่ยน "อยู่มากกว่า 1 ตัว" เป็น "อยู่มากกว่า $k$ ตัว" เมื่อ $k$ เป็นจำนวนนับใดๆ โจทย์นี้ก็ยังใช้ได้อยู่ครับ

ป.ล. ช่วงนี้ผมเริ่มล้าจริงๆแล้วครับ ตอบติดต่อกันทุกวัน วันละหลายๆกระทู้ ยังไงถ้าผมตอบอันไหนช้าไปบ้างก็ขออภัยล่วงหน้าไว้ ณ ที่นี้เลยนะครับ

[warut]

ข้อความเดิมของคุณ nooonuii:
เพิ่งได้การบ้านมาครับ ให้พิสูจน์ special case ของ Dirichlet's Prime Number Theorem ซึ่งผมพิสูจน์โดยใช้ cyclotomic polynomial เลยอยากรู้ว่ามีวิธีพิสูจน์แบบ elementary รึเปล่าครับ

37. ให้ $n$ เป็นจำนวนนับ จงพิสูจน์ว่ามีจำนวนเฉพาะเป็นจำนวนอนันต์ในรูป $an+1$

การบ้านวิชาอะไรเหรอครับ Algebraic Number Theory รึเปล่า เพิ่งได้มาก็ทำเสร็จแล้วเหรอครับ

การพิสูจน์ข้อ 37. โดยใช้ cyclotomic polynomial ก็ถือว่าเป็น standard elementary proof ของกรณีนี้อยู่แล้วครับ (elementary กว่า Dirichlet's proof มาก) ผมเองก็เคยเห็นแค่ sketch of proof เท่านั้น ซึ่งต้องใช้คุณสมบัติของ cyclotomic polynomial บางอันที่ผมไม่เคยพิสูจน์ หรือพิสูจน์ไม่ได้

elementary proof แบบอื่นๆในกรณีนี้ก็มีครับ แต่ผมไม่เคยเห็นว่าทำยังไง ใช้ cyclotomic polynomial อีกหรือเปล่า ถ้าหากคุณ nooonuii สนใจ ผมจะไปค้น references มาให้ แล้วคุณ nooonuii ไปหาดูที่ห้องสมุดเองละกัน บอกด้วยนะครับว่าต้องเร่งแค่ไหน

[nooonuii]

ขอบคุณคุณ Warut สำหรับข้อมูลครับ
คุณ Warut ไม่ต้องรีบหาก็ได้ครับ จริงๆเป็นแค่ความอยากรู้อยากเห็นของผมเท่านั้นเอง โจทย์ข้อนี้เป็นการบ้านจากวิชา Algebraic Number Theory ครับ คิดได้แล้วก็ตั้งคำถามกับตัวเองว่าถ้าเรามีความรู้แค่ระดับเด็กๆไม่ต้องพึ่งทฤษฎีระดับสูงเราจะสามารถพิสูจน์ทฤษฎีนี้ได้หรือไม่ ก็เลยลองเอามาถามดูครับ

[warut]

มาแล้วครับ ข้อมูล...

บทความ: MR0136568, MR0158853, MR0412092

หนังสือ: MR0174513, MR0930670 แต่ผมไม่ทราบว่าอยู่หน้าไหนนะครับ

ถ้าคุณ nooonuii ว่างช่วยแสดงวิธีทำข้อ 37. เป็นวิทยาทานด้วยนะครับ

[nooonuii]

ขอบคุณมากครับ
สำหรับเฉลยผมคงต้องรออาจารย์ส่งการบ้านชุดนั้นคืนมาให้ก่อนครับ เพราะยังไม่รู้ว่าเขียนอะไรตกหล่นไปรึเปล่า

[Pheeradej]

โจทย์ข้อนี้ผมคิดเองครับ แต่ค่อนข้างมั่นใจว่าจริงนะครับ (ลองพิสูจน์ดูมั่งแล้ว)
38. จงแสดงว่า ไม่มี a,b,c,d ฮ $I^{+}$ ที่ทำให้$$a^{2}+b^{2}=c^{2}$$ และ $$b^{2}+c^{2}=d^{2}$$