欧拉定理& 费马小定理 - OI Wiki

欧拉定理& 费马小定理. 费马小定理. 若 为素数， ，则 。

另一个形式：对于任意整数 ，有 。

证明. 设一个质数为 ，我们取一个不为 倍数的数 。

跳转至简介比赛相关工具软件语言基础算法基础搜索动态规划字符串数学数据结构图论计算几何杂项专题关于HuluschoolOIWikiOI-wiki/OI-wiki简介简介GettingStarted关于本项目如何参与格式手册F.A.Q.用Docker部署OIWiki镜像站列表致谢比赛相关比赛相关比赛相关简介赛事赛事OI赛事与赛制ICPC/CCPC赛事与赛制题型题型题型概述交互题学习路线学习资源技巧技巧读入、输出优化常见错误常见技巧出题工具软件工具软件工具软件简介代码编辑工具代码编辑工具VimEmacsVSCodeAtomEclipseNotepad++KateDev-C++GeanyXcodeGUIDESublimeText评测工具评测工具评测工具简介ArbiterCenaCCRPlusLemon命令行WSL(Windows10)SpecialJudgeTestlibTestlibTestlib简介通用GeneratorValidatorInteractorCheckerPolygonOJ工具LaTeX入门Git语言基础语言基础语言基础简介C++基础C++基础Hello,World!C++语法基础变量运算流程控制语句流程控制语句分支循环高级数据类型高级数据类型数组结构体指针函数文件操作C++标准库C++标准库C++标准库简介STL容器STL容器STL容器简介迭代器序列式容器关联式容器无序关联式容器容器适配器STL算法bitsetstringpairC++进阶C++进阶类命名空间值类别重载运算符引用常值新版C++特性Lambda表达式pb_dspb_dspb_ds简介堆平衡树C++与其他常用语言的区别Pascal转C++急救Python速成Java速成Java进阶算法基础算法基础算法基础简介复杂度枚举模拟递归&分治贪心排序排序排序简介选择排序冒泡排序插入排序计数排序基数排序快速排序归并排序堆排序桶排序希尔排序锦标赛排序排序相关STL排序应用前缀和&差分二分倍增构造搜索搜索搜索部分简介DFS（搜索）BFS（搜索）双向搜索启发式搜索A*迭代加深搜索IDA*回溯法DancingLinksAlpha-Beta剪枝优化动态规划动态规划动态规划部分简介动态规划基础记忆化搜索背包DP区间DPDAG上的DP树形DP状压DP数位DP插头DP计数DP动态DP概率DPDP优化DP优化单调队列/单调栈优化斜率优化四边形不等式优化状态设计优化其它DP方法字符串字符串字符串部分简介字符串基础标准库字符串匹配字符串哈希字典树(Trie)前缀函数与KMP算法Boyer-Moore算法Z函数（扩展KMP）自动机AC自动机后缀数组(SA)后缀数组(SA)后缀数组简介最优原地后缀排序算法后缀自动机(SAM)后缀平衡树广义后缀自动机后缀树Manacher回文树序列自动机最小表示法Lyndon分解Main-Lorentz算法数学数学数学部分简介符号复数位运算快速幂进位制高精度计算平衡三进制数论数论数论基础素数最大公约数数论分块欧拉函数筛法Meissel-Lehmer算法分解质因数裴蜀定理类欧几里德算法欧拉定理&费马小定理欧拉定理&费马小定理目录费马小定理证明欧拉定理证明扩展欧拉定理证明习题评论乘法逆元线性同余方程中国剩余定理威尔逊定理升幂定理卢卡斯定理拉格朗日定理原根离散对数二次剩余莫比乌斯反演杜教筛PowerfulNumber筛Min_25筛洲阁筛二次域连分数Stern-Brocot树与Farey序列Pell方程多项式与生成函数多项式与生成函数简介代数基本定理拉格朗日插值快速傅里叶变换快速数论变换快速复数论变换快速沃尔什变换ChirpZ变换多项式求逆多项式开方多项式除法|取模多项式对数函数|指数函数多项式牛顿迭代多项式多点求值|快速插值多项式三角函数多项式反三角函数常系数齐次线性递推多项式平移|连续点值平移符号化方法普通生成函数指数生成函数狄利克雷生成函数线性代数线性代数线性代数简介向量矩阵高斯消元特征多项式线性基线性规划线性规划线性规划简介单纯形算法组合数学组合数学排列组合卡特兰数斯特林数贝尔数伯努利数康托展开容斥原理抽屉原理EulerianNumber分拆数群论群论群论简介置换群概率论概率论快速上手基本概念条件概率与独立性随机变量随机变量的数字特征斐波那契数列博弈论博弈论博弈论简介公平组合游戏非公平组合游戏反常游戏牛顿迭代法数值积分分段打表傅里叶-莫茨金消元法序理论杨氏矩阵Schreier–Sims算法Berlekamp-Massey算法数据结构数据结构数据结构部分简介栈队列链表哈希表并查集并查集并查集并查集复杂度堆堆堆简介二叉堆配对堆左偏树块状数据结构块状数据结构分块思想块状数组块状链表树分块SqrtTree单调栈单调队列ST表树状数组线段树李超线段树区间最值操作&区间历史最值划分树二叉搜索树&平衡树二叉搜索树&平衡树二叉搜索树简介TreapSplayWBLTSizeBalancedTreeAVL树替罪羊树笛卡尔树红黑树左偏红黑树跳表可持久化数据结构可持久化数据结构可持久化数据结构简介可持久化线段树可持久化块状数组可持久化平衡树可持久化字典树可持久化可并堆树套树树套树线段树套线段树平衡树套线段树线段树套平衡树树状数组套主席树分块套树状数组K-DTree珂朵莉树动态树动态树LinkCutTreeEulerTourTreeTopTree析合树PQ树手指树霍夫曼树图论图论图论部分简介图论相关概念图的存储DFS（图论）BFS（图论）树上问题树上问题树基础树的直径最近公共祖先树的重心树链剖分树上启发式合并虚树树分治动态树分治AHU算法树哈希矩阵树定理有向无环图拓扑排序最小生成树斯坦纳树最小树形图最小直径生成树最短路拆点差分约束k短路同余最短路连通性相关连通性相关强连通分量双连通分量割点和桥圆方树2-SAT欧拉图哈密顿图二分图最小环平面图图的着色网络流网络流网络流简介最大流最小割费用流上下界网络流Stoer-Wagner算法图的匹配图的匹配图匹配增广路二分图最大匹配二分图最大权匹配一般图最大匹配一般图最大权匹配Prufer序列LGV引理弦图计算几何计算几何计算几何部分简介二维计算几何基础三维计算几何基础极坐标系距离Pick定理三角剖分凸包扫描线旋转卡壳半平面交平面最近点对随机增量法反演变换计算几何杂项杂项杂项杂项简介离散化双指针离线算法离线算法离线算法简介CDQ分治整体二分莫队算法莫队算法莫队算法简介普通莫队算法带修改莫队树上莫队回滚莫队莫队配合bitset分数规划随机化随机化随机函数随机化技巧爬山算法模拟退火悬线法计算理论基础字节顺序约瑟夫问题格雷码表达式求值在一台机器上规划任务主元素问题Garsia-Wachs算法15-puzzleKahan求和专题专题RMQ并查集应用括号序列关于Hulu关于Hulu关于Hulu目录费马小定理证明欧拉定理证明扩展欧拉定理证明习题评论欧拉定理&费马小定理费马小定理若为素数，，则。

