Number Theory Marathon

[warut]

เอ้อ... คุณ Pheeradej เข้ามาก็ดีละ จะขอถามหน่อยครับว่า โจทย์ข้อ 34. ของคุณ Pheeradej นั่นเอามาจากไหน และเฉลยเค้าทำยังไงครับ ผมมีความรู้สึกว่า ลักษณะของโจทย์ข้อนี้เหมือนพวกโจทย์โอลิมปิกมากๆเลย

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

[warut]

นึกออกละ ข้อ 38. ผมทำอย่างนี้ครับ

ก่อนอื่นขอทบทวนก่อนว่า primitive Pythagorean triple $(X,Y,Z)$ คือจำนวนเต็มบวก $X,Y,Z$ ที่มี $\gcd(X,Y,Z)=1$ และ $X^2+Y^2=Z^2$

ถ้าหาก $(X,Y,Z)$ เป็น primitive Pythagorean triple แล้ว $X,Y$ จะมี opposite parity (ตัวนึงเป็นคู่ ตัวนึงเป็นคี่) ถ้าเราเลือกให้ $Y$ เป็นจำนวนคู่แล้ว จะมี $\alpha, \beta \in \mathbb N$ ที่ทำให้ $$ \begin{array}{rcl} X & = & \alpha^2 - \beta^2 \\ Y & = & 2\alpha \beta \\ Z & = & \alpha^2 + \beta^2 \end{array} $$ เสมอ ให้สังเกตด้วยว่า $\alpha > \beta, \, \gcd(\alpha, \beta)=1$ และ $\alpha, \beta$ มี opposite parity

จบการทบทวน เข้าสู่การพิสูจน์ครับ

สมมติให้ $c$ เป็นจำนวนเต็มบวกที่น้อยที่สุดที่มี $a,b,d\in\mathbb N$ ที่ทำให้ $$ \begin{array}{rcl} a^2+b^2 & = & c^2 \\ b^2+c^2 & = & d^2 \end{array} $$ จะเห็นว่า $\gcd(b,c)=1$ มิฉะนั้นเราจะสามารถหารตลอดได้ด้วย $\gcd(b,c)$ และได้คำตอบชุดใหม่ที่เล็กลงกว่าเดิม

ดังนั้น $(a,b,c)$ และ $(b,c,d)$ ต่างก็เป็น primitive Pythagorean triple โดยมี $b$ เป็นจำนวนคู่ และ $a,c,d$ เป็นจำนวนคี่

จะเห็นว่า $\gcd(a^2, d^2) = \gcd(c^2-b^2, c^2+b^2) =1$ เพราะค่า ห.ร.ม. ต้องหาร $(c^2+b^2) - (c^2-b^2) = 2b^2$ และ $(c^2+b^2) + (c^2-b^2) = 2c^2$ ลงตัว และเรารู้ว่า $(b,c)=1$ และ $b,c$ มี opposite parity

ดังนั้น $\gcd(a,d)=1$

ให้ $$ x= \frac{d+a}{2} ,\quad y= \frac{d-a}{2} $$ จะเห็นว่า $x,y$ เป็นจำนวนนับ เพราะ $d>a$ และ $a,d$ ต่างก็เป็นจำนวนคี่

ให้สังเกตว่า $\gcd(x,y)=1$ (พิจารณาได้จากค่า $x+y$ และ $x-y$)

เนื่องจาก $b^2=2xy$ แสดงว่ามีทางเป็นไปได้ 2 แบบคือ

1. มี $m,n\in\mathbb N$ ที่ทำให้ $x=2m^2$ และ $y=n^2$
2. มี $m,n\in\mathbb N$ ที่ทำให้ $x=m^2$ และ $y=2n^2$

ผมจะพิสูจน์เฉพาะกรณีแรก เพราะอีกกรณีนึงก็ทำแบบเดียวกันครับ

