Number Theory Marathon

[warut]

เพิ่มเติมอีกหน่อยนะครับ

ตรงส่วนที่ใช้ pigeon-hole principle เป็นเทคนิคของ Dirichlet ซึ่งในหนังสือ An Introduction to the Theory of Numbers ของ Hardy & Wright ก็ใช้ครับ

ส่วนที่ว่าเกี่ยวกับ Dynamical Systems อย่างไร ผมว่าน่าจะอยู่ตรงที่มีการใช้ iterative process มั้งครับ

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

[nooonuii]

จริงๆแล้ว Dynamical Systems เป็นวิชาที่มีขอบเขตกว้างมากๆครับ มีการศึกษากันในหลายวิชาทางคณิตศาสตร์ เช่น
1. Topology (Topological Dynamics)
2. Probability Theory (Ergodic Theory)
3. Coding Theory (Symbolic Dynamics)
4. Differential Geometry (Hyperbolic Dynamics)
5. Analysis (Complex Dynamics, Fractal Geometry, and Low-dimensional Dynamics)
6. Differential Equations

นอกจากนี้ยังมีการนำไปประยุกต์ใช้ได้หลากหลายเช่น ในทฤษฎีจำนวน, Chaos Theory, และ Quantum Physics เป็นต้น เทคโนโลยีที่มีวิชานี้เป็นองค์ประกอบในการสร้างที่โด่งดังมากก็คือ Search Engine Google ครับ โจทย์ข้อนี้ผมเอามาจากแบบฝึกหัดในหนังสือ Introduction to Dynamical Systems ซึ่งเขียนโดย Michael Brin และ Garrett Stuck หน้า 5 การพิสูจน์ก็จะคล้ายๆกับ paper ที่คุณ Warut นำมาให้ดูนั่นแหละครับ แต่ของผมจะเขียนด้วยภาษาของวิชา topology

P.S. Michael Brin คือพ่อของ Sergey Brin หนึ่งในผู้ก่อตั้ง Google ครับ

[warut]

ข้อความเดิมของคุณ nongtum:
20. จงหาจำนวนเต็มบวก x,y,z ทั้งหมดที่ทำให้ 4^x+4^y+4^z เป็นจำนวนจัตุรัส

ไม่มีเซียนโจทย์โอลิมปิกคนไหนเข้ามาตอบข้อนี้เลยอ่ะ ถ้างั้นผมขอแปะเฉลยของ Arne ที่ Art of Problem Solving Forum นะครับ

[gools]

ข้อต่อไปนะครับ
หาจำนวนนับ \(a,b,c\) ทั้งหมดที่ \((abcabc)_{10}+1\) เป็นจำนวนกำลังสองสมบูรณ์

[R-Tummykung de Lamar]

ยังทำไม่ได้เลยครับ โพสต์เท่าที่คิดได้ก่อนละกันนะครับ

จาก \(\displaystyle{(abcabc)_{10}\ =\ (abc)_{10} \times 1001} \)
แยกตักประกอบได้ \( \displaystyle{1001\ =\ 7\times 11\times 13}\)

ให้ \(\displaystyle{(abcabc)_{10}+1\ =\ r^2} \)
\(\displaystyle{(abc)_{10}\times 7 \times 11 \times 13\ =\ r^2-1\ =\ (r-1)(r+1)} \)
จะได้ \( \displaystyle{7,11,13|(r-1)(r+1)} \)
เนื่องจากทั้งสามตัวเป็นจำนวนเฉพาดังนั้น ต้องหาร r - 1 , r + 1 ตัวใดตัวหนึ่งลง นั่นคือ
\(\displaystyle{r \equiv \pm 1\ (\bmod \ \ 7,11,13)} \)\(\displaystyle{\qquad ...(i)} \)

จาก \( \displaystyle{\ 111\leq (abc)_{10} \leq 999\ } \)
\( \displaystyle{\ 111111\leq (abc)_{10}\times 1001 \leq 999999\ } \)
\( \displaystyle{\ 111112\leq (abcabc)_{10}+1\leq 10^6\ } \)
\( \displaystyle{\ 334\leq r \leq 10^3\ } \)\(\displaystyle{\qquad ...(ii)} \)


จาก \(\displaystyle{(i)\ } \) และ \(\displaystyle{\ (ii)\ } \)จะได้ r เป็นจำนวนคู่ ที่ \( \displaystyle{\ 334\leq r \leq 10^3\ } \)

เอ..เดี๋ยวพรุ่งนี้มาลองทำต่อนะครับ ..ง่วงละ

[R-Tummykung de Lamar]

