同余定义

若 a,b 为两个整数，且它们的差 a-b 能被某个自然树 m 所整除，则称 a 就模 m 来说同余于 b，或者说 a 和 b 关于模 m 同余，记为：。它意味着：a-b=m*k(k为某一个整数)。

同余类与剩余系

对于任意a∈[0,m-1]，集合 {a+km}(k属于Z) 的所有数模 m 同余，余数都是 a。该集合称为一个模 m 的同余类，简记为。

模 m 的同余类一共有 m 个，分别为 。它们构成 m 的完全剩余系。

1~m 中与 m 互质的数代表的同余类共有 φ(m) 个，它们构成 m 的简化剩余系。

简化剩余系关于模 m 乘法封闭。这是因为若 a,b(1≤a,b≤m) 与 m 互质，则 a*b 也不可能与 m 含有相同的质因子，即 a*b 也与 m互质。再由余数的定义即可得到 a*b mod m 也与 m 互质，即 a*b mod m 也属于 m 的简化剩余系。

快速幂

根据数学常识，每一个正整数可以唯一表示为若干指数不重复的2的次幂的和。也就是说，如果 b 在二进制表示下有 k 位，其中第 i(0≤i

于是：

所以我们很容易通过 k 次递推求出每个乘积项，当 ci=1 时，把该乘积项累积到答案中。b&1 运算可以取出 b 在二进制表示下的最低位，而 b>>1 运算可以舍去最低位，在递推的过程中将二者结合，就可以遍历 b 在二进制表示下的所有数位 ci。整个算法的时间复杂度为 O(logb)。

题目链接

代码示例

#include
#include
#include
#include
#include
using namespace std;
 
int a,b,p;
 
int power(int a,int b,int p){
	int ans=1;
	for(;b;b>>=1){
		if(b&1) ans=(long long)ans*a%p;
		a=(long long)a*a%p;
	}
	return ans;
}
 
int main(){
	cin>>a>>b>>p;
	cout<"^"<" mod "<"="<<power(a,b,p)<
}

费马小定理

若 p 是质数，则对于任意整数 a，有。

欧拉定理

若正整数 a,n 互质，则 ，其中 φ(n) 为欧拉函数

当 p 是质数时，φ(p)=p-1，并且只有 p 的倍数与 p 不互质。所以，只要 a 不是 p 的倍数，就有，两边同乘 a 就是费马小定理。另外，若 a 是 p 的倍数，费马小定理显然成立

欧拉定理的推论

若正整数 a,n 互质，则对于任意正整数 b，有 

许多计数类的题目要求我们把答案对一个质数 p 取模然后输出。面对 a+b,a-b,a*b 这样的算式，可以在计算前先把 a,b 对 p 取模。面对乘方算式，根据欧拉定理的理论，可以先把底数对 p 取模、指数对 φ(p) 取模，再计算乘方。

特别地，当 a,n 不一定互质且 b>φ(n) 时，有 。这意味着即使底数和模数不互质，我们也有办法把指数的规模缩小到容易计算的范围内。上式可以通过寻找  的指数循环节证明。