费马小定理

5的12次方除以11，余数是是35x5=25=2x11+35x5x5=125=11x11+43x4=12=11+1所以5的5次方除以11，余数是1

大于 3 的质数被 3 除余 1 或 2 ，因此 3|(p+q)(p-q) ，也即 p^2≡q^2(mod 3) 。又因为 (2k+1)^2=4k^2+4k+1=4k(k+1)+1 ，因此奇数的平方被 8 除余 1 ，所以，p^2≡q^2≡1(mod 8) ，而（3，8）=1 ，所以，p^2≡q^2(mod 24) 。

这个定理逆命题似乎不成立，没办法判断质数。

先证明Zn里满足（a,n)=1的所有元素的集合在乘法下构成一个群G。不妨设a,b∈G，由(a,n)=1,(b,n)=1推出(ab,n)=1,即ab∈G，乘法是闭的。剩余类乘法是结合的。显然1是单位元。又（a,n)=1，所以存在整数s,t使as+nt=1,则as=1(n),且(s,n)=1故a-1=s∈G，这样G是一个群，且o(G)=φ(n)。根据Lagrange定理，当(a,n)=1时有a^φ(n)=1(mod n)。特别地，n为素数p时，φ(p)=p-1,所以a^(p-1)=1(mod p),两边同时乘以a得a^p=a(mod p) (1)若p整除a,则(1)显然成立。证毕。

11^5 = 1 (mod 6) 【费马小定理 且 6和11互素】所以 11^10 = 1(mod 6) 所以 11^11 = 11 = 5 (mod 6)11^11 = 6k+511^6 = 1 (mod 7) 【费马小定理 且 11和7互素】所以 11^6k = 1 (mod 7)所以 11^(11^11) = 11^(6k+5) = 11^5 (mod 7)11 = 4 (mod 7)所以 11^5 = 4^5 (mod 7) 4^5 = 2^10 = 32^2 而 32= 4 (mod 7)所以 32^2 = 16 = 2 (mod 7)综上 11^(11^11) = 2 (mod 7)【上述过程中涉及的被除数的次数+1 都跟mod后面的互素，所以全部是允许的】

只需证明在Ip中[a^p]=[a]。如果[a]=[0],则[a^p]=[a]^p=[0]=[a].如果[a]!=[0],[a]属于Ip*,它是Ip中非零元素的乘法群。因|Ip*|=p-1,由拉格朗日定理的推论：如果G是有限群，a属于G，则a的阶是|G|的因数。[a]^(p-1)=[1].乘[a]可得要求证明的结果[a^p]=[a]^p=[a].所以a^p和a关于p同余。

（m,c)是求m和c的最大公约数，最大公约数等于1就是说这两个数互质。

费马小定理，欧拉定理，中国剩余定理等相关数论定理是小学生学的。在数论中，欧拉定理是一个关于同余的性质。欧拉定理得名于瑞士数学家莱昂哈德·欧拉，该定理被认为是数学世界中最美妙的定理之一。