เนื่องจาก $x^2+y^2=c^2$ แสดงว่า $(x,y,c)$ เป็น primitive Pythagorean triple ดังนั้นจึงมี $p,q\in\mathbb N, \, p>q, \, \gcd(p,q)=1$ และ $p,q$ มี opposite parity ที่ทำให้ $$ \begin{array}{rcccl} x & = & 2m^2 & = & 2pq \\ y & = & n^2 & = & p^2-q^2 \\ & & c & = & p^2+q^2 \end{array} $$ เนื่องจาก $m^2=pq$ แสดงว่ามี $r,s\in\mathbb N$ ที่ทำให้ $p=r^2, \, q=s^2$

เนื่องจาก $\gcd(r^2-s^2, r^2+s^2) = \gcd(p-q, p+q) =1$ และ $n^2=(r^2-s^2)(r^2+s^2)$ ดังนั้นจึงมี $u,v\in\mathbb N$ ที่ทำให้ $r^2-s^2=u^2$ และ $r^2+s^2=v^2$ นั่นคือ $$ \begin{array}{rcl} u^2+s^2 & = & r^2 \\ s^2+r^2 & = & v^2 \end{array} $$ จะเห็นว่านี่ก็เป็นคำตอบอันนึงของสมการโจทย์ แต่เนื่องจาก $0<r<p<c$ จึงเกิดข้อขัดแย้งกับที่เราสมมติเรื่อง คำตอบที่น้อยที่สุด ไว้ในตอนต้น ดังนั้นสมการโจทย์จึงไม่มีคำตอบครับ

[Pheeradej]

โจทย์ข้อ 34 มีอาจารย์เอามาให้ผมทำครับ เห็นอาจารย์บอกว่าเอามาจาก IMO แต่อาจารย์ไม่ได้เอาเฉลยมาให้ พอผมคิดข้อนี้ได้แล้วผมก็เลยเอามาโพสต์ในกระทู้นี้ครับ วิธีทำของผมก็คล้ายๆ กับพี่ warut เลยครับ คือ แยกกรณีที่ n= 1,2,3,4,5 และ n > 5 ออกจากกันครับ

[warut]

ลืมบอกไปครับว่า โจทย์ข้อ 38. เกือบเทียบเท่ากับการพิสูจน์ Fermat's Right Triangle Theorem หรือการพิสูจน์ว่าสมการ Diophantine: $$ x^4-y^4=z^2 $$ ไม่มีคำตอบเป็นจำนวนเต็มอื่นนอกจาก trivial solutions

[nooonuii]

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

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

37. My Solution :

Suppose there are only finitely many primes $p_i \equiv 1 \,( mod\,\, n), i = 1,2,...,k.$
Let $m = p_1p_2\cdots p_k$ and $\Phi _n (x)$ be the n-th cyclotomic polynomial.
For sufficiently large $x$, we have $\Phi _n (mnx) \neq 1$, so there exists a prime $p$ dividing $\Phi _n (mnx)$.
Then $mnx$ is a root of $\Phi _n (t)\in \mathbb{Z}_p[t].$
Note that $\displaystyle{ t^n - 1 = \prod_{d|n}\Phi _d (t) = \Phi _n (t) \prod_{d|n,d<n}\Phi _d (t) .}$
Thus $(mnx)^n -1 \equiv 0 \,(mod \,\,p).$
Hence $m,n \not\equiv 0 \, (mod\,\, p).$
Note that $t^n - 1 \in \mathbb{Z}_p[t]$ is separable because $n \neq 0$ in $\mathbb{Z}_p$ and $gcd(t^n-1,nt^{n-1})=1.$
We will show that $mnx$ has order $n$ in the cyclic group $\mathbb{Z}_p^{\times}.$
Suppose there is $d|n,d<n$ such that
$$(mnx)^d \equiv 1 \,(mod\,\, p).$$
Then $mnx$ is a root of $\Phi_d(t)\in \mathbb{Z}_p[t].$
Thus $mnx$ is a multiple root of $t^n-1\in \mathbb{Z}_p[t]$ which is a contradiction.
Hence $mnx$ has order $n$ in $\mathbb{Z}_p^{\times}.$
By Lagrange's Theorem, $n||\mathbb{Z}_p^{\times}| = p-1.$
Thus $p\equiv 1 \,(mod\,\, n).$
Note that $p\neq p_i$ for all $i=1,2,...,k$ because $m\not\equiv 0 \,(mod\,\, p).$
Thus $p$ is another prime number which is congruent to 1 modulo $n$, a contradiction.
This completes the proof. $\clubsuit\heartsuit\diamondsuit\spadesuit$

