เพิ่มเติมอีกหน่อยนะครับ
ตรงส่วนที่ใช้ pigeon-hole principle เป็นเทคนิคของ Dirichlet ซึ่งในหนังสือ An Introduction to the Theory of Numbers ของ Hardy & Wright ก็ใช้ครับ ส่วนที่ว่าเกี่ยวกับ Dynamical Systems อย่างไร ผมว่าน่าจะอยู่ตรงที่มีการใช้ iterative process มั้งครับ แม้ว่าผมค่อนข้างมั่นใจว่าการพิสูจน์ใน paper อันนั้นคือแบบเดียวกับที่คุณ nooonuii เรียน อย่างไรก็ตามถ้าจะให้ชัวร์คงต้องให้คุณ nooonuii มา confirm อีกทีครับ |
จริงๆแล้ว 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 ครับ :) |
อ้างอิง:
|
ข้อต่อไปนะครับ
หาจำนวนนับ \(a,b,c\) ทั้งหมดที่ \((abcabc)_{10}+1\) เป็นจำนวนกำลังสองสมบูรณ์ |
ยังทำไม่ได้เลยครับ โพสต์เท่าที่คิดได้ก่อนละกันนะครับ
จาก \(\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\ } \) เอ..เดี๋ยวพรุ่งนี้มาลองทำต่อนะครับ ..ง่วงละ :D |
อ้างอิง:
ทำต่อที่ \(\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)}\) :D |
สงสัยนิดนึงครับ สมมติว่าในกรณีทั่วไป คือ a,b,c ไม่ใช่เลขโดด จะยังสามารถทำแบบที่น้อง Tummykun ทำมาได้หรือไม่ ซึ่งคำตอบน่ะมีแน่ๆ เช่น a=b=c=99 แต่น่าจะแสดงวิธีคิดแบบด้านบนลำบาก โดยส่วนตัวเห็นเหมือนน้อง Tummykun ว่าคำตอบมันขึ้นอยู่กับตัวประกอบของ 10n+1 เมื่อ n เป็นจำนวนหลักของ abc10 จากตรงนี้จึงมีคำถามต่อว่า
1. หาก n มีค่ามากๆ หรือ 10n+1 ไม่สามารถแยกตัวประกอบได้ง่ายๆหรือเป็นจำนวนเฉพาะ จะมี algorithm ใดที่จะใช้หา a,b,c ที่สอดคล้องเงื่อนไขได้ 2. หากตัด +1 ด้านท้ายโจทย์ออก จะมีคำตอบหรือไม่ในกรณีทั่วไป อ้อ อย่าลืมโจทย์ข้อถัดไป(ข้อ 22)นะครับ ;) |
เอ...ตั้งโจทย์ยากๆไม่เป็นแฮะ
แวบไปเอาโจทย์การบ้านมาละกันนะครับ ( :D ) ข้อที่ 22 จงพิสูจน์ว่า \( \displaystyle{2^p \equiv \ \ 2\ (\bmod \ \ p)} \) ก็ต่อเมื่อ p เป็นจำนวนเฉพาะ |
อ้างอิง:
ป.ล. ดีมากครับที่ใส่เลขที่ข้อไว้ด้วย |
อืม ...ก็ขอบคุณพี่ warut มากครับ นึกว่าจะเป็นจริงทั้งสองทางซะอีก
ผมลองๆดูตั้งแต่ 1 - 100 แล้วยังไม่เจอ ก็เลยนึกว่าใช้ ก็ต่อเมื่อ ได้ (ไม่ทราบว่าพี่ warut มีวิธีหาตัวอย่างแย้ง ยังไงครับ ตั้ง 341 ) ขอแก้โจทย์เป็นดังนี้ครับ ข้อที่ 22 ให้ p เป็นจำนวนเฉพาะ จงพิสูจน์ว่า $2^p \equiv 2 (\bmod \ \ p) $ |
ไม่ได้หาหรอกครับ ผมจำได้ :cool:
จำนวนประกอบที่ทำตัวแบบ 341 นี้เค้าเรียกว่า base 2 (Fermat) pseudoprime คำว่า "pseudo-" เป็น prefix แปลว่า เทียมหรือปลอมครับ |
อ้างอิง:
อ้างอิง:
คุณ tunococ อย่าลืมมาช่วยเฉลยข้อ 3 และบอกที่มาของโจทย์ด้วยนะครับ (ถ้าไม่ได้เป็นความลับของการอยู่รอดในยุทธจักร) |
อ้างอิง:
อ้างอิง:
อ้างอิง:
|
ใช่ครับ r ไม่จำเป็นต้องเป็นจำนวนคู่ (สะเพร่าไปหน่อย)
แต่ว่า ผมว่า $111 \leq (abc)_{10} \leq 999$ ถูกแล้วนะครับ เพราะ a,b,c เป็นจำนวนนับ :D |
อ้างอิง:
ให้สังเกตว่า ถ้า \(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\]ตามต้องการครับ :) |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 19:46 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha