费马小定理(易懂)

费马小定理(易懂)费马小定理:内容:若存在整数a,p且gcd(a,p)=1,即二者互为质数,则有a^(p-1)≡1(modp)。(这里的≡指的是恒等于,a^(p-1)≡1(modp)是指a的p-1次幂取模与1取模恒等)(不理解的话请留言)证明:这里证明较为复杂需要先引出两个定理:引理一:若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当a·c≡b·c(modm)时,有...

费马小定理:

内容:

若存在整数 a , p 且gcd(a,p)=1,即二者互为质数,则有a^(p-1)≡ 1(mod p)。(这里的 ≡ 指的是恒等于,a^(p-1)≡ 1(mod p)是指a的p-1次幂取模与1取模恒等)(不理解的话请留言)

证明:

这里证明较为复杂需要先引出两个定理:

引理一:

若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当a·c≡b·c(mod m)时,有a≡b(mod m)。
  证明:a·c≡b·c(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)

引理二:

设m是一个整数且m>1,b是一个整数且(m,b)=1。如果a[1],a[2],a[3],a[4],…a[m]是模m的一个完全剩余系,则b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]也构成模m的一个完全剩余系。
  证明:若存在2个整数b·a[i]和b·a[j]同余即b·a[i]≡b·a[j](mod m)…(i>=1 && j>=1),根据引理1则有a[i]≡a[j](mod m)。根据完全剩余系的定义可知这是不可能的,因此不存在2个整数b·a[i]和b·a[j]同余。
所以b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]构成模m的一个完全剩余系。
构造素数 的完全剩余系
p={1,2,3,…,p-1}.
因为 ,由引理2可得
A={a,2a,3a,…,(p-1)a}.
也是p的一个完全剩余系。由完全剩余系的性质,
1*2*3*…*(p-1)≡a*2a*3a*…*(p-1)a(modp).

(p-1)!≡(p-1)!*a^(p-1)(modp)
易知 ((p-1)!,p)=1,同余式两边可约去(p-1)!,得到
a^(p-1)≡1(modp)
这样就证明了费马小定理。
(上述证明摘自百度百科,博主认为,有兴趣可以自己仔细思考证明一下,没兴趣的话记住定理内容并灵活运用即可。(巨巨勿喷,Orz));

费马小定理历史:

皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求,但是这个要求实际上是不必要的。
1736年,欧拉出版了一本名为“一些与素数有关的定理的证明”(拉丁文:Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio)”的论文中第一次提出证明,但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。
有些学家独立制作相关的假说(有时也被错误地称为中国的假说),当成立时,p是素数。这是费马小定理的一个特殊情况。然而,这一假说的前设是错的:例如,341 ,而341= 11×31是一个伪素数。所有的伪素数都是此假说的反例。
如上所述,中国猜测仅有一半是正确的。符合中国猜测但不是素数的数被称为伪素数。
更极端的反例是卡迈克尔数: 假设a与561互质,则 a560被561除都余1。这样的数被称为卡迈克尔数数,561是最小的卡迈克尔数。Korselt在1899年就给出了卡迈克尔数的等价定义,但直到1910年才由卡迈克尔(Robert Daniel Carmichael)发现第一个卡迈克尔数:561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡迈克尔数有无穷多个。
(为了表示对大师的敬意,可以了解一下(摘自百度百科))。

总结:

为什么要写这篇博客呢?,额~~还要从前几天做题碰到的中国剩余定理开始说,本来只想着学会中国剩余定理,可是发现,(可由下面的导图说明)

中国剩余定理-----》拓展欧几里得是啥来??----》终于看懂exgcd啦-----》除法逆元咋求来??----》由费马小定理易知a%m的逆元是a^(m-2)%m----》费马小定理是啥来-----》啊~~~
终于到头啦,自己实在是太菜啦

不过也看清楚一个道理,知识都是相连的,学好一个知识点不要怕累,都怪自己太懒就行啦(QAQ)。

告诫:

为了珍视你的人,请努力!!!

架构君码字不易,如需转载,请注明出处:https://javajgs.com/archives/209708
0

发表评论