原文
如果a和b为不全为零的整数，则它们的公因子的集合是一个有限的整数集，通常包括+1和-1，我们对其中最大的那个公因子感兴趣.
定义2 不全为零的整数a和b的最大公因子是指能够同时整除a和b的最大整数。
a和b的最大公因子记作(a，b)，(有时也记作gcd(a，b)，特别是在非数论的著作中我们将一直沿用传统的记号(a，b)，虽然有时候这种记法也表示有序数对)。注意当n为正整数时，
(0，n) = (n，0) = n，虽然所有的正整数都能整除0，我们还是定义(0，0) = 0 (这样可以确保关于最大公因子的相关结论在所有情况下均成立。
例如：24 和 84 的公因子有±1，±2，±3，±4，±6，±12，因此(24，84) = 12.类似地，通过查看公因子集合，我们有(0,44)=44，(-6,-15)=3，(-17,289) =17。
定义3 设a,b均为非零整数，如果a和b最大公因子(a,b)=1，则称a与b互素。
注意由于-a的因子与a的因子相同，故有(a，b)=(|a|，|b|)，其中|a|表示a的绝对值，因此，我们只关注正整数对的最大公因子。
定理4
a，b是整数，且(a,b)=d，那么(a/d，b/d)=1。(换言之，a/d与b/d互素.)
证明
已知a，b是整数，且(a，b)=d. 我们将证明a/d，b/d除了1之外没有其他的公因子。假设还有正整数e使得e|(a/d)且e|(b/d)，
那么存在整数k和l使得a/d=ke ，b/d=le，于是a=dek，b=del.因此de是a，b的公因子，因为d是a，b 的最大公因子，故de ≤ d，
于是e=1.因此(a/d，b/d)=1.
一个分数p/q被称为是既约分数，如果(p，q)=1.下面的结论告诉我们每一个分数都与一个既约分数相等.
推论1 如果a，b为整数，且b≠0，则a/b=p/q，其中p，q为整数，且(p，q)=1，q≠0.
证明
假设a，b为整数且b≠0，令p=a/d，q=b/d，其中d=(a，b)，则p/q=(a/d)/(b/d),由定理4可知(p,q)=1，命题得证。
定理5
令a，b，c是整数，那么(a + cb，b) = (a，b)
证明
令a，b，c是整数，证明a，b的公因子与a+cb，b的公因子相同，即证明(a+cb，b)=(a，b)。
令e是a，b的公因子，由定理2可知e|(a+cb)，所以e是a+cb和b的公因子。
如果f是a+cb和b的公因子，由定理2可知f整除(a+cb)-cb= a，所以f是a，b的公因子，因此(a+cb，b)=(a，b)。
定义4
如果a，b是整数，那么它们的线性组合具有形式ma+nb，其中m，n 都是整数.
定理6
两个不全为零的整数a，b的最大公因子是a，b的线性组合中最小的正整数。
证明 令d是a，b的线性组合中最小的正整数，d = ma + nb, 其中m，n是整数，我们将证明d|a，d|b。
由带余除法，得到a=dq+r, 0≤r<d。
由a=dq+r和d=ma+nb，得到r=a-dq=a-q(ma+nb)=(1-qm)a-qnb.
这就证明了整数r是a,b的线性组合。因为0 ≤ r < d，而d是a,b的线性组合中最小的正整数，
于是我们得到r=0（如果r不是等于0，那意味着r才是所有线性组合中最小的正整数，这与d是所有线性组合中最小的正整数矛盾），因此d|a，同理可得，d|b.
我们证明了a,b的线性组合中最小的正整数d是a,b的公因子，剩下要证的是它是 a,b的最大公因子，为此只需证明a,b所有的公因子都能整除d。
由于d = ma + nb，因此如果c l a且c | b，那么由定理2有c l d，因此d > c，这就完成了证明。
定义5
令a1，a2，…，an是不全为零的整数，这些整数的公因子中最大的整数就是最大公因子。
a1，a2，…，an的最大公因子记为(a1，a2，…，an)。(注意ai在这里面出现的顺序并不影响结果.)
引理1
如果A1，A2，…，An，是不全为零的整数，那么(A1，A2，…，An-1，An) = (A1，A2，…，An-2,(An-1,An) )。
证明
n个整数A1，A2，…An-1和An的任意公因子也是An-1和An的公因子，因此也是(An-1,An)的因子。
同样n1个整数A1，A2，…，An-2和(An-1,An) 的公因子也是n个整数A1，A2，…，An-1，An的公因子，因为如果某整数整除(An-1,An)，那么它一定同时整除An-1和An。
因此，这n个整数的公因子和由前n-2个整数与后两个整数的最大公因子组成的集合的公因子完全相同，它们的最大公因子也一定相同。
解析
如果a和b为不全为零的整数，则它们的公因子的集合是一个有限的整数集，通常包括+1和-1（注意包括负数），我们对其中最大的那个公因子感兴趣.
定义2 不全为零的整数a和b的最大公因子是指能够同时整除a和b的最大整数。
a和b的最大公因子记作(a，b)，(有时也记作gcd(a，b)，特别是在非数论的著作中我们将一直沿用传统的记号(a，b)，虽然有时候这种记法也表示有序数对)。
注意当n为正整数时，(0，n) = (n，0) = n，虽然所有的正整数都能整除0（n|0），我们还是定义(0，0) = 0 (这样可以确保关于最大公因子的相关结论在所有情况下均成立。
例如：24 和 84 的公因子有±1，±2，±3，±4，±6，±12，因此(24，84) = 12.类似地，通过查看公因子集合，我们有(0,44)=44
(-6,-15)=3（举例：-6:±1，±2，±3，±6 -15:±1，±3，±5 ,±15 于是，（-6，-15）=最大的公因子，3）
(-17,289) =17。
定义3 设a,b均为非零整数，如果a和b最大公因子(a,b)=1，则称a与b互素（或者互质）。
注意由于-a的因子与a的因子相同，故有(a，b)=(|a|，|b|)，其中|a|表示a的绝对值，因此，我们只关注正整数对的最大公因子。
（例如，（-a，-b），一般可以转换成（a，b）求解，求a和b的最大公因子，如果有负数可以转为整数计算）
定理4
a，b是整数，且(a,b)=d，那么(a/d，b/d)=1。(换言之，a/d与b/d互素.)
举例：a=6, b=4，d=（a,b）=(6,4)=2，（a/d,b/d）=(6/2,4/2)=(3,2)=1
因为已经把a，b的最大公共因数给取掉（除）了，等于把所有公因数去掉了（除1以外的），不可能还有任何公因数（除1以外的）
证明
已知a，b是整数，且(a，b)=d. 我们将证明a/d，b/d除了1之外没有其他的公因子。假设还有正整数e使得e|(a/d)且e|(b/d)，
（转化问题，我们只需要求出e整除（a/d）是1，e整除（b/d）是1，也可以证明）
那么存在整数k和l使得a/d=ke ，b/d=le，于是a=dek，b=del.因此de是a，b的公因子（（a，b）=（dek,del），我们取出可以de，即（k，l）=de）
因为d是a，b 的最大公因子，故de ≤ d，
于是e=1.因此(a/d，b/d)=1.
一个分数p/q被称为是既约分数，如果(p，q)=1.下面的结论告诉我们每一个分数都与一个既约分数相等.
（可以理解为 一个分数约分成最简分数还是等于这个分数）
推论1 如果a，b为整数，且b≠0，则a/b=p/q，其中p，q为整数，且(p，q)=1，q≠0.
证明
假设a，b为整数且b≠0，令p=a/d，q=b/d，其中d=(a，b)，则p/q=(a/d)/(b/d),由定理4可知(p,q)=1，命题得证。
定理5（**********重点*************）
令a，b，c是整数，那么(a + cb，b) = (a，b)
举例：a=6，b=10，c=-3，（6+（-30））=（6,10）， （-24,10）=（6， 10） ， （24,10）=（6,10）， （24,10）=2，（6,10）=2，故合法
证明
令a，b，c是整数，证明a，b的公因子与a+cb，b的公因子相同，即证明(a+cb，b)=(a，b)。
令e是a，b的公因子
若e是（a，b）的公因子，如果e还是（a+cb， b）的公因子；f是（a+cb，b）的公因子，如果f还是（a，b）的公因子，
那么（a+cb，b）与（a，b）公因子肯定相同，所以要互相转换问题！！
，由定理2（c | a，c | b，则c | (ma+nb).）可知e|(a+cb)，所以e是a+cb和b的公因子。（因为 e | （a，b），用定理2，得e | （1*a+c*b），即e | （a+cb））
如果f是a+cb和b的公因子，由定理2可知f整除(a+cb)-cb= a
设a+cb=x, b=y， 因为f | x 且 f | y，所以由定理2，得出 f | (1*x）+（-c）*y，整理得 f | 1*（a+cb）+（-c*b）， 得到，f | a
，所以f是a，b的公因子，因此(a+cb，b)=(a，b)。
定义4
（定义就是定义，没有为什么这样定义，就是规定的这样）
如果a，b是整数，那么它们的线性组合具有形式ma+nb，其中m，n 都是整数.
定理6
两个不全为零的整数a，b的最大公因子是a，b的线性组合中最小的正整数。
证明 令d是a，b的线性组合中最小的正整数，d = ma + nb, 其中m，n是整数，我们将证明d|a，d|b。
（转换问题- 我们知道了d是a，b的线性组合中最小的正整数。此时我们要先证明d是a，b的公因子，才能证明d是a，b的最大公因子）
由带余除法，得到a=dq+r, 0≤r<d。
由a=dq+r和d=ma+nb，得到r=a-dq=a-q(ma+nb)=(1-qm)a-qnb.
a=dq+r=（ma+nb）q+r。 r=a-dq=a-q（ma+nb）=（1-qm）a-qnb=（1-qm）*a+（-qn）*b，满足ma+nb
这就证明了整数r是a,b的线性组合。因为0 ≤ r < d，而d是a,b的线性组合中最小的正整数，
于是我们得到r=0（如果r不是等于0，那意味着r才是所有线性组合中最小的正整数（因为r<d），这与d是所有线性组合中最小的正整数矛盾），
因此d|a（因为没有余数r，所以a=dq，d小在前，a大在后），同理可得，d|b（全部步骤把a换b即可）.
我们证明了a,b的线性组合中最小的正整数d是a,b的公因子，剩下要证的是它是 a,b的最大公因子，为此只需证明a,b所有的公因子都能整除d。
（d是a，b所有公因子的倍数，即d是最大的那个公因子，a，b所有公因子才能整除d）
由于d = ma + nb，因此如果c l a且c | b（若c是a，b的公因子），那么由定理2有c l d（），
因此d > c，这就完成了证明。
定义5
令a1，a2，…，an是不全为零的整数，这些整数的公因子中最大的整数就是最大公因子。
a1，a2，…，an的最大公因子记为(a1，a2，…，an)。(注意ai在这里面出现的顺序并不影响结果.)
这个引理1教会我们，如果有x,y,z，要求最大公因数，我们要先求（y，z），然后（y，z）和a求一个最大公因数，多个数也是如此
引理1
如果A1，A2，…，An，是不全为零的整数，那么(A1，A2，…，An-1，An) （令此式为A）= (A1，A2，…，An-2,(An-1,An)（此式为B） )。
我们只要算出A中的最大公因数x，B中的最大公因数y，并证明x是B的最大公因数，y是A的最大公因数，就能证明A，B最大公因式了
证明
n个整数A1，A2，…An-1和An的任意公因子也是An-1和An的公因子，因此也是(An-1,An)的因子。
同样n1个整数A1，A2，…，An-2和(An-1,An) 的公因子也是n个整数A1，A2，…，An-1，An的公因子，因为如果某整数整除(An-1,An)，那么它一定同时整除An-1和An。
因此，这n个整数的公因子和由前n-2个整数与后两个整数的最大公因子组成的集合的公因子完全相同，它们的最大公因子也一定相同。
标签：正整数,最大,数论,cb,整数,证明,因子,性质 From： https://www.cnblogs.com/didiao233/p/18003777