Wilson定理
判定一个整数是不是素数,一直是个大难题,所以Wilson定理就显得尤为珍贵.
Wilson定理：正整数n＞1,则n是一个素数当且仅当(n-1)!≡-1(modn).
证明：①如果(n-1)!≡-1(modn)成立,则说明n与1、2、...、(n-1)这些小于n的所有整数互素,所以n一定是素数.
②假设n是一个素数,如果n=2显然成立,故下面我们不妨假设n是一个奇素数.对于所有A={1,2,...n-1}中的正整数x,xA除以n的余数也跑遍A,所以都能找到唯一一个A中的y使得xy≡1(modn).也就是说我们把A的数作了两两配对,每一对的乘积除以n的余数都是1.当然其中有些数x是自己和自己配对,这样的x必须满足x2-1≡0(modn),由于n为素数,所以n必然可以整除(x-1)或(x+1),只能有x=1或(n-1),即只有两个数1和(n-1)是自己和自己配对,因此(n-1)!≡(n-1)≡-1(modn).证明完毕.