当前位置：首页 > news >正文

初等数论总结

news 来源：原创 2024/5/17 16:13:03

初等数论

一、整除

1. 定义

设 $\in Z, a \neq 0$ ，若 $\exist q \in Z$ ，使得 $b = a q$ ，则有 $b$ 能被 $a$ 整除，记作 $\mid b$ ，且称 $b$ 是 $a$ 的因数， $a$ 是 $b$ 的约数，反之即 $b$ 不能被 $a$ 整除，则记为 $\nmid b$ ；

2. 性质

性质1

若 $\mid b$ 且 $\mid c$ ，则 $\mid c$ ；

证明如下，

$\begin{aligned} & \because a \mid b \; 则令 \; ax = b (x \in Z \; 且 \; x \neq 0) \\ & \quad \; b \mid c \; 则令 \; by = c (y \in Z \; 且 \; y \neq 0) \\ & \therefore axy = c (x, y \in Z \; 且 \; x, y \neq 0) \\ & \therefore a \mid c \end{aligned}$

性质2

$\mid b$ 且 $\mid c$ 等价于对 $\forall Z x, y$ ，有 $\mid (bx + cy)$ ；

证明如下，

$\begin{aligned} & \because a \mid b \; 则令 \; ap = b (p \in Z \; 且 \; p \neq 0) \\ & \quad \; a \mid c \; 则令 \; aq = c (q \in Z \; 且 \; q \neq 0) \\ & 又\because bx + cy = apx + aqy = a(px + qy) \\ & 又\because a \mid (a(px + qy)) \\ & \therefore a \mid (bx + cy) \end{aligned}$

性质3

设 $\neq 0$ ，则 $\mid b$ 等价于 $\mid (mb)$ ；

证明如下，

$\begin{aligned} & \because a \mid b \; 则令 \; aq = b (p \in Z \; 且 \; p \neq 0) \\ & \therefore aqm = bm \\ & \therefore (ma) \mid (mb) \end{aligned}$

性质4

设有 $\in Z$ 满足 $a x + b y = 1$ ，且 $\mid n, b \mid n$ ，则 $\mid n$ ；

证明如下，

$\begin{aligned} & \because a \mid n, b \mid n \\ & \therefore (ab) \mid (nb), (ab) \mid (na) \\ & \therefore (ab) \mid (nby + nax) \\ & \therefore (ab) \mid (n(by + ax)) \\ & \therefore (ab) \mid n \\ \end{aligned}$

性质5

若 $\in Z$ ，则 $\mid b$ 的充分必要条件为 $\mid c$ ；

证明如下，

证明必要性，即 $\in Z$ 且 $\mid b$ 可得 $\mid c$ ；

$\begin{aligned} & \because d \mid b \; 则令 \; dx = b (x \in Z \; 且 \; x \neq 0) \\ & \therefore dx = qd + c \\ & \therefore d(x - q) = c \\ & \therefore d \mid c \end{aligned}$
证明充分性，即 $\in Z$ 且 $\mid c$ 可得 $\mid b$ ；

$\begin{aligned} & \because d \mid c \; 则令 \; dx = c (x \in Z \; 且 \; x \neq 0) \\ & \therefore b = qd + xd \\ & \therefore d(x + q) = b \\ & \therefore d \mid b \end{aligned}$

二、模运算

1. 定义

对于 $\in Z, b \neq 0$ ， $\div b$ 的余数即为 $a$ 模 $b$ ，记作 $\; mod \; b$ ；

2. 性质

分配律

加法， $\; mod \; c = (a \; mod \; c + b \; mod \; c) \; mod \; c$ ；

证明如下，

$\begin{aligned} & 设 a = cp + x (p, x \in Z, 0 \leq x < c) \\ & \quad b = cq + y (q, y \in Z, 0 \leq y < c) \\ & \therefore (a + b) \; mod \; c = (c(p + q) + x + y) \; mod \; c = (x + y) \; mod \; c \\ & \therefore (a + b) \; mod \; c = (a \; mod \; c + b \; mod \; c) \; mod \; c \end{aligned}$
减法， $\; mod \; c = (a \; mod \; c - b \; mod \; c) \; mod \; c$ ；

证明如下，

