Number Theory Marathon

[nooonuii]

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

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

เห็นวิธีพิสูจน์แบบธรรมดาแล้วอึ้งไปเลย ขอคารวะคุณ Warut ซักสองจอกครับ

Solution : Group Theory Version

เงื่อนไข $a^2 \equiv 1$ (mod $n$) ทุกจำนวนเต็ม $a$ ซึ่ง $(a,n)=1$
เขียนเป็นภาษา Group Theory ได้ว่า ทุกสมาชิกใน $\mathbb{Z}_n^{\times}$ มีขนาดไม่เกิน $2$
ดังนั้นเราจะได้ว่า $\mathbb{Z}_n^{\times}$ มีขนาดเป็น $2^m$ สำหรับบางค่า $m$
แต่เราทราบว่า $|\mathbb{Z}_n^{\times}|=\phi(n)$ เมื่อ $\phi$ เป็น Euler-phi function
เราจึงได้ $$\phi(n) = 2^m .........(*)$$
ต่อไปเขียน $\displaystyle{ n=2^rp_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} }$ เมื่อ $p_i$ เป็นจำนวนเฉพาะคี่ที่แตกต่างกัน
ถ้า $a_i\geq 2$ เราจะได้ว่า $\phi(p_i^{a_i}) = p^{a_{i}-1}(p-1)$ ซึ่งไม่เป็น power ของ 2 จึงขัดแย้งกับ (*)
ดังนั้น $a_i \leq 1$ ทุกค่า $i$ และจาก (*) เราจะได้ว่า $p_i$ ต้องอยู่ในรูป $2^{b}+1$
เนื่องจาก $7$ ไม่อยู่ในรูป $2^{b}+1$ เราจึงได้ว่า $(7,n)=1$ นั่นคือ $7\in \mathbb{Z}_n^{\times}$
ดังนั้น $7^2\equiv 1$ (mod $n$) เราจึงได้ว่า $n | 48$
ถ้า $n=48$ เราทราบว่า $(11,48) = 1$ แต่ $11^2\not\equiv 1$ (mod $48$)
ดังนั้น $n$ เป็นตัวหารของ $24$ ซึ่งหลังจากตรวจสอบเงื่อนไขแล้วก็จะได้ $$n=2,3,4,6,8,12,24$$

[warut]

ใช้ group theory พิสูจน์ก็น่าสนใจมากครับ

ว่าแต่คำไทยสำหรับ "order" (ของ element ของ group) นี่คือคำว่า "ขนาด" เหรอครับ ฟังดูแล้วมันแปลกจัง

ตอนท้ายของการพิสูจน์ที่ใช้ 11 นั่นเปลี่ยนเป็น 5 ก็ได้ใช่ไหมครับ

เห็นประโยค $\phi(n) = 2^m$ ในการพิสูจน์ของคุณ nooonuii แล้วทำให้นึกถึงความจริงที่ว่า

รูป $n$ เหลี่ยมด้านเท่ามุมเท่า (regular $n$-gon) จะสร้างโดย Euclidean construction ได้ ก็ต่อเมื่อ $\phi(n)$ อยู่ในรูป $2^m$

พอดีผมเคยพูดเกี่ยวกับเรื่องนี้ไป 2 ทีแล้ว คือ ที่นี่ กับ ที่นี่ แต่ยังไม่เคยพูดจุดนี้เลย

ขอบคุณคุณ nooonuii สำหรับโจทย์ สวย-โหด-ประหาร ที่เอามาฝาก (ให้ปวดหัวกัน ) อยู่เสมอๆครับ

ป.ล. ใครว่างก็ลองมาทำโจทย์ข้อ 39-41 ที่เหลือ ของคุณ nongtum หน่อยนะ ดูแล้วไม่น่าจะยากครับ แต่ผมก็ยังไม่ได้ลองเหมือนกัน แหะๆ

[nooonuii]

ข้อความเดิมของคุณ warut:
ใช้ group theory พิสูจน์ก็น่าสนใจมากครับ

