# 費馬小定理證明

###### tags: `數學證明`,`數論`

待補

---

資料主要 from wiki 我打得詳細一點 加上自己個人的理解上去

先設兩數 $a,p$。

$p$ 是一個質數。

設 $gcd(a,p)=1$ (兩數互質)

先弄一件事情 假設任意數 $x,y$

如果說 $p \nmid (x-y)$ 那麼 $p \nmid a\times(x-y)$ 必然成立
我是這樣理解：

反證法：

若 $p \mid a\times(x-y)$ 成立。
那麼 $a\times(x-y)$ 一定會有一個因數是 $p$。
原來 $(x-y)$ 的因數裡面本來就沒 $p$ 存在。
可以直接撇除掉 $a$ 因為 $a$ 乘上任何一個原本在$(x-y)$裡面的因數，必然不可能被 $p$ 整除。

換句話說：

一個數因數內有 $p$ 不可能因為後天的乘上一個因數沒有$p$的數造出來(因為它是質數!!)

---

接下來這個部分簡單一點點
先取一個整數集$A$是所有小於$p$的正整數的集合。
意即 $A = \left\{ 1,2,3,4...,p-1 \right\}$
因為 $p$ 是質數，所以 $∀a∈A,gcd(a,p)=1$

在令一個 $B$ 集合 為 $A$ 中所有元素乘以 $a$ 的集合。
意即 $B_i = A_i*a$

可以知道 $\forall$$k \in B,gcd(k,p) = 1$

將它們全部除以$p$，餘數分別為$r_1,r_2...r_{p-1}$ 為集合 $1,2,3...,p-1$ 的重新排列。

至於要證明這個 我覺得 wiki 上的寫的比較不好理解(對我來說)
所以我用反證法來證明

假設今天我有兩個位置出來的餘數是相同的，也就是$r_i=r_j$
換成數學式：
$(A_i \times a)\equiv(A_j\times a) \pmod p$

移項一下

$(A_i \times a - A_j \times a) \equiv 0 \pmod p$

然後把 $a$ 提出來

$a\times (A_i - A_j) \equiv 0 \pmod p$

然後 $gcd(a,p) = 1$ 所以整除這件事跟 $a$ 完全無關。

所以可以直接把 $a$ 從裡面拿掉。

所以剩下
$(A_i - A_j) \equiv 0 \pmod p$

然後奇怪的事情就發生了 因為上式不可能成立
以下列出兩種成立條件
1. $|A_i-A_j|>=p$
2. $|A_i-A_j|=0$

第一種不可能 因為 對於任意 $A$ 集合裡的數最大就到 $p-2$ $((p-1) - 1)$ 所以更不可能大於等於 $p$
第二種也不可能，因為集合$A$裡面沒有重複的元素。
得證。

----

證明完 $B$ 集合 $%p$ 的所有元素是 $1,2,...p-1$ 後，可以知道一件事情
from wiki
這邊就很好理解了 我就不打了。