ข้อความเดิมของคุณ R-Tummykung de Lamar:
ยังทำไม่ได้เลยครับ โพสต์เท่าที่คิดได้ก่อนละกันนะครับ

จาก \(\displaystyle{(abcabc)_{10}\ =\ (abc)_{10} \times 1001} \)
แยกตักประกอบได้ \( \displaystyle{1001\ =\ 7\times 11\times 13}\)

ให้ \(\displaystyle{(abcabc)_{10}+1\ =\ r^2} \)
\(\displaystyle{(abc)_{10}\times 7 \times 11 \times 13\ =\ r^2-1\ =\ (r-1)(r+1)} \)
จะได้ \( \displaystyle{7,11,13|(r-1)(r+1)} \)
เนื่องจากทั้งสามตัวเป็นจำนวนเฉพาดังนั้น ต้องหาร r - 1 , r + 1 ตัวใดตัวหนึ่งลง นั่นคือ
\(\displaystyle{r \equiv \pm 1\ (\bmod \ \ 7,11,13)} \)\(\displaystyle{\qquad ...(i)} \)

จาก \( \displaystyle{\ 111\leq (abc)_{10} \leq 999\ } \)
\( \displaystyle{\ 111111\leq (abc)_{10}\times 1001 \leq 999999\ } \)
\( \displaystyle{\ 111112\leq (abcabc)_{10}+1\leq 10^6\ } \)
\( \displaystyle{\ 334\leq r \leq 10^3\ } \)\(\displaystyle{\qquad ...(ii)} \)

จาก \(\displaystyle{(i)\ } \) และ \(\displaystyle{\ (ii)\ } \)จะได้ r เป็นจำนวนคู่ ที่ \( \displaystyle{\ 334\leq r \leq 10^3\ } \)

เอ..เดี๋ยวพรุ่งนี้มาลองทำต่อนะครับ ..ง่วงละ

----------------------------------------------
ทำต่อที่ \(\displaystyle{\ (i)\ } \) นะครับ

กรณีที่ 1 \( \equiv \ \pm 1\) ทั้งสามตัว ( ( 1,1,1) หรือ (-1,-1,-1) )
ได้ \(\displaystyle{r \equiv \pm 1 (\bmod \ \ 1001)} \) ดูจากช่วงแล้ว กรณีนี้ได้คำตอบคือ r = 1000
นั่นคือ \( \displaystyle{(r-1)(r+1)\ =\ (999)(1001)\ =\ 999999} \)
สรุป a = b = c = 9

กรณีที่ 2 \( \equiv \ 1\) เหมือนกัน 2 ตัว[*]กรณีที่ 2.1 7 กับ 11 เหมือนกัน
ได้ \(\displaystyle{r \equiv 1 (\bmod \ \ 77)} \)
ได้ \(\displaystyle{r \equiv -1 (\bmod \ \ 13)} \)
แก้สมการคอนกรูเอนซ์ได้
\(\displaystyle{r \equiv 155 (\bmod \ \ 1001)} \)

ดูจากช่วงแล้ว กรณีนี้ไม่มีคำตอบ
[*]กรณีที่ 2.2 7 กับ 13 เหมือนกัน
ได้ \(\displaystyle{r \equiv 1 (\bmod \ \ 91)} \)
ได้ \(\displaystyle{r \equiv -1 (\bmod \ \ 11)} \)
แก้สมการคอนกรูเอนซ์ได้
\(\displaystyle{r \equiv 274 (\bmod \ \ 1001)} \)

ดูจากช่วงแล้ว กรณีนี้ไม่มีคำตอบ
[*]กรณีที่ 2.3 11 กับ 13 เหมือนกัน
ได้ \(\displaystyle{r \equiv 1 (\bmod \ \ 143)} \)
ได้ \(\displaystyle{r \equiv -1 (\bmod \ \ 7)} \)
แก้สมการคอนกรูเอนซ์ได้
\(\displaystyle{r \equiv 573 (\bmod \ \ 1001)} \)

ดูจากช่วงแล้ว กรณีนี้ได้คำตอบคือ r = 573
นั่นคือ \( \displaystyle{(r-1)(r+1)\ =\ (572)(574)\ =\ 328328} \)
สรุป a = 3 , b = 2 , c = 8

กรณีที่ 3 \( \equiv \ -1\) เหมือนกัน 2 ตัว[*]กรณีที่ 3.1 7 กับ 11 เหมือนกัน
ได้ \(\displaystyle{r \equiv -1 (\bmod \ \ 77)} \)
ได้ \(\displaystyle{r \equiv 1 (\bmod \ \ 13)} \)
แก้สมการคอนกรูเอนซ์ได้
\(\displaystyle{r \equiv 846 (\bmod \ \ 1001)} \)

