什麼是費馬小定理？
費馬小定理（Fermat's Little Theorem）是數論中的重要基石。它指出：若 p 為質數，且 a 是無法被 p 整除的整數（也就是 \(\gcd(a, p) = 1\)），那麼 a 的 (p − 1) 次方除以 p 後，餘數必為 1。以數學符號表示為：$$a^{\,p-1} \equiv 1 \pmod{p}$$ 此外還有一個更普遍的版本，對所有整數 a 都成立：$$a^{\,p} \equiv a \pmod{p}$$
如何使用本計算機
請輸入底數 a 與數值 p。計算機會先檢查 p 是否為質數，計算 \(\gcd(a, p)\)，再利用「快速模冪運算」分別求出 \(a^{\,p-1} \bmod p\) 與 \(a^{\,p} \bmod p\)。當 p 為質數且 \(\gcd(a, p) = 1\) 時，第一個結果一定會是 1，正好印證了定理。若不符合上述條件，\(a^{\,p-1}\) 的結果會顯示為 n/a，因為此時定理並不保證結果會等於 1。
公式原理解析
模冪運算的做法，是反覆將底數平方並同時對 p 取餘數，因此即使指數很大，計算量仍能維持在可控範圍內。這個定理是許多重要應用的基礎，包括質數檢驗法（費馬測試）、RSA 加密的金鑰運算，以及求模反元素——因為當 p 為質數時，\(a^{\,p-2} \bmod p\) 正是 a 對模 p 的反元素。
實際範例
令 \(a = 2\)、\(p = 7\)。由於 7 是質數且 \(\gcd(2, 7) = 1\)，我們預期 $$2^{6} \bmod 7 = 64 \bmod 7 = 1$$ ✔ 而普遍版本則為 $$2^{7} \bmod 7 = 128 \bmod 7 = 2$$ 恰好等於 \(2 \bmod 7 = 2\)。✔
常見問題 FAQ
如果 p 不是質數會怎樣？ 定理可能不成立。計算機會標示 p 並非質數，此時只有普遍版本 \(a^{\,p} \bmod p\) 才有意義，而且結果不一定等於 a。
如果 a 是 p 的倍數呢？ 這時 \(\gcd(a, p) \neq 1\)，因此 \(a^{\,p-1} \bmod p\) 不會是 1（而會是 0）。但普遍版本 \(a^{\,p} \equiv a\) 仍然成立。
可以用它來求模反元素嗎？ 可以——當 p 為質數時，\(a^{\,p-2} \bmod p\) 就是 a 對模 p 的乘法反元素。
