0x01 整除
概念： 设 (a, b in mathbb Z) 且 (a eq 0)，如果 (exists q in mathbb Z)，使得 (a imes q = b)，则 (b) 能被 (a) 整除，记为 (a mid b)。
性质：
1. 传递性：如果 (a mid b) 且 (b mid c)，则 (a mid c)。
2. 若(a mid b) 且 (a mid c) 则对于 (forall a, b in mathbb Z)，有 (a mid (bx+cy))。
3. 设 (m) 不为 (0)，则 (a mid b) 等价于 (ma mid mb)。
4. 设 (x,y in mathbb Z) 满足下式：(ax+by=1)，且 (a mid n)，(b mid n)，那么 (ab mid n)
5. 若 (exists b, q, d, c in mathbb Z) 且 (b = q imes d + c)，那么 (d mid b) ，(d mid c) 可以互推。
证明：
1. 记 (b = ak_a(k_a in mathbb Z))，且 (c = bk_b(k_b in mathbb Z))
则有 (c = (ak_a)k_b)
即 (c = k_ak_ba)
其中 (k_a, k_b in mathbb Z)
(∴ a mid c)
2. 记 (b = ak_b(k_b in mathbb Z))，且 (c = ak_c(k_c in mathbb Z))
(∴ bx + cy = (ak_b)x + (ak_c)y)
即 (bx + cy = a(k_bx + k_cy))
其中 (k_b, k_c, x, y in mathbb Z)
(∴ (k_bx + k_cy) in mathbb Z)
故 (a mid (bx+cy))
3. 记 (b = ak_b(k_b in mathbb Z))
(∴ mb = mak_b (k_b in mathbb Z))
且 (m in mathbb Z, m eq 0)
(∴ ma mid mb)
4. (∵ ax + by = 1)
(∴ frac x b + frac y a = frac 1 {ab})
(∴ frac n {ab} = frac {xn} b + frac {ny} a)
又由题： (ak_a = n, bk_b = n(k_a, k_b in mathbb Z))
(∴ frac n {ab} = k_ay + k_bx)
即 (n = ab(k_ay + k_bx))
(∵ k_a, k_b, x, y in mathbb Z)
(∴ ab mid n)
5.1
记 (b = d * k_b(k_b in mathbb Z))
(∴ dk_b = qd + c)
即 (d(k_b - q) = c)
(∵ k_b, q in mathbb Z)
(∴ (k_b - q) in mathbb Z)
故 (d mid c)
5.2 记 (c = d * k_c(k_c in mathbb Z))
(∴ b = qd + qk_c)
即 (d(k_c + q) = b)
(∵ k_c, q in mathbb Z)
(∴ (k_c + q) in mathbb Z)
故 (d mid b)
0x02 mod
概念： 对于(a,b in mathbb Z, b eq 0)，求 (a) 除以 (b) 的余数，称为 (a) 模 (b)，记为 (a mod b)。
性质： 暂且研究 (a > 0, b geq 0)
0. 杂论：((a + kb) mod b = a mod b)
1. 分配率：模运算对加、减、乘具有分配率
1.1 ((a + b) mod c = (a mod c + b mod c) mod c)
1.2 ((a - b) mod c = (a mod c - b mod c) mod c)
1.3 ((a imes b) mod c = [(a mod c) imes (b mod c)] mod c)
1.4 ((a^b) mod c = (a mod c)^b mod c)
2. 放缩性:
2.1 如果 (a mod b = c, d eq 0)，则有 ((a imes d) mod (b imes d) = c imes d)
2.2 如果 (a mod b = c, d eq 0)，则有 (frac a d mod frac b d = frac c d)
证明：
0.1 (a < b)
记 (x = a + kb)
根据 (mod) 的定义，(x mod b = a)
所以 ((a + kb) mod b = a)
0.2 (a geqslant b)
(∴(a + kb) mod b = [(a - lfloor frac a b floor imes b) + (k + lfloor frac a b floor)b] mod b)
由定义得：(a mod b = a - lfloor frac a b floor imes b)
(∴[(a - lfloor frac a b floor imes b) + (k + lfloor frac a b floor)b] mod b = [a mod b + (k + lfloor frac a b floor)b] mod b)
(∵ a mod b < b)
然后用 0.1 解决即可。
1.1 记 (a = c * q_a + r_a, b = c * q_b + r_b (q_a, q_b, r_a, r_b in mathbb Z, r_a,rb < c))
(∴ (a + b) mod c = (c * q_a + r_a + c * q_b + r_b) mod c)
即 ((a + b) mod c = [r_a + r_b + (q_a + q_b)c] mod c)
由 0 得：((a + b) mod c = (r_a + r_b) mod c))
(∵r_a = a mod c, r_b = b mod c)
(∴ (a + b) mod c = (a mod c + b mod c) mod c)
1.2 记 (a = c * q_a + r_a, b = c * q_b + r_b (q_a, q_b, r_a, r_b in mathbb Z, r_a,rb < c))
(∴ (a - b) mod c = (c * q_a + r_a - c * q_b - r_b) mod c)
即 ((a - b) mod c = [r_a - r_b + (q_a - q_b)c] mod c)
由 0 得：((a - b) mod c = (r_a - r_b) mod c))
(∵r_a = a mod c, r_b = b mod c)
(∴ (a - b) mod c = (a mod c - b mod c) mod c)
1.3 记 (a = c * q_a + r_a, b = c * q_b + r_b (q_a, q_b, r_a, r_b in mathbb Z, r_a,rb < c))
(∴ (a * b) mod c = [(c * q_a + r_a) * (c * q_b + r_b)] mod c)
(∴ (a * b) mod c = (q_aq_bc^2 + q_ar_bc + q_br_ac + r_ar_b) mod c)
即 $ (a * b) mod c = [r_a * r_b + c(q_aq_bc + q_ar_b + q_br_a)] mod c$
由 0 得：((a * b) mod c = (r_a * r_b) mod c))
(∵r_a = a mod c, r_b = b mod c)
(∴ (a imes b) mod c = [(a mod c) imes (b mod c)] mod c)
1.4
由 1.3 得：
((a^b) mod c = (a imes a^{b - 1}) mod c = [(a mod c) imes (a ^ {b - 1} mod c)] mod c)
((a^b) mod c = [(a mod c) imes (a mod c) imes (a ^ {b - 2} mod c)] mod c)
(...)
((a^b) mod c = [(a mod c) imes (a mod c) ... imes (a mod c)] mod c)
2.1 记 (a = b imes q_a + c)
$∴ (a imes d) mod (b imes d) = (cd + bdq_a) mod bd $
(∵ a mod b = c)
(∴ c < b)
又 (∵ d > 0)
(∴ cd < bd)
(∴) 由 0.1 得：((a imes d) mod (b imes d) = (cd + bdq_a) mod bd = cd)
2.1 记 (a = b imes q_a + c)
$∴ frac a d mod frac b d = (frac c d + frac {bq_a} d) mod frac b d $
(∵ a mod b = c)
(∴ c < b)
又 (∵ d > 0)
(∴ frac c d < frac b d)
(∴) 由 0.1 得：(frac a d mod frac b d = (frac c d + frac {bq_a} d) mod frac b d = frac c d)
0x03 同余
概念： 设 (m) 为给定正整数，若满足 (m mid (a - b), a, b in mathbb Z)，则称 (a) 与 (b) 对 (m) 同余。记作 (a equiv b pmod m)
性质：
0. 一些基本性质：
0.1 反身性：(a equiv a pmod m)
0.2 对称性：(a equiv b pmod m)，则 (b equiv a pmod m)
0.3 传递性：(a equiv b pmod m)，则 (b equiv c pmod m)，则 (a equiv c pmod m)
1. 同加性：若 (a equiv b pmod m)，则 (a + c equiv b + c pmod m)
2. 同减性：若 (a equiv b pmod m)，则 (a - c equiv b - c pmod m)
3. 同乘性：若 (a equiv b pmod m)，则 (a imes c equiv b imes c pmod m)
4. 同除性：若 (a equiv b pmod m, c mid a, c mid b, (c, m) = 1)，则 (frac a c equiv frac b c pmod m)
5. 同幂性：若 (a equiv b pmod m)，则 (a^c equiv b^c pmod m)
6. 若 (a mod p = x, a mod q = x, (p, q) = 1)，则 (a mod (p imes q) = x)
1. 由题：(m mid (a - b))
(∴ m mid [(a + c) - (b + c)])
(∴ a + c equiv b + c pmod m)
2. 由题：(m mid (a - b))
(∴ m mid [(a - c) - (b - c)])
(∴ a - c equiv b - c pmod m)
3. 由题：(m mid (a - b))
(∴ m mid [ac - bc])
(∴ a imes c equiv b imes c pmod m)
4. 记 (a = k_ac, b = k_bc)
(∴ p mid (k_a - k_b)c)
(∵ (c, p) = 1)
(∴ p mid (k_a - k_b))
(∴ pc mid (k_ac - k_bc))
即 (pc mid (a - b))
(∴ p mid frac {a - b} c)
即 (p mid (frac a c - frac b c))
(∴frac a c equiv frac b c pmod m)
5. 由题：(m mid (a - b))
(∴ a^c - b^c = (a - b)(a^{c - 1} + a^{c - 2}b + ... + ab^{c - 2} + b^{c - 1}))
(∵a, b in mathbb Z)
(∴ (a^{c - 1} + a^{c - 2}b + ... + ab^{c - 2} + b^{c - 1}) in mathbb Z)
(∴ (a - b) mid (a^c - b^c))
(∴ m mid (a^c - b^c))
即 (a^c equiv b^c pmod m)
6. (∵ a mod p = x, a mod q = x)
(∴p mid (a - x), q mid (a - x))
(∴ a - x = pk_p, a - x = qk_q(k_p, k_q in mathbb Z))
即 (pk_p = qk_q)
(∵(p, q) = 1)
(∴ k_p = kq(k in mathbb Z))
(∴ a - x = pqk)
故 (pq mid a - x)
即 (a mod (p imes q) = x)