ป.ล. วันนี้เพิ่งเรียนวิธีพิสูจน์แบบเต็มๆของ Dirichlet โดยใช้ Dirichlet L- Series ยากสุดๆไปเลยครับ คิดได้ยังไง

Edit (warut): quote โจทย์

[warut]

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

พูดถึงเรื่องความยากของ Dirichlet's proof ผมขอ quote เอาข้อความที่ MathWorld มาให้อ่านละกัน

Dirichlet proved this theorem using Dirichlet L-series, but the proof is challenging enough that, in their classic text on number theory, the usually explicit Hardy and Wright (1979) report "this theorem is too difficult for insertion in this book."

เอ้อ... แล้วอาจารย์ของคุณ nooonuii ออกเสียง "Dirichlet" ว่ายังไงเหรอครับ (คุณ tana เคยถามเรื่องนี้เอาไว้)

[nooonuii]

"Dirichlet" อาจารย์ผมอ่านออกเสียงประมาณว่า "ดิ-ริค-เล" ก็ไม่รู้ว่าชาวฝรั่งเศสเขาออกเสียงกันยังไงครับ แต่อาจารย์ผมเป็นชาว Greece

[warut]

ผมพิมพ์การพิสูจน์ข้อ 37. ของคุณ nooonuii มาอ่าน ตอนนี้เข้าใจตลอดหมดแล้วครับ เป็นการพิสูจน์ที่ง่ายและสวยงามมากจริงๆ แต่อันพิสูจน์ของผมนี่ดิ ผมยังติดอยู่เยอะครับ อย่างเช่น ในตอนต้นมันต้องใช้ความจริงที่ว่า $|\Phi_n(a)|>1$ for every $a>1$ ซึ่งผมยังไม่รู้ว่าจะพิสูจน์ยังไงเลย แต่การพิสูจน์ของคุณ nooonuii สามารถอ้อมหลบจุดนี้ไปได้

คุณ nooonuii ได้มีโอกาสไปค้นการพิสูจน์แบบอื่นๆบ้างเปล่า ไม่ทราบได้ความว่าไงบ้างครับ

[nooonuii]

ข้อความเดิมของคุณ warut:
ผมพิมพ์การพิสูจน์ข้อ 37. ของคุณ nooonuii มาอ่าน ตอนนี้เข้าใจตลอดหมดแล้วครับ เป็นการพิสูจน์ที่ง่ายและสวยงามมากจริงๆ แต่อันพิสูจน์ของผมนี่ดิ ผมยังติดอยู่เยอะครับ อย่างเช่น ในตอนต้นมันต้องใช้ความจริงที่ว่า $|\Phi_n(a)|>1$ for every $a>1$ ซึ่งผมยังไม่รู้ว่าจะพิสูจน์ยังไงเลย แต่การพิสูจน์ของคุณ nooonuii สามารถอ้อมหลบจุดนี้ไปได้

คุณ nooonuii ได้มีโอกาสไปค้นการพิสูจน์แบบอื่นๆบ้างเปล่า ไม่ทราบได้ความว่าไงบ้างครับ

ผมยังไม่ได้อ่านพิสูจน์ที่คุณ Warut นำมาให้อย่างละเอียดเลยครับ ช่วงนี้ในหัวมีแต่ Topology ครับ

การพิสูจน์ $\Phi_n(a)>1, \forall a>1$ ผมว่าใช้ induction on $n$ ได้ครับ เนื่องจากเรารู้ว่า
$$\displaystyle{x^n - 1 = \prod_{d|n}\Phi_d(x)}$$

[nooonuii]

เอ่อ เริ่มไม่แน่ใจแล้วครับว่า induction ใช้ได้จริงรึเปล่า

[nongtum]

38. Find $n\in\mathbb{N}$ such that $n,\ n+4,\ n+8$ are all prime.

39. Find $n,p\in\mathbb{N}$ such that $$n,\ n+2^p,\ n+2^{p+1},\ n+2^{p+2}$$ are simultaneously prime.

