gcd更相减损术的证明

zjpwwc · 2025-04-07 19:41:21 · 个人记录

试证明：gcd(a,b)=gcd(b-a,b)

证明如下：

设 gcd(a,b)=d，a=k_1d，b=k_2d

则 gcd(k_1,k_2)=1

∴gcd(b-a,b)=gcd((k_2-k_1)d,k_1d)

发现若 gcd(k_2-k_1,k_1)=1，则得证

假设gcd(k_2-k_1,k_1)=g

设 k_2-k_1=t_1g，k_1=t_2g

由②式，g|k_1

由①式+②式，k_2=(t_1+t_2)g

∴g|k_2

∴g|k_1 并且 g|k_2

∵gcd(k_1,k_2)=1

∴ g=1

∴gcd(k_2-k_1,k_1)=1

∴gcd(a,b)=gcd(b-a,b)

证毕。