整除
定义
若(displaystyle a\%b=0)，则称b整除a（a被b整除）
表示
b整除a： (displaystyle b|a Leftrightarrow a\%b=0)
性质
- (displaystyle a | b Leftrightarrow (-a)| b Leftrightarrow abs(a)|abs(b))
- (displaystyle a | b ,b | c Leftrightarrow a | c)
- (displaystyle a | b , a | c Leftrightarrow exists x,y , a| bx+cy)
- (displaystyle m eq 0 , a | b Leftrightarrow ma | mb)
- (displaystyle a | b,b | a Leftrightarrow b=±a)
基于整除的专有名词
因数（约数）
所有满足 (displaystyle a|b) 的 (a) 为 $ b$ 的全部因数（也就是说满足 (a|b) 的 (a) 就是 (b) 的一个因数）
性质
成对出现：(displaystyle d_1,d_2,d_3,cdots)为 (b) 的全部约数 ({displaystyleLeftrightarrow frac{b}{d_1},frac{b}{d_2},frac{b}{d_3}, ormalsizecdots})为b的全部约数
（也就是说如果确定了 (d_1) 是约数，那么 (displaystyle frac{b}{d_1}) 肯定也是另一个约数）
质数
约数只有(1)和自身的自然数
质数的数量
用于时间复杂度分析和取数组大小
(1sim n)中质数数量的上界约为(displaystylefrac{n}{ln n})
下界约为 (displaystylelog_2(log_2x))
合数
能被除了(1)和自身的其他正整数整除的自然数
易错：0、1既非质数也非合数，但是注意题干上是非质数（含0，1）还是合数（不含0，1）