费马小定理

费尔马小定理即费马小定理。费马小定理是数论中的一个重要定理，其内容为： 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）。即：假如p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1。注意事项：由17世纪法国数学家皮耶·德·费玛提出。它断言当整数n >2时，关于x, y, z的方程 x^n + y^n = z^n 没有正整数解。德国佛尔夫斯克曾宣布以10万马克作为奖金奖给在他逝世后一百年内，第一个证明该定理的人，吸引了不少人尝试并递交他们的“证明”。被提出后，经历多人猜想辩证，历经三百多年的历史，最终在1995年被英国数学家安德鲁·怀尔斯彻底证明。

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

ewr

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

先证明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后面的互素，所以全部是允许的】

费马小定理的证明 一、准备知识： 引理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-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≡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）

费马小定理(Fermat Theory)是数论中的一个重要定理，其内容为： 假如p是质数，且(a,p)=1，那么 a(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

一、准备知识：　　引理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．　　若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)引理3．　　设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).根据完全剩余系的定义可知这是不可能的,因此不存在2个整数ba和ba[j]同余.所以ba[1],ba[2],ba[3],ba[4],…ba[m]构成模m的一个完全剩余系.构造素数的既约剩余系 因为，由引理3可得 也是p的一个既约剩余系。由既约剩余系的性质， 即易知，同余式两边可约去，得到这样就证明了费马小定理。

3^9mod10=27^3mod10=7^3mod10=3mod10 而由费马小定理3^10mod11=1mod11那么3^(3^9)mod11=3^(10k+3)mod11=5mod11

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. 前面那朋友的作法也对,不过好像不是用的费马小定理.

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

洪殊明的费马小定理具体如下：费马小定理(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的一个完全剩余系。

证明一、准备知识： 引理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-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≡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）[编辑本段]费马小定理在数论中的地位 费马小定理是数论四大定理（威尔逊定理，欧拉定理(数论中的欧拉定理，即欧拉函数)，中国剩余定理和费马小定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况（见于词条“欧拉函数”）。

a和p的最大公约数是1

我来拯救你吧。我弄2个证明方法给你看看。第一种设一个比质数p小的正整数a，让a依次乘以1 2 3 ...到p-1,得到a,2a,3a...(p-1)a，而由于a与p互质，每次乘积所得到的余数都不一样，设如果ab与ac同余p（a,b,c均小于p），必定b=c，故若b不等于c，ac与ab不同余,则a到(p-1)a的余数恰好有p-1种，与1到p-1完全能一一对应，于是（p-1的阶乘）同余（a的p-1次方乘以p-1的阶乘），约去p-1的阶乘，就有了a的p-1次方除以p余1。第二种（这种方法其实我自己没法做的，是照书打的，比较巧妙）构造二项式（a+1)^p,因为展开这个二项式，每项都是C(r)(p)（组合数，下标p,上标r)*a^r,只有r等于0或者p的那一项才不被p整除，故（a+1)^p与a^p+1同余p，先归纳假设a^p次方除以p余a（这里别把它看成真理），则p整除a^a-a=a(a^(p-1)-1)，而a与p互质，a整除a^(p-1)-1,由反向的数学归纳法证明出来。

皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求，但是这个要求实际上是不必要的。1736年，欧拉出版了一本名为“一些与素数有关的定理的证明”(拉丁文：Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio)”的论文中第一次提出证明，但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。有些数学家独立制作相关的假说（有时也被错误地称为中国的假说），当成立时，p是素数。这是费马小定理的一个特殊情况。然而，这一假说的前设是错的：例如，341 ，而341= 11×31是一个伪素数。所有的伪素数都是此假说的反例。

费马是神，费马大小定理及费马引理都是对的，证明就设个整数甲，比质数忆乙小 然后用乙减一的接乘乘以甲的乙减一次方，若对乙取模，这个的数与乙减一的接乘同余，就可以了

