模乘法反元素計算機

模 m 的乘法反元素是在模運算中能夠抵消乘法的整數。對於整數 a，反元素 x 須滿足：a 乘以 x 後除以 m，餘數為 1。通常寫成 a 乘以 x 模 m 同餘於 1。例如，3 乘以 4 等於 12，12 除以 11 餘 1，因此 4 是 3 模 11 的乘法反元素。 並非每一對整數都有反元素。存在的充要條件是 a 與 m 互質，也就是最大公因數為 1。以 6 模 9 為例：6 的任何倍數都與 9 有公因數 3，因此不可能餘 1。相較之下，7 與 26 的最大公因數為 1，而 7 模 26 的反元素為 15，因為 105 除以 26 餘 1。計算機會先檢查最大公因數，再顯示答案。 擴展歐幾里得演算法可有效率地求出反元素。一般歐幾里得演算法藉由反覆相除並取餘數，計算最大公因數；擴展版本同時追蹤係數，將最大公因數表示為原始輸入的整數線性組合。當最大公因數等於 1，a 的係數就是一個反元素。此係數可能為負，因此計算機會將它對 m 取模，顯示從零到 m 減一之間的最小非負代表元。 模反元素讓同餘系統中的除法成為可能。若要解 a 乘以 x 模 m 同餘於 b，只要在反元素存在時，將 b 乘以 a 的反元素即可。它們在一次同餘方程式、中國剩餘定理、模分數、雜湊、錯誤偵測與公開金鑰密碼學中都很重要。例如，RSA 金鑰產生流程會求某個指數對歐拉函數值的模反元素。實際密碼學實作應使用經過嚴格稽核的任意精度函式庫，而不是一般瀏覽器數值。 請只輸入整數，模數須大於 1。a 可以是負數，因為每個負整數在模 m 下都有等價的最小非負餘數。計算機使用 JavaScript 安全整數，適合課堂練習及中等規模的數論問題。它會顯示最大公因數與直接乘法驗算，讓您確認所得反元素確實使餘數為 1。處理密碼學中的超大整數時，請使用專為大整數及安全敏感運算設計的軟體。