离散数学 Chap.3 整数, 数论

离散数学此后的内容会跟数论沾点边, 所以这部分我们把数论的内容捡一下.

3.1 除法 / 整除

3.1.1 整除及其性质

首先是一个整除的标识:

概念: 整除
两个整数 $ a, b $ , 如果存在一个整数 $ c $ 使得 $ b = ac $ 成立, 则我们称之为 $ a $ 整除 $ b $ . 记为 $ a \mid b $ . 反之则 $ a \nmid b $ .

还有四个比较常用的性质:

$ \forall a, b, c \in Z $

$ a \mid 0 \space (a \neq 0) $
$ (a \mid b \land a \mid c) \to a \mid (b+c) $
$ a \mid b \to a \mid bc $
$ (a \mid b \land b \mid c) \to a \mid c $

3.1.2 余数 / 取余

概念: 余数
对任意被除整数 $ a $ 以及除数 $ d $ , 存在唯一的两个整数 $ p, r $ , 使 $ a = dp + r $ 成立, 其中 $ 0 \leq r \leq |d| $ . r被称为余数.

我们为这种运算单独写个运算子叫 取余运算子 . 按上面的定义来说:

$$ a \space mod \space d = r $$

余数是有限的, 而整数是无限的, 因此理论上所有整数可以根据余数来分类对不对, 我们引出同余的概念.

概念: 同余(Modular Congruence)
对于除数 $ d $ , 整数 $ a, b $ 有相同的余数, 称 $ a, b $ 相对于 $ d $ 同余. 记作 $ a \equiv b \space (mod \space d) $
这同样代表着 $ d \mid (a-b) $

取余运算同样有些有用的性质:

$ \exists a, b, c, d \in Z, m \in Z^+, a \equiv b \space (mod \space m) , c \equiv d \space (mod \space m) $

$ a + c \equiv b + d \space (mod \space m) $
$ a + b \equiv ((a \space mod \space m) + (b \space mod \space m)) \space (mod \space m) $
$ ac \equiv bd \space (mod \space m) $
$ ab \equiv ((a \space mod \space m)(b \space mod \space m)) \space (mod \space m) $

~~(叽里咕噜说啥呢, 听不懂)~~ , 读者莫急, 这上面一大片, 其实本质意思就是 取余这个运算, 对加法, 减法, 乘法而言, 都是具有分配律的 .

3.1.3 质数 / 最大公因数

质数是从整除这个概念衍生出来的一种蛮特殊的数字:

概念: 质数(Prime)
对于整数 $ p, p \geq 2 \land p \in Z $ , 如果有且仅有 $ 1, p $ 两个数字能够整除 $ p $ , 则我们称 $ p $ 是质数.

随后是两个任意整数的最大公因数和最小公倍数:

概念: 最大公因数(GCD)
$ gcd(a, b) = max \lbrace m: m \mid a \land m \mid b \rbrace $

概念: 最小公倍数(LCM)
$ lcm(a, b) = min \lbrace m: a \mid m \land b \mid m \rbrace $

当两个数的最大公因数等于1时, 称两个数 互质(coprime) .

3.2 进制转换

这个部分其实写过很多次了, 读者容博主犯个懒, 这里可以自行搜索关于 不同进制互相转换 的内容.

3.3 欧几里得算法 / 逆元

3.3.1 算法概述

注意
这一部分会写的非常简略, 因为在本博客中信安数学基础_期末复习章这一节写的很清楚, 就把基础部分粘过来, 还请读者移步该章节.

基本思路:

$$ (a, b) = (qb+r, b) = (r, b) $$

将大的数字换成小的数字的带余除法形式, 而后依据最大公因子性质2, 直接将乘积去掉.
这个方法也叫做 辗转相除法 .
直到没有余数为止, 此时的数字被就是二者的最大公因子.

这里可以稍微给个证明, 其实很简单:

$$
\begin{align*}
Known: & (c \mid a) \land (c \mid b) \land (a = qb + r) \\
Proof: & c \mid r \\
Solution: & (a = qb + r) \to (r = a - qb) \\
& (c \mid a) \land (c \mid b) \to c \mid (a - qb) \to (c \mid r) \\
Proof & \space End
\end{align*}
$$

反过来是一样的:

$$
\begin{align*}
Known: & (c \mid r) \land (c \mid b) \land (a = qb + r) \\
Proof: & c \mid a \\
Solution: & (c \mid r) \land (c \mid b) \to c \mid (qb + r) \to (c \mid a) \\
Proof & \space End
\end{align*}
$$

3.3.2 Re: 同余

我们在之前讲余数这个玩意的时候, 说了这东西面对加 / 减 / 乘都能分开算, 那除法呢?
事实上, 除法也能算, 但是有一定特殊条件.

同余除法消去律(Cancellation Rules) 如下:

$$
\begin{align*}
known : & m \in Z^+, a, b, c \in Z \\
if : & ac \equiv bc \space (mod \space m) \land gcd(m, c) = 1 \\
then: & a \equiv b \space (mod \space m)
\end{align*}
$$

这个玩意的证明也好办, 在这里也写一下:

$$
\begin{align*}
\because & \space ac \equiv bc \space (mod \space m) \\
\therefore & \space m \mid (ac - bc) \\
\therefore & \space m \mid (a - b)c \\
\because & \space gcd(m, c) = 1 \\
\therefore & \space m \mid (a-b)
\end{align*}
$$

3.3.3 逆元

给出逆元的概念: 对于整数 $ a $ , 存在 $ b $ 使得 $ ab \equiv 1 \space (mod \space m) $ , 此时称 $ a, b $ 互为逆元.
还请各位读者明确, 逆元存在的前提是 $ gcd(a, m) = 1 $ .

读者可能稍微有点疑惑, 为什么? 别急, 我们把逆元的求法写出来就清晰了.
由 $ gcd(a, m) = 1 $ , 可以通过扩展欧几里得算法得到 $ sa + tm = 1 $ .
等式两边同时对m取余: $ sa \equiv 1 \space (mod \space m) $
得到这个 $ s = b $

看完这个求法, 我们所说前提的必要性就呼之欲出了:
没有 $ gcd(a, m) = 1 $ , 这个式子 $ sa + tm = 1 $ 就不成立, 那何谈逆元?