ดูจากช่วงแล้ว กรณีนี้ได้คำตอบคือ r = 846
นั่นคือ \( \displaystyle{(r-1)(r+1)\ =\ (845)(847)\ =\ 715715} \)
สรุป a = 7 , b = 1 , c = 5
[*]กรณีที่ 3.2 7 กับ 13 เหมือนกัน
ได้ \(\displaystyle{r \equiv -1 (\bmod \ \ 91)} \)
ได้ \(\displaystyle{r \equiv 1 (\bmod \ \ 11)} \)
แก้สมการคอนกรูเอนซ์ได้
\(\displaystyle{r \equiv 727 (\bmod \ \ 1001)} \)

ดูจากช่วงแล้ว กรณีนี้ได้คำตอบคือ r = 727
นั่นคือ \( \displaystyle{(r-1)(r+1)\ =\ (726)(728)\ =\ 528528} \)
สรุป a = 5 , b = 2 , c = 8
[*]กรณีที่ 3.3 11 กับ 13 เหมือนกัน
ได้ \(\displaystyle{r \equiv -1 (\bmod \ \ 143)} \)
ได้ \(\displaystyle{r \equiv 1 (\bmod \ \ 7)} \)
แก้สมการคอนกรูเอนซ์ได้
\(\displaystyle{r \equiv 428 (\bmod \ \ 1001)} \)

ดูจากช่วงแล้ว กรณีนี้ได้คำตอบคือ r = 428
นั่นคือ \( \displaystyle{(r-1)(r+1)\ =\ (427)(429)\ =\ 183183} \)
สรุป a = 1 , b = 8 , c = 3


รวมทุกกรณี ได้ \( \displaystyle{(a,b,c)\ =\ (9,9,9)\ ,\ (3,2,8)\ ,\ (7,1,5)\ ,\ (5,2,8)\ ,\ (1,8,3)}\)

[nongtum]

สงสัยนิดนึงครับ สมมติว่าในกรณีทั่วไป คือ a,b,c ไม่ใช่เลขโดด จะยังสามารถทำแบบที่น้อง Tummykun ทำมาได้หรือไม่ ซึ่งคำตอบน่ะมีแน่ๆ เช่น a=b=c=99 แต่น่าจะแสดงวิธีคิดแบบด้านบนลำบาก โดยส่วนตัวเห็นเหมือนน้อง Tummykun ว่าคำตอบมันขึ้นอยู่กับตัวประกอบของ 10ⁿ+1 เมื่อ n เป็นจำนวนหลักของ abc₁₀ จากตรงนี้จึงมีคำถามต่อว่า
1. หาก n มีค่ามากๆ หรือ 10ⁿ+1 ไม่สามารถแยกตัวประกอบได้ง่ายๆหรือเป็นจำนวนเฉพาะ จะมี algorithm ใดที่จะใช้หา a,b,c ที่สอดคล้องเงื่อนไขได้
2. หากตัด +1 ด้านท้ายโจทย์ออก จะมีคำตอบหรือไม่ในกรณีทั่วไป

อ้อ อย่าลืมโจทย์ข้อถัดไป(ข้อ 22)นะครับ

[R-Tummykung de Lamar]

เอ...ตั้งโจทย์ยากๆไม่เป็นแฮะ
แวบไปเอาโจทย์การบ้านมาละกันนะครับ ( )

ข้อที่ 22
จงพิสูจน์ว่า \( \displaystyle{2^p \equiv \ \ 2\ (\bmod \ \ p)} \) ก็ต่อเมื่อ p เป็นจำนวนเฉพาะ

[warut]

ข้อความเดิมของคุณ R-Tummykung de Lamar:
เอ...ตั้งโจทย์ยากๆไม่เป็นแฮะ
แวบไปเอาโจทย์การบ้านมาละกันนะครับ ( )

ข้อที่ 22
จงพิสูจน์ว่า \( \displaystyle{2^p \equiv \ \ 2\ (\bmod \ \ p)} \) ก็ต่อเมื่อ p เป็นจำนวนเฉพาะ

เป็นที่ทราบกันดีครับว่าข้อความข้างต้นไม่เป็นจริง อย่างเช่นถ้าให้ \(p=341=11\times31\) ซึ่งเป็นจำนวนประกอบ แต่เราก็ยังได้ \(2^p\equiv2\pmod p\) ครับ

