整除

定義

若\(a=bk\) \((a, b, k \in Z)\) 則\(b\)整除\(a\)記做\(b \mid a\)

也稱\(b\)為\(a\)的約數（因數） 或 \(a\)為\(b\)的倍數

性質

若 \(b\mid a\) , \(c\mid a\), \(b\perp c\) 則 \(bc\mid a\)

若 \(a \mid b\), \(b\mid a\), 則: \(\mid a \mid = \mid b \mid\)

若 \(a\mid b\), \(c \in Z\)， 則: \(a\mid bc\)

若 \(a\mid b\), \(m\in Z\) , 且 \(m \not= 0\), 則 : \(ma \mid mb\)

若 \(a\mid b\), \(a\mid c\) ,則對于任意 \(x,y\in Z\),均有 \(a\mid xb+yc\)

若 \(a\mid b\), \(a\mid c\) ,則 \(a\mid (b + c)\) , \(a \mid (b - c)\)

其實整除的題有很多，如果想好好學一學應該去找MO選手

例題 CF 762A

注意到約數總是成對出現：

若 \(k\) 是 \(n\) 的約數, 則 \((n/k)\) 也是 \(n\) 的約數。

在一對約數中，必有一個不大于

\(\sqrt n\)，另一個不小于 \(\sqrt n\)。

是以枚舉 \(1.. \sqrt n\) 就能求出 \(n\) 的所有約數。