文章主要根据百度百科和维基百科相关相关知识点整理而成！
辗转相除法
辗转相除法， 又名欧几里德算法(Euclidean algorithm)，是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数(第一余数)去除除数，再用出现的余数(第二余数)去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
另一种求两数的最大公约数的方法是更相减损法。
中文名
辗转相除法
外文名
Euclidean algorithm
别 称
欧几里德算法
用 途
求最大公约数
基本原理
编辑
两个数的最大公约数是指能同时整除它们的最大正整数。
设两数为a、b(a≥b)，求a和b最大公约数 的步骤如下：
(1)用a除以b(a≥b)，得 。
(2)若 ，则 ；
(3)若 ，则再用b除以 ，得 .
(4)若 ，则 ；若 ，则继续用 除以 ，......，如此下去，直到能整除为止。其最后一个余数为0的除数即为 的最大公约数。
证明
编辑
设两数为a、b(a>b)，用 表示a，b的最大公约数，r=a (mod b) 为a除以b的余数，k为a除以b的商，即 。辗转相除法即是要证明 。
第一步：令 ，则设
第二步：根据前提可知
第三步：根据第二步结果可知， 也是 的因数
第四步：可以断定 与 互质(这里用反证法进行证明：设 ，则 ，则 ，则a与b的一个公约数 ，故c非a与b的最大公约数，与前面结论矛盾，因此c也是b与r的最大公约数)从而可知 ，继而 。
证毕
注：以上步骤的操作是建立在刚开始时 的基础之上的，即m与n亦互质。 [1]
算法描述
编辑
用辗转相除法确定两个正整数 a 和 b(a≥b) 的最大公因数 当 时， ；否则 递归或循环运算得出结果。
算法流程图如下：
伪代码描述如下：
1
2
3
4
5
6
7
function gcd(a,b)
{
if b0
return gcd(b,a mod b);
else
return a；
}
示例
编辑
例1
123456 和 7890 的最大公因数是 6，这可由下列步骤(其中，“a mod b”是指取 a ÷ b 的余数)看出：
a
b
a mod b
123456
7890
5106
7890
5106
2784
5106
2784
2322
2784
2322
462
2322
462
12
462
12
6
12
6
例2
已知不定方程为
，利用辗转相除法求出一组整数解
解：求 的算式为：
所以
即
所以
所以
是不定方程
的一组解。
代码实现
c语言
1
2
3
4
5
6
7
int GCD(int a,int b)
{
return b==0?a:GCD(b,a%b);
}
Java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int gcd(int m,int n)
{
while (true)
{
if ((m = m % n) ==0)
return n;
if ((n = n % m) ==0)
return m;
}
}
费马小定理
费马小定理是数论中的一个定理：假如是一个整数，是一个质数，那么是p的倍数，可以表示为，如果a不是p的倍数，这个定理也可以写成，
这个书写方式更加常用。
欧拉定理
费马小定理是欧拉定理的一个特殊情况：如果n和a的最大公因数是1，那么
这里φ(n)是欧拉函数。欧拉函数的值是所有小于或等于n的正整数中与n互质的数的个数。假如n是一个素数(质数)，则φ(n) = n-1，即费马小定理。
欧拉函数
请思考以下问题：
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？(比如，在1到8之中，有多少个数与8构成互质关系？)
计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。
φ(n) 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。
第一种情况
如果n=1，则 φ(1) = 1 。因为1与任何数(包括自身)都构成互质关系。
第二种情况
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
第三种情况
如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
上面的式子还可以写成下面的形式：
可以看出，上面的第二种情况是 k=1 时的特例。
第四种情况
如果n可以分解成两个互质的整数之积，
n = p1 × p2
则
φ(n) = φ(p1p2) = φ(p1)φ(p2)
即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。
这一条的证明要用到"中国剩余定理"，这里就不展开了，只简单说一下思路：如果a与p1互质(a第五种情况
因为任意一个大于1的正整数，都可以写成一系列质数的积。
根据第4条的结论，得到
再根据第3条的结论，得到
也就等于
这就是欧拉函数的通用计算公式。比如，1323的欧拉函数，计算过程如下：
裴蜀定理
在数论中，裴蜀等式(英语：Bézout's identity)或裴蜀定理(Bézout's lemma)是一个关于最大公约数(或最大公约式)的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数、和，关于未知数和的线性丢番图方程(称为裴蜀等式)：
有整数解时当且仅当是及的最大公约数的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解、都称为裴蜀数，可用扩展欧几里得算法求得。
例如，12和42的最大公约数是6，则方程有解。事实上有及。
特别来说，方程 有整数解当且仅当整数和互素。
裴蜀等式也可以用来给最大公约数定义：其实就是最小的可以写成形式的正整数。这个定义的本质是整环中“理想”的概念。因此对于多项式整环也有相应的裴蜀定理。
中国剩余定理
中国剩余定理，又称中国余数定理，是数论中的一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。也称为孙子定理，古有“韩信点兵”、“孙子定理”、“求一术”(宋沈括)、“鬼谷算”(宋周密)、“隔墙算”(宋 周密)、“剪管术”(宋杨辉)、“秦王暗点兵”、“物不知数”之名。
用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：
有解的判定条件，并用构造法给出了在有解情况下解的具体形式。
中国剩余定理说明：假设整数m1, m2, ... , mn其中任两数互质，则对任意的整数：a1, a2, ... , an，方程组有解，并且通解可以用如下方式构造得到：
设是整数m1, m2, ... , mn的乘积，并设
，即是除了mi以外的n − 1个整数的乘积。
设为模的数论倒数：
方程组{\displaystyle (S)}的通解形式为： 在模的意义下，方程组只有一个解：
例子：
