ความรู้เบื้องต้นเรื่อง mod
 

ที่โพสต์กระทู้นี้ ไม่ได้แปลว่า ผมเก่งกาจ หรือเป็นเซียน

แต่เป็นเพราะมักมีกระทู้ถามว่า mod คืออะไร อยู่บ่อยๆ

และมักจะมีคำตอบว่า ให้ไปอ่านหนังสือเล่มนี้ เล่มโน้น

อย่างหนังสือ สอวน ทฤษฎีจำนวน

ไปอ่านแล้วก็หงายหลังออกมา ไม่รู้เรื่องเลยครับ

จนวันหนึ่งไปอ่านที่อาจารย์ ดำรงค์ ทิพย์โยธาเขียนไว้

อ่านแล้วเข้าใจพื้นฐานของการหาเศษเหลือ

จึงนำมาเรียบเรียงใหม่ แล้วมาโพสต์

ด้วยความหวังว่า ผู้ที่เคยได้ยินเรื่อง mod จะพอเข้าใจได้บ้างว่า mod คืออะไร แล้วหาได้อย่างไร

นั่ง 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$

ค่อยๆทำความเข้าใจตัวอย่างต่อไปนี้นะครับ

ตัวอย่างที่ 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$ จะดีกว่า

ถึงตรงนี้ ก็ไปหาความรู้เรื่องทฤษฎีทวินามมาอ่าน หรืออย่างน้อย จำรูปแบบนี้ไว้ก่อนก็ได้

ตัวอย่าง 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$

ถึงตรงนี้พอได้แนวคิดบ้างหรือยังครับ

ถ้าอย่างนั้น ก็มาดูตัวอย่างต่อไป

ตัวอย่างที่ 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$


เป็นไงครับ เริ่มมันแล้วหรือยัง :haha:

มาดูตัวอย่างต่อไป ตอนนี้อาจต้องยาวหน่อย แต่พอถึงเรื่อง mod จะค่อยๆสั้น แล้วก็สั้นอีก

ใจเย็นๆ เอาให้คล่องก่อน แล้วพื้นฐานจะแน่น :D

ตัวอย่างที่ 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$

ต่อนี้ไป เราจะไม่เขียนยาวๆแบบนี้อีกแล้ว

แต่จะอ้างเหตุผลข้างต้นแทน

ดูตัวอย่างต่อไปเลยครับ

ตัวอย่างที่ 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 เสียที :haha:

ใจเย็นๆ ตัวอย่างข้างล่างนี้ เราก็จะเข้าเรื่อง mod เสียที :haha:

ตัวอย่างที่ 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) $

ตัวอย่างที่ 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 ให้เกิดประโยชน์อย่างไร :D

ตัวอย่างที่ 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$


เป็นยังไงบ้าง ง่ายไหมครับ

ตัวอย่าง 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$


มันส์ไหมครับ ถ้ามันส์ ก็มามันส์ด้วยกันต่อในตัวอย่างต่อไป :haha:

ยังมีวิธีง่ายกว่านี้ขึ้นไปอีก

เรามาศึกษาด้วยกันนะครับ

ตัวอย่างที่ 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}$




มาดูตัวอย่างต่อไปนะครับ

ตัวอย่าง 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$



ง่ายขึ้นไหมครับ :haha:

ตัวอย่าง 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$

ท้ายสุดของปัญหาในข้อนี้จะขอนำทฤษฎีของระบบจำนวนมาแนะนำให้ใช้
เพื่อเกิดประโยชน์ในการคิดเลขให้เร็วขึ้น ดังนี้

ทฤษฎีบท 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$

อ่านถึงตรงนี้ ผมเชื่อว่า พอจะเข้าใจพื้นฐานเรื่อง mod ได้แล้ว

ถ้าน้องๆหลานๆสนใจ ก็ต้องหาแบบฝึกหัดมาทำให้เกิดความช่ำชอง

