費馬小定理，也稱費馬定理，是壹個數論中的基本定理，是指在模質數下，任取壹個不是該質數倍數的整數a，其冪次為p-1時，模質數的結果恒為1，即：a^(p-1)
≡ 1 (mod p)
其中，p為壹個素數，a為任意壹個滿足1 <= a < p的整數。
費馬小定理最早由法國數學家費馬於17世紀提出，它是歐拉定理和歐拉-費馬定理的基礎，被廣泛應用於密碼學、編碼、計算機科學等領域。
費馬小定理的證明可以采用數學歸納法，設k為壹個正整數，則有：
當k=1時，a^0 ≡ 1 (mod p)，結論成立。
當k>1時，假設a^(p-1) ≡ 1 (mod p)成立，則有：
a^(kp-k) ≡ (a^(p-1))^k * a^(-k) ≡ 1^k * a^(-k) ≡ a^(p-1)
* a^(-k) ≡ a^(p-1-k) (mod p)
因此，當k>1時，a^(kp-k) ≡ a^(p-1-k)
(mod p) 成立。
因為p是素數，a是不是p的倍數的整數，所以a和p互質，即它們沒有公***因數。由歐拉定理可知，a^(φ(p)) ≡ 1 (mod p)，其中φ(p)表示小於p且與p互質的正整數的個數，因此有φ(p)
≤ p-1。
根據算術基本定理，p是質數，所以φ(p) = p-1，因此有：
a^(p-1) ≡ 1 (mod p)
費馬小定理的應用非常廣泛，其中壹個重要的應用領域是密碼學。在加密算法中，選擇兩個大質數p和q，將它們乘積pq作為公***模數，並選擇壹個整數e作為公鑰，使得e與(p-1) *
(q-1)互質，然後選擇壹個整數d作為私鑰，使得d*e ≡ 1
(mod (p-1) * (q-1))，這樣就可以利用費馬小定理對加密和解密進行高效的處理。