费马小定理

[複製鏈接]
39_avatar_small 在線會員 wozuiai13265 發表於 2011-7-21 19:41 | 顯示全部樓層 |閱讀模式
分享到: 更多
求助编辑千科名片 费马
费马小定理是数论中的一个重要定理,其内容为: 假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1(mod p) 假如p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1

目录
费马小定理的历史费马小定理的证明费马小定理在数论中的地位费马小定理的实际应用C语言中实现Miller-Rabin素性判定的算法 费马小定理的历史  皮埃尔•德•费马于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&#91;1&#93;,a&#91;2&#93;,a&#91;3&#93;,a&#91;4&#93;,…a&#91;m&#93;为m个整数,若在这m个数中任取2个整数对m不同余,则这m个整数对m构成完全剩余系。   证明:构造m的完全剩余系(0,1,2,…m-1),所有的整数必然这些整数中的1个对模m同余。取r&#91;1&#93;=0,r&#91;2&#93;=1,r&#91;3&#93;=2,r&#91;4&#93;=3,…r=i-1,1<i<=m。令(1):a&#91;1&#93;≡r&#91;1&#93;(mod m),a&#91;2&#93;≡r&#91;2&#93;(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&#91;1&#93;,ba&#91;2&#93;,ba&#91;3&#93;,ba&#91;4&#93;,…ba&#91;m&#93;也构成模m的一个完全剩余系。   证明:若存在2个整数ba和ba&#91;j&#93;同余即ba≡ba&#91;j&#93;(mod m),根据引理2则有a≡a&#91;j&#93;(mod m)。根据完全剩余系的定义和引理4(完全剩余系中任意2个数之间不同余,易证明)可知这是不可能的,因此不存在2个整数ba和ba&#91;j&#93;同余。由引理5可知ba&#91;1&#93;,ba&#91;2&#93;,ba&#91;3&#93;,ba&#91;4&#93;,…ba&#91;m&#93;构成模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的一个完全剩余系。令麗緻=1*2*3*4…*(p-1),显然麗緻≡麗緻(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)即麗緻*a^(p-1)≡麗緻(modp)。易知(麗緻,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&#91;1..5&#93;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 &#91;2,3,5,7,11&#93; then exit(true);   for i:=1 to 5 do   if modular_exp(c&#91;i&#93;,n-1,n)<>1 then exit(false);   exit(true);   end; 扩展阅读: 1
1.广州大学教研稿
2
2.《奥林姓匹克数学竞赛小丛书-数论》
3
3.《算法导论》
开放分类: 数学,定理,数论,费马猜想 我来完善 “费马小定理”相关词条:
回復

使用道具 舉報

您需要登錄後才可以回帖 登錄 | 註冊

本版積分規則