ทวินาม vs Modulo

[sharkyboy]

2543^2543 หาร 25 เหลือเศษเท่าไร


อยากได้วิธีทำทั้งแบบทวินามและModulo น่ะครับ
ผมอยากทราบเทคนิคว่าเวลาเราจะกระจายกำลังจะมองอย่างไร และเวลาเราใช้ Mod จะทำอย่างไรให้เร็วสุดน่ะครับ

[Puriwatt]

ตอบ เหลือเศษ 7 ครับ

$2543^{2543}~mod ~25 \equiv 18^{2543}~ mod ~25$

เนื่องจาก $18^2 = 324 = (325-1)$ จะได้ว่า $18^{4}~ mod ~25 \equiv 1~ mod ~25$

ดังนั้น $18^{2543}~ mod ~25 \equiv (18^{2540}\cdot 18^2\cdot 18)~ mod ~25 \equiv (1\cdot -1\cdot 18)~ mod ~25 \equiv (-18)~ mod ~25 \equiv 7~ mod ~25 $