证明:若 c 为 a 与 b 之共同因数,则 c 为 gcd(a,b) 之因数.
作者:gugod 发布于: 2020/10/14 ,更新于: 2020/10/15 #math
此处 gcd(a,b) 为 a 与 b 之最大公因数之表记.
因 c 为 a, b 之因数,可知有两整数 m, n 使得:
a = mc
b = nc
令 d = gcd(a,b).依 Bezout's identity,可知存在有两整数 x, y 使得:
d = xa + yb
将 a 与 b 代换后,得:
d = xmc + ync
= (xm + yn)c
因 d 为 a,b 之最大公因数, d ≥ c > 0 . xm + yn 必为