混凝土数学第四章之数论学习笔记

我总觉得混凝土数学内容的层次性不足, 因此从这篇学习笔记开始, 我会把分段分得更细致一些.

整除性

这是整除的定义:

[m | n Rightarrow m > 0且对于某个整数k有n = mk ]

接下来我们还定义了最大公因子:

[gcd(m, n) = max{ k | k | m且k | n } ]

以及最小公倍数

[lcm(m, n) = min{ k | k > 0且m | k且n | k} ]

欧几里得算法

考虑如何计算(gcd(n, m)): 我们一般用欧几里德辗转相除法. 这种算法我们都很熟悉, 因此对于做法我们不再赘述.

考虑如何证明欧几里德算法的正确性: 我们不妨假设(n ge m).

(1) (m = 0), 则(gcd(n, m) = gcd(n, 0) = n).

(2) (m > 0), 不妨设(gcd(n, m) = d), 则(n = n'd), (m = m'd), 且(gcd(n', m') = 1). 我们考虑辗转相除的本质实际上是辗转相减, 因此我们实际上要证明的是(gcd(n, m) = gcd(m, n - m)). 我们有

[egin{aligned} gcd(m, n - m) &= gcd(m'd, n'd - m'd) \ &= gcd(m'd, (n' - m')d) end{aligned} ]

