辗转相除法（离散数学基础算法）

**前导定理：**我们用（a，b）来表示a和b的最大公因子： 有定理：存在整数x和y使得（a，b）=xa+yb

下面给出辗转相除法的证明和x和y的初始状态 我们可以算出每一步的q，然后根据x_-2= 1 ,x_-1= -0 , y_-2= 0 , y_-1= 1 , 利用公式 x_i = x_i-2 - q_i*x_i-1 和公式 y_i = y_i-2 - q_i*y_i-1 可以算出每一个xi和yi，然后一定可以得出来x_n和y_n使得x_n*a+y_n*b =(a,b)

下面是一个例题

下面是代码实现

int gcd(int a,int b){ if(b==0)return a; return gcd(b,a%b); }

多项式

关于多项式的辗转相除：