$\begin{aligned} & 设 a = cp + x (p, x \in Z, 0 \leq x < c) \\ & \quad b = cq + y (q, y \in Z, 0 \leq y < c) \\ & \therefore (a - b) \; mod \; c = (c(p - q) + x - y) \; mod \; c = (x - y) \; mod \; c \\ & \therefore (a - b) \; mod \; c = (a \; mod \; c - b \; mod \; c) \; mod \; c \end{aligned}$
乘法， $\; mod \; c = (a \; mod \; c \times b \; mod \; c) \; mod \; c$ ；

证明如下，

$\begin{aligned} & 设 a = cp + x (p, x \in Z, 0 \leq x < c) \\ & \quad b = cq + y (q, y \in Z, 0 \leq y < c) \\ & \quad \; (ab) \; mod \; c \\ & = ((cp + x) * (cq + y)) \; mod \; c \\ & = (ccpq + cpy + cqx + xy) \; mod \; c \\ & = xy \; mod \; c \\ & = (a \; mod \; c \times b \; mod \; c) \; mod \; c \end{aligned}$
扩展， $a^b) \; mod \; c = (a \; mod \; c)^b \; mod \; c$ ;

放缩性

乘法，有 $\; mod \; b = c, d \neq 0$ ，则有 $\; mod \; (bd) = cd$ ；

证明如下，

$\begin{aligned} & \because a \; mod \; b = c \; 则令 \; a = bx + c (x \in Z) \\ & \therefore ad = bdx + cd \\ & \therefore (bdx + cd) \; mod \; (bd) = cd \\ & \therefore (ad) \; mod \; (bd) = cd \end{aligned}$
除法，有 $\; mod \; b = c, d \neq 0$ ，则有 $(\frac{a}{d}) \; mod \; (\frac{b}{d}) = \frac{c}{d}$ ；

3. 推论

推论1

若 2 能整除 $a$ 的最末位 (0 能被 $\forall Z$ 整除) ，则 $a$ 能被 2 整除；

证明如下，

$\begin{aligned} & 设 \; a = 10x + y (x, y \in Z^{+}, 0 \leq y \leq 9) \\ & \therefore 2 \mid y \\ & 又\because a \; mod \; 2 = (10x \; mod \; 2 + y \; mod \; 2) \; mod \; 2 = 0 \\ & \therefore 2 \mid a \end{aligned}$

推论2

若 4 能整除 $a$ 的最末 2 位 (0 能被 $\forall Z$ 整除) ，则 $a$ 能被 4 整除；

证明如下，

$\begin{aligned} & 设 \; a = 100x + y (x, y \in Z^{+}, 0 \leq y \leq 99) \\ & \therefore 4 \mid y \\ & 又\because a \; mod \; 4 = (100x \; mod \; 4 + y \; mod \; 4) \; mod \; 4 = 0 \\ & \therefore 4 \mid a \end{aligned}$

推论3

若 8 能整除 $a$ 的最末 3 位 (0 能被 $\forall Z$ 整除) ，则 $a$ 能被 8 整除；

证明如下，

$\begin{aligned} & 设 \; a = 1000x + y (x, y \in Z^{+}, 0 \leq y \leq 999) \\ & \therefore 8 \mid y \\ & 又\because a \; mod \; 8 = (1000x \; mod \; 8 + y \; mod \; 8) \; mod \; 8 = 0 \\ & \therefore 8 \mid a \end{aligned}$

推论4

若 3 能整除 $a$ 的各个数位之和，则 $a$ 能被 3 整除；

证明如下，以 3 位数为例，

$\begin{aligned} & 设 \; a = \overline{xyz} \; (x, y, z \in Z^{+}, 1 \leq x \leq 9, 0 \leq y,z \leq 9) \\ & \therefore (x + y + z) \; mod \; 3 = 0 \\ & \therefore \overline{xyz} \; mod \; 3 \\ & = (100x + 10 y + z) \; mod \; 3 \\ & = 100x \; mod \; 3 + 10y \; mod \; 3 + z \; mod \; 3 \\ & = x \; mod \; 3 + y \; mod \; 3 + z \; mod \; 3 \\ & = 0 \\ & \therefore 3 \mid a \end{aligned}$