（1）费马小定理费马小定理的前提条件就是模为质数，且与底数互素。模是质数，再互素，实际上就是不整除了。至于小于，恕我孤陋寡闻，我没见过。下面的问题同样成立：9^1≡1（mod 2），此时9>2啊？（2）绝对伪素数你看看不互素会出现什么情况。不妨使用现今找到的任一伪素数，是不是绝对伪素数都行，10585吧。按理说，存在某个x，使得x^10584≡1（mod 10585）如果不互素，那么对于任意m∈Z都有：10585^m一定是10585的倍数，只能10585^m≡0（mod 10585）那就热闹了……这定义也不要算了……

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

费马大 当整数n >2时，关于x, y, z的方程 x^n + y^n = z^n 没有正整数解费马小 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）。即：假如p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1

费马小定理：如果p是一个素数，a是一个不能被p整除的正整数。则，a^(p-1) 带余数除法 除以p 的余数是1用数论的同余符号表示就是 a^(p-1) = 1(mod p) [这里的等号一般是用三条横线]

定义： , ,若 ,则称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为素数, ,则 证明：

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

矩阵幂满足费马小定理: 思路如下： (ab)p[n]= ab * ((ab)p[n-1])c * ((ab)p[n-2]);递推式子可以这样写;合并后变为(ab)p[n]=(ab)(c*p[n-1]+p[n-2]+1);可以得到p[n]=c*p[n-1]+p[n-2]+1;这样的递推式可以用矩阵乘法得到第n项;这是矩阵乘法的一个应用,给matrix67大神的博客地址可以学习,点这里构造矩阵乘法:p[n]　　　　c    1    1　　　　p[n-1]p[n-1]   =  1   0    0   *  　p[n-2]1　　　　　  0   0    1　　　　　　1然后这中间还有一个问题,就是取模的问题;ab*p[n]%mod=ab*p[n]%(mod-1)%mod;这是根据费马小定理得到的;a(p-1)Ξ1%p;ab*p[n]%mod=ab*p[n]/(mod-1)*(mod-1)+b*p[n]%(mod-1)%mod;令x=b*p[n]/(mod-1)则ab*p[n]%mod=ax*(mod-1)+b*p[n]%(mod-1)%mod=ab*p[n]%(mod-1)%mod;

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

费马小定理是数论中的一个重要定理,其内容为: 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）

费马小定理是数论中的一个重要定理,其内容为:假如p是质数，且(a,p)=1，那么a^(p-1)≡1(modp)

费马小定理是初等数论四大定理（威尔逊定理，欧拉定理（数论中的欧拉定理），中国剩余定理(又称孙子定理)和费马小定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况（即 ，见于词条“欧拉函数”）。卡迈克尔数如上所述，中国猜测只有一半是正确的，符合中国猜测但不是质数的数被称为“伪质数”。更极端的反例是卡迈克尔数：假设a与561互质，则a^560被561除都余1。这样的数被称为卡迈克尔数数，561是最小的卡迈克尔数。Korselt在1899年就给出了卡迈克尔数的等价定义，但直到1910年才由卡迈克尔(Robert Daniel Carmichael)发现第一个卡迈克尔数:561。1994年William Alford 、 Andrew Granville 及 Carl Pomerance证明了卡迈克尔数有无穷多个。

对与p互质的整数a，考虑a,2a,3a...(p-1)a，由p是质数，任何两个的差不被p整除，所以任何两个数模p不同余，即a,2a,3a...(p-1)a是1,2,3..p-1的一个排列。将两组数全相乘，得到a*2a*3a*...*(p-1)a=1*2*3..*(p-1)，整理成(p-1)!*a^(p-1)同余(p-1)!(mod p)。由于(p-1)!和p互质，两遍可以约掉，就有a^(p-1)同余1模p

任何一个质数总能除尽任何几何级数中的某一项减1，且该项的指数是这个给定的质数减1的因子。设 a 是任意一个整数，考虑以它为底的几何级数即 a 的各次方幂构成的数列：a, a2, a3, a4, a5, a6, a7,  .....费马断言，给定任何一个质数 p ，在上述数列中一定能找到一个数 an，它减去 1 后是 p 的倍数，并且 n 是 p - 1 的因子。

mod函数是一个求余函数，其格式为： mod(nExp1,nExp2)，即是两个数值表达式作除法运算后的余数。那么：两个同号整数求余与你所知的两个正数求余完全一样(即两个负整数与两个正整数的算法一样)，即两数取余后返回两数相除的余数。

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