[编辑本段]费马小定理 费马小定理是数论中的一个重要定理,其内容为: 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）[编辑本段]费马小定理的历史 皮埃尔u2022德u2022费马于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(modm)时，有a≡b(modm) 证明：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-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)，根据引理2则有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≡bc(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可知A中所有元素必然满足a≡1(mod p),2a≡2(modp),…(p-1)a≡p–1(mod p)。由引理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的质数就可以了。 这个算法的缺点是它非常慢，运算率高；但是它很适合在计算机上面运行程序进行验算一个数是否是质数。

洪殊明的费马小定理具体如下：费马小定理(Fermat"s little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求，但是这个要求实际上是不必要的。当成立时，p是素数。这是费马小定理的一个特殊情况。然而，这一假说的前设是错的：例如，341，而341= 11×31是一个伪素数。所有的伪素数都是此假说的反例。如上所述，中国猜测仅有一半是正确的。符合中国猜测但不是素数的数被称为伪素数。设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的一个完全剩余系。

　　费马点发现者　　费马　　费马(Fermat，Pierre de Fermat) (1601～1665）法国数学家，被誉为“业余数学家之王。”费马（也译为“费尔马”）1601年8月17日出生于法国南部图卢兹附近的博蒙·德·洛马涅。他的父亲多米尼克·费马在当地开了一家大皮革商店，拥有相当丰厚的产业，使得费马从小生活在富裕舒适的环境中。 图卢兹　　费马点定义　　在一个三角形中，到3个顶点距离之和最小的点叫做这个三角形的费马点。 (1)若三角形ABC的3个内角均小于120°，那么3条距离连线正好平分费马点所在的周角。所以三角形的费马点也称为三角形的等角中心。 (2)若三角形有一内角不小于120度，则此钝角的顶点就是距离和最小的点。　　编辑本段费马点的判定　　（1）对于任意三角形△ABC，若三角形内或三角形上某一点E,若EA+EB+EC有最小值,则E为费马点。 费马点的计算　　（2）如果三角形有一个内角大于或等于120°，这个内角的顶点就是费马点；如果3个内角均小于120°，则在三角形内部对3边张角均为120°的点，是三角形的费马点。　　编辑本段证明　　我们要如何证明费马点呢： 费马点证明图形　　(1)费马点对边的张角为120度。 △CC1B和△AA1B中,BC=BA1,BA=BC1,∠CBC1=∠B+60度=∠ABA1, △CC1B和△AA1B是全等三角形,得到∠PCB=∠PA1B 同理可得∠CBP=∠CA1P 由∠PA1B+∠CA1P=60度，得∠PCB+∠CBP=60度,所以∠CPB=120度 同理,∠APB=120度，∠APC=120度 (2)PA+PB+PC=AA1 将△BPC以点B为旋转中心旋转60度与△BDA1重合，连结PD，则△PDB为等边三角形，所以∠BPD=60度 又∠BPA=120度，因此A、P、D三点在同一直线上， 又∠CPB=∠A1DB=120度，∠PDB=60度，∠PDA1=180度，所以A、P、D、A1四点在同一直线上，故PA+PB+PC=AA1。 (3)PA+PB+PC最短 在△ABC内任意取一点M（不与点P重合），连结AM、BM、CM，将△BMC以点B为旋转中心旋转60度与△BGA1重合，连结AM、GM、A1G(同上)，则AA1<A1G+GM+MA=AM+BM+CM.所以费马点到三个顶点A、B、C的距离最短。 平面四边形费马点 平面四边形中费马点证明相对于三角型中较为简易，也较容易研究。 （1）在凸四边形ABCD中，费马点为两对角线AC、BD交点P。 费马点　　（2）在凹四边形ABCD中，费马点为凹顶点D（P）。 经过上述的推导，我们即得出了三角形中费马点的找法： 当三角形有一个内角大于或等于一百二十度的时候，费马点就是这个内角的顶点；如果三个内角都在120度以内，那么，费马点就是使得费马点与三角形三顶点的连线两两夹角为120度的点。　　编辑本段费马点性质：　　费马点　　（1）平面内一点P到△ABC三顶点的之和为PA+PB+PC，当点P为费马点时，距离之和最小。 特殊三角形中： (2).三内角皆小于120°的三角形，分别以 AB,BC,CA，为边，向三角形外侧做正三角形ABC1,ACB1,BCA1,然后连接AA1,BB1,CC1,则三线交于一点P,则点P就是所求的费马点. (3).若三角形有一内角大于或等于120度,则此钝角的顶点就是所求. (4)当△ABC为等边三角形时,此时外心与费马点重合！！！

Fermat-欧拉定理a^f(n)=1 (modn)n=15=3*5 (没有必要15是素数, 3和5是素数 )f(15)=15(1-1/3)(1-1/5) =81025=127*8 93^1025=3^(8*127 9)=((3^8)^127 )*3^9 3^1025 mod15=((3^8)^127 )*3^9 mod15=1^127 *3^9 mod15=3^9 mod15=19683 mod15=33^1025 mod15=3

2^5432675=(2^12)^452722*(2^11) 由费马小定理知2^12 mod 13为1,则(2^12)^452722 mod 13为1 2^12 和14 mod 13 同余,则2^11和7 mod 13 同余,说明2^11 mod 13为7 则2^5432675 mod 13为1*7=7. 前面那朋友的作法也对,不过好像不是用的费马小定理.

题主是否想询问“费马大定理什么时候学”？八年级下学期。根据查询相关课本内容显示，费马大定理八年级下学期学。1994年10月，美国普林斯顿大学数学教授安德鲁·怀尔斯，终于圆了童年的梦想，证明了费马大定理。

定义： , ,若 ,则称a与b模m同余,记作 ,否则称a与b模m不同余,记作 利用同余,可在整数集合Z上诱导出一个关系 ,称为模m同余关系 定理： ,则模m同余关系是等价关系,即 (1) ,有 (2) (3) 注： 1.模m同余关系的商集记作 2.任一整数a所在的同余类记作 ,也称为同余类或剩余类 3.任一整数a用m除所得的余数只能为 中的一个, 为模m的完全剩余类,其中 为那些除m所得的余数为i的所有整数构成的集合 定理： , ,则 1.若 ,则2. 3. 4.若 ,d为a,b,m的任一公因数,则5.若 ,则6. 7. 证明： 3. 定义： , ,若其中任意两个数均不在模m的同一个剩余类中,则称 为模m的一个完全剩余系 若 中有某个数与m互素,则 中所有的数与m均互素,此时称 为与模m互素的一个剩余类,因而有 个与模m互素的剩余类,在与模m互素的每个剩余类中取一个数,得到 个与模m互素的数,它们组成的集合称为模m的一个缩系 定理：若 ,则 为模m的一个缩系 且 ,有 定理：若 ,且 ,则当x与y分别跑遍模m的一个完全剩余系时, 恰好跑遍模mn的一个完全剩余系 证明：定理：若 且 ,则当 分别跑遍模m,n的一个缩系时, 恰好跑遍模mn的一个缩系, 证明：推论：设 ,则定理：设 , ,则 证明：在实际应用中经常要计算 模m的值,利用欧拉定理,先计算 ,其中 ,即 ,即 ,从而简化运算 推论：若p为素数, ,则 证明：

2^5432675=(2^12)^452722*(2^11)由费马小定理知2^12 mod 13为1，则(2^12)^452722 mod 13为12^12 和14 mod 13 同余，则2^11和7 mod 13 同余，说明2^11 mod 13为7则2^5432675 mod 13为1*7=7。 前面那朋友的作法也对，不过好像不是用的费马小定理。

费马小定理可以看做是Euler定理的一个推论,Euler定理中的n不要求是素数,而x的指数是φ(n).费马定理中n换成了素数p,而φ(p)=p-1,所以,就这样了. 不是素数当然不行.随便举个例子试试呗.

关于费马小定理数论的证明：mod的简单介绍 (Congruence) a=b(mod m) a和b除以m以后有相同的余数不失一般性地另a>b 则a=km+b比如7=1 mod 2 9=4 mod 5 简单的Congruence 计算 如果a=b mod m c=d mod m 则a=km+b c=tm+d直接可推出 a+b=c+d (mod m) a-b=c-d (mod m) ab=cd (mod m)并且可得存在正整数c 使得ac=bc (mod mc) 当然ac=bc(mod m)费马小定理 如果a,p互质 且q是质数 则a^(p-1)=1 (mod p) 考虑数列An= a,2a,3a,4a…… (p-1)a假设An中有2项ma, na 被p除以后的余数是相同的.那么必然有ma=na (mod p)即a(m-n)=0(mod p) 由于a和p互质,所以m-n=0(mod p) 但是m,n属于集合{1,2,3..p-1}且m不等于n,所以m-n不可能是p的倍数.和假设产生矛盾 所以An中任意2项被p除得到的余数都是不同的, 并且对于任一个整数被p除以后的余数最多有p-1个,分别是1,2,3,….p-1 而数列An中恰好有p-1个数,所以数列中的数被p除以后的余数一定正好包含所有的1,2,3,4,5…. p-1 由此我们可以用Congruence的乘法性质,a*2a*3a*…(p-1)a=1*2*3*4..*(p-1) (mod p)对两边进行化简,即可以得到a^(p-1)=1 (mod p)Euler"s Totient function定义o(n)是所有比n小且和n互质的数的总数(包括1) 例如o(5)=4 o(10)=8我们发现引入这个以后费马小定理可以改写为a^o(p)=1 (mod p)事实上,这个结论对所有的正整数n都成立 即a^o(n)=1 (mod n)证明过程其实和前面的证明类同.只需考虑数列An=b1*a,b2*a,b3*a…bo(n)*a其中数列b1,b2…bo(n) 表示比n小且和n互质的数.其余证明皆相似掌握了a^o(n)=1 (mod n)以后,最后一个问题就是如何计算o(n)显然n是质数时 o(n)=n-1 n=p^k, p为质数,k为非负整数时 o(n)=p^k-p^(k-1)因为只有p,2p,3p..p^(k-1)p这些和p^k有共因数.这里面共有p^(k-1)个数所以o(p^k)=p^k-p^(k-1)最后证明o(mn)=o(m)*o(n)当m,n互质时考虑数列Am A1,A2,A3…Ao(m) 数列Bn B1,B2,B3…Bo(n)因为m,n互质所以我们总能找到c,d使得cm=1 (mod n) dn=1 (mod m)考虑Emn=Am*dn+Bn*cm 这里 显然cm能被m 整除, 所以Emn=Am*dn(mod m)=Am (mod m)所以Emn和m互质 同样可以证明Emn和n互质所以Emn和mn也互质而对于Emn<mn 我们可以理解Emn是比mn小且和mn互质的整数如果Emn>mn 我们可以通过减去k倍的mn(不影响其性质),同样得到比mn小和mn互质的整数 并且如果Am, Bn变换时Emn也会变换 而Am,Bn总共变化可以有o(m)*o(n)种所以o(mn)=o(m)o(n)

2^5432675=(2^12)^452722*(2^11) 由费马小定理知2^12 mod 13为1,则(2^12)^452722 mod 13为1 2^12 和14 mod 13 同余,则2^11和7 mod 13 同余,说明2^11 mod 13为7 则2^5432675 mod 13为1*7=7. 前面那朋友的作法也对,不过好像不是用的费马小定理.

(a , p) = 1 说明 a 和 p 的最大公约数是 1也就是说 a 和 p 互质

费马小定理是数论中的一个定理,其内容为:假如a是一个整数，p是一个质数的话，那么 <math>a^p equiv a p mod</math>假如a不是p的倍数的话，那么这个定理也可以写成 <math>a^ equiv 1 p mod</math> 。（符号的应用请参见模运算） 皮埃尔u2022德u2022费马于1636年发现了这个定理，在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个质数的要求，但是这个要求实际上是不存在的。与费马无关的有一个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当当2p=2(mod p)，p才是一个质数。 假如p是一个质数的话，则2p = 2(mod p)成立（这是费马小定理的一个特殊情况）是对的。但反过来，假如2p = 2(mod p)成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。因此整个来说这个猜想是错误的。一般认为中国数学家在费马前2000年的时候就已经认识中国猜测了，但也有人认为实际上中国猜测是1872年提出的，认为它早就为人所知是出于一个误解。关于费马定理证明 假如a 差不能被p整除的话 ， 那么假如x>0和x和p的最 大 公约数为1的话(a,p互素) ， 则xu2022a与xu2022a 的差也不能被n整除(也就是说x.a,x.a,.....(p-1).a 不是模n同余的)。取A为所有小于p 的整数的集（A中的数都不能被p整除），B为A中所有元素除以a所获得的数集。任何两个A 的元素的差都不能被p整除而又有相同的余数，由此任何两个B中的元素的差也无法被p整除。由此 可得 而试图在p-1个元素里取p-1个不同的元素，则必定是相同的则A集合中元素的乘积，和B集合中元素的乘积一定是模p同余的即 1.a ×2.a x×3.a......(p-1).a=1×2×3×4......×（p-1)(mod p)(p-1)!=ap-1(p-1)!(mod p)在这里W=1u20222u20223u2022...u2022(p-1)。(威尔逊定理）由于gcd((p-1),p)=1,两边同除以(p-1)!,即可得到费马小定理

费马小定理：如果p是一个素数，而a是任何不能被p整除的整数，那么p能除a - 1。这个由皮埃尔·德·费马在1640年发现的数字性质，本质上是说，取任意素数p和任意不能被该素数整除的数a，假设p = 7, a = 20。通过费马小定理，我们发现：费马小定理通常用来检验一个数是否是素数，是素数的必要非充分条件。然而满足费马小定理检验的数未必是素数，这种合数叫做卡迈克尔数（Carmichael Number），最小的卡迈克尔数是561【A002997】

费马小定理是数论中的一个重要定理，在1636年提出，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p），例如：假如a是整数，p是质数，则a,p显然互质(即两者只有一个公约数1)，那么我们可以得到费马小定理的一个特例，即当p为质数时候， a^(p-1)≡1(mod p)。费马小定理是初等数论四大定理（威尔逊定理，欧拉定理（数论中的欧拉定理），中国剩余定理(又称孙子定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况。

1、费马小定理(Fermats little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。 2、皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求，但是这个要求实际上是不必要的。