當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

初等数论--同余--WILSON定理

發(fā)布時(shí)間：2025/3/21 编程问答 13 豆豆

生活随笔收集整理的這篇文章主要介紹了初等数论--同余--WILSON定理小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

博主是初學(xué)初等數(shù)論（整除+同余+原根），本意是想整理一些較難理解的定理、算法，加深記憶也方便日后查找；如果有錯(cuò)，歡迎指正。
我整理成一個(gè)系列：初等數(shù)論，方便檢索。

$設(shè)m∈N+,若a∈Z,(a,m)=1,則在模m的意義下存在唯一的整數(shù)a?1。設(shè)m\in N^{+},若a\in Z,(a,m)=1,則在模m的意義下存在唯一的整數(shù)a^{-1}。$

$存在性：(a,m)=1→ax+my=1,?x,y∈Z→ax≡1(modm),即a?1就是這里的x，是存在的存在性：(a,m)=1\rightarrow ax+my=1,{\exists}x,y\in Z\rightarrow ax\equiv 1(mod m),即a^{-1}就是這里的x，是存在的$
$唯一性：反證法，假設(shè)?x1,x2∈Z,x1≠x2,使得ax1≡x1a≡1(modm),ax2≡x2a≡1(modm),那么x1≡x1(ax2)≡(x1a)x2≡x2(modm)唯一性：反證法，假設(shè){\exists}x_1,x_2\in Z,x_1\neq x_2,使得\\ ax_1\equiv x_1a\equiv 1(mod m),\\ ax_2\equiv x_2a\equiv 1(mod m),\\ 那么x_1\equiv x_1(ax_2)\equiv (x_1a)x_2\equiv x_2(mod m)$

$若p為素?cái)?shù)，則(p?1)!≡?1(modp)若p為素?cái)?shù)，則(p-1)!\equiv -1(mod p)$
$分情況考慮，從 p = 2 開始：$

$p=2,則(p?1)!=1!=1≡?1(mod2)p=2,則(p-1)!=1!=1\equiv -1(mod 2)$
$p≥3,對(duì)于整數(shù)a,1≤a≤p?1,有(a,p)=1,存在唯一整數(shù)a?1使得aa?1≡a?1a≡1(modp)現(xiàn)在考慮在1p\ge3,對(duì)于整數(shù)a,1\le a\le p-1,有(a,p)=1,存在唯一整數(shù)a^{-1}使得aa^{-1}\equiv a^{-1}a\equiv 1(mod p)\\ 現(xiàn)在考慮在1$ ~ $p?1之間有幾對(duì)互為逆元,有哪些數(shù)的逆元是其本身,即a≡a?1(modp),a≡a?1(modp)a2≡1(modp)a2?1≡0(modp)(a+1)(a?1)≡0(modp)a≡?1(modp)或a≡+1(modp)a=p?1,或a=1所以我們得到只有p?1和1的逆元是其本身，其余的數(shù)皆可寫成逆元對(duì)形式，即(p?1)!≡(p?1)?1≡p?1≡?1(modp)p-1之間有幾對(duì)互為逆元,有哪些數(shù)的逆元是其本身,即a\equiv a^{-1}(mod p),\\ a\equiv a^{-1}(mod p)\\ a^{2}\equiv 1(mod p)\\ a^{2}-1\equiv 0(mod p)\\ (a+1)(a-1)\equiv 0(mod p)\\ a\equiv -1(mod p)或a\equiv +1(mod p)\\ a=p-1,或a=1\\ 所以我們得到只有p-1和1的逆元是其本身，其余的數(shù)皆可寫成逆元對(duì)形式，即\\ (p-1)!\equiv (p-1)·1\equiv p-1\equiv -1(mod p)$

$綜上，(p?1)!≡?1(modp)綜上，(p-1)!\equiv -1(mod p)$

以上是生活随笔為你收集整理的初等数论--同余--WILSON定理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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