最大公约数
一组整数的 公约数 (Common Divisor)，是指同时是这组数中每一个数的约数的数。±1\pm 1 是任意一组整数的公约数。
一组整数的 最大公约数 (Greatest Common Divisor, GCD)，是指所有公约数里面最大的一个。
对不全为 00 的整数 a,ba,b，将其最大公约数记为 gcd(a,b)\gcd(a,b)，不引起歧义时可简写为 (a,b)(a,b)。
对不全为 00 的整数 a1,…,ana_1,\dots,a_n，将其最大公约数记为 gcd(a1,…,an)\gcd(a_1,\dots,a_n)，不引起歧义时可简写为 (a1,…,an)(a_1,\dots,a_n)。
最小公倍数
一组整数的 公倍数 (Common Multiple)，是指同时是这组数中每一个数的倍数的数。00 是任意一组整数的公倍数。
一组整数的 最小公倍数 (Least Common Multiple, LCM)，是指所有正的公倍数里面，最小的一个数。
对整数 a,ba,b，将其最小公倍数记为 lcm(a,b)\operatorname{lcm}(a,b)，不引起歧义时可简写为 [a,b][a,b]。
对整数 a1,…,ana_1,\dots,a_n，将其最小公倍数记为 lcm(a1,…,an)\operatorname{lcm}(a_1,\dots,a_n)，不引起歧义时可简写为 [a1,…,an][a_1,\dots,a_n]。
最大公约数的性质
- 符号无关： (a1,…,an)=(∣a1∣,…,∣an∣)(a_1,\dots,a_n)=(|a_1|,\dots,|a_n|)；
- 交换律： (a,b)=(b,a)(a,b)=(b,a)；
- 与零的公约数： 若 a≠0a\ne 0，则 (a,0)=(a,a)=∣a∣(a,0)=(a,a)=|a|；
- (bq+r,b)=(r,b)(bq+r,b)=(r,b)；
- 局部计算： (a1,…,an)=((a1,a2),a3,…,an)(a_1,\dots,a_n)=((a_1,a_2),a_3,\dots,a_n)。进而 ∀1<k<n−1\forall 1 < k < n-1, (a1,…,an)=((a1,…,ak),(ak+1,…,an))(a_1,\dots,a_n)=((a_1,\dots, a_k ),( a_{k+1},\dots,a_n))；
- 同时乘： 对不全为 00 的整数 a1,…,ana_1,\dots,a_n 和非零整数 mm，(ma1,…,man)=∣m∣(a1,…,an)(ma_1,\dots,ma_n)=|m|(a_1,\dots,a_n)；
- 同时除： 对不全为 00 的整数 a1,…,ana_1,\dots,a_n，若 (a1,…,an)=d(a_1,\dots,a_n)=d，则 (a1/d,…,an/d)=1(a_1/d,\dots,a_n/d)=1；
- 幂： (an,bn)=(a,b)n(a^n,b^n)=(a,b)^n。
最大公约数还有如下与互素相关的性质：
- 若 b∣acb|ac 且 (a,b)=1(a,b)=1，则 b∣cb\mid c；
- 若 b∣cb|c、a∣ca|c 且 (a,b)=1(a,b)=1，则 ab∣cab\mid c；
- 若 (a,b)=1(a,b)=1，则 (a,bc)=(a,c)(a,bc)=(a,c)；
- 若 (ai,bj)=1, ∀1≤i≤n,1≤j≤m(a_i,b_j)=1,~\forall 1\leq i\leq n,1\leq j\leq m，则 (∏iai,∏jbj)=1\left(\prod_i a_i,\prod_j b_j\right)=1。特别地，若 (a,b)=1(a,b)=1，则 (an,bm)=1(a^n,b^m)=1；
- 对整数 a1,…,ana_1,\dots,a_n，若 ∃v∈Z, ∏iai=vm\exists v\in \mathbf{Z},~\prod_i a_i=v^m，且 (ai,aj)=1, ∀i≠j(a_i,a_j)=1,~\forall i\ne j，则 ∀1≤i≤n, aim∈Z\forall 1\leq i\leq n,~\sqrt[m]{a_i}\in\mathbf{Z}。
最小公倍数的性质
- 符号无关： [a1,…,an]=[∣a1∣,…,∣an∣][a_1,\dots,a_n]=[|a_1|,\dots,|a_n|]；
- 交换律： [a,b]=[b,a][a,b]=[b,a]；
- 与一的公倍数： 若 a≠0a\ne 0，则 [a,1]=[a,a]=∣a∣[a,1]=[a,a]=|a|；
- 若 a∣ba\mid b，则 [a,b]=∣b∣[a,b]=|b|；
- [a1,…,an]=[[a1,a2],a3,…,an][a_1,\dots,a_n] = [[a_1,a_2], a_3, \dots, a_n]。进而 ∀1<k<n−1, [a1,…,an]=[[a1,…,ak],[ak+1,…,an]]\forall 1<k<n-1,~[a_1,\dots,a_n]=[[a_1,\dots,a_k],[a_{k+1},\dots,a_n]]；
- 若 ai∣m, ∀1≤i≤na_i\mid m,~\forall 1\leq i\leq n，则 [a1,…,an]∣m[a_1,\dots,a_n]\mid m；
- 同时乘： [ma1,…,man]=∣m∣[a1,…,an][ma_1,\dots,ma_n]=|m|[a_1,\dots,a_n]；
- [a,b,c][ab,bc,ca]=[a,b][b,c][c,a][a,b,c][ab,bc,ca]=[a,b][b,c][c,a]；
- 幂： [an,bn]=[a,b]n[a^n,b^n]=[a,b]^n。
最大公约数和最小公倍数的性质
- (a,b)[a,b]=∣ab∣(a,b)[a,b]=|ab|；
- (ab,bc,ca)[a,b,c]=∣abc∣(ab,bc,ca)[a,b,c]=|abc|；
- (a,b,c)2(a,b)(b,c)(a,c)=[a,b,c]2[a,b][b,c][a,c]\dfrac{(a,b,c)^2}{(a,b)(b,c)(a,c)}=\dfrac{[a,b,c]^2}{[a,b][b,c][a,c]}。