威尔逊定理
首先介绍几个简单的概念：
1.m|(a-b）：表示(a-b)被m整除
设a%m=c,则b%m=c;也就是说a和b除以m的余数是相同的。
举一个例子：3|(11-5)
11%3=2,5%3=2,(11-5)%3=0 大体就是这个意思。
2.同余：设m是大于1的正整数,a,b是整数,如果m|(a-b),则称a与b关于模m同余,记作a≡b(mod m),读作a与b对模m同余.
【同余的主要性质】：
(a+b)%d=(a%d+b%d)%d
加减乘除都能分开写
要注意的是减法，因为减法可能会减出来负值所以可以这样写（a-b+mod）%mod；
下面是威尔逊定理： 在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。 即：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )
证明在百度完全可以找到，转载一下：
1.充分性
如果“p”不是素数：
当p=4时，显然（p-1)!≡6≡2(mod p),；
当p>4时，若p不是完全平方数，则存在两个不等的因数a，b使得ab=p，则(p-1)!≡nab≡0(mod p);
若p是完全平方数即p=k^2，因为p>4,所以k>2，k,2k<p，(p-1)!≡n(k*2k)≡2nk^2≡0(mod p)。
2.必要性
若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 )
TCL公司福利 1293人发布