整数（integers）
零和正整数统称为自然数。-1、-2、-3、…、-n、…（n为非零自然数）为负整数。正整数、零与负整数构成整数。
因数
又称约数，假设a/b=c（a、b、c都是整数），那么我们称b和c就是a的因数。整数a除以整数b(b≠0) 除得的商c正好是整数而没有余数，我们就说a能被b整除，或b能整除a。
a称为b的倍数，b称为a的约数。12=2·2·3，2和3就是12的因数。把一个式子以12=2·2·3的形式表示，叫做分解因数（或叫因数分解）。
质数（prime number）
又称素数，有无限个。除了 1 和它本身以外没有其他因数；最小的质数是2，1不属于质数
质因数
又称素因数或质因子，就是一个数的约数，并且是质数，比如8=2·2·2，2就是8的质因数。12=2·2·3，2和3就是12的质因数。把一个式子以12=2·2·3的形式表示，叫做分解质因数。
mod运算(求模运算)
mod运算，即求余运算，是在整数运算中求一个整数n除以另一个整数p的余数的运算
例如：7 mod 3 = 1
给定一个正整数p，任意一个整数n，一定存在等式
n = kp + r 其中k、r是整数，且 0 ≤ r < p，称呼k为n除以p的商，r为n除以p的余数。
如果两个数a、b满足a mod p = b mod p，则称他们模p相等，记做
$$a \equiv b\ mod\ p$$
求模主要的分配律
((a +b)mod p · c) mod p = ((a · c) mod p + (b · c) mod p) mod p
(a·b) mod c=(a mod c * b mod c) mod c
(a+b) mod c=(a mod c+ b mod c) mod c
(a-b) mod c=(a mod c- b mod c) mod c
互质
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
关于互质关系，不难得到以下结论：
1. 任意两个质数构成互质关系，比如13和61。
2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
4. 1和任意一个自然数是都是互质关系，比如1和99。
5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。
6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。
7. 两个数互质，那么它们最大公约数是1，最小公倍数是这两数的乘积。欧拉函数
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）计算这个值的方法就叫做欧拉函数，以 φ(n) 表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(8) = 4。
欧拉函数的通式为：
$$\phi (n) = n (1-\frac{1}{p1}) (1-\frac{1}{p2}) ... (1-\frac{1}{pr})$$
其中p1, p2……pr为n的所有质因数，n是不为0的整数。
8的质因子只有2，所以 $$\phi (8) = 8 (1-\frac{1}{2})$$
下面我们就来推到下这个公式
第一种情况
如果n=1，则:
$$\phi (1) = 1$$
因为1与任何数（包括自身）都构成互质关系。
第二种情况
如果n是质数，则:
$$\phi (n) = n-1$$
因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
第三种情况
若n是质数p的k次幂，即 n = p^k (p为质数，k为大于等于1的整数)，则:
$$\phi (n) = \phi (p^{k}) = p^{k} - p^{k-1} = p^{k}(1-\frac{1}{p})$$
比如 $$\phi (8) = \phi (2^{3}) = 2^{3}-2^{2} = 2^{3}(1-\frac{1}{2}) = 4$$
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1·p、2·p、3·p、...、p^(k-1)·p，把它们去除，剩下的就是与n互质的数。这里有些
难理解，读多几篇，用笔写写。
第四种情况
如果n可以分解成两个互质的整数之积，n = p1 · p2，则:
$$\phi (n) = \phi (p1p2) = \phi (p1)\phi (p2)$$
即积的欧拉函数等于各个因子的欧拉函数之积。比如 $$\phi (56) = \phi (7·8) = \phi (7)·\phi (8) = 6·4 = 24$$
第五种情况
因为任意一个大于1的正整数，都可以写成一系列质数的积。
$$n = p1^{k1} p2^{k2} ... pr^{kr}$$
根据第4条的结论，得到:
$$\phi (n) = \phi (p{1}^{k1}) \phi (p{2}^{k2})...\phi (p{r}^{kr})$$
再根据第3条的结论，得到:
$$\phi (n) = p1^{k1} p2^{k2} ... pr^{kr} (1-\frac{1}{p1}) (1-\frac{1}{p2}) ... (1-\frac{1}{pr})$$
也就等于
$$\phi (n) = n (1-\frac{1}{p1}) (1-\frac{1}{p2}) ... (1-\frac{1}{pr})$$
这就是欧拉函数的通用计算公式。比如，1323的欧拉函数，计算过程如下：
$$\phi (1323) = \phi (3^{3}7^{2}) = 1323(1-\frac{1}{3})(1-\frac{1}{7}) = 75$$
欧拉定理
欧拉定理表明，若n,a为正整数，且n,a互质，则:
$$a^{\phi (n)} \equiv 1(mod\ n)$$
或者写成
$$1 \equiv a^{\phi (n)}(mod\ n)$$
也就是说，a的φ(n)次方除与n的余数为1。或者说，a的φ(n)次方减去1，可以整除n。
$$a^{\phi (n)}\ \%\ n = 1$$
$$(a^{\phi (n)}-1)\ \%\ n = 0$$
比如，3和7互质，而7的欧拉函数φ(7)=6，所以3的6次方（3^6=729）减去1，可以整除7
$$3^{\phi (7)}\ \%\ 7 = 1$$ $$729\ \%\ 7 = 1$$
费马小定理
假设正整数a与质数p互质，根据欧拉第二种情况，φ(p)=p-1，则此处欧拉定理可以写成：
$$a^{p-1} \equiv 1(mod\ p)$$
模反元素
如果两个正整数a和n互质，那么一定可以找到整数b，使得ab-1被n整除，或者说ab被n除的余数为1。
$$ab \equiv 1(mod\ n)$$
这时，b就是a的模反元素。
比如，3和11互质，那么3的模反元素就是4，因为 (3 · 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍(k)都是3的模反元素 {...,-18,-7,4,15,26,...}，即如果b是a的模反元素， 则 b+kn 都是a的模反元素。
欧拉定理可以用来证明模反元素必然存在。
$$a^{\phi (n)} = a·a^{\phi (n)-1}$$ $$a^{\phi (n)} \equiv 1(mod\ n)$$ 所以 $$a·a^{\phi (n)-1} \equiv 1(mod\ n)$$
幂取模的算法
由于一个整数的指数结果非常大，可能远远超出计算机处理范围，所以需要简化计算方式。这里采用快速取模算法。原理如下例子：
4^5 mod 3
= (4^2·4^2·4) mod 3
= ((4^2 mod 3)·(4^2 mod 3)·(4 mod 3)) mod 3 //求模主要的分配律
= (1·1·1) mod 3
= 1 mod 3
= 1快速幂算法依赖于以下明显的公式：
b是偶数
$$a^{b}\ mod\ c = ((a^{2})^{b/2})\ mod\ b$$
b是奇数
$$a^{b}\ mod\ c = ((a^{2})^{b/2}·a)\ mod\ b$$
C语言实现
//快速幂取模 a^b mod c
int
PowerMod(int a, int b, int c) {
int ans = 1;
a = a%c;
while(b > 0) {
if(b%2 == 1) {
ans = (ans*a)%c;
}
b = b/2;
a = (a*a)%c;
}
return ans;
}本算法的时间复杂度为O(logb)