1.整除的性质
定义 \(a|b\) 表示 \(b \% a =0\) 。
\(a\) 与 \(b\) 满足 \(a \in factor \ b\) ( \(b\) 是 \(a\) 的因子）
2.质因数分解
下述的 \(x,y\) 均为合数，\(p\) 均为质数
将 \(x\) 分解为 \(p_1^{q_1} \times p_2^{q_2} \times ...... \times p_n^{q_n}\)
将 \(y\) 分解为 \(p_1^{w_1} \times p_2^{w_2} \times ...... \times p_n^{w_n}\)
3.算术基本定理
前置： \(gcd\) 最大公因数 ， \(lcm\) 最小公倍数
\(gcd(x,y)=p_1^{min(q_1,w_1)} \times p_2^{min(q_2,w_2)} \times ...... \times p_n^{min(q_n,w_n)}\)
\(lcm(x,y)=p_1^{max(q_1,w_1)} \times p_2^{max(q_2,w_2)} \times ...... \times p_n^{max(q_n,w_n)}\)
实例：线性筛质数