急 欧几里得算法是什么原理啊?

来源：百度知道 编辑：UC知道 时间：2024/05/31 00:48:06
我知道怎么算的,不过谁来告诉我为什么可以这样算,
我不知道原理啊,那样记着公式没用
我想弄清为什么!!!!!!!!!
急急急!!!!!
我要问为什么这么推可以推出最大公约数!!!!!!!!!!
拜托各位数学高手了!!!!

欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

看看这样说能明白不/

http://zhidao.baidu.com/question/5032628.html?fr=qrl3

在求两个整数的最大公约数要用到欧几里得算法,简单的说就是：
设A,B(A>B)最大公约数为k,则
A = k*A1
B = k*B1
所以
C = A-B*t = k*(A1-B1*t) (C<B)
得到
(A,B) == (C,B)

欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则
d