费马小定理:若 \(p\) 为质数,则 \(x^{p}\equiv x(\text{mod}\ p)\)。特别地,若 \(p\not\mid x\),则 \(x^{p-1}\equiv 1(\text{mod}\ p)\)。
首先,若 \(p\mid x\),则 \(x\equiv 0(\text{mod}\ p)\Leftrightarrow x^p\equiv x(\text{mod}\ p)\)。
若 \(p\not\mid x\),则我们构造一个集合 \(\{x, 2x, \dots (p - 1)x\}\)。
假设这个集合里的元素有相同的,则若对于 \(i\not= j\),有 \(ix\equiv jx(\text{mod}\ p)\)。
移向,得 \((i - j)x\equiv 0(\text{mod}\ p)\)。
因为 \(i\not=j\),且 \(0<i,j<p\),因此 \(p\not\mid(i-j)\)。
又因为 \(p\not\mid x\),所以 \((i - j)x\not\equiv 0(\text{mod}\ p)\),矛盾。
因此 \(x,2x\dots,(p-1)x\) 没有相同的元素,且里面的元素对 \(p\) 取模后与集合 \(\{1,2,\dots,p-1\}\) 相同。
我们让两个集合的所有元素分别相乘,得到 \(x\cdot 2x\cdots (p-1)x\equiv 1\cdot 2\cdots (p-1)(\text{mod}\ p)\)。
得到 \(x^{p - 1}\equiv 1(\text{mod}\ p)\)。
且 \(x^{p}\equiv x(\text{mod}\ p)\)。