费马小定理(易懂)_四年rain的博客_什么易懂

费马小定理：

内容：

若存在整数 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://javaforall.cn/198605.html原文链接：https://javaforall.cn