数论入门——整除，带余除法，GCD-526互联

整除

设 $a,b\in \mathbb{Z},a\ne 0$。如果 $\exists q\in \mathbb{Z}$，使得 $b=a\times q$，那么就说 $b$ 可被 $a$ 整除，记作 $a\mid b$ ；$b$ 不被 $a$ 整除记作 $a\nmid b$ 。

--------OI Wiki

整除的性质：

$a\mid b \Longleftrightarrow -a\mid b\Longleftrightarrow a\mid -b\Longleftrightarrow \left | a \right | \mid \left | b \right | $
$a\mid b \wedge b\mid c\Longrightarrow a\mid c$
$a\mid b \wedge a\mid c \Longleftrightarrow \forall x,y\in \mathbb{Z},a\mid (x b+y c)$
$a\mid b\wedge b\mid a \Longrightarrow b=\pm a$
设 $m\ne 0$，那么 $a\mid b \Longleftrightarrow ma\mid mb$
设 $b\ne 0$，那么 $a\mid b\Longrightarrow \left | a \right | \le \left | b \right | $
设 $a\ne 0,b=qa+c$，那么 $a\mid b\Longleftrightarrow a\mid c$

约数（因数）：若 $a\mid b$，则称 $b$ 是 $a$ 的倍数，$a$ 是 $b$ 的约数。

$0$ 是所有非 $0$ 整数的倍数。对于整数 $b\ne 0$ ，$b$ 的约数有无限个。

平凡约（因）数：对于整数 $b\ne 0,\pm 1、\pm b$ 是 $b$ 的平凡约数，当 $b=\pm 1$ 时，$b$ 只有两个平凡约数。

对于整数 $b\ne 0$ ，$b$ 的其他约数称为真约数（真因数、非平凡约数）。

如果没有特别说明，约数总是指正约数

带余除法

设 $a,b$ 为两个给定的整数，$a\ne 0$ 。设 $d$ 是一个给定的整数。那么，一定存在唯一的一对整数 $q,r$，满足 $b=qa+r,d\le r<\left | a \right | +d$。

无论 $d$ 取何值，$r$ 统称为余数。$a\mid b$ 等价于 $a\mid r$ 。

一般情况下 $d$ 取 $0$ ，此时等式 $b=qa+r,\le r< \left | a \right | $ 统称为带余除法。这里的余数 $r$ 成为最小非负余数。

-------OI Wiki

$a\div b=c...d$

其中 $a$ 是被除数，$b$ 是除数，$c$ 是商，$d$ 是余数。

性质：

$a=b\times c+d$
$b>d\ge 0$
$c=a/b,d=a\bmod b$
$(a+b)\bmod c=(a\bmod c+b\mod c)\bmod c$ 同理减和乘也成立
任一整数被正整数 $a$ 除后，余数一定是且仅是 $0$ 到 $(a-1)$ 这 $a$ 个数中的一个。
相邻的 $a$ 个整数被正整数 $a$ 除后，恰好取到上述 $a$ 个余数。

对于四的证明：

设 $a=x\times c+a',b=y\times c+b'$ 将这两个式子代入 $(a+b)\bmod c$ 后得到：$(x\times c+a'+y\times c+b')\bmod c$ 很显然最后剩下的是 $(a'+b')\bmod c$ ，而我们知道 $a'=a\bmod c,b'=a\bmod c$ ，故得证。