ความรู้เบื้องต้นเรื่อง 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$