ว่าแต่คำไทยสำหรับ "order" (ของ element ของ group) นี่คือคำว่า "ขนาด" เหรอครับ ฟังดูแล้วมันแปลกจัง

ตอนท้ายของการพิสูจน์ที่ใช้ 11 นั่นเปลี่ยนเป็น 5 ก็ได้ใช่ไหมครับ

ขนาดของ $a$ ก็คือขนาดของ cyclic group $<a>$ ไงครับ

ส่วนตอนท้ายการพิสูจน์สามารถใช้ 5 ได้เหมือนกันครับ แต่ผมข้ามไป 11 ได้ไงหว่า

[warut]

ข้อความเดิมของคุณ nongtum:
39. Find $n,p\in\mathbb{N}$ such that $$n,\ n+2^p,\ n+2^{p+1},\ n+2^{p+2}$$ are simultaneously prime.

เนื่องจาก $2^p\equiv(-1)^p\pmod3$ ดังนั้นภายใต้ modulo 3 เลข 4 ตัวที่ให้มาจึงเป็น $$n, n+(-1)^p, n+(-1)^{p+1}, n+(-1)^p$$ ซึ่งเป็น complete residue system modulo 3 (เนื่องจากประกอบด้วย $n-1,n,n+1$) ดังนั้นจึงต้องมีอย่างน้อยตัวนึงที่หารด้วย 3 ลงตัว แต่เนื่องจากเราต้องการให้ทุกตัวเป็นจำนวนเฉพาะ เลขตัวที่ 3 หารลงตัวนั้นจึงต้องเป็น 3 แต่ $n+2^p$ หรือ $n+2^{p+1}$ หรือ $n+2^{p+2}$ เป็น 3 ไม่ได้ เพราะจะทำให้ $n\le1$ ดังนั้น $n=3$

พิจารณา $$3,\ 2^p+3,\ 2^{p+1}+3,\ 2^{p+2}+3$$ กรณีที่ 1: $p\equiv1\pmod4$

จะเห็นว่า $5\mid2^p+3$ ดังนั้นในกรณีนี้เราจึงต้องได้ว่า $2^p+3=5$ นั่นคือ $p=1$ ซึ่งจะนำเราไปสู่คำตอบ $3,5,7,11$

กรณีที่ 2: $p\equiv3\pmod4$

จะเห็นว่า $5\mid2^{p+2}+3$ แต่ $2^{p+2}+3>5$ เสมอ ดังนั้นกรณีนี้จึงไม่มีคำตอบ

กรณีที่ 3: $p\equiv0\pmod4$

จะเห็นว่า $5\mid2^{p+1}+3$ แต่ $2^{p+1}+3>5$ เสมอ ดังนั้นกรณีนี้จึงไม่มีคำตอบเช่นกัน

กรณีที่ 4: $p\equiv2\pmod4$

ให้ $p=4k+2$ แล้วแบ่งเป็นอีก 3 กรณีย่อย

กรณีที่ 4.1: $k\equiv1\pmod3$

จะเห็นว่า $7\mid2^{p+2}+3$ แต่ $2^{p+2}+3>7$ เสมอ ดังนั้นกรณีนี้จึงไม่มีคำตอบ

กรณีที่ 4.2: $k\equiv2\pmod3$

จะเห็นว่า $7\mid2^{p+1}+3$ แต่ $2^{p+1}+3>7$ เสมอ (เพราะ $p\ge10$) ดังนั้นกรณีนี้จึงไม่มีคำตอบเช่นกัน

กรณีที่ 4.3: $k\equiv0\pmod3$

จะเห็นว่า $7\mid2^p+3$ ดังนั้นในกรณีนี้เราจึงต้องได้ว่า $2^p+3=7$ นั่นคือ $p=2$ ซึ่งจะนำเราไปสู่คำตอบ $3,7,11,19$

สรุปว่ามีเพียง 2 คำตอบคือ $(n,p)=(3,1),(3,2)$

ป.ล. ยากกว่าที่คาดไว้เยอะเลยครับ แต่ยังไม่โหดร้ายเท่า ปัญหาชิงรางวัลข้อที่ 16 เนอะ

