[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}$




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