0、欧几里德定理
一切的基础，自然就是欧几里德定理了。它的形式非常简单（sometimes naive）
gcd(a,b)=gcd(b,a mod b)
证明：
假设a,b的公约数为g,且$${a}={bx+y}{(x,y\in Z)}$$
则显然有$${g \mid a},\qquad {g \mid b},\qquad{{a}\ mod\ {b}}={y}$$
$${\because g \mid b}$$
$${\therefore g \mid bx}$$
又$${\because g \mid a}$$
$${\therefore g \mid {(a-bx)}}$$
即$${g \mid y}$$
即$${g \mid {{a}\ mod\ {b}}}$$
故g是b和a mod b的公约数
即（a，b）和（b，a mod b）的公约数是相同的，所以它们的最大公约数也是相同的。
- 欧几里德算法
又名"辗转相除法"，是目前求最大公约数的通用算法，实现简单功能强大。（代码可以说是很漂亮了）
原理正是欧几里德定理，话不多说上代码：
int gcd(int x, int y){return y ? gcd(y, x%y) : x;}时间复杂度：由于a mod b必然小于，上一次的b变成a，上一次的a mod b变成b，故最差情况也是O(log n)的。
- Bezout定理
在介绍扩展欧几里德定理之前，首先需要介绍一下Bezout定理（贝祖定理，裴蜀定理）。
Bezout定理：若${ax+by=z}$，则有$${gcd(a,b)}\mid{z}$$
Bezout定理拓展：若${a_1x_1+a_2x_2+...+a_nx_n}=z$，则有$${gcd(a_1,a_2,...,a_n)}\mid{z}$$
- 扩展欧几里德算法
扩展欧几里德算法十分强大，可以用来求二元一次方程的通解。
显然当 $b=0$，$gcd(a,b)=a$。此时 $x=1，y=0$
当$a>b>0$ 时
设 $$ax_1+by_1=gcd(a,b)$$
$${bx_2}+{({a}\ mod\ {b})y_2}={gcd(b,{a}\ mod\ {b})}$$
由欧几里德定理得 $$gcd(a,b)=gcd(b,{{a}\ mod\ {b}})$$
则：$$ax_1+by_1=bx_2+{({a}\ mod\ {b})y_2}$$
也就是 $$ax_1+by_1=ay_2+b(x_2-{[{a}/{b}]}{\times} y_2)$$
根据恒等定理得：$${x_1=y_2},\qquad{y_1=x_2-{[{a}/{b}]}{\times} y_2}$$
这样我们就得到了求解${x_1},{y_1}$的方法：${x_1},{y_1}$的值基于 ${x_2},{y_2}$
由Bezout定理我们知道：${ax+by=z}$，z为gcd（a，b）若干倍，所以我们先求解${ax+by={gcd(a,b)}}$，再将求出的解乘以 ${{z}/{gcd(a,b)}}$ 就好了。(上文中'/'指整除)Cpp代码：
int exgcd(int a, int b, int x, int y) {int d = a;if (b != 0) {d = exgcd(b, a%b, y, x);y -= (a / b)*x;}else {x = 1; y = 0;}return d; }