另一个形式：对于任意整数，有。

证明设一个质数为，我们取一个不为倍数的数。

构造一个序列：，这个序列有着这样一个性质：证明：又因为每一个都是独一无二的，且得证（每一个都对应了一个)设,则证毕。

也可用归纳法证明：显然，假设成立，那么通过二项式定理有因为对于成立，在模意义下，那么，将带入得得证。

欧拉定理在了解欧拉定理（Euler'stheorem）之前，请先了解欧拉函数。

定理内容如下：若，则。

证明实际上这个证明过程跟上文费马小定理的证明过程是非常相似的：构造一个与互质的数列，再进行操作。

设为模意义下的一个简化剩余系，则也为模意义下的一个简化剩余系。

所以，可约去，即得。

当为素数时，由于，代入欧拉定理可立即得到费马小定理。

扩展欧拉定理（读者可能对第二行是有疑问的。

这一行表达的意思是：如果的话，那么就不能降幂了。

主要是题目中不会太大，而如果，那么自然复杂度是可以接受的。

而如果的话，那么复杂度可能超出预期了，这个时候我们才需要降幂来降低复杂度。

）证明证明转载自synapse7，并进行了一些整理。

命题：的从次，次到次幂模构成的序列中，存在和，使得前个数（即从到)互不相同，从第个数开始，每个数就循环一次。

证明：由鸽巢定理易证。

我们把称为幂次模的循环起始点，称为循环长度。

（注意：可以为）用公式表述为：命题：为素数的情况，该式成立。

证明：若模不能被整除，而因为是一个素数，那么成立，根据欧拉定理，容易证明该式成立。

若模能被整除，那么存在和使得，且成立。

所以根据欧拉定理有。

又由于，所以根据欧拉函数的求值规则，容易得到：，即我们有：。

所以，即，两边同时乘以，得（因为）所以对于中素因子的次数满足：。

我们可以简单变换形式，得到推论：又由于，所以（tips：是素数，最小是，而）。

所以因为，故有：所以即。

命题：为素数的幂的情况，该式成立。

证明：不妨令，是否依然有？答案是肯定的，由命题1可知存在使得，所以，所以令时，我们能有。

此时有关系：且，且，由与的关系，依然可以得到。

合数：为合数的情况，该式成立。

证明：只证拆成两个素数的幂的情况，大于两个的用数学归纳法可证。

设，其中，而的循环长度为；则，由于，那么，所以，；由与的关系，依然可以得到。

证毕。

习题SPOJ#4141"EulerTotientFunction"[Difficulty:CakeWalk]UVA#10179"IrreducibleBasicFractions"[Difficulty:Easy]UVA#10299"Relatives"[Difficulty:Easy]UVA#11327"EnumeratingRationalNumbers"[Difficulty:Medium]TIMUS#1673"AdmissiontoExam"[Difficulty:High]build本页面最近更新：2022/7/1512:54:08，更新历史edit发现错误？想一起完善？在GitHub上编辑此页！people本页面贡献者：Enter-tainer,PeterlitsZo,Acfboy,Dev-XYS,Great-designer,guodong2005,H-J-Granger,hjsjhn,hly1204,Ir1d,MegaOwIer,Menci,sshwy,stevebraveman,tth37copyright本页面的全部内容在CCBY-SA4.0和SATA协议之条款下提供，附加条款亦可能应用评论