hce_kmu
115年
計算機概論與程式設計
第 29 題
Please calculate the value of $2^{2026} \pmod{13}$. Which of the following is CORRECT?
- A 0
- B 1
- C 7
- D 10
- E 11
思路引導 VIP
當我們面對一個極大的指數，而模數（除數）剛好是一個質數時，除了逐次相乘尋找規律，是否有什麼定理可以幫助我們預知「餘數何時會重新開始循環」，進而將巨大的指數縮小到可以輕鬆計算的範圍呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精確計算出這題的答案，代表你對大數求餘數的處理非常有心得，這在密碼學與演算法分析中是非常核心的能力。
費馬小定理與指數簡化
這類題目的解題核心在於利用費馬小定理 (Fermat's Little Theorem)。當除數 $p$ 為質數時，若底數 $a$ 不是 $p$ 的倍數，則 $a^{p-1} \equiv 1 \pmod{p}$。在本題中 $p=13$ 是質數，因此我們知道 $2^{12} \equiv 1 \pmod{13}$。這意味著指數部分每過 $12$ 就會回到 $1$ 的循環。我們將 $2026$ 除以 $12$，得到 $2026 = 12 \times 168 + 10$，因此原式可以簡化為：
▼ 還有更多解析內容