推论5

若 9 能整除 $a$ 的各个数位之和，则 $a$ 能被 9 整除；

证明如下，以 3 位数为例，

$\begin{aligned} & 设 \; a = \overline{xyz} \; (x, y, z \in Z^{+}, 1 \leq x \leq 9, 0 \leq y,z \leq 9) \\ & \therefore (x + y + z) \; mod \; 9 = 0 \\ & \therefore \overline{xyz} \; mod \; 9 \\ & = (100x + 10 y + z) \; mod \; 9 \\ & = 100x \; mod \; 9 + 10y \; mod \; 9 + z \; mod \; 9 \\ & = x \; mod \; 9 + y \; mod \; 9 + z \; mod \; 9 \\ & = 0 \\ & \therefore 9 \mid a \end{aligned}$

推论6

若 11 能整除 $a$ 的奇数数位与偶数数位的差，则 $a$ 能被 11 整除；

证明如下，以 5 位数为例，

$\begin{aligned} & 设 \; a = \overline{x_1x_2x_3x_4x_5} \; (x_1, x_2, x_3, x_4, x_5 \in Z^{+}, 1 \leq x_1 \leq 9, 0 \leq x_2, x_3, x_4, x_5 \leq 9) \\ & \therefore (x_1 + x_3 + x_5 - x_2 - x_4) \; mod \; 11 = 0 \\ & \therefore \overline{x_1x_2x_3x_4x_5} \; mod \; 11 \\ & = ((9999 + 1)x_1 + (1001 - 1)x_2 + (99 + 1)x_3 + (11 - 1)x_4 + x_5) \; mod \; 11 \\ & = (x_1 - x_2 + x_3 - x_4 + x_5) \; mod \; 11 \\ & = 0 \\ & \therefore 11 \mid a \end{aligned}$

推论7

若 7, 11, 13 能整除 $a$ 的末 3 位与末 3 位以前的数字所组成的数的差，则 $a$ 能被 7, 11, 13 整除；

证明如下，以 5 位数为例，

$\begin{aligned} & 设 \; a = \overline{x_1x_2x_3x_4x_5} \; (x_1, x_2, x_3, x_4, x_5 \in Z^{+}, 1 \leq x_1 \leq 9, 0 \leq x_2, x_3, x_4, x_5 \leq 9) \\ & \therefore \overline{x_3x_4x_5} - \overline{x_1x_2} \; mod \; 1001 = 0 \\ & \therefore \overline{x_1x_2x_3x_4x_5} \; mod \; 1001 \\ & = (\overline{x_1x_2} * 1000 + \overline{x_3x_4x_5}) \; mod \; 1001 \\ & = (-\overline{x_1x_2} + \overline{x_3x_4x_5}) \; mod \; 1001 \\ & = 0 \\ & \therefore 1001 \mid a \end{aligned}$

三、同余

1. 定义

若 $\in Z，m \in Z^{+}$ ，且 $\mid (a - b)$ ，或 $\in Z)$ 则称 $a$ 与 $b$ 模 $m$ 同余，记为 $\equiv b (mod \; m)$ ；

证明 $\mid (a - b) \Leftrightarrow a \equiv b (mod \; m)$ 如下，

$\begin{aligned} & \because m \mid (a - b) \\ & \therefore m(q_1 - q_2) = a - b (q_1, q_2 \in Z) \\ & \therefore a - mq_1 = b - mp_2 = r \\ & \therefore a = mq_1 + r, b = mp_2 + r \\ & \therefore a \equiv b (mod \; m) \\ \end{aligned}$

2. 性质

自反性

$\equiv a (mod \; m)$ ；

证明如下，

$\begin{aligned} & \because m \mid (a - a) \\ & \therefore a \equiv a (mod \; m) \end{aligned}$

对称性

$\equiv b (mod \; m)$ 则 $\equiv a (mod \; m)$ ；

证明如下，

$\begin{aligned} & \because a \equiv b (mod \; m) \\ & \therefore m \mid (a - b) \\ & \therefore m \mid (b - a) \\ & \therefore b \equiv a (mod \; m) \end{aligned}$

传递性

若 $\equiv b (mod \; m)$ 且 $\equiv c (mod \; m)$ ，则 $\equiv c (mod \; m)$ ；