显然, 现在问题变成了证明(gcd(m', n' - m') = 1).

反证法, 我们假设存在(d' > 1)满足(d' | m')且(d' | n' - m'), 则(d' | n' - m' + m'), 即(d' | n'), 因此与条件矛盾.

扩展欧几里得算法

我们注意到(n mod m)的本质: (n \bmod m = n - mlfloor frac nm floor)
考虑对欧几里得算法加以推广, 用于计算满足

[mm' + nn' = gcd(m, n) ]

的整数(m'), (n'). 做法如下: 假如(m = 0), 则取(m' = 0), (n' = 1), 否则我们令(r = n \bmod m = n - mlfloor frac nm floor), 递归计算

[rr'' + mm'' = gcd(r, m)\ ]

中满足条件的(r''), (m'')
又因为有

[(n - mlfloor frac nm floor)r'' + mm'' = gcd(r, m) = gcd(m, n) \ nr'' + m(m'' - m lfloor frac nm floor) = gcd(m, n) ]

因而

[egin{cases} n' = r'' \ m' = m'' - m lfloor nm floor end{cases} ]

依据这种方法, 我们总是能找到合法的一组解.

另外的一个小定理

[k | m且k | n Leftrightarrow k | gcd(m, n) ]

至于证明:

[ecause k | m且k | n \ herefore k | mm' + nn' \ ]

又根据上面的扩展欧几里德定理, 我们有

[mm' + nn' = gcd(m, n) \ k | gcd(m, n) ]

整除意义下的和式处理技巧

[sum_{m | n} a_m = sum_{m | n} a_{n / m}, n > 0 ]

这种变换的正确性在于同样都是取遍了(n)的每个约数.
同时还有另一种表达方式:

[sum_{m | n} a_m = sum_k sum_{m > 0} a_m [n = mk] ]

我们再看二重和式中的情况:

[sum_{m | n} sum_{k | m} a_{k, m} = sum_{k | n} sum_{l | (n / k)} a_{k, kl} ]

考虑如何证明:
等式的左边是:

[sum_{j, l, k, m} a_{k, m} [n = jm][m = kl] = sum_{j, l, k} a_{k, kl} [jkl = n] ]

等式的右边:

[sum_{i, j, k, l} a_{k, kl} [n = ik] [lj = n / k] = sum_{i, j, k, l} a_{k, kl} [jkl = n] ]

左边等于右边, 证毕.

素数

按照惯例, (1)既不是素数, 又不是合数. 假如一个正整数不等于(1)且恰好只有(1)和(p)两个因子, 那么就把这个数称为素数, 否则为合数.

算数基本定理

任何正整数(n)都可以表示成素数的乘积:

[n = p_1 ... p_m = prod_{k = 1}^m p_k, p1 le ... le p_m ]

并且对于每个合数, 以上这种站开方式是唯一的, 仅有一种方式将(n)按照素数非减的次序写成素数的乘积. 这个定理称为算术基本定理.
考虑如何证明这一定理:
我们令

[n = p_1 ... p_m = q_1 ... q_k, p_1 le ... le p_m且q_1 le ... le q_k ]

运用数学归纳法, 对于(n = 1)的情况, 命题显然就是成立的; 考虑(n ge 2)的情况, 我们只需要证明(p_1 = q_1), 然后再递归证明(p_2 = q_2)即可.
使用反证法. 假设我们能找到这样的一组(p_1 e q_1), 由于(p_1)和(q_1)都是质数, 因此根据扩展欧几里得算法, 我们可以找到一组

[ap_1 + bq_1 = 1 ]

这样就有了

[ap_1q_2 ... q_k + bq_1q_2 ... q_k = q_2 ... q_k \ ]

注意到(p_1 | n = q_1 ... q_k), 等式左边被(p_1)整除, 因此等式右边也被(p_1)整除. 我们又有(q_2 ... q_k < n), 根据数学归纳法, (X = q_2 ... q_k)只有唯一分解, 因此(p_1)只能是(q_1)的因数, 这与(p_1 < q_1)且(q_1)为质数矛盾. 因此假设不成立, 命题得证.
我们更倾向于把算术基本定理表述为另一种形式:

[n = prod_p p^{n_p}, n_p ge 0 ]

右边是无穷多个素数的乘积.
另外的就是数系的定义: 我们把序列(langle n_2, n_3, n_5, ... angle)看作是正整数的数系, 比如说(12)的素指数表示是(langle2, 1, 0, 0, ... angle), 而(18)的素指数表示就是(langle 2, 1, 0, 0, ... angle). 两个数相乘, 直接把其素指数表示相加即可.

同余关系

[a equiv b Leftrightarrow m | a - b pmod m ]

对于同余, 我们有以下性质:

[a equiv b 且 c equiv d Rightarrow a + c equiv b + d pmod m \ a equiv b 且 c equiv d Rightarrow a - c equiv b - d pmod m \ a equiv b 且 c equiv d Rightarrow ac equiv bd pmod m \ a equiv b Rightarrow a^n equiv b^n pmod m , n ge 0 \ ad equiv bd Leftrightarrow a equiv b pmod m, d perp m \ ad equiv bd pmod {md} Leftrightarrow a equiv b pmod m ]

中国剩余定理:

[a equiv b pmod{mn} Leftrightarrow a equiv b pmod m 且 a equiv b pmod n, m perp n ]

独立剩余

我们将一个整数(x)表示为一组互素的模的剩余序列:

[Res(x) = (x mod m_1, cdots, x mod m_r), forall j e k有m_j perp m_k ]

则我们另(m = prod_{k = 1}^r m_r), 我们可以确定(x mod m).

比如说, 我们观察(0)到(14)每个数分别模(3)和(5)得到的余数形成的有序对(x = (x mod 3, x mod 5))

(x)	(x mod 3)	(x mod 5)
0	0	0
1	1	1
2	2	2
3	0	3
4	1	4
5	2	0
6	0	1
7	1	2
8	2	3
9	0	4
10	1	0
11	2	1
12	0	2
13	1	3
14	2	4

我们发现每一个有序对都是不同的, 因为根据中国剩余定理, (x mod 3 = y mod 3)且(x mod 5 = y mod 5)的充分必要条件为(x mod 15 = y mod 15).

因此我们可以在两个分量上独立执行加法, 减法和乘法: 考虑用(13 = (1, 3))来乘上(7 = (1, 2)), 这相当于独立计算(1 imes 1 mod 3 = 1)以及(2 imes 3 mod 5 = 1), 因此答案是((1, 1) = 1).

因而(7 imes 13 mod 15 = 1).