มาดูตัวอย่างต่อไป ตอนนี้อาจต้องยาวหน่อย แต่พอถึงเรื่อง 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$
ต่อนี้ไป เราจะไม่เขียนยาวๆแบบนี้อีกแล้ว
แต่จะอ้างเหตุผลข้างต้นแทน
ดูตัวอย่างต่อไปเลยครับ