能力值：
![]()
(RANK：650 )
|
-
-
2 楼
gcd算法这个名字比较好，很亲切
我只记得一点点，可能说得不准确，书上大概是这样的
不防设A > B
那么A = q1 * B + r1 (1)
B = q2 * r1 + r2 (2)
r1 = q3 * r2 + r3 (3)
r2 = q4 * r3 + r4 (4)
...
r(n-2) = q(n) * r(n-1) + r(n) (5)
r(n-1) = q(n+1) * r(n) + 0 (6)
(6) -> r(n)是r(n-1)的因子
(5) -> 因为r(n)是r(n-1)的因子，所以这里r(n) 是r(n-2)的因子
(4) -> r(n)是r2的因子
..
(2) -> r(n)是B的因子
(1) -> r(n)是A的因子
|
能力值：
( LV13，RANK：1250 )
|
-
-
3 楼
辗转相除法的依据说穿了就一条：(a, b) = (a-b, b)
至于这是为什么？
首先你承认这个事实否：a与b的任何公因子都能整除(a, b)？
好，你承认就好办了。
a与b的任何公因子显然也能整除a-b，因此也是a-b与b的公因子，
特别地(a, b)也是a-b与b的公因子，因此：(a, b)整除(a-b, b)
反过来，a-b与b的任何公因子显然也能整除a = (a-b) + b，
因此也是a与b的公因子，特别地，(a-b, b)也是a与b的公因子，
因此：(a-b, b)整除(a, b)。
综上所述，(a-b, b)与(a, b)彼此整除对方，它们只能相等。
|
能力值：
![]()
(RANK：1060 )
|
-
-
4 楼
感谢两位。
欧几里德真是厉害。
|
|
|
|
