$4 blog: 🚀 深入淺出模逆元：費馬小定理與快速冪的完美結合

2026年4月9日星期四

🚀 深入淺出模逆元：費馬小定理與快速冪的完美結合

在解決涉及「巨大數字」與「取餘數 (Modulo)」的演算法題目時，我們經常會遇到一個棘手的問題：加、減、乘法都可以直接在取餘數的狀態下進行，唯獨「除法」不行。

為了解決除法失效的問題，數學家們引入了「模逆元 (Modular Multiplicative Inverse)」的概念，而最優雅的實作方式，莫過於結合「費馬小定理」與「快速冪」。這篇文章將帶您一步步拆解其中的奧秘。

🛑 第一步：為什麼取餘數的世界裡，除法會壞掉？

讓我們先來看一個簡單的例子：我們想要計算 (12 / 4) % 7。

在正常的數學裡：12 / 4 = 3，然後 3 % 7 = 3。答案是 3。

現在，如果我們在計算過程中，數字已經因為太大而被取過餘數了呢？

12 % 7 = 5。
如果我們拿取完餘數的數字直接去除：5 / 4 = 1.25。
1.25 是小數！在取餘數的整數運算世界裡，這完全失去了意義。

🔄 第二步：模逆元的救贖 (Modular Multiplicative Inverse)

既然不能「除以 4」，那我們能不能改成「乘以某個數字」？

在普通的數學裡，除以 4 等同於乘以 0.25（因為 4 × 0.25 = 1，它們互為倒數）。
在模 7 的世界裡，我們也在尋找一個數字 X，使得 (4 × X) % 7 = 1。這個 X 就是 4 在模 7 底下的模逆元。

讓我們暴力找找看 X 是多少：

4 × 1 = 4 ≡ 4 (mod 7)
4 × 2 = 8 ≡ 1 (mod 7) 🎯 找到了！

所以，在模 7 的世界裡，「除以 4」就等同於「乘以 2」！

我們回頭驗證一開始的算式：
先取餘數：12 % 7 = 5
把除以 4 改成乘以 2：5 × 2 = 10
再取餘數：10 % 7 = 3。答案完美吻合！

📜 第三步：費馬小定理 (Fermat's Little Theorem)

雖然我們可以用迴圈暴力找出模逆元，但當模數 P = 10^9 + 7（十億等級的質數）時，暴力尋找會非常慢。這時候，偉大的費馬小定理就派上用場了。

💡 費馬小定理：
如果 P 是一個質數，且 A 不是 P 的倍數，那麼：

A^P-1 ≡ 1 (mod P)

我們把這個等式稍微拆解一下，把其中一個 A 獨立出來：

A × A^P-2 ≡ 1 (mod P)

看出來了嗎？根據模逆元的定義（A × X ≡ 1），這個 A^P-2 完美符合 X 的位置！

結論：在模 P 的世界裡，數字 A 的模逆元就是 A^P-2 (mod P)。

⚡ 第四步：快速冪 (Binary Exponentiation) —— O(log N) 的超光速引擎

雖然我們得出模逆元是 A^P-2，但當 P = 10^9 + 7 時，我們要計算 A^1000000005。如果傻傻地用 for 迴圈乘十億次，肯定會超時 (TLE)。

為了解決這個問題，我們使用快速冪 (Binary Exponentiation) 技巧。它的核心概念是「倍增」。

💻 第五步：程式碼實作

有了費馬小定理與快速冪的觀念，求模逆元的實作就非常簡單了。在 Python 中甚至有內建的高效寫法；而在 C/C++ 中，我們通常會自己實作一個 power 函數。

Python 實作

Python 從 3.8 版本開始，內建的 pow 函數直接支援了求模逆元，只要將指數設為 -1 即可（底層自動採用快速冪與擴展歐幾里得演算法）：

MOD = 10**9 + 7
v = 4

# Python 內建魔法，直接求 4 在模 10^9+7 下的模逆元
inv_v = pow(v, -1, MOD)

# 或是手動利用費馬小定理：v^(MOD-2) % MOD
inv_v_fermat = pow(v, MOD - 2, MOD)

print(inv_v) # 輸出：250000002

C++ 實作

在 C++ 中，我們需要手動實作快速冪函數（Binary Exponentiation）：

#include <iostream>

long long MOD = 1e9 + 7;

// 快速冪實作：計算 (base^exp) % MOD
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        // 如果當前二進位最低位是 1，則乘上當前的 base
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        // base 自我平方 (A^1 -> A^2 -> A^4 -> A^8 ...)
        base = (base * base) % MOD;
        // 將 exp 右移一位 (等同於 exp /= 2)
        exp /= 2;
    }
    return res;
}

// 求模逆元
long long modInverse(long long n) {
    // 根據費馬小定理，逆元為 n^(MOD-2)
    return power(n, MOD - 2);
}

int main() {
    long long v = 4;
    std::cout << "4 的模逆元是: " << modInverse(v) << std::endl;
    // 驗證： (4 * 250000002) % 1000000007 == 1
    return 0;
}