首页 > 代码库 > 辗转相除法的原理

辗转相除法的原理

今天我思考了辗转相除法的原理,在此记录下来;

1,先介绍一下辗转相除法,这是为了求两个数的最大公约数的方法;如果有两个数a,b;且a>b,设a/b商q余c,则a和b的最大公约数也是b和c的最大公约数。这样辗转相除,直到余数为0时除式的商(也就相当于a/b时c那个位置的数字)即为最大公约数;

2,首先证明公约数。如果a和b有公约数x,令a = xm;b = xn,则c = pa±qb = pxm±qxn = x(pm±qn)也能够整除x,即c和a、b有公约数x;

3,证明b、c的最大公约数即为a、b的最大公约数。

  设a = kb +c。

  设a和b的最大公约数是x;设b和c的最大公约数是y;

  b和c的最大公约数y也是a、b的公约数(证明见第二条)。

  因为x是a、b的最大公约数,则y肯定是x的因数(如果有质疑请亲自尝试,因为忘记的知识太多了)。

  上面式子变形得c = a-kb ,则a、b的最大公约数x也是b和c的公约数。

  因为y是b、c的最大公约数,则x肯定是y的因数

  y是x的因数,x也是y的因数,那可以证明x=y;

  即b、c的最大公约数即为a、b的最大公约数。

  

辗转相除法的原理