Hint: ทั้งสองข้อทำไปได้สักพักให้ลองคิดใน $\mathbb{Z}_3$ ครับ

[Timestopper_STG]

ข้อความเดิมของคุณ nongtum:
38. Find $n\in\mathbb{N}$ such that $n,\ n+4,\ n+8$ are all prime.

We know that $3|n$ or $3|(n+4)$ or $3|(n+8)$
So all of these will be prime if and only if one of them is 3.
But $n+4,n+8$ can't be 3, because the other won't be natural number.
Finally we get $n=3$

ข้อความเดิมของคุณ nongtum:

Hint: ทั้งสองข้อทำไปได้สักพักให้ลองคิดใน $\mathbb{Z}_3$ ครับ

ผมสงสัยนิดหน่อยครับว่า$\mathbb{Z}_3$คืออะไรหรอครับ

[nongtum]

ผมหมายถึง $\mathbb{Z}_3=\{3k,\ 3k+1,\ 3k+2, k\in\mathbb{Z}\}$ ครับ ในที่นี้ ถ้าเขียนเป็นภาษาไทยก็ระบบส่วนตกค้างบริบูรณ์มอดุโล 3 (complete residue system modulo 3) ซึ่งที่จริงแล้วในเฉลยที่ผมมีก็ใช้การคิดแยกกรณีตามเศษการหารด้วยสามล่ะครับ ผมหมายถึงตรงนั้นล่ะ อาจใช้สัญลักษณ์เกินจำเป็นไปนิด แต่มันสั้นดีก็เลยใช้

ที่ทำมาด้านบนไม่ผิดนะครับ แต่ทำแบบนี้กับข้อ 39 น่าจะลำบาก(หรือเปล่า)นะครับ ผมมีโจทย์ที่เกี่ยวกับสองข้อนี้อีกเยอะ เช่น

40. จงหาจำนวนเฉพาะ $p$ ที่ทำให้ $$2p+1,\ 3p+2,\ 4p+3,\ 6p+1$$ เป็นจำนวนเ้ฉพาะพร้อมกัน

ซึ่งสามารถคำนวณได้ใน $\mathbb{Z}_5$ หรือจะเป็น

41. จงหาจำนวนเฉพาะ $p$ ที่ทำให้ $$p,\ p^2+2,\ p^2+4,\ p^2+20$$ เป็นจำนวนเ้ฉพาะพร้อมกัน

ซึ่งสามารถคำนวณได้ใน $\mathbb{Z}_3$ ครับ

โจทย์ในชุดนี้ที่น่าเล่นมีอีกหลายข้อ แล้วจะค่อยๆทยอยโำพสต์ให้ครับ

[nooonuii]

เพิ่งได้โจทย์มาข้อนึงจากเพื่อน ไม่แน่ใจว่าจะใช้ทฤษฎีจำนวนพื้นฐานได้รึเปล่าครับ แต่ผมใช้ Group Theory พิสูจน์

42. จงหาจำนวนนับ $n>1$ ทั้งหมด ซึ่งทำให้ $a^2 \equiv 1$ (mod $n$) ทุกจำนวนเต็ม $a$ ซึ่ง $(a,n)=1$

[warut]

ส่วนที่จุกจิกที่สุดในการพิสูจน์ข้อ 42. ของผม เห็นจะเป็นจุดที่ต้องพิสูจน์ว่า

(*) ถ้า $a^2\equiv1\pmod n$ สำหรับทุก $a$ ที่ $(a,n)=1$ และ $p$ เป็นตัวประกอบเฉพาะของ $n$ แล้ว $a^2\equiv1\pmod p$ สำหรับทุก $a$ ที่ $(a,p)=1$ (i.e., $p\!\not|\;a$)

ดูๆเหมือนจะ obvious แต่ไม่ครับ เพราะ $$\{a\in\mathbb N\mid(a,n)=1\}\subseteq\{a\in\mathbb N\mid(a,p)=1\}$$ อย่างเช่น $(3,15)\ne1$ แต่ $(3,5)=1$ ดังนั้นตรงนี้จึงดูเหมือนเราต้องขยายผลออกไป

