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

[banker]

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

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

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

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

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

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

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

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

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

[banker]

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

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

[banker]

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

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

[banker]

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

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

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

[banker]

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


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

[banker]

มาดูตัวอย่างต่อไป ตอนนี้อาจต้องยาวหน่อย แต่พอถึงเรื่อง 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$

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

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

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

[banker]

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

[banker]

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

[banker]

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

[banker]

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


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

[banker]

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


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

[banker]

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

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

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




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

[banker]

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



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

[banker]

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

[banker]

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

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