目錄

目錄地址

上一篇

下一篇

---

威爾遜定理

最早由英國的威爾遜爵士提出

一個大于 (1) 的自然數(shù)為 (p) ，則它為質(zhì)數(shù)的充要條件為 ((p-1)!equiv -1(mod p))

證明：

充分性我們使用反證法：設(shè) (p) 是合數(shù)，則設(shè)其最小質(zhì)因子為 (a)

由于 (a<p) 故 (aleq p-1) 因此 (amid (p-1)!)

所以 (a
mid [(p-1)!+1])

又因為 ((p-1)!equiv -1(mod p)) 因此 (pmid [(p-1)!+1])

由 (amid p) 得出 (amid [(p-1)!+1]) 矛盾

因此 (p) 不為合數(shù)

故 (p) 為質(zhì)數(shù)

必要性我們這么來考慮：

首先 (2-1equiv -1equiv 1equiv 1!(mod 2))

對于任意質(zhì)數(shù) (p) 考慮整數(shù) (nin[1,p-1]igcap Z) 令 (ncdot nequiv 1(mod p))

解得 (nequiv pm1(mod p))

所以，對于除了 (1) 與 (p-1) 的所有數(shù)，一定存在 (m) 使得 (nmequiv 1(mod p))

而除了 (2) 的所有質(zhì)數(shù)一定為奇數(shù)，則剩余的 ((p-3)) 個數(shù)一定兩兩配對，乘積為 (1)

因此 (displaystyle (p-1)!equiv 1cdotprod_{i=2}^{p-2}icdot (p-1)=1cdot 1cdot (-1)equiv -1(mod p))

---

費馬定理

對于整數(shù) (p) ，任意非 (p) 倍數(shù)的整數(shù) (a) ，一定有 (a^{p-1}equiv 1(mod p))

考慮到對 (forall n<p,na
mid p)

因此 ([a]) 為 (p) 的一個簡化剩余類， ([na]) 也為一個簡化剩余類

對 (forall n<p,[na]) 互不相同

故 (displaystyle prod_{i=1}^{p-1}(ia)equiv prod_{i=1}^{p-1}i(mod p))

( herefore displaystyle (p-1)!cdot a^{p-1}equiv (p-1)!(mod p))

由威爾遜定理得到 (-1cdot a^{p-1}equiv -1(mod p))

因此得到費馬小定理 (a^{p-1}equiv 1(mod p))

當(dāng)然，費馬定理還有其它的形式，例如： (a^pequiv a(mod p))

費馬定理的推論

由 (a^{p-1}equiv 1(mod p)) 得

(a^nequiv (a^{p-1})^{n/(p-1)}cdot a^{nmod (p-1)}equiv 1^{n/(p-1)}cdot a^{nmod (p-1)}=a^{nmod (p-1)}(mod p))

因此，對于求與模數(shù)互質(zhì)整數(shù)很大的次方，可以用該方法優(yōu)化

總結(jié)

以上是生活随笔為你收集整理的费马小定理与威尔逊定理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。