整除与gcd的一些有用性质

· · 个人记录

前言

其实是初等数论的内容，这里只记录与 OI 有关的，欢迎补充。

这里默认 (a,b) 中 a<b。

性质 1

(a,b)=d$，则 $(\frac ad,\frac bd)=1

用于其它证明中。

证明：显然，若 (\frac ad,\frac bd)>1=d2，则 (a,b)=d*d2，此时 d 肯定不是最大公因数。

性质 2

证明 $a,b$ 的公约数集和 $a,ka+b$ 的公约数集完全一致即可： 首先，对于整数 $d\mid a,d\mid b$，有 $a=qd,b=pd$，则 $ka+b=kqd+pd=d(kq+p)$。 所以 $d\mid ka+b$。即 $a,b$ 的任意公约数都是 $a,ka+b$ 的公约数。 同理，若有 $u\mid a,u\mid ka+b$，不难推出 $u\mid b$。即 $a,ka+b$ 的任意公约数都是 $a,b$ 的公约数。 所以一开始的那句话成立，所以 $(a,b)=(a,ka+b)$。 ### 性质 3 $(a,b)=(a,b-a) (a,b)=(b,b\bmod a)

性质 2 的推论。

性质 4

接下来将进一步涉及到整除，补充下。

d\mid a,d\mid b$，则 $d\mid sa+tb

（若 d 整除 a,b，则 d 也一定整除 a,b 的线性组合）

所以 $sa+tb=sqd+tpd=d(sq+tp)$，所以 $d\mid sa+tb$。 ### 性质 5 $(a,k)=1$，则 $(a,b)=(a,kb)$。 采取和性质 $2$ 一样的策略，首先我们易证 $a,b$ 的公约数一定是 $a,kb$ 的公约数。 之后我们发现，证明 $d\mid kb,d\mid a \to d\mid b$ 即可，那么咋整嘞？ * #### 引理： 若有 $(a,b)=d$，且 $d\mid c$。则 $\exists s,t\in \mathbb Z$，使得 $sa+bt=c$。 ~~就是裴蜀定理啦。~~ 所以对于 $(a,k)=1$，由引理知：$sa+tk=1$ 成立。 同时乘 $b$ 有：$abs+kbt=b$。 因为 $d\mid a,d\mid kb$，那么由性质 $4$ 知：$d\mid abs+kbt$，即 $d\mid b$，证毕。 ### 性质 6 $(a,b) = (a,b,a+b)

还可以拓展到 n 个元素的情况：

(a_1,a_2...a_n)=(a_1,...a_n,a_i+a_j...a_i+a_j+a_k...)

是上述性质的推论

性质 7

[d\mid (a,b)]$ 等价于 $[d\mid a, d\mid b]

在某些数论（尤其是反演）里面较常见。