定义
设 (a, b) 是不都为 (0) 的整数, (c) 为满足 (c | a) 且 (c | b) 的最大整数.
则称 (c) 是 (a, b)的最大公约数
记为 (gcd(m, n)) 或 ((a, b))
若((a, b) = 1), 则称 (a, b) 互质(互素)
性质
((1)) ((a, a) = (0, a) = a)
((2)) 若 (a|b) , 则((a, b) = a)
((3)) ((a, b) = (a, a + b) = (a, ka + b))
((4)) ((ka, kb) = k imes (a, b))
((5)) ((a, b, c) = ((a , b), c))
求gcd
求 (GCD) 的一般公式:质因数分解
$ a = p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k} $
$ b = p_1^{b_1}p_2^{b_2}p_3^{b_3}...p_k^{b_k} $
$ (a, b) = p_1^{min(a_1, b_1)}p_2^{min(a_2, b_2)}p_3^{min(a_3, b_3)}...p_k^{min(a_k, b_k)} $
例题
[CF 664A] Complicated GCD
[CF 757B] Bash’s Big Day
证明性质1
因为 (a) 是 (a) 的最大约数,且 (a | 0)
所以 ((a, a) = (0, a) = a)
证明性质2
因为 (a) 是 (a) 的最大约数, 且 (a | b)
所以 ((a, b) = a)
证明性质3
设 (c = (a, b))
所以 (c | a, c | b)
所以 (c | (a + b)) (这个在整除的部分里写过也证过)
所以 (a, b) 的最大公约数是 (a, a + b) 的约数
设 (d = (a, a + b))
所以 (d | a, d | (a + b))
所以 (d | (a - (a + b)) Rightarrow d | (-b) Rightarrow d | b)
所以 (a , a + b) 的最大公约数是 (a, b) 的约数
所以 ((a, b) = (a , a + b))
同理可得: ((a, b) = (a, a + b) = (a, ka + b))
证明性质4
设 (kc = (ka, kb))
所以 (kc | ka, kc | kb)
所以 (c | a, c | b)
所以 $ ka, kb $ 最大公约数是 (a, b) 的约数的 (k) 倍
设 (d = (a, b))
所以 (d | a, d | b)
所以 (kd | ka, kd | kb)
所以 $ a, b $ 最大公约数的 (k) 倍是 (a, b) 的约数
所以 ((ka, kb) = k imes (a, b))
证明性质5
根据求 (gcd) 的一般方法即可证明(不想写不证了)