[warut]

โจทย์ข้อ 39. มีความยากและน่าสนใจโดดเด่นเป็นพิเศษ แต่ข้อ 40-41 นี่ไม่ได้ยากไปกว่าข้อ 38. เท่าไหร่เลย แต่ก็ไม่มีใครทำอยู่ดีง่ะ ดังนั้นผมขอแสดงวิธีทำแบบย่อๆนะครับ

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

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

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

ถ้า $p\equiv1\pmod5$ แล้ว $5\mid3p+2$
ถ้า $p\equiv2\pmod5$ แล้ว $5\mid2p+1$
ถ้า $p\equiv3\pmod5$ แล้ว $5\mid4p+3$
ถ้า $p\equiv4\pmod5$ แล้ว $5\mid6p+1$

ดังนั้นคำตอบของข้อนี้จึงมีเพียง $p=5$ ครับ

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

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

เนื่องจากถ้า $p\equiv\pm1\pmod3$ แล้ว $3\mid p^2+2$ ดังนั้นคำตอบของข้อนี้จึงมีเพียง $p=3$ ครับ

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

แต่เกรงว่าจะไม่มีใครเล่นน่ะสิครับ...

[nongtum]

ข้อความเดิมของคุณ warut:
แต่เกรงว่าจะไม่มีใครเล่นน่ะสิครับ...

ผมก็ว่างั้นล่ะ ปกติคนเล่นกับคนออกโจทย์ก็แทบจะนับนิ้วไล่ชื่อได้อยู่แล้ว เอาเป็นว่าไว้เจอโจทย์อื่นที่น่าสนใจค่อยเอามาแปะดีกว่าครับ

[warut]

43. จงหาจำนวนเต็มบวก $x,y,z$ ทั้งหมด ที่ทำให้ $4(x+y+z)=xyz$

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

[gools]

ข้อความเดิมของคุณ warut:
43. จงหาจำนวนเต็มบวก $x,y,z$ ทั้งหมด ที่ทำให้ $4(x+y+z)=xyz$

สมมติให้ $x,y,z \geq 3$
กำหนดจำนวนเต็มบวก $a,b,c$ โดยที่ $a+2=x,b+2=y,c+2=z$
ดังนั้น \[\begin{array}{rcl} (a+2)(b+2)(c+2) &=& 4(a+b+c+6) \\
abc+2(ab+bc+ca)+4(a+b+c)+8 &=& 4(a+b+c)+24 \\
2(ab+bc+ca)+abc &=& 16 \end{array} \]
ลองแทน $a,b,c=2$ ฝั่งซ้ายของสมการจะเป็น $32$
ดังนั้นระหว่าง $a,b,c$ ต้องมีอย่างน้อยหนึ่งตัวที่เท่ากับ $1$ สมมติให้เป็น $c$
\[3ab+2a+2b=16\]
แทน $a,b=2$ ฝั่งซ้ายของสมการจะเป็น $20$
ดังนั้นระหว่าง $a,b$ ต้องมีอย่างน้อยหนึ่งตัวที่เท่ากับ $1$ สมมติให้เป็น $b$
ดังนั้น $5a=14$ ซึ่ง $a$ ไม่เป็นจำนวนเต็ม

ดังนั้นใน $x,y,z$ ต้องมีอย่างน้อยหนึ่งตัวที่น้อยกว่า $3$
สมมติให้เป็น $x$

กรณีที่ 1 $x=1$
\[\begin{array}{rcl} 4(1+y+z) &=& yz \\
(y-4)(z-4) &=& 20 \end{array} \]
จะได้ $(y,z)=(9,8),(8,9),(14,6),(6,14),(24,5),(5,24)$

กรณีที่ 2 $x=2$
\[\begin{array}{rcl} 4(2+y+z) &=& 2yz \\
(y-2)(z-2) &=& 8 \end{array} \]
จะได้ $(y,z)=(10,3),(3,10),(6,4),(4,6) $

