首页 > 代码库 > 威尔逊定理x

威尔逊定理x

2024-09-17 14:24:34   215人阅读

威尔逊定理

在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。即：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )，但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。

充分性

如果“p”不是素数，那么它的正因数必然包含在整数1, 2, 3, 4, … ,p− 1 中，因此gcd((p− 1)!,p) > 1，所以我们不可能得到(p− 1)! ≡ −1 (modp)。
 
必要性
 
若p是素数,取集合 A={1,2,3,...p -1}; 则A 构成模p乘法的缩系,即任意i∈A ,存在j∈A,使得:
( i j ) ≡ 1 ( mod p )那么A中的元素是不是恰好两两配对呢? 不一定,但只需考虑这种情况
x^2 ≡ 1 ( mod p )
解得: x ≡ 1 ( mod p ) 或 x ≡ p - 1 ( mod p )
其余两两配对;
故而
( p - 1 )! ≡ 1﹡( p -1 ) ≡ -1 ( mod p )
ps：
(我试了一下它只能判断n<=35......比暴力都弱......轻易不要用，理解就行啦)
代码如下：
 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio>  4 #include<cmath> 5  6 using namespace std; 7  8 long long int f(int p) 9 {10     if(p==0)11     return 1;12     else return p*f(p-1);13 }14 int main()15 {16     int n;17     scanf("%d",&n);18     long long int ans=f(n-1);19     if(ans%n==n-1)20     printf("YES");21     else 22     printf("NO");23     return 0;24 }

 

威尔逊定理x


联系
我们