สอบถาม congruence ผมไม่เข้าใจ

[lnพwsะบุ๑sสุ๑xล่o]

ข้อความเดิมเขียนโดยคุณ StrikeFreedom

ขอบคุณมากครับบ ผมไปต่อได้ล่ะครับบบ
พี่ครับแล้วถ้าเป็นโจทย์หาเศษ เลขยกกำลังซ้อนกันมากกว่า2ตัว นี่ทำยังไงหรอครับ เช่น $2554^{{2554}^{2554}}ด้วย1000$

ทำทีละขั้นครับจากล่างขึ้นบน

$2554^{40}\equiv 1(mod1000)$

เราหาต่อว่า

$2554^{2554}\equiv ?(mod40)$

[StrikeFreedom]

ข้อความเดิมเขียนโดยคุณ lnพwsะบุ๑sสุ๑xล่o

ทำทีละขั้นครับจากล่างขึ้นบน

$2554^{40}\equiv 1(mod1000)$

เราหาต่อว่า

$2554^{2554}\equiv ?(mod40)$

ไม่เข้าใจอ่ะครับ อยากได้แบบหลักการอ่ะครับ ผมไปไม่เปนเลย ขอบคุณครับ

[phonophile]

ข้อความเดิมเขียนโดยคุณ lnพwsะบุ๑sสุ๑xล่o

ทำทีละขั้นครับจากล่างขึ้นบน

$2554^{40}\equiv 1(mod1000)$

เราหาต่อว่า

$2554^{2554}\equiv ?(mod40)$

ขออนุญาตถามครับ กรณียกกำลังในโจทย์ไม่มีวงเล็บแบบนี้ ต้องยกกำลังจากบนลงล่างมิใช่หรือครับ ถ้ายังไง ช่วยทำต่อหน่อยครับ ขอบคุณครับ

[ฟินิกซ์เหินฟ้า]

ข้อความเดิมเขียนโดยคุณ phonophile

ขออนุญาตถามครับ กรณียกกำลังในโจทย์ไม่มีวงเล็บแบบนี้ ต้องยกกำลังจากบนลงล่างมิใช่หรือครับ ถ้ายังไง ช่วยทำต่อหน่อยครับ ขอบคุณครับ

ใช่ครับ ต้องบนลงล่าง โดยเลขบนควรวนLoopใน$mod?$

[StrikeFreedom]

คือผมยังไม่เข้าใจหลักการยกกำลังซ้อนเลยอ่ะครับ ช่วยอธิบายหน่อยได้มั้ยครับ

[lnพwsะบุ๑sสุ๑xล่o]

ข้อความเดิมเขียนโดยคุณ ฟินิกซ์เหินฟ้า

ใช่ครับ ต้องบนลงล่าง โดยเลขบนควรวน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$ ไหนก่อน ลองแชร์วิธีกันดูครับ

[StrikeFreedom]

โหดมากครับ ต้องอ่านให้ลึกซึ่งไปอีก มันยากกว่าที่ผมคิดเยอะเลยแหะเลขยกกำลังซ้อน ขอบคุณมากครับ

[IMO]

ข้อความเดิมเขียนโดยคุณ lnพwsะบุ๑sสุ๑xล่o

จาก ทบ ออยเลอร์ จะได้ว่า

$2553^{40}\equiv 1(mod1000)...(1)$

ผมคิดว่า $\phi (1000) $คือ 400 นะครับ
ปล. ถ้ากำลัง 40 mod จะเหลือ 801 ครับ