ดังนั้น $(x,y,z)$ ทั้งหมดที่เป็นคำตอบของสมการคือ $(1,9,8),(1,8,9),(1,14,6),(1,6,14),(1,24,5),(1,5,24),(2,10,3),(2,3,10),(2,6,4),(2,4,6)$

[warut]

โอ๊ะโอว... โจทย์ข้อ 43. นี่สามารถทำให้คุณ gools ปรากฎตัวออกมาได้แฮะ แถมรู้สึกว่ากลับมาคราวนี้ จะมีพลังยุทธเพิ่มขึ้นอีกซะด้วย

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

ให้ $a,b,c\in\mathbb N$ แทนความยาวของด้านทั้งสามของสามเหลี่ยม
ให้ $A$ แทนพื้นที่ของสามเหลี่ยม
ให้ $r$ แทนรัศมีของวงกลมแนบในสามเหลี่ยม (inradius)
ให้ $s$ แทน semiperimeter ของสามเหลี่ยม นั่นคือ $$s=\frac{a+b+c}{2}$$ เรามีสูตรอยู่ว่า $A=rs$ และในที่นี้เราต้องการให้ $A=2s$ ดังนั้น $r=2$

ดังนั้นปัญหาที่กระทู้นั้นจึงสมมูลกับ การหาสามเหลี่ยมที่เป็นไปได้ทั้งหมด ที่มีความยาวด้านเป็นจำนวนเต็ม และมี inradius เท่ากับ 2

ซึ่งปัญหาการหาสามเหลี่ยมที่เป็นไปได้ทั้งหมด ที่มีความยาวด้านและ inradius เป็นจำนวนเต็ม เป็นปัญหา classic ครับ

กลับมาแก้ปัญหาของเรากันต่อ

จาก Heron's formula เรารู้ว่า $$A= \sqrt{s(s-a)(s-b)(s-c)}$$ แต่เราต้องการให้ $A=2s$ ดังนั้นเราจึงได้ว่า $$(*) \quad 4s=(s-a)(s-b)(s-c)$$

เนื่องจาก $4s$ เป็นจำนวนเต็ม (ให้สังเกตว่า $s$ เป็นจำนวนเต็ม หรือไม่ก็เป็น half-integer) ดังนั้น $(s-a)(s-b)(s-c)$ เป็นจำนวนเต็ม นั่นแสดงว่า $s$ ต้องเป็นจำนวนเต็มด้วย

ให้ $x=s-a,y=s-b,z=s-c$ จะเห็นว่า $x,y,z\in\mathbb N$ และ $x+y+z=s$ แทนค่ากลับลงไปใน $(*)$ เราก็จะได้สมการของโจทย์ข้อ 43. ครับ

ถ้านำคำตอบที่คุณ gools หาได้มาแปลงกลับเป็นความยาวของด้านสามเหลี่ยม เราจะพบว่า สามเหลี่ยมที่มีความยาวด้านเป็นจำนวนเต็ม และมีพื้นที่เท่ากับความยาวของเส้นรอบรูป มีอยู่ 5 แบบคือ สามเหลี่ยมที่มีความยาวด้านเป็น $\{6,8,10\}$, $\{5,12,13\}$, $\{9,10,17\}$, $\{7,15,20\}$, $\{6,25,29\}$ ครับผม

[dektep]

44. Let x,y,z be positive integers such that
1/x-1/y=1/z
Let h be the greatest common divisor of x,y,z.Prove that hxyz and h(y-x) are perfect squares.

Edit: ใส่เลขข้อ

[nongtum]

ข้อความเดิมของคุณ dektep:
44. Let $x,y,z$ be positive integers such that $$\frac1x-\frac1y=\frac1z.$$Let $h$ be the greatest common divisor of $x,y,z$. Prove that $hxyz$ and $h(y-x)$ are perfect squares.