ผมเชื่อว่า ด้วยพื้นฐานที่ได้อ่านมานี้ ก็สามารถไปอ่านเรื่อง mod ในหนังสือต่างๆด้วยความเข้าใจได้

ไม่มีวิธีลัดที่จะให้เก่งเรื่อง mod มากไปกว่าการทำแบบฝึกหัดมากๆ

ส่วนผม ผมคงจบตรงนี้ เพราะวัตถุประสงค์ของผม แค่เพื่อติวหลานที่อยู่ประถมเท่านั้น

โปรดอย่าถามอะไรที่ยากๆ หรือที่เกินประถมหรือมัธยมต้น

เพราะผมก็รู้แค่นี้แหละ

รู้แล้วเอามาเผยแพร่ให้เด็กๆของเรา เป็นเด็กเก่ง

เพราะเด็กๆในวันนี้ จะเป็นอนาคตของชาติต่อไป

เสริมสุดท้าย

ถ้าเซียน หรือท่านผู้รู้เรื่อง mod เห็นว่า มีผิดพลาดตรงไหน

หรืออยากเพิ่มเติมตรงไหน ก็ช่วยแนะนำด้วยครับ

สุดท้ายจริงๆ ขอบคุณอาจารย์ ดำรงค์ ทิพย์โยธา ที่เสียสละเวลาเขียนหนังสือดีๆให้พวกเราได้เรียนรู้

:great:ขอบคุณ คุณลุง banker จริงๆครับ สมควรปักหมุดๆ

ฝากไว้
จงแสดงว่า $2^{340} \equiv 1 (mod 341)$

hint
$2^{10} = (1024) = (1023+1) = (3(341) +1)$

ขอบคุณ คุณbankerมากครับ สมควรปักหมุดมากๆ
ขอถามหน่อยนะครับว่า ทวินาม เป็นเรื่องที่หาได้จากระดับการศึกษาชั้นไหนครับ

อยากเพิ่มเติมข้างหน้า mod เพื่อให้เกิดความกระชุ่มกระช่วยของ ท่านสว. banker โดยเติมคำว่า four เป็น four mod ครับ เพราะนอกจากจะปักหมุดแล้วอาจปักอกแถมอีกอย่างได้ครับ :D:D:laugh:

ต้องขอขอบคุณคุณอา banker มากๆเลยครับ
ผมกำลังสนใจเรื่อง mod อยู่พอดี แต่หาอ่านยากมาก
ได้แบบนี้แล้วหาโจทย์ใน MC ทำให้มันส์ไปเลยล่ะกัน
ขอบคุณคุณอาอีกครั้งครับที่เสียสละเวลามาแบ่งปันความรู้:please:

ย่อยของยากให้ทานได้ง่ายและคล่องคอมากขึ้น
ขอบคุณครับคุณอาBanker

อธิบายได้เห็นภาพเลยลุง เข้าใจง่ายดี ขอบคุณมากๆครับ เก็บเข้าคลังไว้ก่อน

ลองทำข้อพวกนี้แบบไม่ใช้ mod ดู ^^
จงหาเศษ
1.$(4)(4!)^2000$ หารด้วย 7
2.$(5)(5!)^2000$ หารด้วย 7
3.$(6)(6!)^2000$ หารด้วย 7

1.$(4!)^{2000}=24^{2000}=(7(3)+3)^{2000}$ เหลือเศษเท่ากับ $3^{2000}$
คิดตามแบบปกติ จะได้ว่า$(3^5)^{400}=(7(34)+5)^{400}$
$5^{400}=(7(89)+2)^{100}$
$2^{100}\times 4 =2^{102}=(7+1)^{34}$.....ตอบว่าเหลือเศษ 1
$24\equiv 24 (mod 7) \equiv3 (mod 7) $
$24^2 \equiv 72(mod 7) \equiv 2(mod 7)$
$24^3 \equiv 48(mod 7) \equiv 6(mod 7)$
$24^4 \equiv 144(mod 7) \equiv 4(mod 7)$
$24^5 \equiv 96(mod 7) \equiv 5(mod 7)$
$24^6 \equiv 120(mod 7) \equiv 1(mod 7)$
$24^6 \equiv 1(mod 7)$
ดังนั้น $k=6$
$2000=6(333)+2$
$24^{6(333)+2} \equiv 24^2(mod 7) \equiv 2(mod 7)$
$4\times 24^{2000} \equiv 4\times 2(mod 7) \equiv 8(mod 7) \equiv 1(mod 7)$
ได้คำตอบเท่ากันคือ เศษ 1

