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的公约数。
那么第一次 ------>
,又由于
,
------>
这里
------>d是24的约数。
到这里可以归纳一下，若d为a和b的约数，即公约数，我们记为,用括号来表示a和b的公约数。
那么在a>b的假设条件下，必然能得到,因为r是余数一定小于除数b。所以一直推下去，
那么有人会问了，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.贝祖数
有如下方程： 。若此方程想要有整数解，即x,y为整数的。有整数解的充要条件是m为a,b的最大公约数的倍数。
证明：若d为a,b的最大公约数，，所以m为d的倍数，注意这里面的所有数都是整数。我们假设a,b的线性组合最小正值为s，
，s为能取到的最小正数，有s>0且s可以被d整除，所以有
。我们突然用 s去除a试一下，得到
，改写一下
,s是除数，q是商，r是余数，所以
。移项得到
，r也是a和b的线性组合。那么因为我们假设了s为线性组合的最小正数，
，所以r只能=0才能满足假设。所以a÷s余数为0，所以s是a的一个约数，同理可得s是b的一个约数，所以s为a,b的公约数，因为d是a,b的最大公约数，所以
。刚才还说的
呢，所以，S=d。即我们假设的线性组合取到的最小正数s就是d,就是a,b的最大公约数。所以当m为最大公约数的倍数时，ax+by=m一定有整数解。 精彩
