|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
||||
|
||||
congruence problems
1.จงหาคำตอบของระบบสมการ
$$a^2+bc\equiv a(mod 37)$$ $$b(a+d)\equiv b(mod 37)$$ $$c(a+d)\equiv c(mod 37)$$ $$bc+d^2\equiv d(mod 37)$$ $$ad-bc\equiv 1(mod 37)$$ 2.จงแสดงว่าสมการ $y^{37}\equiv x^3+11(mod p)$ ไม่สามารถแก้ได้สำหรับทุกจำนวนเฉพาะ $p\leq 100$ 3.ให้ $n$ เป็นจำนวนนับและ $p$ เป็นจำนวนเฉพาะซึ่ง $n>p$ จงพิสูจน์ว่า $$\binom{n}{p}\equiv \left\lceil\,\dfrac{n}{p}\right\rceil (mod p)$$ have fun!!!
__________________
AL-QAEDA(เอXข้างหน้า!!)!!!!!!!!!! ถึง บิน ลาเดนจะลาโลกไปแล้ว แต่เรายังมีผู้นำ jihad คนใหม่....อย่าง อับดุล อาบาเร่ คราลิดทากัน...เราจะใช้รถดูดส้XXเป็นคาร์บอม!!!จงพลีชีพเพื่อผู้นำของเรา!!!!!!! BOOM!!!!!!!!!!!!!!!!!!!!!
|
#2
|
||||
|
||||
เอ่อ รอดูพวกเทพๆๆๆๆเฉลยนะเนี่ย
|
#3
|
|||
|
|||
แน่ใจข้อ 2 นะคับ ไม่งั้น ผมให้ $p=2,a=1,b=2$ ก็พังเลยนะคับ
โจทย์มันน่าจะเป็น "สามารถแก้ได้สำหรับทุก..." หรือเปล่าคับ? คุณ tatari/nightmare ช่วยไขกระจ่างด้วยครับ 17 กันยายน 2008 18:06 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ nongtum เหตุผล: double post+แก้ไขข้อความเล็กน้อย โปรดใช้ปุ่มแก้ไข |
#4
|
|||
|
|||
สำหรับข้อ 3 ถ้าตรงที่เป็น ceiling function มันเป็น floor function ก็คิดว่ามีบทพิสูจน์ให้เจ้าค่ะ (รบกวนเจ้าของโจทย์ตรวจสอบความถูกต้องด้วยนะเจ้าคะ)
คิดว่ามีอยู่หลายวิธีเหมือนกัน แต่ในที่นี้จะขอเสนอวิธีการพิสุจน์โดยการอุปนัยเชิงคณิตศาสตร์บน $n$ เจ้าค่ะ ก่อนอื่น เห็นได้ชัดว่า $\binom{p}{p} \equiv \lfloor \frac{p}{p} \rfloor \pmod{p}$ และ $\binom{p+1}{p} \equiv \lfloor \frac{p+1}{p} \rfloor \pmod{p}$ เป็นจริง ต่อไป สมมติว่า $\binom{n}{p} \equiv \lfloor \frac{n}{p} \rfloor \pmod{p}$ เป็นจริง จะพิสูจน์ว่า $\binom{n+1}{p} \equiv \lfloor \frac{n+1}{p} \rfloor \pmod{p}$ เป็นจริงด้วย ก่อนอื่น ถ้า $p$ หาร $n+1$ ไม่ลงตัว จะได้ว่า $(n+1,n-p+1)=(n+1,p)=1$ แต่ $(n+1)\frac{1}{n-p+1}\binom{n}{p}=\binom{n+1}{p}\in \mathbb{Z}$ จึงสรุปได้ว่า $\frac{1}{n-p+1}\binom{n}{p}\in \mathbb{Z}$ ด้วย ดังนั้น $$\binom{n+1}{p}=\frac{n+1}{n-p+1}\binom{n}{p}\equiv (n+1)(n-p+1)^{-1}\binom{n}{p} \pmod{p}$$ แต่ $n+1 \equiv n-p+1 \pmod{p}$ ดังนั้น $$\binom{n+1}{p} \equiv \binom{n}{p} \pmod{p}$$ ในอีกทางหนึ่ง เพราะว่า $p$ หาร $n+1$ ไม่ลงตัว จึงได้ว่า $\lfloor \frac{n+1}{p} \rfloor = \lfloor \frac{n}{p} \rfloor$ เมื่อรวมกับขอสมมติฐานการอุปนัยที่ว่า $\binom{n}{p} \equiv \lfloor \frac{n}{p} \rfloor \pmod{p}$ จึงได้ว่า $\binom{n+1}{p} \equiv \lfloor \frac{n+1}{p} \rfloor \pmod{p}$ ตามต้องการ ในอีกกรณี ถ้า $p$ หาร $n+1$ ลงตัวแล้ว เราให้ $n+1=kp$ สำหรับบาง $k\in \mathbb{N}$ ดังนั้น $$\binom{n+1}{p}=\frac{(n+1)n(n-1)\ldots(n-p+2)}{p!}=k\frac{(kp-1)\ldots(kp-p+2)}{(p-1)!}$$ แต่ $\frac{(kp-1)\ldots(kp-p+2)}{(p-1)!}=\binom{kp-1}{p-1}\in \mathbb{Z}$ ดังนั้น \[\begin{array}{rcl} \frac{(kp-1)\ldots(kp-p+2)}{(p-1)!} & \equiv & (kp-1)\ldots(kp-p+2)((p-1)!)^{-1} \pmod{p}\\ & \equiv & (-1)\ldots(-p+2)((p-1)!)^{-1} \pmod{p}\\ & \equiv & (-1)^{p-2}(p-2)!((p-1)!)^{-1} \pmod{p}\\ & \equiv & (-1)^{p-2}(p-1)^{-1} \pmod{p}\\ & \equiv & (-1)^{p-2}(-1) \pmod{p}\\ & \equiv & (-1)^{p-1} \pmod{p} \end{array}\] กรณีที่ $p>2$ จะได้ว่า $(-1)^{p-1} = 1$ ส่วนในกรณี $p=2$ นั้น $1 \equiv -1 \pmod{2}$ อยู่แล้ว ดังนั้นสำหรับทุกๆ จำนวนเฉพาะ $p$ $$\frac{(kp-1)\ldots(kp-p+2)}{(p-1)!} \equiv 1 \pmod{p}$$ จึงได้ว่า $$\binom{n+1}{p} \equiv k = \frac{n+1}{p} = \lfloor \frac{n+1}{p} \rfloor \pmod {p}$$ ดังนั้น ด้วยหลักการอุปนัยเชิงคณิตศาสตร์จึงพิสูจน์ตามต้องการ... เจ้าค่ะ
__________________
Behind every beautiful proof lies a mountain of trash-turned calculation notes. ไปเยี่ยมกันได้ที่ต่างๆ ต่อไปนี้นะเจ้าคะ blog ดนตรีโดจิน: http://aiko-no-heya.exteen.com "กลุ่มศึกษาดนตรีโดจิน": http://www.facebook.com/doujinmusiclife "เส้นทางสู่โตได (วิชาเลข)": http://www.facebook.com/roadtotodai 18 กันยายน 2008 11:06 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ Ai-Ko เหตุผล: เพิ่มเติมรายละเอียด |
#5
|
|||
|
|||
แล้วก็สำหรับข้อ 1 เจ้าค่ะ...
ก่อนอื่น สังเกตว่า 37 เป็นจำนวนเฉพาะเจ้าค่ะ เราเริ่มจากการแยกกรณีว่า $b$ หารด้วย 37 ลงตัวหรือไม่ กรณีที่ $b$ หารด้วย 37 ลงตัว จากสมภาคแรกจะได้ว่า $$a \equiv a^2+bc \equiv a^2 \pmod{37}$$ จะได้ว่า $37|a$ หรือ $a \equiv 1 \pmod{37}$ แต่ถ้า $37|a$ จะทำให้สมภาคที่ห้ากลายเป็น $$0 \equiv ad-bc \equiv 1 \pmod{37}$$ เกิดข้อขัดแย้ง ดังนั้น $a \equiv 1 \pmod{37}$ แล้วจากสมภาคที่ห้าจะได้ว่า $d \equiv 1 \pmod{37}$ ด้วย สุดท้ายแทนเข้าไปในสมภาคที่สาม จะได้ว่า $2c \equiv c \pmod{37}$ นั่นคือ $c \equiv 0 \pmod{37}$ ดังนั้นในกรณีนี้ \[\begin{array}{rcl} a & \equiv & 1 \pmod{37}\\ b & \equiv & 0 \pmod{37}\\ c & \equiv & 0 \pmod{37}\\ d & \equiv & 1 \pmod{37}\\ \end{array}\] กรณีที่ $b$ หารด้วย 37 ไม่ลงตัว จากสมภาคที่สองจะได้ว่า $a+d \equiv 0 \pmod{37}$ ตรงนี้หากเราพิจารณาผลบวกของสมภาคที่หนึ่งและสี่ จะได้ว่า $$a^2+2bc+d^2 \equiv a+d \equiv 0 \pmod{37}$$ แต่ในอีกแง่หนึ่ง $a+d \equiv 0 \pmod{37} \rightarrow a \equiv -d \pmod{37}$ ดังนั้น $a^2 \equiv d^2 \pmod{37}$ จึงได้ว่า $$2a^2 +2bc \equiv 0 \pmod{37} \rightarrow a^2+bc \equiv 0 \pmod{37}$$ นำไปเทียบกับสมภาคที่หนึ่งอีกครั้ง จะได้ว่า $a \equiv 0 \pmod{37}$ ในทำนองเดียวกันก็แสดงได้ว่า $d \equiv 0 \pmod{37}$ แล้วแทนค่าเหล่านี้ลงในสมภาคที่สอง จะได้ว่า $$b \equiv b(a+d) \equiv 0 \pmod{37}$$ จึงขัดแย้งกับที่สมมติได้ว่า $b$ หารด้วย 37 ไม่ลงตัว ดังนั้นคำตอบของระบบสมภาคนี้จึงมีเพียง \[\begin{array}{rcl} a & \equiv & 1 \pmod{37}\\ b & \equiv & 0 \pmod{37}\\ c & \equiv & 0 \pmod{37}\\ d & \equiv & 1 \pmod{37}\\ \end{array}\] เท่านั้น... เจ้าค่ะ
__________________
Behind every beautiful proof lies a mountain of trash-turned calculation notes. ไปเยี่ยมกันได้ที่ต่างๆ ต่อไปนี้นะเจ้าคะ blog ดนตรีโดจิน: http://aiko-no-heya.exteen.com "กลุ่มศึกษาดนตรีโดจิน": http://www.facebook.com/doujinmusiclife "เส้นทางสู่โตได (วิชาเลข)": http://www.facebook.com/roadtotodai |
#6
|
||||
|
||||
เห็นด้วยครับว่าข้อ 3 ต้องเป็น floor function
|
หัวข้อคล้ายคลึงกัน | ||||
หัวข้อ | ผู้ตั้งหัวข้อ | ห้อง | คำตอบ | ข้อความล่าสุด |
รบกวนถามผู้รู้เกี่ยวกับ congruence และจำนวนเฉพาะ | หยินหยาง | ทฤษฎีจำนวน | 4 | 27 มกราคม 2008 09:01 |
congruence | หยินหยาง | ทฤษฎีจำนวน | 4 | 11 ธันวาคม 2007 23:48 |
congruence | alexandre | ทฤษฎีจำนวน | 8 | 30 สิงหาคม 2007 20:16 |
ถามโจทย์congruence | CmKaN | ปัญหาคณิตศาสตร์ ม.ปลาย | 3 | 07 มกราคม 2007 15:42 |
อยากทราบวิธีคิดแบบ congruence ของโจทย์ข้อนี้ | Pramote | ปัญหาคณิตศาสตร์ ประถมปลาย | 4 | 06 พฤษภาคม 2006 17:44 |
|
|