费马小定理
定义：
设 p 为素数，a 为整数，则 a p ≡ a ( m o d p ) a^p \equiv a\ (\mod p) ap≡a (modp) ，若 p ∤ a p \nmid a p∤a ，则 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1\ (\mod p) ap−1≡1 (modp)
先证明若
p
∣
a
p \mid a
p∣a ，证明过程如下：
∵
p
∣
a
a
m
o
d
p
=
0
a
p
m
o
d
p
=
0
\because p \mid a \\ a\mod p=0 \\ a^p \mod p =0
∵p∣aamodp=0apmodp=0
再证明当
p
∤
a
p \nmid a
p∤a 时：
创建集合 S = S= S={ x 1 , x 2 , x 3 , ⋯ , x p − 1 x_1,x_2,x_3,\cdots,x_{p-1} x1,x2,x3,⋯,xp−1} ，S为1，2，3， ⋯ \cdots ⋯，p-1的一个 排列 ， a x 1 , a x 2 , a x 3 , ⋯ , a x p − 1 ax_1,ax_2,ax_3,\cdots,ax_{p-1} ax1,ax2,ax3,⋯,axp−1 ，任意两项模 p 不同余
若 ∃ ∀ i , j , ╞ 1 ≤ i < j < p \exists\ \forall\ i,j,╞ 1\le i <j <p ∃ ∀ i,j,╞1≤i<j<p ，使得 a x i ≡ a x j ( m o d p ) ax_i\ \equiv ax_j (\mod p) axi ≡axj(modp)
则 p ∣ a ( x i − x j ) p\mid a(x_i-x_j) p∣a(xi−xj)
∵ p ∤ a , ∴ p ∣ ( x i − x j ) \because p \nmid a\ \ ,\therefore p\mid(x_i-x_j) ∵p∤a ,∴p∣(xi−xj)
又 ∵ x i m o d p ≠ x j m o d p \because x_i \mod p \not= x_j\mod p ∵ximodp=xjmodp
∴ 矛盾 \therefore 矛盾 ∴矛盾
设 ∀ k ∈ S , p ∤ S k \forall \ k \in S,p\ \nmid\ S_k ∀ k∈S,p ∤ Sk
∵ a x 1 m o d p , a x 2 m o d p , ⋯ , a x p − 1 m o d p \because ax_1\mod p,ax_2\mod p,\cdots,ax_{p-1}\mod p ∵ax1modp,ax2modp,⋯,axp−1modp 为1,2,3, ⋯ \cdots ⋯ ，p-1的一个排列（上文已提到）
∴
(
a
x
1
)
(
a
x
2
)
(
a
x
3
)
⋯
(
a
x
p
−
1
)
≡
x
1
⋅
x
2
⋅
x
3
⋯
x
p
−
1
(
m
o
d
p
)
\therefore (ax_1)(ax_2)(ax_3)\cdots(ax_{p-1})\equiv x_1\cdot x_2\cdot x_3 \cdots x_{p-1} (\mod p)
∴(ax1)(ax2)(ax3)⋯(axp−1)≡x1⋅x2⋅x3⋯xp−1(modp)
x
1
⋅
x
2
⋅
x
3
⋯
x
p
−
1
=
(
p
−
1
)
(
p
−
2
)
(
p
−
3
)
⋯
2
⋅
1
=
(
p
−
1
)
!
x_1\cdot x_2 \cdot x_3 \cdots x_{p-1} \\ =(p-1)(p-2)(p-3)\cdots 2\cdot 1 \\ =(p-1)!
x1⋅x2⋅x3⋯xp−1=(p−1)(p−2)(p−3)⋯2⋅1=(p−1)!
∵
p
∤
(
p
−
1
)
!
\because p\nmid(p-1)!
∵p∤(p−1)!
∴ a p − 1 ≡ 1 ( m o d p ) \therefore a^{p-1}\equiv 1 (\mod p) ∴ap−1≡1(modp)
