一開始我都不知道費馬是個人，以為和胡不歸問題起名方法一樣，是個浪費馬的小定理所以叫費馬小定理
內容
若 p p p是質數，則對于任意整數 a a a，有 a p ≡ a^p \equiv ap≡ a ( m o d a(mod a(mod p ) p) p)，
證明
反過來兩邊同時除以
a
a
a我們可以得到
a
p
?
1
≡
1
a^{p-1} \equiv1
ap?1≡1
(
m
o
d
(mod
(mod
p
)
p)
p)，所以此時可以把該問題轉換為證明
a
p
?
1
a^{p-1}
ap?1
m
o
d
mod
mod
p
=
1
p=1
p=1，隨手舉個例子也確實沒什么大問題：
a
=
2
a=2
a=2，
p
=
3
p=3
p=3時
a
p
?
1
=
4
a^{p-1}=4
ap?1=4，
4
4
4
m
o
d
mod
mod
3
=
1
3=1
3=1，但是這只是個小資料的代入，所以不能看做是嚴格的證明，
a
p
?
1
a^{p-1}
ap?1
m
o
d
mod
mod
p
=
1
p=1
p=1可以轉化為
p
×
x
=
a
p
?
1
+
1
p \times x=a^{p-1}+1
p×x=ap?1+1，然后這個方法我就證不下來了……
換個思路
g
c
d
(
a
,
p
)
=
1
gcd(a,p)=1
gcd(a,p)=1，考慮
1
×
a
,
2
×
a
,
3
×
a
,
…
…
(
p
?
1
)
×
a
1\times a,2\times a,3\times a,……(p-1)\times a
1×a,2×a,3×a,……(p?1)×a共
(
p
?
1
)
(p - 1)
(p?1)個數，將它們分別除以p，余數分別為
r
1
,
r
2
,
.
.
.
.
.
,
r
p
?
1
r_1,r_2,.....,r_{p-1}
r1?,r2?,.....,rp?1?，為集合{
1
,
2
,
3...
p
?
1
1,2,3...p-1
1,2,3...p?1}的重新排列，即1.3…(p-1)在余數中恰好各出現一次;這是因為對于任兩個相異
k
×
a
k\times a
k×a而言
(
k
=
1
,
2
,
3...
(
p
?
1
)
)
(k=1,2,3...(p-1))
(k=1,2,3...(p?1))，其差不是p的倍數(所以不會有相同余數)，且任一個
k
×
a
k\times a
k×a亦不為
p
p
p的倍數(所以余數不為
0
0
0)，
因此
1
×
2
×
3.....
(
p
?
1
)
≡
(
1
×
a
)
×
(
2
×
a
)
.
.
.
.
(
(
p
?
1
)
×
a
)
(
m
o
d
1\times 2\times 3.....(p-1)\equiv (1\times a)\times (2\times a)....((p-1)\times a) (mod
1×2×3.....(p?1)≡(1×a)×(2×a)....((p?1)×a)(mod
p
)
p)
p)
即
W
≡
W
×
(
a
p
?
1
)
(
m
o
d
p
)
W \equiv W \times (a^{p-1}) (mod p)
W≡W×(ap?1)(modp)
在這里
W
=
1
×
2
×
3
…
×
(
p
?
1
)
W=1 \times 2\times 3…\times (p-1)
W=1×2×3…×(p?1)，且
g
c
d
(
W
,
p
)
=
1
gcd(W,p)=1
gcd(W,p)=1
整理后可得費馬小定理，
而費馬小定理只是素數判定的一個必要條件，素數一定滿足費馬小定理，滿足費馬小定理的數，卻不一定是素數，
另外一個應用就是求逆元，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/282348.html
標籤：區塊鏈
上一篇：vue-router路由使用