1.gcd与exgcd
欧几里得算法：
(gcd(a, b) = gcd(b, a mod b))
(code:)
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
扩展欧几里得算法：
(ax + by = gcd(a, b)(a > 0, b > 0))
若(a < 0), 可把符号转移到(x')中，令(x = x')。
令(d=gcd(a,b))，对于一组不定方程(ax+by=c)，有解当且仅当(d | c)。
对于这组不定方程，我们可以先求出(ax_0 + by_0 = d)，得到一组解(x_0,y_0)，同时乘上(frac {c} {d})，即得到一组原方程的解。(exgcd)函数返回的值，是(gcd(a,b))。
(code:)
int exgcd(int a, int b, int &x, int &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
int gcd = exgcd(b, a % b, x, y), t;
t = x;
x = y;
y = t - a / b * y;
return gcd;
}
对于这组不定方程的通解，可以表示为：
(x = x cdot frac {c}{d} + t cdot frac {b}{d}, y = y cdot frac {c}{d} - t cdot frac {a}{d}.)
其中(t)的取值在整数集合里。
2.欧拉函数及欧拉定理
欧拉函数
欧拉函数(( phi (n)))：表示([1,n-1])中与(n)互质的整数的个数。
一些定理
(1.) 若(n)为质数，则(phi(n) = n - 1).
证明：显然。
(2.)若(n)为一个质数(p)的幂次方，表示为(p ^ a)，则(phi(p^a) = (p-1) cdot p^{a-1}).
证明：
小于等于(p^a)的正整数一共有(p^a - 1)个，对于那些可以被(p)整除的数可以表示为(pcdot t)，其中(t=(1,2,cdots, p^{a-1}-1 )),共有(p^{a-1}-1)个数。所以不能被整除的数的个数，即(phi(p^a)=p^a-1-(p^{a-1}-1)=p^a-p^{a-1} = (p-1) cdot p^{a-1}.)
(3.)若(a,b)互质，则(phi(a cdot b)= phi(a) cdot phi(b)).
证明：
根据(phi(n))的通项公式易证。
(4.)若(a|b)，则$ phi(a cdot b)=a cdot phi(b)$.
证明：
根据(phi(n))的通项公式易证。
欧拉函数的通项公式
设(n =prod _{i=1}^{k}p_i^{ai})为(n)的质数幂乘积，则(phi(n) = n cdot prod_{i = 1}^{k}(1- frac{1}{p_i}).)
证明：
各质数幂之间显然互质，根据上面的定理，即可表示出：
(phi(n) = phi(p_{1}^{a_1}) imes phi(p_{2}^{a_2}) imesphi(p_{3}^{a_3}) imes cdots imes phi(p_{k}^{a_k}))
(=(p_{1}^{a_1} - p_{1}^{a_1 - 1}) imes (p_{2}^{a_2} - p_{2}^{a_2 - 1}) imes(p_{3}^{a_3} - p_{3}^{a_3 - 1}) imes cdots imes(p_{k}^{a_k} - p_{k}^{a_k - 1}))
(= p_1^{a_1} imes p_2^{a_2} imes p_3^{a_3} imes cdots imes p_{k}^{a_k} imes (1-frac{1}{p_1}) imes (1-frac{1}{p_2}) imes(1-frac{1}{p_3}) imes cdots imes (1-frac{1}{p_k}).)
$ = n imes (1-frac{1}{p_1}) imes (1-frac{1}{p_2}) imes(1-frac{1}{p_3}) imes cdots imes (1-frac{1}{p_k}).$
欧拉定理
若(a)与(p)互质，则(a^{phi{(p)}} equiv 1(mod p).)
一些定理
(1.)若(b,p)互质，则(a^b mod p = a^{b mod phi(p)} mod p.)
证明：
由欧拉定理，则：
(a^b mod p =frac{a^b}{a^{phi(p)}} mod p = a^{b mod phi(p)} mod p.)