证明如下，

$\begin{aligned} & \because m \mid (a - b), m \mid (b - c) \\ & \therefore m \mid (a - b + b - c) \\ & \therefore m \mid (a - c) \\ & \therefore a \equiv c (mod \; m) \end{aligned}$

同加性

若 $\equiv b (mod \; m)$ ，则 $\equiv b + c (mod \; m)$ ；

证明如下，

$\begin{aligned} & \because a \equiv b (mod \; m) \\ & \therefore m \mid (a - b) \\ & \therefore m \mid (a - b) + c - c \\ & \therefore m \mid (a + c) - (b + c) \\ & \therefore a + c \equiv b + c (mod \; m) \end{aligned}$

同减性

若 $\equiv b (mod \; m)$ ，则 $\equiv b - c (mod \; m)$ ；

证明如下，

$\begin{aligned} & \because a \equiv b (mod \; m) \\ & \therefore m \mid (a - b) \\ & \therefore m \mid (a - b) - c + c \\ & \therefore m \mid (a - c) - (b - c) \\ & \therefore a - c \equiv b - c (mod \; m) \end{aligned}$

同乘性

若 $\equiv b (mod \; m)$ ，则 $\equiv bc (mod \; m)$ ；

证明如下，

$\begin{aligned} & \because a \equiv b (mod \; m) \\ & \therefore m \mid (a - b) \\ & \therefore m \mid c(a - b) \\ & \therefore m \mid ca - cb \\ & \therefore ac \equiv bc (mod \; m) \end{aligned}$

同除性

若 $\equiv b (mod \; m)$ 且 $\mid a, c \mid b, (c, m) = 1$ ，则 $\frac ac \equiv \frac bc (mod \; m)$ ；

$\begin{aligned} & \because a \equiv b (mod \; m) \\ & \therefore m \mid (a - b) \\ & 又\because (c, m) = 1 \\ & \therefore m \mid \frac{(a - b)}{c} \\ & \therefore m \mid \frac ac - \frac bc \\ & \therefore \frac ac \equiv \frac bc (mod \; m) \end{aligned}$

同幂性

若 $\equiv b (mod \; m)$ ，则 $a^n \equiv b^n (mod \; m)$ ；

证明如下，

$\begin{aligned} & \because a \equiv b (mod \; m) \\ & \therefore a \; mod \; m = b \; mod \; m \\ & \therefore (a \; mod \; m)^n = (b \; mod \; m)^n \\ & \therefore (a \; mod \; m)^n - (b \; mod \; m)^n = 0 \\ & \therefore a^n \equiv b^n (mod \; m) \end{aligned}$

推论1

若 $\equiv b (mod \; m), c \equiv d (mod \; m)$ ，则 $\equiv c + d (mod \; m)$ ；

证明如下，

$\begin{aligned} & \because a \equiv b (mod \; m) \\ & \therefore m \mid (a - b) \\ & \because c \equiv d (mod \; m) \\ & \therefore m \mid (c - d) \\ & \therefore m \mid (a - b + c - d) \\ & \therefore a + b \equiv c + d (mod \; m) \end{aligned}$

推论2

若 $\equiv b (mod \; m), c \equiv d (mod \; m)$ ，则 $\equiv cd (mod \; m)$ ；

证明如下，

$\begin{aligned} & \because a \equiv b (mod \; m) \\ & \therefore m \mid c(a - b) \\ & \because c \equiv d (mod \; m) \\ & \therefore m \mid a(c - d) \\ & \therefore m \mid (ac - bc + bc - cd) \\ & \therefore ab \equiv cd (mod \; m) \end{aligned}$

推论3

若 $\; mod \; p = x, a \; mod \; q = x, (p, q) = 1$ ，则 $\; mod \; (pq) = x$ ；

证明如下，

$\begin{aligned} & \because a \; mod \; p = x \; 则令 \; sp = a - x \\ & \quad \; a \; mod \; q = x \; 则令 \; tq = a - x \\ & \therefore sp = tq \\ & \because (p, q) = 1 \\ & \therefore s = nq \\ & \therefore a = npq + x \\ & \therefore a \; mod \; (pq) = x \end{aligned}$