อ้างอิง:
ข้อความเดิมเขียนโดยคุณ ฟินิกซ์เหินฟ้า
ใช่ครับ ต้องบนลงล่าง โดยเลขบนควรวนLoopใน$mod?$
|
ล่างขึ้นบนสามารถหาได้ครับ แต่ข้อนี้เลขยากหน่อย
ส่วนข้อความข้างบนผมได้ใช้ทฤษฎีรั่วไป เพราะลืมไปว่า $(2554,1000)\not= 1$
สมมติเปลี่ยนโจทย์ให้ง่ายขึ้น ผมจะแสดงวิธีหาจากล่างขึ้นบน
----------------------------------------
จงหาเศษจากการหาร $2553^{2553^{2553}}$ ด้วย $100$
เช็คตัวฐาน ใน $mod100$
จาก ทบ ออยเลอร์ จะได้ว่า
$2553^{40}\equiv 1(mod100)...(1)$
เช็คเลขชี้กำลังของตัวฐานใน $mod 40$
$2553^{4}\equiv 1(mod40)$
$2553^{2552}\equiv 1(mod40)$
$2553^{2553}\equiv 2553\equiv 33(mod40)$
แสดงว่า $40$ หาร $2553^{2553}$ เหลือเศษ $33$
ให้ $2553^{2553}=40x+33$ (เลขชี้กำลังของตัวฐาน)
จาก $(1)$
$2553^{40}\equiv 1(mod100)$
$2553^{40x}\equiv 1(mod100)$
$2553^{40x+33}\equiv 2553^{33}(mod100)$
$2553^{2553^{2553}}=2553^{40x+33}\equiv 2553^{33}(mod100)$
เราหาว่า $2553^{33}\equiv ?(m0d100) $ ก็จะเป็นคำตอบของเรา
=============================
$2553^2\equiv 809\equiv -191(m0d100) $
$2553^4\equiv 481(m0d100) $
$2553^8\equiv 361(m0d100) $
$2553^{16}\equiv 321(m0d100) $
$2553^{32}\equiv 41(m0d100) $
$2553^{33}\equiv 673(m0d100) $
ดังนั้น เศษจากการหาร $2553^{2553^{2553}}$ ด้วย $100$ คือ $673$
ปล.ถ้าทำจากบนลงล่างผมไม่ทราบว่าจะเริ่มเช็ค $mod$ ไหนก่อน ลองแชร์วิธีกันดูครับ