ป.ล. ดีมากครับที่ใส่เลขที่ข้อไว้ด้วย

[R-Tummykung de Lamar]

อืม ...ก็ขอบคุณพี่ warut มากครับ นึกว่าจะเป็นจริงทั้งสองทางซะอีก
ผมลองๆดูตั้งแต่ 1 - 100 แล้วยังไม่เจอ ก็เลยนึกว่าใช้ ก็ต่อเมื่อ ได้
(ไม่ทราบว่าพี่ warut มีวิธีหาตัวอย่างแย้ง ยังไงครับ ตั้ง 341 )

ขอแก้โจทย์เป็นดังนี้ครับ
ข้อที่ 22
ให้ p เป็นจำนวนเฉพาะ จงพิสูจน์ว่า $2^p \equiv 2 (\bmod \ \ p) $

[warut]

ไม่ได้หาหรอกครับ ผมจำได้

จำนวนประกอบที่ทำตัวแบบ 341 นี้เค้าเรียกว่า base 2 (Fermat) pseudoprime คำว่า "pseudo-" เป็น prefix แปลว่า เทียมหรือปลอมครับ

[warut]

ข้อความเดิมของคุณ tunococ:
ข้อแรก ผมก็คิดคล้าย ๆ หยั่งงี้แหละครับ

แต่ ทำไมมันถึงตอบข้อ 2 ได้ล่ะครับ?

ผมเช็คดูอย่างละเอียดอีกทีแล้วปรากฎว่าวิธีทำข้อ 2 ของผมใช้ไม่ได้ครับ ผมจึงได้ลบทิ้งไป

ข้อความเดิมของคุณ tunococ:
(ข้อ 2 ผมคิดที่ mod 3 น่ะครับ มันจะได้ลำดับ 1 2 1 2 1 2...)

เป็นวิธีที่ฉลาดมากครับ

คุณ tunococ อย่าลืมมาช่วยเฉลยข้อ 3 และบอกที่มาของโจทย์ด้วยนะครับ (ถ้าไม่ได้เป็นความลับของการอยู่รอดในยุทธจักร)

[warut]

ข้อความเดิมของคุณ gools:
หาจำนวนนับ \(a,b,c\) ทั้งหมดที่ \((abcabc)_{10}+1\) เป็นจำนวนกำลังสองสมบูรณ์

ยังติดใจข้อนี้อยู่ครับ คืออยากทราบว่าสัญลักษณ์ \((\dots)_{10}\) หมายความว่าอย่างไร แล้วเฉลยของน้อง gools สำหรับข้อนี้ทำยังไงครับ

ข้อความเดิมของคุณ R-Tummykung de Lamar:
จาก \( \displaystyle{\ 111\leq (abc)_{10} \leq 999\ } \)

น่าจะเป็น \(100\le(abc)_{10}\le999\) มากกว่านะครับ

ข้อความเดิมของคุณ R-Tummykung de Lamar:
จาก \(\displaystyle{(i)\ } \) และ \(\displaystyle{\ (ii)\ } \)จะได้ r เป็นจำนวนคู่ ที่ \( \displaystyle{\ 334\leq r \leq 10^3\ } \)

ผมว่า r ไม่จำเป็นต้องเป็นเลขคู่นา

[R-Tummykung de Lamar]

ใช่ครับ r ไม่จำเป็นต้องเป็นจำนวนคู่ (สะเพร่าไปหน่อย)

แต่ว่า ผมว่า
$111 \leq (abc)_{10} \leq 999$
ถูกแล้วนะครับ เพราะ a,b,c เป็นจำนวนนับ

[warut]

ข้อความเดิมของคุณ R-Tummykung de Lamar:
ข้อที่ 22
ให้ p เป็นจำนวนเฉพาะ จงพิสูจน์ว่า $2^p \equiv 2 (\bmod \ \ p) $

ผมขอลองทำข้อนี้เพื่อทดสอบเว็บบอร์ดบางเรื่องไปในตัวด้วยนะครับ

ให้สังเกตว่า ถ้า \(p\) เป็นจำนวนเฉพาะ และ \(k\) เป็นจำนวนเต็มที่ \(1\le k\le p-1\) แล้วเราจะพบว่า p หาร\[{p\choose k}
=\frac{p!}{k!(p-k)!}\]ลงตัว เพราะ \(k!(p-k)!\) ไม่มี \(p\) เป็นตัวประกอบอยู่เลย

ดังนั้นเราจึงได้ว่า\[2^p=(1+1)^p=1+\sum_{k=1}^{p-1}{p\choose k}+1
\equiv2\pmod p\]ตามต้องการครับ