整除

设 $n$ 为非负整数，$d$ 为正整数，若 $\frac{n}{d}$ 为整数，则称 $d$ 整除 $n$，记为 $d∣n$，称 $d$ 为 $n$ 的约数，或因数，或因子，而称 $n$ 为 $d$ 的倍数。

任何正整数都整除 $0$。

$d$ 不整除 $n$ 记为 $d∤n$。

最大公约数

设 $a,b$ 为非负整数，$d$ 为正整数，若 $d∣a$ 且 $d∣b$，则称 $d$ 为 $a$ 和 $b$ 的公约数，或公因数，或公因子。

$a$ 和 $b$ 的所有公约数中最大的数称为 $a$ 和 $b$ 的最大公约数，或最大公因数，或最大公因子，记为 $gcd(a,b)$，有时简记为 $(a,b)$。

根据定义，显然有 $gcd(a,b)=gcd(b,a)$。

若 $gcd(a,b)=1$，则称 $a$ 和 $b$ 互质或互素。

由于任何正整数都是 $0$ 和 $0$ 的公约数，故 $gcd(0,0)$ 不存在。

对任意正整数 $a$，有 $gcd(0,a)=a$。

gcd 的性质

设 $a,b$ 为正整数且 $a>b$，有性质 $gcd(b,a)=gcd(b,a−b)$

由此可进一步得到性质 $gcd(b,a) = gcd(b,a \bmod b)$

对于斐波那契数列 1 1 2 3 5 8 13 21 34 55 89 ...的 $gcd$ 有个特殊性质： $gcd(fib[a],fib[b])=fib[gcd(a,b)]$，举例 $fib(9) = 34 , fib(6) = 8 $, 左边 $gcd(34,8) = 2$,右边 $fib(gcd(6,9)) = fib(3) = 2$，两边相等。

斐波那契数列还有几个与数论相关的性质： - $gcd(fib(i),fib(i+1))=1$ 即，斐波那契数列任意相邻两项都是互质。 证明：考虑反证法，假设 $d=gcd(fib(i),fib(i+1))>1$，设 $fib(x)=a*d,fib(i+1)=b*d$，则 $fib(i−1)=fib(i+1)-fib(i)=(b−a)*d，fib(i−2)=(2a−b)*d$，以此类推可得 $fib(1)$ 也是 $d$ 的整数倍，而 $fib(1)=1$，矛盾！故原命题成立。 - $gcd(fib(x),fib(y)=fib(gcd(x,y))$ 证明：可以通过反证法先证fibonacci数列的任意相邻两项一定互素，然后可证 $x>y$ 时$gcd(fib(x),fib(y))=gcd(fib(x-y),fib(y))$，递归可求 $gcd(fib(x),fib(y))$ =gcd(fib(k),fib(l))，最后 $k=l$，不然继续递归。$k$ 是通过展转相减法求出，易证 $k=gcd(x,y)$，所以 $gcd(fib(x),fib(y)) = gcd(fib(k),fib(k)) = gcd(fib(k)) = fib(gcd(x,y))$，这……不就辗转相除法吗？故 $gcd(fib(x),fib(y))=fib(gcd(x,y))$ - 推论：若 $x∣y$，那么 $fib(x)|fib(y)$

gcd 的计算

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

复杂度为 $O(log \ max(a,b))$

最小公倍数

设 $a,b$ 为正整数，$m$ 为非负整数，若 $a∣m$ 且 $b∣m$，则称 $m$ 为 $a$ 和 $b$ 的公倍数。

$a$ 和 $b$ 的所有公倍数中最小的正数称为 $a$ 和 $b$ 的最小公倍数，记为 $lcm(a,b)$。

根据定义，显然有 $lcm(a,b)=lcm(b,a)$。

一个显然而重要的公式是 $lcm(a,b)= \frac{a \times b }{ gcd(a,b)}$

这个公式给出了 lcm 与 gcd 的关系。

需要注意的是，在实际的代码实现中，为避免中间结果的溢出，应该使用 $a/gcd(a,b)∗b$ 而不是 $a∗b/gcd(a,b)$。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com