求高中数学中更相减损术的原理

“更相减损术”又名“欧几里德辗转相除法”
对于二个自然数a和b，若存在正整数q，使a=bq，则a能被b整除，b为a的因子，a为b的倍数。
如果a能被c整除，并且b也能被c整除，则c为a、b的公因数（公有因数）。
由此我们可以得出以下推论：
推论1、如果a能被b整除（a=qb），若k为正整数，则ka也能被b整除（ka=kqb）
推论2、如果a能被c整除（a=hc），b也能被c整除（b=tc），则(a±b)也能被c整除
因为：将二式相加：a+b=hc+tc=(h+t)c 同理二式相减：a－b=hc－tc=(h－t)c
所以：(a±b)也能被c整除
推论3、如果a能被b整除（a=qb），b也能被a整除（b=ta），则a=b
因为：a=qb b=ta a=qta qt=1 因为q、t均为正整数，所以t=q=1
所以：a=b
如果 q 和 r 是 m 除以 n 的商及余数，即 m=nq+r，则 gcd(m,n)=gcd(n,r)。
证明是这样的: 设 a=gcd(m,n)，b=gcd(n,r)
a=gcd(m,n)
m能被a整除，并且n也能被a整除，则由推论1得：qn也能被a整除
由推论2得：m-qn也能被a整除
而m-qn=r，即r也能被a整除，所以a=b
或
b=gcd(n,r)
n能被b整除，并且r也能被b整除，则由推论1得：qn也能被b整除
由推论2得：qn+r也能被b整除
而m=qn+r，即m也能被b整除，所以a=b
例如计算 gcd(546, 429)
gcd(546, 429) 546=1*429+117
=gcd(429, 117) 429=3*117+78
=gcd(117, 78) 117=1*78+39
=gcd(78, 39) 78=2*39
=39