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