WLOG let $h=1$ (since if the statatement is true, the factor $h^2$ or $h^4$ can be pulled out from the terms and they are still perfect squares).
From $\displaystyle\frac1x-\frac1y=\frac{y-x}{yx}=\frac1z$ we must have $xy=z$, since $y-x=yx/z$ is an integer, and the case $xy>z$ contradicts $z\not\vert x,\ z\not\vert y$.
From this we get $x=x,\ y=x+1,\ z=x(x+1)$ which satisfy the desired conditions.###

45. Find the natural numbers $N$ so that $N\times8888$ contains all the digits of the decimal system, each taken once.

[Onasdi]

สวัสดีครับ ผมเป็นสมาชิกใหม่ ฝากตัวด้วยครับ

คุณ nongtum ครับ ผมว่าการสรุปว่า xy=z ไม่ถูกนะครับ
เช่น x=6, y=10, z=15 เป็นคำตอบ แต่ไม่สอดคล้อง xy=z

[nongtum]

ข้อความเดิมของคุณ Onasdi:
สวัสดีครับ ผมเป็นสมาชิกใหม่ ฝากตัวด้วยครับ

คุณ nongtum ครับ ผมว่าการสรุปว่า xy=z ไม่ถูกนะครับ
เช่น x=6, y=10, z=15 เป็นคำตอบ แต่ไม่สอดคล้อง xy=z

ใช่ครับ ขอบคุณที่ท้วงครับ เดี๋ยวขอทดกรณีนี้อีกรอบแล้วจะมาแก้ครับ

[warut]

ข้อความเดิมของคุณ dektep:
44. Let $x,y,z$ be positive integers such that $$\frac1x-\frac1y=\frac1z.$$Let $h$ be the greatest common divisor of $x,y,z$. Prove that $hxyz$ and $h(y-x)$ are perfect squares.

พิสูจน์

กรณีที่ 1: $h=\gcd(x,y,z)=1$

จาก $\dfrac1x-\dfrac1y=\dfrac1z$ ดังนั้น $(y-x)(z-x)=x^2$

ต่อไปเราจะแสดงว่า $\gcd(y-x,z-x)=1$

สมมติให้มีจำนวนเฉพาะ $p$ ที่หาร $\gcd(y-x,z-x)$ ลงตัว จากที่ $(y-x)(z-x)=x^2$ ดังนั้น $p\mid x^2$ นั่นคือ $p\mid x$ และเนื่องจาก $p\mid y-x$ และ $p\mid z-x$ ดังนั้น $p\mid y$ และ $p\mid z$ แสดงว่า $p$ เป็นตัวหารร่วมของ $x,y,z$ จึงขัดแย้งกับที่เราสมมติว่า $\gcd(x,y,z)=1$ ดังนั้น $\gcd(y-x,z-x)$ จึงต้องเป็น $1$

จากที่ $(y-x)(z-x)=x^2$ และ $\gcd(y-x,z-x)=1$ ดังนั้น $y-x$ (และ $z-x$) จึงเป็น perfect square และเนื่องจาก $xyz=(y-x)z^2$ ดังนั้น $xyz$ จึงเป็น perfect square ด้วย

กรณีที่ 2: $h>1$

ให้ $x=hx'$, $y=hy'$, $z=hz'$ เราจะได้ว่า $\gcd(x',y',z')=1$ และ $\dfrac{1}{x'} -\dfrac{1}{y'} =\dfrac{1}{z'}$

จากกรณีที่ 1 เราจึงได้ว่า $x'y'z'$ เป็น perfect square ดังนั้น $hxyz=h^4x'y'z'$ จึงเป็น perfect square และเนื่องจาก $hxyz=h(y-x)z^2$ ดังนั้น $h(y-x)$ จึงเป็น perfect square ด้วย

ป.ล. ช่วงนี้ผมคงแทบไม่มีโอกาสได้เข้ามาเล่น ขอให้สนุกกันให้เต็มที่นะครับ

[gon]

ข้อความเดิมของคุณ warut:
ป.ล. ช่วงนี้ผมคงแทบไม่มีโอกาสได้เข้ามาเล่น ขอให้สนุกกันให้เต็มที่นะครับ

อยู่ฉลองของใหม่กันสักปีก่อนครับ ใกล้แล้ว