辗转相除法是一种求最大公因数的计算方法。
这种方法在编程中很常用，在数学计算中也可以用来求很复杂的最大公因数问题。
如何使用
题目：求最大公因数(36,14)
我们如何用辗转相除法做这道题呢？
$$ { 反复用除数除以余数直到除尽 \\\\ 36{\div}14=2\dots8\\ 14{\div}8=1\dots6\\ 8{\div}6=1\dots2\\ 6{\div}2=3\\ 最后一个除数就是最大公约数，也就是2 } $$我们算出最大公约数(36,14)=2
到这里，我们就知道如何使用辗转相除法了。
但是，鲁迅曾说过“我们学公式必须得懂得原理”，我们明白了原理才能灵活运用
原理
求最大公因数(a,b)
首先我们推出这几条式子
$$ { a{\div}b=q\dots r \\ a=bq+r \\ r=a-bq } $$这是我们辗转法的原理
$${ (a,b)=(b,r) \\a和b的最大公约数就等于b和r的最大公约数 } $$接下来让我们证明这条公式
$$ { (1)设(a,b)=d \\那么a=dm,b=dn \\然后我们将其带入r=a-bq \\ 得r=d(m-nq)\\ 因为m,n,q都是整数，所以r是d的倍数，d是r的因数\\ 所以：只要是a,b的因数，就一定是d,r的约数\\ } $$$$ { (2)设(b,r)=d\\ 和之前一样，那么b=dx,r=dy\\ 然后将其代入a=bq+r\\ 得a=d(xq+y)\\ 因为x,q,y都是整数，所以a是d的倍数，d是a的因数\\ 所以：只要是d,r的因数，就一定是a的因数\\ } $$这样，我们就得出(a,b)的因数和(b,r)的因数相同，它们的因数都相同，那么它们的最大公因数也就相同。
所以我们要求(a,b)的最大公因数，我们就通过可以求(b,r)的最大公因数来得到。
现在我们再来看看开头的题
题目：求最大公因数(36,14)
反复用(a,b)=(b,r)的方法
(36,14)=(14,8)=(8,6)=(6,2)
最后得到(6,2)，显而易见最大公约数是2
写gcd函数
接下来看看我们如何在C++中用辗转相除法写gcd函数
gcd函数就是用来求最大公因数的函数
int gcd(int a,int b) {
while (a % b != 0) //a能被b整除时就终止循环
{
int r = a % b;
a = b;
b = r; //讲a换成除数b，b换成余数r
}
当然也可以直接用algorithm头文件中的gcd函数，
我们学会自己写是为了理解原理，提升思维，
自己写还可以在有特殊需求的时候更自定义化。