1.求正整数 a, b 的最大公因数
a,b 是两个正整数,其中 a > b,则 a 可以写成如下形式:
a = kb + r
其中 0 <= r < b
- 如果 r 等于 0,则 a = kb,那么最大公因数即为 b
- 如果 r 不等于 0,设 a, b 的一个因数为正整数 q,则有:
a = tq
b = sq
其中 t s 为正整数,得到
=> tq = ksq + r
=> r = (t - ks)q
因此 q 也是 r 的一个因数,所以,a,b 的公因数同时也是 b,r 的公因数。 同理可证 b,r 的公因数同时也是 a,b 的公因数,因此:
a,b 与 b,r 的公因数相同
如果用 gcd(a, b) 表示 a,b 的最大公因素,则
gcd(a, b) == gcd(b, r)
程序实现:
function gcd(a, b) {
if(a < b){
var tmp = a;
a = b;
b = tmp;
}
var mod = a % b;
if(mod === 0){
return b;
}else{
return gcd(b, mod);
}
}
2.求正整数 a, b 的最小公倍数
a,b 是两个正整数,其中 a > b,则:
a = kb + r
其中 0 <= r < b
- 如果 r 等于 0,则 a = kb,那么最小公倍数即为 a
- 如果 r 不等于 0,设 a, b 的最小公倍数为正整数 q,则有:
q = sa
q = tb
其中 t s 为正整数。
已知 a,b 的最大公因数为 g,则
q = sa = sug
q = tb = tvg
=> sa = sug = tb = tvg
=> su = tv
=> s/t = v/u
其中 u v 为正整数,且 u v 互质(因为如果 u v 不互质,那么 g 就不是 a,b 的最大公因数)。
同理可知:s t 也一定互质,因为假设 s t 不互质,且有公因数 z,那么存在如下关系:
s = mz
t = nz
=> q = sa = mza
q = tb = nzb
因此,存在一个正整数 w = ma = nb,w也是 a b 的公倍数,显然 w < q,与 “q 是最小公倍数”相矛盾。 此时可以得出:
s/t = v/u
其中 u v 互质,s t 互质。可知:
s = vt/u
因此 t 必定可以整数 u,假设 t = xu,其中 x!=1,可以得到 s = xv。与 “s t 互质”相矛盾。因此 x 必定是 1,所以
s = v
t = u
得到
q = sa = va = ab/q
程序实现:
function lcm(a, b){
var _gcd = gcd(a, b);
return a * b / _gcd;
}