「一本书上每多一个公式，就会死掉减少一半读者。」—— 霍金
「这上面每多一个公式，我就会失明一次。」—— JQ
一、整除
- 若整数(b) 除以非零整数(a) ，商为整数，且余数为零， 我们就说(a) 能整除(b)，记作(a\mid b)，读作「(a) 整除(b)」或「(b) 能被(a) 整除」。其中，(a) 叫做(b) 的约数（因数），(b) 叫做(a) 的倍数。
- 否则，我们就说(a) 不能整除(b)，记作(a \nmid b)。
- 整除属于除尽的一种特殊情况。
性质 1（传递性）：若 (a\ |\ b,\ b\ |\ c)，则 (a\ |\ c)。
[\begin{align} 证：&由题可得： a \mid b,\ b \mid c \&令\ b = ax,\ c = by\ (x, y\in \mathbb{Z}, x \ne 0) \ &\therefore c = ax \cdot y \ &\therefore a \mid c \end{align}]
性质 2： 若 (a\ |\ b,\ a\ |\ c)，则 (a\ |\ bx\ \pm cy\ (x, y\in \mathbb{Z}))。
[\begin{align} 证：&由题可得： a \mid b,\ a \mid c \ &令\ b = am,\ c = an\ (x, y\in \mathbb{Z}) \ &\therefore a \mid bx \pm cy \ &\ \ \ \ \Leftrightarrow a\mid amx \pm any \ &\ \ \ \ \Leftrightarrow a\mid a(mx \pm ny) \ &\therefore a \mid bx \pm cy \end{align}]
补充：若 (a\ |\ b_i(i =1,2,\cdots,k)) , 则 (a \mid p_1b_1+p_2b_2+ \cdots+p_kb_k (p_j(j = 1,2\cdots,k) \in \mathbb{Z}))
性质 3：若 (x \in \mathbb{Z}, x \ne 0) 且 (a \mid b) ，则 (ax\mid bx\ (x\in \mathbb{Z}, x \ne 0))。
[\begin{align} 证：&令\ b = am\ (m\in \mathbb{Z},m\ne 0) \ &\therefore 目标 \Leftrightarrow ax\mid amx \ &\therefore ax\mid bx \end{align}]
性质 4：若 (ax + by = 1) ，且 (a \mid k,\ b \mid k)，则 (ab \mid k\ (x, y\in \mathbb{Z} 且\ a, b\ne 0))。
[\begin{align} 证：&令\ k = am = bn\ (m, n\in \mathbb{Z}) \ &\because ax + by = 1 \ &\therefore \frac{x}{b} + \frac{y}{a} = \frac{1}{ab} \ &\therefore \frac{k}{ab} = k \cdot (\frac{x}{b} + \frac{y}{a})= \frac{kx}{b} + \frac{ky}{a} = nx + my \ &\therefore 1 \mid \frac{k}{ab} \ &\therefore ab \mid k \end{align}]
性质 5：若 (a = bx + c)，则 (b \mid a) 的充分必要条件是 (b \mid c)。
[\begin{align} 证：&若已知\ b \mid c\ 且\ a = bx + c \ &令\ c = bm\ (m\in \mathbb{Z}) \ &\therefore a = bx + c \ &\ \ \ \ \Leftrightarrow a = bx + bm \ &\ \ \ \ \Leftrightarrow a = b(x + m) \ &\therefore b \mid a \ &若已知\ b \mid a\ 且\ a = bx + c \ &令\ a = bn\ (n\in \mathbb{Z}) \ &\therefore bn = bx + c \ &\ \ \ \ \Leftrightarrow c = bm – bx \ &\ \ \ \ \Leftrightarrow c = b(m – x) \ &\therefore b \mid c \end{align}]
注释：
- 充分必要条件：充分必要条件也即充要条件。意思是说，如果能从命题 p 推出命题 q，而且也能从命题 q 推出命题 p ，则称 p 是 q 的充分必要条件，且 q 也是 p 的充分必要条件。
- 充分条件：如果 A 能推出 B，那么 A 就是 B 的充分条件。
- 必要条件：如果没有 A，则必然没有 B；如果有 A 而未必有 B，则 A 就是 B 的必要条件。
性质 6：若 (p \mid a)，(q \mid a) 且 ((p, q) = 1)，则 (pq \mid a)。
[\begin{align} 证：&设\ a = mp = nq\ (m, n \in \mathbb{Z}) \& 由\ mp = nq\ 可知：p\mid nq \& \because p\ 与\ q\ 互质 \& \therefore p\mid n \& 设\ n = xp\ (x \in \mathbb{Z}) \& \therefore a = nq = xpq \& \therefore pq\mid a \end{align}]
注释：
- 为什么要加「((p, q) = 1) （即互质）」?
假若不加互质，是有可能成立的，但并不一定所有情况都成立。举个反🌰——
[3\mid 12\ 且\ 6\mid 12，但\ 3 \times 6 = 18，18\nmid 12。 ]
变式：
若 (p \mid a)，(q \mid a) 且 (mp + nq = 1)，则 (pq \mid a\ (m, n \in \mathbb{Z})).
解释：其实这个变式和「性质 6」是同理的。
「(mp + nq = 1)」，其实就表达了「 ((p, q) = 1)」（根据裴蜀定理可得，以后会补充）。
习题集 1. 证明：任意奇数的平方减 1 是 8 的倍数。
[\begin{align} 证：&设此奇数为\ 2k + 1\ (k \in \mathbb{Z}) \ & (2k + 1)^2 – 1 \ &= 4k^2 + 4k + 1- 1 \ &= 4k(k + 1) \ &\because8 \mid 4k(k + 1) \ &\therefore 8 \mid (2k + 1)^2 \end{align}]
- 证明：当 n 是偶数时，2 | 3^n + 1；当 n 是奇数时，2^2 | 3^n + 1；但无论 n 是偶数还是奇数，对任意正整数 α > 2，都有 2^α ∤ 3^n + 1 (n ∈ N+)。
[\begin{align} 证： \ (1) &\because n \equiv 0\pmod 2 \ &\therefore(3^n + 1)\bmod 2 \ &= [(3^n \bmod 2) + (1 \bmod 2)] \bmod 2 \ &= {[(3 \bmod 2)^n \bmod 2] + 1} \bmod 2 \ &= [(1 \bmod 2) + 1] \bmod 2 \ &= (1 + 1) \bmod 2 \ &= 0 \ (2)&\because n \equiv 1\pmod 2 \ &\therefore(3^n + 1)\bmod 2^2 \ &= [(3^n \bmod 4) + (1 \bmod 4)] \bmod 4 \ &= (3 + 1) \bmod 4 \ &= 0 \ (3)\ &若\ n \equiv 0 \pmod 2 \ &(3^n + 1)\bmod 2^{\alpha} \ &= [(3^n \bmod 2^{\alpha}) + (1 \bmod 2^{\alpha})] \bmod 2^{\alpha} \ &= (1 + 1) \bmod 2^{\alpha} \ &= 2 \bmod 2^{\alpha} \ &\because \alpha > 2 \ &\therefore 2^{\alpha} \gt 4 \ &\therefore 2 \bmod 2^{\alpha} = 2 \ &\therefore2^{\alpha} \nmid (3^n + 1) \ \ &若\ n \equiv 1 \pmod 2 \ &(3^n + 1)\bmod 2^{\alpha} \ &= [(3^n \bmod 2^{\alpha}) + (1 \bmod 2^{\alpha})] \bmod 2^{\alpha} \ &= (3 + 1) \bmod 2^{\alpha} \ &= 4 \bmod 2^{\alpha} \ &\because \alpha > 2 \ &\therefore 2^{\alpha} \gt 4 \ &\therefore 4 \bmod 2^{\alpha} = 4 \ &\therefore 2^{\alpha} \nmid (3^n + 1) \ \ &\therefore 综上，当\ \alpha > 2\ 时，无论\ n\ 是奇数还是偶数，都有\ 2^{\alpha} \nmid (3^n + 1)。 \end{align}]
- 感觉显然，过程待补。
There is NOTHING.
- 证明：如果 2a + 3b，9a + 5b 中有一个能被 17 整除，那么另外一个也能被 17 整除。
[\begin{align} 证：&若\ 17 \mid 2a + 3b \ &\because 17 \mid 2a + 3b \ &则\ 17 \mid 5 \times(2a + 3b) \ &\therefore 17 \mid 10a + 15b \ &\because (9a + 5b) \times 3 = 27a + 15b = (10a + 15b) + 17a \ &\because 17 \mid 17a \ &又\because 17 \mid 10a + 15b \ &\therefore 17 \mid (10a + 15b) + 17a \ &\therefore 17 \mid (9a + 5b) \times 3 \ &又\because (3, 17) = 1 \ &\therefore 17 \mid 9a + 5b \ \ &若\ 17 \mid 9a + 5b \ &\because 17 \mid 9a + 5b \ &则\ 17 \mid 3 \times(9a + 5b) \ &\therefore 17 \mid 27a + 15b \ &\because (2a + 3b) \times 5 = 10a + 15b = (27a+ 15b) – 17a \ &\because 17 \mid -17a \ &又\because 17 \mid 27a + 15b \ &\therefore 17 \mid (27a + 15b) – 17a \ &\therefore 17 \mid (2a + 3b) \times 5 \ &又\because (5, 17) = 1 \ &\therefore 17 \mid 2a + 3b \end{align}]
- x，y，z 均为整数，若 11 ∣ 7x + 2y − 5z，求证：11 ∣ 3x−7y+12z。
[\begin{align} 证：&令\ a = 7x + 2y − 5z，b = 3x – 7y + 12z \ &可构造：3a + 4b = 11(3x − 2y + 3z) \ &则\ 4b = 11 (3x − 2y + 3z ) − 3a \ &\because 11 \mid (11( 3x − 2y + 3z ) − 3a) \ &\therefore 11 \mid 4b \ &\because (11, 4) = 1 \ &\therefore 11\mid b \ &即\ 11\mid (3x−7y+12z) \end{align}]
二、模运算
- 对于整数(a,b\ (b \ne 0))，求(a) 除以(b) 的余数，记作(a \bmod b)。
[\begin{align} &(a + b) \bmod p = (a \bmod p + b \bmod p) \bmod p \ &(a – b) \bmod p = (a \bmod p – b \bmod p) \bmod p \ &(a \times b) \bmod p = (a \bmod p \times b \bmod p) \bmod p \ &a^b \bmod p = (a \bmod p)^b \bmod p \end{align}]
运算规则 1：((a + b) \bmod p = (a \bmod p + b \bmod p) \bmod p)。
[\begin{align} 证：&令\ a = mp + x, b = np + y\ (m, n, x, y \in \mathbb{Z}\ 且\ x = a \bmod p, y = b \bmod p) \ &\therefore a + b = (mp + x) + (np + y) \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ = p(m + n) + (x + y) \ &\therefore (a + b) \bmod p = [p(m + n) + (x + y)] \bmod p \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (x + y) \bmod p \ &又\because x = a \bmod p, y = b \bmod p \ &\therefore (a + b) \bmod p = (x + y) \bmod p \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (a \bmod p + b \bmod p) \bmod p \end{align}]
运算规则 2：((a – b) \bmod p = (a \bmod p – b \bmod p) \bmod p)。
[\begin{align} 证：&令\ a = mp + x, b = np + y\ (m, n, x, y \in \mathbb{Z}\ 且\ x = a \bmod p, y = b \bmod p) \ &\therefore a – b = (mp + x) – (np + y) \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ = p(m – n) + (x – y) \ &\therefore (a – b) \bmod p = [p(m – n) + (x – y)] \bmod p \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (x – y) \bmod p \ &又\because x = a \bmod p, y = b \bmod p \ &\therefore (a – b) \bmod p = (x – y) \bmod p \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (a \bmod p – b \bmod p) \bmod p \end{align}]
运算规则 3：((a \times b) \bmod p = (a \bmod p \times b \bmod p) \bmod p)。
[\begin{align} 证：&令\ a = mp + x, b = np + y\ (m, n, x, y \in \mathbb{Z}\ 且\ x = a \bmod p, y = b \bmod p) \ &\therefore a \times b = (mp + x) \times (np + y) \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ = mnp^2 + mpy + npx + xy \ &\therefore (a \times b) \bmod p = [(mp + x) \times (np + y) ] \bmod p \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (mnp^2 + mpy + npx + xy) \bmod p \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = [p(mnp + my + nx) + xy] \bmod p \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = xy \bmod p \ &又\because x = a \bmod p, y = b \bmod p \ &\therefore (a \times b) \bmod p = (x \times y) \bmod p \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (a \bmod p \times b \bmod p) \bmod p \end{align}]
运算规则 4：(a^b \bmod p = (a \bmod p)^b \bmod p)。
析：可使用多次「运算规则 3」来证明，为节省篇幅，此略。
1.放：若 (a \bmod b = c)，则 (ax \bmod bx = cx\ (x \in \mathbb{Z}\ 且\ x \ne 0))。
[\begin{align} 证：&令\ a = mb + c \ &则\ ax \bmod bx \ &\Leftrightarrow (mbx + cx) \bmod bx \ &\Leftrightarrow [(mbx \bmod bx) + (cx \bmod bx)] \bmod bx \ &又\because a \bmod b = c \ &\therefore c \lt b \ &\therefore [(mbx \bmod bx) + (cx \bmod bx)] \bmod bx \ &= (0 + cx) \bmod bx \ &= cx \ &\therefore ax \bmod bx = cx \end{align}]
2.缩：若 (a \bmod b = c)，则 (\dfrac{a}{x} \bmod \dfrac{b}{x} = \dfrac{c}{x}\ (x \in \mathbb{Z}\ 且\ x \ne 0))。
[\begin{align} 证：&令\ a = mb + c \ &\therefore \dfrac{a}{x} = \dfrac{mb}{x} + \dfrac{c}{x} \ &又\because a \bmod b = c \ &\therefore c \lt b \ &\therefore \dfrac{c}{x} \lt \dfrac{b}{x} \ &\therefore \dfrac{a}{x} \bmod \dfrac{b}{x} = \dfrac{c}{x} \end{align}]
1.若 (2) 能整除 (a) 的末一位（约定 (0) 可被任意数整除），则 (2 \mid a)。
[\begin{align} 证：&设\ a = 10x + b\ (x, b \in \mathbb{N}\ 且\ 0 \le b \le 9) \ &\therefore a \bmod 2 \ &\Leftrightarrow (10x + b) \bmod 2 \ &= (10x \bmod 2) + (b \bmod 2) \ &\because 2 \mid 10\ 且\ 2 \mid b \ &\therefore 原式 = 0 \end{align}]
2.若 (4) 能整除 (a) 的末两位（约定 (0) 可被任意数整除），则 (4 \mid a)。
[\begin{align} 证：&设\ a = 100x + b\ (x, b \in \mathbb{N}\ 且\ 0 \le b \le 99) \ &\therefore a \bmod 4 \ &\Leftrightarrow (100x + b) \bmod 4 \ &= (100x \bmod 4) + (b \bmod 4) \ &\because 4 \mid 100\ 且\ 4 \mid b \ &\therefore 原式 = 0 \end{align}]
3.若 (8) 能整除 (a) 的末三位（约定 (0) 可被任意数整除），则 (8 \mid a)。
[\begin{align} 证：&设\ a = 1000x + b\ (x, b \in \mathbb{N}\ 且\ 0 \le b \le 999) \ &\therefore a \bmod 8 \ &\Leftrightarrow (1000x + b) \bmod 8 \ &= (1000x \bmod 8) + (b \bmod 8) \ &\because 8 \mid 1000\ 且\ 8 \mid b \ &\therefore 原式 = 0 \end{align}]
4.若 (3) 能整除 (a) 的各个数位上的数之和（约定 (0) 可被任意数整除），则 (3 \mid a)。
[\begin{align} 证：&设\ a = \overline{b_1b_2 \cdots b_n}\ (b_i \in \mathbb{N}\ 且\ 0 \le b_i \le 9\ 且\ b_1 \ne 0) \ &\therefore a = b_1 \times \underbrace{100\cdots00}{n} + b_2 \times \underbrace{100\cdots00}{n – 1} + \cdots + b_{n – 1} \times 10 + b_n \times 1 \ &\therefore a \bmod 3 \ &= (b_1 \times \underbrace{100\cdots00}{n} \bmod 3) + (b_2 \times \underbrace{100\cdots00}{n – 1} \bmod 3) + \cdots + (b_{n – 1} \times 10 \bmod 3) + (b_n \times 1 \bmod 3) \ &= (b_1 \bmod 3) \times (\underbrace{100\cdots00}{n} \bmod 3) + (b_2 \bmod 3) \times (\underbrace{100\cdots00}{n – 1} \bmod 3) + \cdots + (b_{n – 1} \bmod 3) \times (10 \bmod 3) + (b_n \bmod 3) \times (1 \bmod 3) \ &= (b_1 \bmod 3) \times 1 + (b_2 \bmod 3) \times 1 + \cdots + (b_{n – 1} \bmod 3) \times 1+ (b_n \bmod 3) \times 1 \ &= (b_1+ b_2 + \cdots + b_{n – 1} + b_n) \bmod 3 \ &\therefore a \bmod 3 \Leftrightarrow(b_1+ b_2 + \cdots + b_{n – 1} + b_n) \bmod 3 \end{align}]
5.若 (11) 能整除 (a) 的奇数位（从低位向高位数）之和与偶数位之和的差（约定 (0) 可被任意数整除），则 (11 \mid a)。
[\begin{align} 证：&设\ a = \overline{b_1b_2 \cdots b_n}\ (b_i \in \mathbb{N}\ 且\ 0 \le b_i \le 9\ 且\ b_1 \ne 0) \ &\therefore a = b_1 \times \underbrace{100\cdots00}{n} + b_2 \times \underbrace{100\cdots00}{n – 1} + \cdots + b_{n – 1} \times 10 + b_n \ &\therefore a \bmod 11 \ &= (b_1 \times (\underbrace{999\cdots99}{n – 1} + 1) \bmod 11) + (b_2 \times (\underbrace{100\cdots01}{n – 1} – 1) \bmod 11) + \cdots + (b_{n – 1} \times (11 – 1) \bmod 11) + (b_n \bmod 11) \ &= (b_1 \times 1 \bmod 11) + (b_2 \times (-1) \bmod 11) + \cdots + (b_{n – 1} \times (-1) \bmod 11) + (b_n \bmod 11) \ &= (b_1 \bmod 11) – (b_2 \bmod 11) + \cdots – (b_{n – 1} \bmod 11) + (b_n \bmod 11) \ &= (b_1 – b_2 + \cdots – b_{n – 1} + b_n) \bmod 11 \ &= (b_1 + b_3 + \cdots + b_n) – (b_2 + b_4 + \cdots + b_{n – 1}) \bmod 11 \end{align}]
6.若 (7,11,13) 能整除 (a) 的末三位与末三位之前的数所组成的数之差（约定 (0) 可被任意数整除），则 (7 \mid a) 且 (11 \mid a) 且 (13 \mid a)（即 (1001 \mid a)）。
[\begin{align} 证：&设\ a = \overline{b_1b_2 \cdots b_n}\ (b_i \in \mathbb{N}\ 且\ 0 \le b_i \le 9\ 且\ b_1 \ne 0) \ &\therefore a \bmod 1001 \ &\Leftrightarrow (\overline{b_1b_2 \cdots b_{n – 3}} \times 1000 + \overline{b_{n – 2}b_{n – 1}b_n}) \bmod 1001 \ &\Leftrightarrow {(\overline{b_1b_2 \cdots b_{n – 3}} \bmod 1001) \times [(1001 – 1) \bmod 1001] + (\overline{b_{n – 2}b_{n – 1}b_n} \bmod 1001)] \bmod 1001 \ &\Leftrightarrow {(\overline{b_1b_2 \cdots b_{n – 3}} \bmod 1001) \times (-1) + (\overline{b_{n – 2}b_{n – 1}b_n} \bmod 1001)] \bmod 1001 \ &\Leftrightarrow (\overline{b_{n – 2}b_{n – 1}b_n} -\overline{b_1b_2 \cdots b_{n – 3}}) \bmod 1001 \end{align}]
三、同余
- 设 (m) 是一个给定的正整数，若满足 (m \mid a – b)，则称 (a) 与 (b) 对模 (m) 同余，记作 (a \equiv b \pmod m)（称为 (a, b) 模 (m) 的同余式）。
- 若 (m \nmid a – b)，则 (a, b) 一定不同余。
- 若满足 (a = b + km\ (k \in \mathbb{Z}))，则 (a) 和 (b) 被 (m) 除时有相同的余数。即：(m \mid a – b \Leftrightarrow a \equiv b \pmod m)。
- 如果没有特别说明， 模数总是正整数。
- 若 (p = a – b)，则 (a \equiv b \pmod p\ (a, b, p \in \mathbb{Z}))。证明：若 p = a – b，则 a≡b(mod p) (a,b,p ∈ Z)
[\begin{align} 证：&\because a = b + p \ &\therefore a \bmod p \ &\Leftrightarrow (b + p) \bmod p \ &\Leftrightarrow [(b \bmod p) + (p \bmod p)] \bmod p \ &\Leftrightarrow b \bmod p \end{align}]
性质 1（自反性）：(a \equiv a \pmod m)。
析：真 · 显然
性质 2（对称性）：若 (a \equiv b \pmod p)，则 (b \equiv a \pmod p)。
析：真 · 显然
性质 3（传递性）：若 (a \equiv b \pmod p)，(b \equiv c \pmod p)，则 (a \equiv c \pmod p)。
析：真 · 显然
性质 4（同加性）：若 (a \equiv b \pmod p)，则 ((a + c) \equiv (b + c) \pmod p)。
[\begin{align} 证：&\because a \equiv b \pmod p \ &\therefore p \mid a – b \ &\Rightarrow p \mid a – b + c – c \ &\Rightarrow p \mid (a + c) – (b + c) \ &\therefore (a + c) \equiv (b + c) \pmod p \end{align}]
性质 5（同减性）：若 (a \equiv b \pmod p)，则 ((a – c) \equiv (b – c) \pmod p)。
[\begin{align} 证：&\because a \equiv b \pmod p \ &\therefore p \mid a – b \ &\Rightarrow p \mid a – b + c – c \ &\Rightarrow p \mid (a – c) – (b – c) \ &\therefore (a – c) \equiv (b – c) \pmod p \end{align}]
性质 6（同乘性）：若 (a \equiv b \pmod p)，则 ((a – c) \equiv (b – c) \pmod p)。
[\begin{align} 证：&\because a \equiv b \pmod p \ &\therefore p \mid a – b \ &\Rightarrow p \mid (a – b) \times c \ &\Rightarrow p \mid ac – bc \ &\therefore (a – c) \equiv (b – c) \pmod p \end{align}]
性质 7（同除性）：若 (a \equiv b \pmod p)，且 (c \mid a,\ c \mid b,\ (c, m) = 1)，则 (\dfrac{a}{c} \equiv \dfrac{b}{c} \pmod p)。
[\begin{align} 证：&令\ a = k_1c,\ b = k_2c\ (k \in \mathbb{Z}) \ &\therefore \dfrac{a}{c} \equiv \dfrac{b}{c} \pmod p \Leftrightarrow k_1 \equiv k_2 \pmod p \ &\ \ \ \ \ m \mid (a – b) \Leftrightarrow m \mid (k_1 – k_2) \cdot c \ &又\because (c, m) = 1 \ &\therefore m \mid k_1 – k_2 \ &\therefore k_1 \equiv k_2 \pmod p \ &即\ \dfrac{a}{c} \equiv \dfrac{b}{c} \pmod p \end{align}]
性质 8（同幂性）：若 (a \equiv b \pmod p)，(c \gt 0)，则 (a^c \equiv b^c \pmod p)。
析：多次「性质 6」可证，不重复赘述。
性质 9：若 (a \equiv b \pmod p)，(c \equiv d \pmod p)，则 ((a + c) \equiv (b + d) \pmod p)。
[\begin{align} 证：&\because a \equiv b \pmod p,\ c \equiv d \pmod p \ &\therefore m \mid a – b,\ m \mid c – d \ &\therefore m \mid a – b + c – d \ &\therefore m \mid (a + c) – (b + d) \end{align}]
性质 10：若 (a \equiv b \pmod p)，(c \equiv d \pmod p)，则 (ac \equiv bd \pmod p)。
[\begin{align} 证：&\because a \equiv b \pmod p,\ c \equiv d \pmod p \ &\therefore m \mid a – b,\ m \mid c – d \ &\therefore m \mid (a – b) \cdot c,\ m \mid (c – d) \cdot b \ &\therefore m \mid ac – bc + bc – bd \ &\Leftrightarrow m \mid ac – bd \ &\therefore ac \equiv bd \pmod m \end{align}]
性质 11：若 (a \equiv x \pmod p)，(a \equiv x \pmod q) 且 ((p, q) = 1)，则 (a \equiv x \pmod {pq})。
[\begin{align} 证：&\because a \equiv x \pmod p,\ a \equiv x \pmod q \ &\therefore p \mid (a – x),\ q \mid (a – x) \ &\therefore (a – x)\ 是\ p,q\ 的公倍数 \ &\therefore (a – x)=p^{k_1}q^{k_2}\ (1 \le k,k \in \mathbb{Z}) \ &\therefore pq \mid a – x \ &\therefore a \equiv x \pmod {pq} \end{align}]
关于『数论』:整除理论 填坑完毕（习题待补）。 (淋漓的诠释了什么是 “鸽王”)
(我 真 爱 数 学 呢)
(救命学数学真的会头秃)
填坑.ING🌚🌚🌚
更博弈论怕是要等到猴年马月了。。。
蒟蒻要励志学好数学！！1
Original: https://www.cnblogs.com/kylin-king/p/16650980.html
Author: 北柒kylin
Title: 关于『数论』：整除理论
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588146/
转载文章受原作者版权保护。转载请注明原作者出处！