1.辗转相除法

1.1 先引出直观的图解法：求104和40的最大公约数。

图解最大公约数

若要求104和40的最大公约数，以40和104为长方形的宽和长，此时若要用若干个全等的边长为k的正方形来填满这个长方形，则K为40和104的公约数，其中最大的k为最大公约数。这样来来回回的最后发现了边长为8的正方形可以填满，所以最大公约数为8。

证明：因为正方形可以填满长方形，那么边长k一定是104和40的约数。8边长的可以填满16边长的，那么也可以填满24边长的，那么肯定可以填满40边长的。。推下去。证毕。

1.2辗转相除法

辗转相除法过程

证明：

假设d为104和40的公约数。

那么第一次 $104\div 40 = 2 ......24$ ------> $24=104-40\times 2$ ,又由于 $104=d\times k_1$ , $40=d\times k_2$ ------> $24=d\times k_1-d\times k_2 \times 2 =d \times (k_1-2k_2)$ 这里 $k_1>2k_2，因为104=d\times k_1 ,40=d\times k_2$ ------>d是24的约数。

到这里可以归纳一下，若d为a和b的约数，即公约数，我们记为 $d=(a,b)$ ,用括号来表示a和b的公约数。

那么在a>b的假设条件下，必然能得到 $d=(b,r)$ ,因为r是余数一定小于除数b。所以一直推下去， $d=(a,b)=(b,r)=(r,r_1) ，r1是b/r的余数 =.........直到有一天余数变为0时，前一个（）的余数就是所求的最大公约数$

那么有人会问了，d是a,b的约数，没说d是最大公约数啊？为啥这么辗转下去就是最大公约数了呢？

证明：反证法，我们以104，40辗转举例子容易理解。假设d是104和40的非最大公约数，假设k为104何40的最大公约数，——>d<k。

根据上述传递性，d=(104,40)=(40,24)=(24,16)=(16,8),(16,8）=8这个是公认的。而根据假设，k=（104,40)=.....=(16,8) >8，而（16,8) 最大的公约数就是除数本身8。k不可能再大于8了，所以矛盾，故不存在k>b。所以这么辗转，就是得到的是最大公约数。

2.贝祖数

有如下方程： $ax+by=m ,(a,b,m\in Z)$ 。若此方程想要有整数解，即x,y为整数的。有整数解的充要条件是m为a,b的最大公约数的倍数。

证明：若d为a,b的最大公约数， $ax+by=k_1dx+k_2dy=(k_1x+k_2y)d$ ，所以m为d的倍数，注意这里面的所有数都是整数。我们假设a,b的线性组合最小正值为s， $ax+by=s$ ，s为能取到的最小正数，有s>0且s可以被d整除，所以有 $S\geq d$ 。我们突然用 s去除a试一下，得到 $a=qs+r$ ，改写一下 $a\div s=q.....r$ ,s是除数，q是商，r是余数，所以 $0\leq r<s$ 。移项得到 $r=a-qs=a-q(ax+by)=a-aqx-bqy=(1-qx)a+(-qy)b$ ，r也是a和b的线性组合。那么因为我们假设了s为线性组合的最小正数， $0\leq r<s$ ，所以r只能=0才能满足假设。所以a÷s余数为0，所以s是a的一个约数，同理可得s是b的一个约数，所以s为a,b的公约数，因为d是a,b的最大公约数，所以 $s\leq d$ 。刚才还说的 $S\geq d$ 呢，所以，S=d。即我们假设的线性组合取到的最小正数s就是d,就是a,b的最大公约数。所以当m为最大公约数的倍数时，ax+by=m一定有整数解。精彩