ข้อ 2 แบบนี้ถูกรึป่าวอ่ะครับ
$5!=120$
${(120)}^{2000}={(7(17)+1)}^{2000}$
${(5!)}^{2000}≡1(mod 7)$
$5{(5!)}^{2000}≡5(mod 7)$
ตอบเหลือเศษ 5
(พิมเครื่องหมาย ≡ ยังไงอ่ะครับ)

2.$5(5!)^{2000}$ $(120)^{2000}$
แยกเป็น $8^{2000}\times 3^{2000} \times 5^{2000}$
$8^2 \equiv 64 (mod 7) \equiv 1(mod7)$
$2000 =2(1000)+0$
$8^{2000} \equiv 8^0(mod 7) \equiv 1(mod7)$...เศษ 1

$3^2 \equiv 9 (mod 7) \equiv 2(mod7)$
$3^3 \equiv 6 (mod 7) $
$3^4 \equiv 18 (mod 7) \equiv 4(mod7)$
$3^5 \equiv 12 (mod 7) \equiv 5(mod7)$
$3^6 \equiv 15 (mod 7) \equiv 1(mod7)$
$3^6 \equiv 1(mod7)$
$2000=6(333)+2$
$3^{2000} \equiv 9 (mod 7) \equiv 2(mod7)$......เศษ 2

$5^2 \equiv 25 (mod 7) \equiv 4(mod7)$
$5^3 \equiv 20 (mod 7) \equiv 6(mod7)$
$5^4 \equiv 30 (mod 7) \equiv 2(mod7)$
$5^5 \equiv 10 (mod 7) \equiv 3(mod7)$
$5^6 \equiv 15 (mod 7) \equiv 1(mod7)$
$2000=6(333)+2$
$5^{2000} \equiv 25 (mod 7) \equiv 4(mod7)$......เศษ 4

$8^{2000} \equiv 1(mod7)$ $3^{2000} \equiv 2(mod7)$
$8^{2000} \times 3^{2000} \equiv 1\times 2(mod7) \equiv 2(mod7)$
$8^{2000} \times 3^{2000} \equiv 2(mod7)$ กับ $5^{2000} \equiv 4(mod7)$
$8^{2000} \times 3^{2000} \times 5^{2000}\equiv 2\times 4(mod7) \equiv 1(mod7)$
$(120)^{2000}\equiv 1(mod7)$
$5\times (120)^{2000}\equiv 5\times 1(mod7) \equiv 5(mod7)$
ตอบเศษ 5

ให้ง่ายอีกหน่อยเมื่อกี้รู้แล้วว่า$(4!)^{2000} \equiv 2(mod7)$
$5^{2000} \equiv 4(mod7)$
$(4!)^{2000}\times5^{2000} \equiv 2\times 4(mod7) \equiv 1(mod7)$
$(5!)^{2000} \times 5 \equiv 5(mod7)$

แหมตอนแรกผมนึกว่าจะหมายถึงmode (ฐานนิยม)เสียแล้วครับ

3.$6(6!)^{2000}$
$(5!)^{2000} \equiv 1 (mod7)$
$6^2 \equiv 36(mod7) \equiv 1(mod7)$
$6^{2000}\equiv 36(mod7) \equiv 1(mod7)$
$(6!)^{2000} \equiv 1(mod7)$
$6(6!)^{2000}\equiv 6(mod7)$
เศษ 6

