![]() |
|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
![]() ![]() |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
![]() ที่โพสต์กระทู้นี้ ไม่ได้แปลว่า ผมเก่งกาจ หรือเป็นเซียน
แต่เป็นเพราะมักมีกระทู้ถามว่า mod คืออะไร อยู่บ่อยๆ และมักจะมีคำตอบว่า ให้ไปอ่านหนังสือเล่มนี้ เล่มโน้น อย่างหนังสือ สอวน ทฤษฎีจำนวน ไปอ่านแล้วก็หงายหลังออกมา ไม่รู้เรื่องเลยครับ จนวันหนึ่งไปอ่านที่อาจารย์ ดำรงค์ ทิพย์โยธาเขียนไว้ อ่านแล้วเข้าใจพื้นฐานของการหาเศษเหลือ จึงนำมาเรียบเรียงใหม่ แล้วมาโพสต์ ด้วยความหวังว่า ผู้ที่เคยได้ยินเรื่อง mod จะพอเข้าใจได้บ้างว่า mod คืออะไร แล้วหาได้อย่างไร
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#2
|
|||
|
|||
![]() นั่ง Time Machine ไปยุคประถม
ถ้าถามว่า 5 หารด้วย 2 เหลือเศษเท่าไร เด็กๆก็ตอบได้ว่า เหลือเศษ 1 ถามว่า 289 หารด้วย 13 เหลือเศษเท่าไร เด็กก็จะตั้งหารยาว ได้ผลลัพธ์เป็น 22 เหลือเศษ 3 เขียนในรูปเศษส่วน จะได้ $\frac{289}{13} = \frac{22(13) +3}{13} = \frac{22(13) }{13} + \frac{3}{13}$ จะเห็นว่า $\frac{22(13) }{13}$ ตัวเศษ มี 13 เป็นพหุคูณ หรือตัวร่วม ทำให้ หารด้วย 13 ลงตัว และมี $\frac{3}{13}$ เศษคือ $3$ แต่โจทย์ไม่ง่ายๆแบบข้างต้น มักเป็นการหารเลขยกกำลัง เช่น $2^{10}$ หารด้วย $5$ เหลือเศษ เท่าไร จงหาเศษเหลือจากการหาร $3^{100}$ ด้วย $7$ เศษเหลือจาการหาร $17^{1000}$ ด้วย $13$ เป็นเท่าไร แบบนี้ถ้าทำแบบตั้งหารยาว คงยุ่งยากและยาวมากๆ เราจะหาแนวทางในการหาเศษเหลือของตัวเลข $x^n$ ที่หารด้วย $p$ ค่อยๆทำความเข้าใจตัวอย่างต่อไปนี้นะครับ
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#3
|
|||
|
|||
![]() ตัวอย่างที่ 1
เศษเหลือที่ได้จากการหาร $2^{100}$ ด้วย 5 เท่ากับเท่าใด วิธีที่ 1 เพราะว่า $2^{100} = (2^4)^{25}= (16)^{25} =...6$ เพราะฉะนั้นหลักหน่วยของ $2^{100}$ เป็นเลข $6$ สรุป เศษเหลือที่ได้จากการหาร $2^{100}$ ด้วย $5$ มีค่าเท่ากับ $1$ วิธีที่ 2 $2^{100}= (2^2)^{50} = 4^{50}= (5-1)^{50}$ $=\binom{50}{0}5^{50} - \binom{50}{1}5^{49} + \binom{50}{2}5^{48} - \binom {50}{3}5^{47} + ... - \binom{50}{49}5^{1}+1 $ เพราะว่า $5$ หาร $\binom{50}{k}5^{50-k}$ ลงตัวทุกค่า $ k=0,1,...,49$ เพราะฉะนั้น $5$ หาร $2^{100}$ เหลือเศษ $1$ หมายเหตุ การแก้ปัญญาข้อนี้วิธีที่ $1$ เป็นวิธีที่เข้าใจได้ง่ายกว่าวิธีที่ $2$ แต่เมื่อ ต้องการหาในกรณีที่ตัวหารไม่ใช่เลข $5$ หรือ $10$ จะพบว่าวิธีที่ $2$ จะดีกว่า ถึงตรงนี้ ก็ไปหาความรู้เรื่องทฤษฎีทวินามมาอ่าน หรืออย่างน้อย จำรูปแบบนี้ไว้ก่อนก็ได้
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#4
|
|||
|
|||
![]() ตัวอย่าง 2.
เศษเหลือที่ได้จากการหาร $10^{ 10}$ ด้วย $7$ เท่ากับเท่าใด วิธีทำ $ \because \ \ 10^{10} = (7+3)^{10}$ $ \ \ \ \ \ \ \ \ \ = \binom{10}{0}7^{10}\cdot 3^0 + \binom{10}{1}7^{9}\cdot 3^1 + ...+ \binom{10}{9}7^{1}\cdot 3^9 + 3^{10}$ เพราะฉะนั้นเศษเหลือที่ได้จากการหาร $10^{10}$ ด้วย $7$ ต้องเท่ากับเศษเหลือจากการหาร $3^{10}$ ด้วย $7$ แต่เพราะว่า $3^{10} =(3^2)^5 = 9^5 = (7+2)^5$ $= \binom{5}{0}7^{5}\cdot 2^0 + \binom{5}{1}7^{4} \cdot 2^1 + ... + \binom{5}{4}7^{1} \cdot 2^4 + 2^5$ เพราะฉะนั้นเศษเหลือที่ได้จากการหาร $3^{10}$ ด้วย $7$ ต้องเท่ากับเศษเหลือที่ได้จากการหาร $2^5$ ด้วย $7$ เพราะว่า $2^5 = 32 $ หารด้วย $7$ เหลือเศษ $4$ สรุป $10^{10}$ หารด้วย $7$ เหลือเศษ $4$ ถึงตรงนี้พอได้แนวคิดบ้างหรือยังครับ ถ้าอย่างนั้น ก็มาดูตัวอย่างต่อไป
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#5
|
|||
|
|||
![]() ตัวอย่างที่ 3.
เศษเหลือที่ได้จากการหาร $10^{100} \ $ ด้วย $ \ 13$ เท่ากับเท่าใด วิธีทำ $10^{100} =(10^2)^{50} =(100)^{50} =[ 7(13)+9]^{50}$ เพราะว่าเศษเหลือจากการหาร $10^{100}$ ด้วย $13$ เท่ากับเศษเหลือที่ได้จากการหาร $9^{50}$ ด้วย $13$ $ \ \ \ 9^{50} = (9^2)^{25} =(81)^{25} =(6(13)+3)^{25}$ เพราะฉะนั้นเศษเหลือที่ได้จากการหาร $9^{50}$ ด้วย $13$ ต้องเท่ากับเศษเหลือที่ได้จากการหาร $3^{25} $ ด้วย $13$ $ \ \ \ \ 3^{25} = (3^5)^5 =(243)^5 =(18(13)+9)^5$ เศษเหลือจากการหาร $3^{25}$ ด้วย $13$ เท่ากับเศษเหลือจากการหาร $9^5$ ด้วย $13$ $ \ \ \ \ \ \ 9^5 = (3^2)^5 =(3^5)^2 =(243)^2 =(18(13)+9)^2$ เศษเหลือจากการหาร $9^5$ ด้วย $13$ เท่ากับเศษเหลือจากการหาร $9^2$ ด้วย $13$ เพราะว่า $9^2 = 81$ หารด้วย $13$ เหลือเศษ $3$ เพราะฉะนั้น $10^{100}$ หารด้วย $13$ เหลือเศษ $3$ เป็นไงครับ เริ่มมันแล้วหรือยัง ![]()
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#6
|
|||
|
|||
![]() มาดูตัวอย่างต่อไป ตอนนี้อาจต้องยาวหน่อย แต่พอถึงเรื่อง mod จะค่อยๆสั้น แล้วก็สั้นอีก
ใจเย็นๆ เอาให้คล่องก่อน แล้วพื้นฐานจะแน่น ![]() ตัวอย่างที่ 4. เศษเหลือที่ได้จากการหาร $2^{100}$ ด้วย $7$ เท่ากับเท่าใด วิธีทำ $2^{100} = (2^4)^{25} = (16)^{25} = (14+2)^{25}$ $ \ \ \ \ \ = \binom{25}{0}14^{25} \cdot 2^0 + \binom{25}{1}14^{24} \cdot 2^1 + ... + \binom {25}{24}14^{1} \cdot 2^{24} +2^{25}$ เพราะว่า $7$ หาร $ \binom{25}{0}14^{25} \cdot 2^0 + \binom{25}{1}14^{24} \cdot 2^1 + ... + \binom{25} {24}14^{1} \cdot 2^{24}$ ลงตัว เพราะฉะนั้นเศษเหลือที่ได้จากการหาร $2^{100}$ ด้วย $7$ ต้องเท่ากับเศษที่ได้จากการหาร $2^{25}$ ด้วย $7$ $2^{25} = (2^5)^5 = 32^5 = (28+4)^5$ $ \ \ \ \ = \binom{5}{0}28^{5} \cdot 4^{0} + \binom{5}{1}28^{4} \cdot 4^{1} + ... + \binom{5} {4}28^{1} \cdot 4^{4}+4^5$ เพราะว่า $7$ หาร $\binom{5}{0}28^{5} \cdot 4^{0} + \binom{5}{1}28^{4} \cdot 4^{1} + ... + \binom{5} {1}28^{1} \cdot 4^{4}$ ลงตัว เพราะฉะนั้นเศษเหลือจากการหาร $2^{25}$ ด้วย $7$ ต้องเท่ากับเศษเหลือที่ได้จากการหาร $4^5$ ด้วย $7$ $4^5 = (2^2)^5 = (2^5)^2 = (32)^2 = (28+4)^2 =28^2+2(28)(4)+4^2$ $ \ \ \ \ \ \ \ = 28^2+2(28)(4)+16$ $ \ \ \ \ \ \ \ = 28^2+2(28)(4)+14+2$ ดังนั้น $7$ หาร $4^5$ เหลือเศษ $2$ สรุป $7$ หาร $2^{100}$ เหลือเศษ $2$ เหตุผลสำคัญที่เราจะอ้างใช้ในโอกาสต่อไป คือ ถ้า $x^n= (kp+r)^n$ แล้วเศษเหลือที่ได้จากการหาร $x^n$ ด้วย $p$ เท่ากับเศษเหลือ จากการหาร $r^n$ ด้วย $p$ ข้อพิสูจน์ จากการกระจายทวินาม $(a+b)^n = \binom{n}{0}a^n+ \binom{n}{1}a^{n-1} b + \binom{n}{2}a^{n-2} b^2 + ... + \binom{n}{n} b^n$ ดั้งนั้น $(kp+r)^n = \binom{n}{0}(kp)^n+ \binom{n}{1}(kp)^{n-1}r + ...+ \binom{n}{n-1}(kp)r^{n-1} + \binom{n}{n}r^n$ แต่เพราะว่า $p$ หาร $\binom{n}{i}(kp)^{n-i}r^i$ ลงตัวทุกค่า $ i = 0,1,2,...,n-1$ เพราะฉะนั้น $p$ หาร $ \binom{n}{0}(kp)^n+ \binom{n}{1}(kp)^{n-1}r + ...+ \binom{n}{n-1}(kp)r^{n-1} $ ลงตัว ดังนั้นเศษเหลือจากการหาร $ \ (kp+r)^n$ ด้วย $p$ ต้องเท่ากับเศษเหลือจากการหาร $r^n$ ด้วย $p$ ต่อนี้ไป เราจะไม่เขียนยาวๆแบบนี้อีกแล้ว แต่จะอ้างเหตุผลข้างต้นแทน ดูตัวอย่างต่อไปเลยครับ
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() 09 กรกฎาคม 2010 07:56 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ banker |
#7
|
|||
|
|||
![]() ตัวอย่างที่ 5.
เศษเหลือจากการหาร $2^{1000}$ ด้วย $13$ เท่ากับเท่าใด วิธีทำ $2^{1000} = (2^5)^{200} = (32)^{200} = (26+6)^{200} = (2(13)+6)^{200}$ $6^{200} = (6^2){100} =(36){100} =(26+10)^{100} =(2(13)+10)^{100}$ $10^{100} = (10^2)^{50} =(100)^{50} =(7(13)+9)^{50}$ $9^{50} = 81^{25} = (6(13)+3)^{25}$ $3^{25} = (3^5)^5 = (243)^5 = (18(13)+9)^5$ $9^5 = 59049$ เพราะว่า $59049$ หารด้วย $3$ เหลือเศษ $3$ โดยการอ้างเหตุผลข้างต้น เศษเหลือจากการหาร $2^{1000}$ ด้วย $13$ = เศษเหลือจากการหาร $6^{200}$ ด้วย $13$ = เศษเหลือจากการหาร $10^{100}$ ด้วย $13$ = เศษเหลือจากการหาร $9^{50}$ ด้วย $13$ = เศษเหลือจากการหาร $3^{25}$ ด้วย $13$ = เศษเหลือจากการหาร $9^5$ ด้วย $13$ = เศษเหลือจากการหาร $59049$ ด้วย $13$ = $3$ หมายเหตุ การหาเศษเหลือแบบนี้จะทำได้เร็วหรือช้าขึ้นอยู่กับผู้ฝึก จะแบ่งตัวเลขออกเป็นผลบวกหรือการแบ่งกำลัง (ฝึกบ่อยๆ จะมองออกเอง) ซึ่งอาจทำได้หลายวิธีเช่น $2^{1000} = (2^8)^{125} =(256)^{125} =(19(13)+9)^{125}$ $9^{125} = 3^{250} =(3^5)^{50} =(243)^{50} =(18(13)+9)^{50}$ $9^{50} = (9^2)^{25} =81^{25} =(6(13)+3)^{25}$ $3^{25} = (243)^5 = (18(13)+9)^5$ $9^5 = 59049$ ดังนั้นจะได้เศษเหลือของ $2^{1000}$ หารด้วย $13$ เท่ากับ $3$ เหมือนกัน แล้วเมื่อไรจะเข้าเรื่อง mod เสียที ![]() ใจเย็นๆ ตัวอย่างข้างล่างนี้ เราก็จะเข้าเรื่อง mod เสียที ![]()
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#8
|
|||
|
|||
![]() ตัวอย่างที่ 6.
เศษเหลือจากการหาร $7^{2541}$ ด้วย $4$ เท่ากับเท่าใด วิธีทำ $ \ \ \ \ \ \ \ \ 7^{2541}= (4+3)^{2541}$ $ \ \ \ \ \ \ \ \ 3^{2541} = (3^3)^{847} =(27)^{847} =(6(4)+3)^{847}$ $ \ \ \ \ \ \ \ \ 3^{847} = (3^7)^{121} =(2187)^{121} =(546(4)+3)^{121}$ $ \ \ \ \ \ \ \ \ 3^{121} =(3^{11})^{11} = (177147)^{11} = (44286(4)+3)^{11}$ $ \ \ \ \ \ \ \ \ 3^{11} = 177147$ หารด้วย $4$ เหลือเศษ $3$ เศษจากการหาร $7^{2541}$ ด้วย $4$ = เศษจากการหาร $3^{2541}$ ด้วย $4$ = เศษจากการหาร $3^{847}$ ด้วย $4$ = เศษจากการหาร $3^{121}$ ด้วย $4$ = เศษจากการหาร $3^{11}$ ด้วย $4$ = $3$ ในหลักสูตรเกี่ยวกับระบบจำนวนมีการกำหนดสัญลักษณ์ $a \equiv b \pmod{m} $ หมายความว่า $a-b$ หารด้วย $m$ ลงตัว ตัวอย่างเช่น $10-1$ หารด้วย $3$ ลงตัว เพราะฉะนั้น $10 \equiv 1 \pmod{3} $ $17-5$ หารด้วย $12$ ลงตัว เพราะฉะนั้น $17 \equiv 5 \pmod{12} $ $100-50$ หารด้วย $10$ ลงตัว เพราะฉะนั้น $100 \equiv 50 \pmod{10} $ ในกรณีที่ $0\leqslant b < m$ และ $a \equiv b \pmod{m} $ จะได้ว่า $b$ เป็นเศษเหลือที่ได้จากการหาร $a$ ด้วย $m$ โดยการใช้สัญลักษณ์ $a \equiv b \pmod{m} $ จะได้ว่า $7^{2541} \pmod{4} \equiv 3^{2541} \pmod{4} \equiv 3^{847} \pmod{4} \equiv 3^{121} \pmod{4} \equiv 3^{11}\pmod{4} $ $ \equiv 177147\pmod{4} $ $ \equiv 3 \pmod{4} $ ต่อไปพิจารณาเศษเหลือที่ได้จากการหาร$(m+b)^n$ ด้วย $m$ โดยการกระจายทวินาม $(m+b)^n = \binom{n}{0}mn+\binom{n}{1}m^{n-1} b+...+ \binom{n}{n-1}mb^{n-1}+b^n$ ดังนั้น $(m+b)^n-b^n =\binom{n}{0}m^n+\binom{n}{1}m^{n-1} b+...+ \binom{n}{n-1}mb^{n-1}$ เพราะว่า $m$ หาร $\binom{n}{0}m^n+\binom{n}{1}m^{n-1} b+...+ \binom{n}{n-1}mb^{n-1}$ ลงตัว เพราะฉะนั้น $m$ หาร $(m+b)^n-b^n$ ลงตัว สรุป $(m+b)^n \equiv b^n \ (mod \ m) $
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#9
|
|||
|
|||
![]() ตัวอย่างที่ 7.
การหาเศษเหลือที่ได้จากการหาร $2^{1000}$ ด้วย $13$ เพราะว่า $ 2^{1000} =(2^4)^{250} =16^{250} =(13+3)^{250}$ เพราะฉะนั้น $2^{1000} \equiv (13+3)^{250} \pmod {13} \equiv 3^{250} \pmod {13}$ ในทำนองเดียวกันกับการพิสูจน์ว่า $(m+b)^n \equiv b^n \pmod{m} $ จะได้ว่า $(km+b)^n \equiv b^n \pmod{m} $ นั้นคือ ถ้า $m$ หาร $A$ ลงตัว แล้ว $(A+b)^n \equiv b^n \pmod{m} $ เพราะว่า $3^{250} = (3^5)^{50} = (243)^{50} =(18(13))+9)^{50}$ เพราะฉะนั้น $3^{250} \pmod {13} \equiv (18(13+9))^{50} \pmod {13}$ $\equiv 9^{50} \pmod {13} \ \ \ \ \ \ \ \ \ \equiv (9^2)^{25} \pmod {13} $ $\equiv 81^{25} \pmod {13} \ \ \ \ \ \ \ \ \ \equiv (6(13) +3)^{25} \pmod {13}$ $\equiv 3^{25} \pmod {13} \ \ \ \ \ \ \ \ \ \equiv (3^5) ^5 \pmod {13} $ $\equiv (18(13)+9)^5 \pmod {13} \ \ \ \ \ \ \ \ \ \equiv9^5 \pmod {13} $ $\equiv 3^{10} \pmod {13} \ \ \ \ \ \ \ \ \ \equiv(3^5) ^2 \pmod {13} $ $\equiv 9^2 \pmod {13} \ \ \ \ \ \ \ \ \ \equiv 81 \pmod {13} $ $\equiv 3 \pmod {13} $ สรุป $2^{1000} \equiv 3 \pmod {13} $ นั้นคือ $2^{1000}$ หารด้วย $13$ เหลือเศษ $3$ ต่อไปเราจะหาเหตุผลที่สำคัญซึ่งจะช่วยในการหาเศษเหลือที่ได้จากการหารได้ง่ายขึ้น ก่อนอื่นขอให้ดูจากตัวอย่างง่ายๆ ดังนี้ $14$ หารด้วย $3$ เหลือเศษ $2$ $11$ หารด้วย $3$ เหลือเศษ $2$ $(14)(11) = 154$ หารด้วย $3$ เหลือเศษ $1$ เศษที่เหลือจากการหารด้วย $3$ จากสองสมการข้างต้นคูณกัน $(2)(2) = 4$ หารด้วย $3$ อีกครั้ง จะเหลือเศษ $1$ สรุปด้วยการเขียนในรูปแบบสัญลักษณ์ $14 \equiv 2 \pmod {3} $ $11 \equiv 2 \pmod {3} $ $ (14)(11) =(2)(2) \pmod {3} \equiv 4 \pmod {3} \equiv 1 \pmod {3}$ ในกรณีทั่วไปเราสรุปเป็นทฤษฎีบทได้ดังนี้ ทฤษฎีบท 1 $a,b,c,d $ เป็นจำนวนเต็ม, $m$ เป็นจำนวนเต็มบวก ถ้า $a \equiv b \pmod {m }$ และ $c \equiv d \pmod {m }$ แล้ว $ac \equiv bd \pmod {m }$ $a - c \equiv ( b - d ) \pmod {m }$ $a + c \equiv ( b + d) \pmod {m }$ ข้อพิสูจน์ $a \equiv b \pmod {m }, \ \ c \equiv d \pmod {m }$ $a = mk + b, \ \ c = ml + d$ $ a - c = mk + b - ml - d$ $ = m(k - 1) + ( b - d )$ เพราะฉะนั้น $m$ หาร $a - c$ เหลือเศษ $ b -d$ นั้นคือ $a- c \equiv (b - d ) \pmod {m }$ ในทำนองเดียวกัน $a + c \equiv ( b + d ) \pmod {m }$ เพราะว่า $ac = ( mk + b) (ml + d )$ $= m^2 kl + mkd + mbl + bd$ $= m ( mkl + kd + bl ) + bd$ เพราะฉะนั้น $m$ หาร $ac$ เหลือเศษ $bd$ นั้นคือ $ac \equiv bd \pmod {m }$ หมายเหตุ ผลจากทฤษฎีบทจะได้ว่า ถ้า $a \equiv b \pmod {m } $ แล้ว $ \ a^n \equiv b^n \pmod {m }$ ทุกค่า $n$ ที่เป็นจำนวนเต็ม ผลจากทฤษฎีบท 1 นี้จะช่วยให้การหาเศษเหลือง่ายขึ้น เป็นอย่างไรบ้างครับ มึนไหม ถ้ายังมึนก็ย้อนกลับไปอ่านใหม่อีกรอบ, อีกรอบ, อีกรอบ ถ้าหายมึนแล้ว เรามาดูว่า จะใช้ mod ให้เกิดประโยชน์อย่างไร ![]()
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#10
|
|||
|
|||
![]() ตัวอย่างที่ 8.
การหาเศษเหลือของ $10^{10}$ หารด้วย ${7}$ วิธีทำ เพราะว่า $10$ หารด้วย $7$ เหลือเศษ $3$ เพราะฉะนั้น $10 \equiv 3 \pmod{7} $ ดังนั้น $10^{10} \equiv 3^{10} \pmod{7}$ เพราะว่า $3^{10} = 9^5$ และ $ \ 9 \equiv 2 \pmod{7}$ เพราะฉะนั้น $3^{10} \pmod{7} \equiv 9^5 \pmod{7}$ $ \equiv (7+2)^5 \pmod {7}$ $ \ \ \ \ \ \ \ \ \ \equiv 2^5 \pmod{7}$ $ \ \ \ \ \ \ \ \ \ \equiv 32 \pmod{7}$ $ \ \ \ \ \ \ \ \ \ \equiv 4 \pmod{7}$ สรุป $10^{10} \ $ หารด้วย $ \ 7$ เหลือเศษ $4$ เป็นยังไงบ้าง ง่ายไหมครับ
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#11
|
|||
|
|||
![]() ตัวอย่าง 9.
การหาเศษเหลือจากการหาร $10^{100} \ $ ด้วย $ \ 13$ วิธีทำ $10^{100} = (10^2) ^{50} = 100^{50}$ เพราะว่า $100 \ $ หารด้วย $ \ 13$ เหลือเศษ $ \ 9 \ $ เพราะฉะนั้น $ 100 \equiv 9 \pmod{13} $ ดังนั้น $100^{50} \equiv 9^{50} \pmod{13} $ $\equiv (9^2)^{25} \pmod{13} \ \ \ \ \ \ \equiv 81^{25} \pmod{13}$ $\equiv (6(13)+3)^{25} \pmod{13} \ \ \ \ \ \ \equiv 3^{25} \pmod{13}$ $ \equiv (3^5)^5 \pmod{13} \ \ \ \ \ \ \equiv (243)^5 \pmod{13}$ $ \equiv (18(13)+9)^5 \pmod{13} \ \ \ \ \ \ \equiv 9^5 \pmod{13}$ แต่ $ \ 9 \equiv 9 \pmod{13}$ $9^2 \equiv 9^2 \pmod{13} \equiv 81 \pmod{13} \equiv 3 \pmod{13}$ $ 9^4 \equiv 3^2 \pmod{13} \equiv 9 \pmod{13}$ $9^5 \equiv 9 (9) \pmod{13} \equiv 81 \pmod{13} \equiv 3 \pmod{13}$ สรุป $10^{100} \equiv 100^{50} \pmod{13} \equiv 9^{50} \pmod{13}$ $ \equiv 9^5 \pmod{13} \equiv 3 \pmod{13}$ นั้นคือ $10^{100}$ หารด้วย $13$ เหลือเศษ $3$ มันส์ไหมครับ ถ้ามันส์ ก็มามันส์ด้วยกันต่อในตัวอย่างต่อไป ![]()
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#12
|
|||
|
|||
![]() ยังมีวิธีง่ายกว่านี้ขึ้นไปอีก
เรามาศึกษาด้วยกันนะครับ ตัวอย่างที่ 10. เศษเหลือที่ได้จากการหาร $13^{100}$ ด้วย $17$ เท่ากับเท่าใด วิธีทำ เศษเหลือที่ได้จากการหาร $13^{100}$ ด้วย $17$ $ \equiv 13^{100} \pmod{17} \ \ \ \ \ \equiv ( 13^2)^{50} \pmod{17} $ $ \equiv (169)^{50} \pmod{17} \ \ \ \ \ \equiv (9(17)+16)^{50} \pmod{17} $ $ \equiv (16)^{50} \pmod{17} \ \ \ \ \ \equiv (2^4)^{50} \pmod{17} $ $ \equiv (2^5)^{40} \pmod{17} \ \ \ \ \ \equiv (32)^{40} \pmod{17} $ $ \equiv ( 17+15)^{40} \pmod{17} \ \ \ \ \ \equiv (15)^{40} \pmod{17} $ $ \equiv (15^2)^{20} \pmod{17} \ \ \ \ \ \equiv (225)^{20} \pmod{17} $ $ \equiv (4)^{20} \pmod{17} \ \ \ \ \ \equiv 2^{40} \pmod{17} $ $ \equiv (2^5)^{8} \pmod{17} \ \ \ \ \ \equiv 32^8 \pmod{17} $ $ \equiv (17+15)^{8} \pmod{17} \ \ \ \ \ \equiv 15^8 \pmod{17} $ $ \equiv (15^2)^{4} \pmod{17} \ \ \ \ \ \equiv (225^4) \pmod{17} $ $ \equiv4^{4} \pmod{17} \ \ \ \ \ \equiv 256 \pmod{17} $ $ \equiv 1 \pmod{17} $ สรุป $13^{100}$ หารด้วย $17$ เหลือเศษ $1$ ต่อไปเราจะหาขั้นตอนวิธีที่จะทำให้การคำนวณง่ายขึ้น ก่อนอื่นขอทบทวนแนวคิดของการหาหลักหน่วยของ $3^n$ เพราะว่า $3^1= 3$ $3^2 = 9$ $3^3 = 27$ $3^4 = 81$ . . . $ 3^{4k} = ...1$ หลักหน่วยเป็นเลข $1$ $3^{4k+1} = ...3 $ หลักหน่วยเป็นเลข $3$ $3^{4k+2} = ...9 $ หลักหน่วยเป็นเลข $9$ $3^{ 4k+3} =...7 $ หลักหน่วยเป็นเลข $7$ เพราะฉะนั้นหลักหน่วยของ $3^n$ จึงขึ้นอยู่กับเศษเหลือของ $n$ หารด้วย $4$ แนวทางการหาเศษเหลือจาก $a^n$ ด้วย $m$ 1. หาค่า $k$ น้อยสุดที่ทำให้ $a^k \equiv 1 \pmod{m}$ 2. หาเศษเหลือจากการหาร $n$ ด้วย $k$ สมมติเป็น $p$ 3. จะได้ว่า $a^n \equiv a^p \pmod{m}$ มาดูตัวอย่างต่อไปนะครับ
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() 09 กรกฎาคม 2010 08:23 : ข้อความนี้ถูกแก้ไขแล้ว 3 ครั้ง, ครั้งล่าสุดโดยคุณ banker เหตุผล: แก้คำผิด |
#13
|
|||
|
|||
![]() ตัวอย่าง 11.
การหาเศษเหลือจากการหาร $13^{100}$ ด้วย $17$ ขั้นตอนที่ 1 $13 \equiv 13 \pmod{17} $ $13^2 \equiv 169 \pmod{17} \ \ \ \ \equiv 16 \pmod{17}$ $13^3 \equiv 13(16) \pmod{17} \ \ \ \ \equiv 208 \pmod{17} \ \ \ \ \equiv 4 \pmod{17}$ $13^4 \equiv 13(4) \pmod{17} \ \ \ \ \equiv 52 \pmod{17} \ \ \ \ \equiv 1 \pmod{17}$ ได้ $k = 4$ ขั้นที่ $2 \ \ \ 100$ หารด้วย $4$ เหลือเศษ $0$ ขั้นที่ $3 \ \ \ 13^{100} \equiv 13^0 \pmod{17} \ \ \equiv 1 \pmod{17}$ สรุป $13^{100}$ หารด้วย $17$ เหลือเศษ $1$ ง่ายขึ้นไหมครับ ![]()
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#14
|
|||
|
|||
![]() ตัวอย่าง 12.
จงหาเศษเหลือที่ได้จากการหาร $10^{100}$ ด้วย $7$ วิธีทำ ขั้นที่ $1$ หาค่า $k$ น้อยสุดที่ทำให้ $ 10^k \equiv 1 \pmod{7} $ $ 10^1 \equiv 10 \pmod{7} \equiv 3 \pmod{7}$ $ 10^2 \equiv 30 \pmod{7} \equiv 2 \pmod{7}$ $ 10^3 \equiv 20 \pmod{7} \equiv 6 \pmod{7}$ $ 10^4 \equiv 60 \pmod{7} \equiv 4 \pmod{7}$ $ 10^5 \equiv 40 \pmod{7} \equiv 5 \pmod{7}$ $ 10^6 \equiv 50 \pmod{7} \equiv 1 \pmod{7}$ สรุป $k = 6$ ขั้นที่ $2 \ \ \ 100 = 16(6)+4 $ ขั้นที่ $3 \ \ \ 10^{100} \equiv 10^{16(6)+4} \pmod{7} \equiv 10^4 \pmod{7} \equiv 4 \pmod{7} $ สรุป $7$ หาร $10^{100}$ เหลือเศษ $4$
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
#15
|
|||
|
|||
![]() ท้ายสุดของปัญหาในข้อนี้จะขอนำทฤษฎีของระบบจำนวนมาแนะนำให้ใช้
เพื่อเกิดประโยชน์ในการคิดเลขให้เร็วขึ้น ดังนี้ ทฤษฎีบท 2 ถ้า $p$ เป็นจำนวนเฉพาะ และ $a$ เป็นจำนวนบวกที่ $p$ หาร $a$ ไม่ลงตัวแล้ว $ a^{p- 1} \equiv 1 \pmod{p} $ ตัวอย่าง 13. จงหาเศษเหลือจากการหาร $10^{100}$ ด้วย $17$ วิธีทำ เพราะว่า $10^{16} \equiv 1 \pmod{17 } $ และ $ \ \ 100 = 6(16) + 4 $ เพราะฉะนั้น $10^{16} \equiv 1 \pmod{17} $ $(10^{16})^6 \equiv 1^6 \pmod{17} $ $10^{6(16)} \equiv 1 \pmod{17} $ $10^{6(16)+4} \equiv 10^4 \pmod{17} $ เพราะว่า $10^2 \equiv 100 \pmod{17} \ \ \ \equiv 15 \pmod{17} $ $10^3 \equiv 150 \pmod{17} \ \ \ \equiv 14 \pmod{17} $ $10^4 \equiv 140 \pmod{17} \ \ \ \equiv 4 \pmod{17} $ เพราะฉะนั้น $10^{100}$ หารด้วย $17$ เหลือเศษ $4$ ตัวอย่าง 14. จงหาเศษเหลือจากการหาร $2^{100!}$ ด้วย ${19}$ วิธีทำ เพราะว่า $2^{18} \equiv 1 \pmod{19} \ $ และ $\frac{100!}{18} \ $ เป็นจำนวนเต็ม เพราะฉะนั้น $(2^{18})^{\frac{100!}{18}} \equiv 1 \pmod{19} $ $2^{100!} \equiv 1 \pmod{19} $ เพราะฉะนั้น $19$ หาร $2^{100!}$ เหลือเศษ $1$
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ![]() ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) ![]() |
![]() ![]() |
|
|