ตัวอย่าง 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$
มันส์ไหมครับ ถ้ามันส์ ก็มามันส์ด้วยกันต่อในตัวอย่างต่อไป
