# 費馬小定理 Fermat's little theorem
要讀種這篇的證明，請先看看之前講過的[拉格朗日定理](https://hackmd.io/@ShanC/Lagrange-Theorem)

## 引理 1
### 敘述
若 $G$ 是一個有限群，則對於所有 $g\in G$，$|g|$ 整除 $|G|$

### 證明
因為 $\langle g\rangle\le G$，根據拉格朗日定理，$|g|=|\langle g\rangle|$ 整除 $|G|$

## 引理 2
### 敘述
對於所有 $x\in G$，$x^{|G|}=1$

### 證明
根據引理 1，$k\cdot|x|=|G|$，且根據 order 定義，$x^{|x|}=1$，因此
$$
x^{|G|}=x^{k\cdot|x|}=1^k=1
$$

## 費馬小定理
### 敘述
若 $p$ 為質數，則對於所有整數 $a$ :

$$a^{p-1} \equiv 1 \pmod p$$

### 證明
考慮所有與質數 $p$ 互質且小於 $p$ 的整數集合，這就是模 $p$ 乘法群，記作 $(\mathbb{Z}/p\mathbb{Z})^\times$

$$G = \{1, 2, 3, \dots, p-1\}$$

在這個群中，運算方式是模 $p$ 乘法

因為 $p$ 是質數，根據質數的性質，從 $1$ 到 $p-1$ 的每一個數都與 $p$ 互質。因此，群 $G$ 的 order 為 :

$$|G| = p - 1$$

根據引理 2，對於所有 $a \in G$：$$a^{|G|} \equiv 1 \pmod p$$將 $|G| = p-1$ 代入，我們得到：$$a^{p-1} \equiv 1 \pmod p$$

## 費馬小定理的應用 : 模逆元
### 稍微推論一下
如果 $p$ 為質數 :
$$a^{p-1} \equiv 1 \pmod p$$
兩邊同乘 $a^{-1}$ :
$$a^{p-2} \equiv a^{-1} \pmod p$$

### 實作
配合[快速冪](https://hackmd.io/@ShanC/Binary-Exponentiation-and-Lifting)，把程式碼加上某個質數 $p$

#define ll long long
int p = 1e9 + 7; // 質數
ll fpow(ll a, ll b){
    ll ret = 1;
    while(b){
        if(n & 1) ret = ret * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ret;
}

然後直接求 $a^{p-2} \pmod p$

fpow(a, p - 2);

這樣就可以求出逆元了

## 題目練習
[Zerojudge s093. 模逆元練習](https://zerojudge.tw/ShowProblem?problemid=s093) (我出的，裸的)

----

## 參考資料

- Dummit, Foote - Abstract Algebra, 3/e
- [Wikipedia - Fermat's little theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem)
- 某讀書會用的 [ppt](https://github.com/bearomorphism/math-slides/blob/86f997d124ad2656d1d6cf023a3c3ff5436c39fc/subgroups/main.pdf)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2026/2/4