威爾森定理是一個判別一個數是否為質數的方法,但在事實上此方法未必實用,因為判別的對象越來越大時,判定其階乘會越來越困難。
說明[]
威爾森定理敘述如下:
對於任意正整數,是質數當且僅當時。
若時,,故定理依舊可以成立。
證明[]
此處所給之證明可能不嚴謹,或有所疏漏,還請大家校驗與修正
以下僅討論的狀況:
若是合數(即不是質數的數),則因的每個因數及其乘方小於(的因數不可能等於),而有,且由n|(n-1)!可推出為合數,故若不為的因數,則必須是質數。
若是質數,則因構成的一個完全剩餘系,且對於等皆有其逆元,且其逆元具唯一性,其中除和的逆元與自己相同外,其他數的逆元皆不同於自身(在模質數的狀況下,若一個數的逆元與自己同,則有,故有,從中可得n|x-1或n|x+1,意即或),且任意數與其逆元皆可包含於某個完全剩餘系中,加上同餘的乘法具交換性,因此,在將每個數與其逆元相乘後,只剩與未與其逆元相乘(的逆元為、的逆元為),故,並因,而有,故當為質數時,。
參見[]
上下節[]
初等数论(学科代码:1101710,GB/T 13745—2009) | |
---|---|
整除理论 | 整除 ▪ 带余除法 ▪ 素数 ▪ 公因数 ▪ 辗转相除法 ▪ 公倍数 ▪ 惟一因子分解定理 ▪ 容斥原理 |
同余理论 | 同余 ▪ 同余类(完全代表系,缩同余类) ▪ 同余类的代数结构 ▪ 一次同余方程 ▪ 中国剩余定理 ▪ 线性同余方程组 ▪ 二元一次同余方程组 |
剩余理论 | Euler-Fermat 定理 ▪ 原根 ▪ 指数 ▪ 威尔森定理 ▪ K 次剩餘 ▪ 二次剩余 ▪ Legendre 符号 ▪ 二次互反律 ▪ Jacobi 符号 ▪ 二次同余方程 |
数论函数 | 除数函数 ▪ 除数和函数 ▪ Euler 函数 ▪ Liouville 函数 ▪ Möbius 反演公式 ▪ 数论函数的卷积 ▪ 数论函数的均值 ▪ Dirichlet 特征 |
不定方程 | 二元一次不定方程 ▪ Pythagoras 方程 ▪ 四平方和问题 ▪ 二平方和问题 ▪ Fermat 方程 ▪ 立方和问题 |
素数分布 | Eratosthenes 筛法 ▪ 素数定理 ▪ Chebyshev 函数 ▪ Mangoldt 函数 ▪ Euler 恒等式 |
所在位置:数学(110)→ 数论(11017)→ 初等数论(1101710) |