ถ้าใครมีวิธีพิสูจน์ หรือมุมมองดีๆ ในการจัดการกับส่วนนี้ก็ช่วยบอกด้วยนะครับ แต่วิธีพิสูจน์ของผมเป็นดังนี้

เราจะพิสูจน์ (*) โดยเริ่มจากการแสดงว่า

สำหรับทุก $x\in\{1,2,\dots,p-1\}$ จะมี $b\equiv x\pmod p$ ที่ $(b,n)=1$

ซึ่งทำได้ดังนี้

ให้ $n=p^rq$ โดยที่ $(p,q)=1$ และให้ $b$ สอดคล้องกับระบบสมการ $$\begin{array}{rcll} b & \equiv & x & \pmod p \\ b & \equiv & 1 & \pmod q \end{array}$$ (ซึ่งเรารู้ว่าจะต้องมีอยู่จริงโดย Chinese Remainder Theorem) เราจะได้ว่า $(b,p)=(b,q)=1$ นั่นคือ $(b,n)=1$ ตามต้องการ

จากที่ $(b,n)=1$ ดังนั้น $b^2\equiv1\pmod n$ นั่นคือ $b^2\equiv1\pmod p$ แต่ $b^2\equiv x^2\pmod p$ ดังนั้น $x^2\equiv1\pmod p$ สำหรับทุก $x\in\{1,2,\dots,p-1\}$

แต่เรารู้ว่าถ้า $p\!\not|\;a$ แล้ว $a\equiv x\pmod p$ สำหรับบาง $x\in\{1,2,\dots,p-1\}$ ดังนั้นเราจึงได้ว่า $a^2\equiv x^2\equiv1\pmod p$ สำหรับทุก $a$ ที่ $(a,p)=1$

ตอนนี้เราก็พร้อมที่จะพิสูจน์โจทย์ข้อ 42. แล้วครับ

เนื่องจากจำนวนเฉพาะ $p$ ที่มีสมบัติว่า $a^2\equiv1\pmod p$ สำหรับทุก $a$ ที่ $(a,p)=1$ มีเพียง $2$ กับ $3$ (ถ้าจำนวนเฉพาะ $p>3$ เราจะได้ว่า $(2,p)=1$ แต่ $2^2=4 \not\equiv 1\pmod p$) ดังนั้น ตัวประกอบเฉพาะที่เป็นไปได้ ของจำนวนนับที่มีสมบัติตามที่โจทย์ต้องการ จึงมีเพียง $2$ กับ $3$ เท่านั้น

จะเห็นว่า $2^3$ มีสมบัติตามที่โจทย์ต้องการ แต่ $2^4$ ไม่มีสมบัติตามที่โจทย์ต้องการ เพราะ $3^2=9\not\equiv1\pmod{2^4}$

จะเห็นว่า $3$ มีสมบัติตามที่โจทย์ต้องการ แต่ $3^2$ ไม่มีสมบัติตามที่โจทย์ต้องการ เพราะ $2^2=4\not\equiv1\pmod{3^2}$

ให้สังเกตว่า

1. ถ้า prime power $p^r$ มีสมบัติตามที่โจทย์ต้องการแล้ว $p^s$ เมื่อ $1\le s\le r$ ก็จะมีสมบัติตามที่โจทย์ต้องการด้วย
2. ถ้า prime power $p^r$ ไม่มีสมบัติตามที่โจทย์ต้องการแล้ว $p^s$ เมื่อ $s\ge r$ ก็จะไม่มีสมบัติตามที่โจทย์ต้องการด้วย
3. ถ้า $m,n$ มีสมบัติตามที่โจทย์ต้องการ และ $(m,n)=1$ แล้ว $mn$ ก็จะมีสมบัติตามที่โจทย์ต้องการด้วย

ดังนั้นจำนวนนับทั้งหมดที่มีสมบัติตามที่โจทย์ต้องการคือ จำนวนที่อยู่ในรูป $2^a3^b>1$ โดยที่ $0\le a\le3$ และ $0\le b\le1$ นั่นคือ $2,3,4,6,8,12,24$ ครับ