ลองทำตามวิธีคุณอาbankerสอนให้ทำ ย่นเวลาเยอะเลยครับ....

ไม่เข้าใจว่าคุณกิตติทำไมถึงต้องทำยาวขนาดนั้นอ่ะครับ
ข้อ 2 ตามที่ผมเข้าใจคือ 7 หาร ${(120)}^{2000}$ จะเหลือเศษเท่ากับ 7 หาร ${(7(17)+1)}^{2000}$
ดังนั้นก็จะเท่ากับเศษที่ได้จากการหารด้วย $1^{2000}$ ซึ่งก็คือ 1 แสดงว่า ${(5!)}^{2000}≡1(mod7)$ ไม่ใช่เหรอครับ
วิธีผมมีอะไรผิดรึป่าวครับ
(เอ่อ.. เครื่องหมาย≡พิมไงอ่ะครับ ขี้เกียจก๊อปง่ะ)

ก็ลองทำตามทฤษฎีบทที่มีให้ดูครับ จริงๆจะแยกเป็น$12\times 10$ก็ได้ แล้วแต่ถนัดครับ จะใช้เป็น$24\times 5$ก็แล้วแต่ถนัด
$12^2 \equiv 144 (mod 7) \equiv 4(mod 7)$
$12^3 \equiv 48 (mod 7) \equiv 6(mod 7)$
$12^4 \equiv 72 (mod 7) \equiv 2(mod 7)$
$12^5 \equiv 24 (mod 7) \equiv 3(mod 7)$
$12^6 \equiv 36 (mod 7) \equiv 1(mod 7)$
$12^{2000} \equiv 12^2 (mod 7) \equiv 4(mod 7)$

$10^2 \equiv 100 (mod 7) \equiv 2(mod 7)$
$10^3 \equiv 20 (mod 7) \equiv 6(mod 7)$
$10^4 \equiv 60 (mod 7) \equiv 4(mod 7)$
$10^5 \equiv 40 (mod 7) \equiv 5(mod 7)$
$10^6 \equiv 50 (mod 7) \equiv 1(mod 7)$
$2000=6(333)+2$
$10^{2000} \equiv 10^2 (mod 7) \equiv 2(mod 7)$
$12^{2000} \times 10^{2000}\equiv 4\times 2(mod 7) \equiv 1(mod 7)$
$5(5!)^{2000}\equiv 5(mod 7)$
ก็ได้คำตอบเท่ากันนี่ครับ

สัญลักษณ์$\equiv $ อยู่ในกลุ่มเดียวกับ$\leqslant \not= \approx $

ขอบคุณครับ วิธีที่ผมทำไม่ผิดใช่มั้ยครับ
ถ้าจำผิดๆไปล่ะแย่เลย

คุณ banker เอามาจากเล่มไหนของ อ.ดำรงค์ ทิพย์โยธา ครับ
คณิตศาสตร์ปรนัยรึเปล่า แนะนำผมหน่อยนะคร้าบบบบบบบบบบ

คณิตศาสตร์ปรนัยเล่ม 19 ครับ

Attachment 3297

ดูเหมือนเล่มนี้จะยกเป็นรางวัล math contest ไปแล้วครับ

รอ modertor ประกาศว่าใครจะเป็นผู้ได้รับ :D

*0* อยากได้

ซื้อที่ไหนได้มั้งเนี่ย

เข้าไปในเวปไซด์ศูนย์หนังสือจุฬา...น่าจะมีอยู่
ผมเพิ่งซื้อที่ดวงกมลเชียงใหม่เมื่อปลายเดือนที่แล้ว หนังสือปกเยินมีแต่รอยขูดขีด ก็ซื้อครับ 160 บาท..เห็นมีอยู่2เล่ม
น่าอ่านครับ

เจอที่ห้องสมุดโรงเรียน แต่บัตรสมาชิกหาย== อดเลย ToT

รบกวนขอโจทย์อีกได้มั้ยครับอยากฝึกทำอ่ะครับ