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