費馬小定理計算機

費馬小定理連結質數、次方與模運算。其標準形式指出：若 p 為質數，且 a 不能被 p 整除，則 a^(p - 1) 除以 p 的餘數為 1。以同餘符號表示，就是 a^(p - 1) 與 1 模 p 同餘。當 a = 2、p = 7 時，2^6 = 64，而 64 除以 7 的餘數為 1。 等價形式指出：當 p 為質數，對每個整數 a，a^p 都與 a 模 p 同餘。這個版本也涵蓋 p 整除 a 的情況，因為此時兩邊餘數皆為零。標準形式要求 a 與 p 的最大公因數等於 1。計算機會先檢查質數條件與互質條件，再計算選定的同餘式。 直接計算很大的次方可能產生龐大的中間數值。本工具改用二進位模冪法，也稱反覆平方法：持續將目前底數平方，並在每次乘法後對 p 取模。這能保留精確餘數、避免處理巨大的完整冪值，且所需步驟數僅隨指數呈對數成長。此方法是實務密碼軟體中的基礎演算法。 這項定理可證明某數是合數：若互質底數不符合該同餘式，候選模數就不可能是質數。不過，通過一次費馬測試不能證明是質數。有些合數可在特定底數下通過，卡邁克爾數甚至能對每個與其互質的底數通過標準測試。因此，可靠的質數判定需要更強的確定性檢查，或採用精選底數的 Miller-Rabin 等測試。 費馬的結果支援數論與運算領域的多種應用，包括簡化模運算中的指數、啟發質數測試，以及構成公開金鑰密碼學的數學基礎。RSA 更直接依賴相關的歐拉定理，但費馬小定理解釋了其核心的質數模數行為。當 p 為質數且 a 模 p 不為零時，也能用 a^(p - 2) 模 p 求得模反元素。 請用本計算機驗證課堂範例與探索模運算規律，而非認證大型密碼學質數。輸入限於 JavaScript 安全整數，以確保可靠的質數檢查；模冪運算本身使用精確整數算術。成功結果僅確認所選質數與底數符合指定形式，不能單憑此結果認定尚未檢查的合數候選值是質數。