基础数论

· · 算法·理论

PART 1 整除

1 整除的定义

若有 a=lb（a,b,l 为整数，b\ne0），则称 b 整除 a，写为 b \mid a，且称 a 为 b 的倍数，b 为 a 的约数。

2 整除的基本性质

2.1 传递性

若有 b \mid a，c \mid b，则 c \mid a。

证明：

\because c \mid b \therefore b = l_1 c \because b \mid a \therefore a = l_2 b

将 b = l_1 c 代入 a = l_2 b 可得 a = l_2 l_1 c

可发现 a = l_2 l_1 c 中 l_2，l_1 均为整数，因而可写为 a = l_3 c（l_3 = l_2 l_1，l_3 为整数） 根据整除的定义可得 c \mid a

##### 2.2 线性组合 若有 $d \mid a$，$d \mid b$，则有 $d \mid (ax+by)$（$x,y$ 为整数）。 **证明**： $\because d \mid a$，$d \mid b $\therefore ax = x l_1 d$，$by = y l_2 d \therefore ax+by = d(x l_1 + y l_2)

可发现 x l_1 + y l_2 为整数

根据整除的定义可得 d \mid (ax+by)

##### 2.3.1 整除的乘法变形 若有 $m \ne 0$（$m$ 为整数），$b \mid a$，那么有 $(mb) \mid (ma)$。 **证明**： $\because b \mid a $\therefore ma = m l_1 b

设 ma=A，mb=B，可得 A = l_1 B

根据整除的意义（A，l_1，B 为整数），可得 B \mid A，即 (mb) \mid (ma)

##### 2.3.2 整除对乘法的封闭性 若有 $m \ne 0$（$m$ 为整数），$a \mid b$，那么有 $a \mid bm$。 **证明**： $\because a \mid b \therefore b = l_1 a $\because l_1$，$m$ 均为整数 $\therefore l_2$ 为整数 $\therefore a \mid bm ##### 2.4 有关互质 ##### 2.4.1 若有整数 $a,b,x,y$（$a,b$ 不全为 $0$），使得 $ax+by=1$，那么 $a$ 与 $b$ 互质。 **证明**： 假设 $d=\gcd(a,b)$，那么有 $d \mid a$，$d \mid b \because d \mid a$，$d \mid b (ax+by)$（$x,y$ 为整数） $\because$ 有 $ax+by=1$（条件） $\therefore d \mid 1$，即 $d=1 \because a,b$ 的最大公因数为 $1 $\therefore$ 原命题成立 ##### 2.4.2 若 $a,b$ 互质，且有 $a \mid n$，$b \mid n$，那么有 $(ab) \mid n$。 **证明**： $\because a \mid n \therefore n = ak

根据上面的 2.4.1 性质，我们可以知道因为 a 与 b 互质，所以有整数 x,y 使得 ax+by=1

$\because$ 有 $n=ak \therefore$ 有 $nx+bky=k \because b \mid n \therefore b \mid nx$，即 $b \mid akx \therefore b \mid akx$ 且 $b \mid bky \therefore$ 显然有 $b \mid (kax+kby)$，也就是 $b \mid k \therefore k = l_3 b \because n = ak \therefore n = ab l_3 $\therefore (ab) \mid n ##### 2.5 整除判定的核心性质 $b=qd+c$ 时，$d \mid b \iff d \mid c$（$b,q,d,c$ 为整数）。 **证明**： 当 $d \mid b$ 时 $\because d \mid qd $\because c = b-qd \therefore d \mid c

当 d \mid c 时

\because c = b-qd \therefore d \mid (b-qd) \because d \mid qd \therefore d \mid b --- ## PART 2 同余 ### 1 同余的定义 若有整数 $a,b,p$ 且 $a,b$ 除以 $p$ 的余数相同，则称 $a \equiv b \pmod{p}$。 ### 2 同余的基本性质 ##### 2.1 同余与整除的关系 $a \equiv b \pmod{p}$ 等价于 $p \mid (a-b)$。 **证明**： $\because a \equiv b \pmod{p} \therefore a = l_1 p + c$，$b = l_2 p + c \therefore a-b = p(l_1 - l_2) \therefore p \mid (a-b)
2.2 同加性

若有 a \equiv b \pmod{p}，那么有 a+c \equiv b+c \pmod{p}，c 为整数。

证明：

\because p \mid (a-b) \therefore p \mid [(a+c)-(b+c)] \therefore a+c \equiv b+c \pmod{p} ##### 2.3 同减性 若有 $a \equiv b \pmod{p}$，那么有 $a-c \equiv b-c \pmod{p}$，$c$ 为整数。 **证明**： $\because p \mid (a-b) \therefore p \mid [(a-c)-(b-c)] \therefore a-c \equiv b-c \pmod{p} ##### 2.4 同乘性 若有 $a \equiv b \pmod{p}$，那么有 $ac \equiv bc \pmod{p}$，$c$ 为整数。 **证明**： $\because p \mid (a-b) \therefore p \mid [(a \times c)-(b \times c)] \therefore ac \equiv bc \pmod{p} ##### 2.5 同幂性 若有 $a \equiv b \pmod{p}$，那么有 $a^c \equiv b^c \pmod{p}$，$c$ 为正整数。 **证明**： $\because a \equiv b \pmod{p} $\therefore a = b + (l_1 - l_2)p

令 l_3 = l_1 - l_2，则 a = b + l_3 p

由二项式定理可得：

a^c = (b + l_3 p)^c = \sum_{i=0}^{c}\binom{c}{i} b^{c-i} (l_3 p)^i

展开后，第一项为 \binom{c}{0}b^c(l_3 p)^0 = b^c，剩余项均含有因子 p，即：

a^c = b^c + p \cdot \sum_{i=1}^{c}\binom{c}{i} b^{c-i} l_3^i p^{i-1}

令 M = \sum_{i=1}^{c}\binom{c}{i} b^{c-i} l_3^i p^{i-1}，M 为整数，则 a^c = b^c + pM

\therefore p \mid (a^c - b^c) \therefore a^c \equiv b^c \pmod{p}