费马小定理是数论中的一个重要定理，其内容为： 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p） 假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1

历史

证明

在数论中的地位

实际应用

历史

皮埃尔·德·费马于1636年发现了这个定理，在一封1640年10月18日的信中他第一次使用了上面的书写方式。在信中费马还要求a是一个质数，但是这个要求实际上是不必要的。与费马小定理相关的有一个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当2^(p-1）≡1(mod p），p是一个质数。

假如p是一个质数的话，则2^(p-1）≡1(mod p）成立（这是费马小定理的一个特殊情况）是对的。但反过来，假如2^(p-1）≡1(mod p）成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。因此整个来说这个猜想是错误的。一般认为中国数学家在费马前2000年的时候就已经提出中国猜想了，但也有人认为实际上中国猜想是1872年提出的，认为它早就为人所知是出于一个误解。

证明

一、准备知识：

引理1．剩余系定理2

若a,b,c为任意3个整数，m为正整数，且（m,c)=1，则当ac≡bc(mod m）时，有a≡b(mod m)

证明：ac≡bc(mod m）可得ac–bc≡0(mod m）可得（a-b)c≡0(mod m）因为（m,c)=1即m,c互质，c可以约去，a–b≡0(mod m）可得a≡b(mod m)

引理2．剩余系定理5

若m为整数且m>1,a[1],a[2],a[3],a[4]，…a[m]为m个整数，若在这m个数中任取2个整数对m不同余，则这m个整数对m构成完全剩余系。

证明：构造m的完全剩余系（0,1,2，…m-1），所有的整数必然这些整数中的1个对模m同余。取r[1]=0,r[2]=1,r[3]=2,r[4]=3，…r[i]=i-1,1<i<=m。令（1）：a[1]≡r[1](mod m),a[2]≡r[2](mod m),a≡r(mod m）（顺序可以不同），因为只有在这种情况下才能保证集合{a1,a2,a3,a4，…am}中的任意2个数不同余，否则必然有2个数同余。由式（1）自然得到集合{a1,a2,a3,a4，…am}对m构成完全剩余系。

引理3．剩余系定理7

设m是一个整数，且m>1，b是一个整数且（m,b)=1。如果a1,a2,a3,a4，…am是模m的一个完全剩余系，则ba[1],ba[2],ba[3],ba[4]，…ba[m]也构成模m的一个完全剩余系。

证明：若存在2个整数ba和ba[j]同余即ba≡ba[j](mod m），根据引理1则有a≡a[j](mod m）。根据完全剩余系的定义和引理4（完全剩余系中任意2个数之间不同余，易证明）可知这是不可能的，因此不存在2个整数ba和ba[j]同余。由引理5可知ba[1],ba[2],ba[3],ba[4]，…ba[m]构成模m的一个完全剩余系。

引理4．同余定理6

如果a,b,c,d是四个整数，且a≡b(mod m),c≡d(mod m），则有ac≡bd(mod m)

证明：由题设得ac≡bc(mod m),bc≡bd(mod m），由模运算的传递性可得ac≡bd(mod m)

二、证明过程：

构造素数p的完全剩余系P={1,2,3,4…（p-1)}，因为（a,p)=1，由引理3可得A={a,2a,3a,4a，…（p-1)a}也是p的一个完全剩余系。令W=1*2*3*4…*(p-1），显然W≡W(mod p）。令Y=a*2a*3a*4a*…（p-1)a，因为{a,2a,3a,4a，…（p-1)a}是p的完全剩余系，由引理2以及引理4可得a*2a*3a*…（p-1)a≡1*2*3*…（p-1)(mod p）即W*a^(p-1）≡W(modp）。易知（W,p)=1，由引理1可知a^(p-1）≡1(modp）

在数论中的地位

费马小定理是初等数论四大定理（威尔逊定理，欧拉定理（数论中的欧拉定理，即欧拉函数），中国剩余定理和费马小定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况（见于词条“欧拉函数”）。

实际应用

如上所述，中国猜测只有一半是正确的，符合中国猜测但不是质数的数被称为“伪质数”。

对于中国猜测稍作改动，即得到判断一个数是否为质数的一个方法：

如果对于任意满足1 < b < p的b下式都成立：

b^(p-1）≡1(mod p)

则p必定是一个质数。

这个定理告诉我们，判定一个数是否为质数，没有必要测试所有的小于p的自然数，只要测试所有的小于p的质数就可以了。事实上，测试小于p的平方根的所有质数就可以了。

这个算法的缺点是它非常慢，但是实现简单；很适合在计算机上面运行程序进行验算一个数是否是质数，不过这种方法并不是实际工程中采用的判定方法。

C语言中实现Miller-Rabin素性判定的算法

#include<cstdio>

#include<cstdlib>

#include<cmath>

bool Btest(int a,int n)

{

int i,d=1,x;

for(i=(int)ceil(log((double)n-1)/log(2.0))-1;i>=0;--i){

x=d;

d=(d*d)%n;

if((1==d)&&(x!=1)&&(x!=n-1))return 1;

if(((n-1)&(1<<i))>0)d=(d*a)%n;

}

return(d!=1);

}

bool Rabin_Miller(int n,int s)

{

int j,a;

for(j=0;j<s;++j){

a=rand()*(n-2)/RAND_MAX+1;

if(Btest(a,n))return false;

}

return true;

}

int main()

{

int a,n;

bool result;

result=Rabin_Miller(a,n);

if (result)

{ printf("yes");}

else

{

printf("No");

}

}

附：若此算法要求以不超过e的概率出错，那么main（）中n的值（测试次数）应为n=lg(1/e)/2向上取整。

Pascal版本的Miller—Rabbin

方法：如果a^(n-1)=1 (mod n) （a为任意<n的正整数）则可近似认为n为素数。这种方法叫做 Miller-Rabbin算法。取多个底进行试验，次数越多概率越大。如取2 3 5 7 11 是在maxlongint范围内只有一组解不能通过。2.5*10^13以内也只有这一个合数！3215031751！这里有很大的问题 对于另一个合数29341，该组数也不能通过，而29341=13×37×61

时间效率分析：取s次不同的底判断时间效率为O(s*log(x））；在maxlongint范围内就是5*31=165；

参考代码如下：

const

c:array[1..5]of longint=(2,3,5,7,11);

function modular_exp(a,p,k:longint):int64;

var t,ans:int64;

begin

t:=a; ans:=1;

while p>0 do

begin

if (p and 1=1) then ans:=((ans mod k)*(t mod k)) mod k;

t:=((t mod k)*(t mod k)) mod k;

p:=p>>1;

end;

exit(ans);

end;

function miller_rabbin(n:longint):boolean;

var

i:longint;

begin

if n=1 then exit(false);

if n in [2,3,5,7,11] then exit(true);

for i:=1 to 5 do

if modular_exp(c[i],n-1,n)<>1 then exit(false);

exit(true);

end;