因为自己的Surface Pen丢了，决定拿Futarino写离散数学课的笔记）
2 Likes
2023 04 23 Number Theory class 1
Defination 1
-
完全剩余系 Complete residue system: Z_n = \{0, 1, 2, ... ,n\}
-
简约剩余系 Reduced residue system Z_n^* = \{a | \gcd(a, n) = 1 , a \in Z_n\}
Theorem 1
(Willem) For any prime p, (p-1)! \equiv -1 \pmod p
Proof: 从群论中很容易得知，我们在 Z_p^* 中能找到且只能找到一个非单位元的二阶元 k,(k^2 = 1) . (p-1)! 即将 Z_p^* 的所有元素相乘，除了某一个 k 和 1 以外，剩余的所有元素 a 都有唯一的 a^{-1} \neq a \in Z^*_p 有 aa^{-1} = 1 抵消。故 (p-1)! \equiv k \pmod p
Suppose k^2 \equiv 1 \pmod p, then p | k^2-1 \Rightarrow p | (k-1)(k+1). 显然 p \not | \ k-1, 故 p | k+1 \Rightarrow p = k+1 \Rightarrow k = p-1 得证。
Defination 2
Eular function \phi(n) = |Z_n^*|
Prepostion 2
\forall a, b, gcd(a,b)=1, \phi(ab) = \phi(a)\phi(b) （欧拉函数的积性）
Theorem 2.1
(Eular) \forall a \in Z_n^*, a^{\phi(n)} \equiv 1 \pmod n
(Femat) \forall a \in Z_p^*, a^{p-1} \equiv 1 \pmod p where p prime.
Example 2.1
Let a, b be positive integers s.t. \forall n \in Z^*, a^n+n \ |\ b^n+n.
Prove a = b.
思路： 考虑设 a=1 ，则退化到证明 n+1 | b^n + n 则 b=1
如果 n+1 = p (p prime) 则得到了 Femat little theorem 的形式： b^{p-1} \equiv 1 \pmod p
因此 p \not | \ b 对任意 prime p 成立。故 b =1
一般情况，设 a < b. P:a^n+n \ |\ b^n+n \Rightarrow a^n+n \ | \ b^n-a^n
If we can find p, n where p | a^n+n and p \not | \ b^n+n then P is false.
Let n = k(p-1) + 1 for some k, 代入 a^n \equiv -n \pmod p 得 a^n \equiv k-1 \pmod p
We want to make sure that for some n, b^n \not \equiv - n. 代入上面的式子, 得到 b^{ k(p-1) + 1} \equiv a^{ k(p-1) + 1} \pmod p. 由 Femat’s theorem, \exists p \not | \ b, p \not | \ a, b^{p-1} \equiv 1 \pmod p. So b \equiv a \pmod p. 故 b-a =0
Theorem 2.2
(Gauss) \forall n \in Z^*, \sum\limits_{d|n} \phi(d) = n
Proof: 上式显然等价于 \sum\limits_{d|n} \phi(\dfrac n d) = n
\forall d | n, \{a | gcd(n, a) = d \} = \phi(\dfrac nd) . 得证.
Theorem 2.3
\forall prime p, Z_p^* is a cyclic group.
Proof: \forall a \in Z_p^*, a^{p-1} \equiv p \pmod p \Rightarrow order(a) | p-1
\forall d| p-1 lets count the number of order-d elements.
If \exists a, order(a) = d, then all elements of <a> are solutions of x^d \equiv 1 \pmod p which has \leq d solutions.
Therefore, <a> have all solutions.
Consider a^k
Case A: \gcd(k,d) = 1: \forall d' where d'\neq d , d' | d, we have d \not |\ kd' \Rightarrow (a^k)^{d'} \not \equiv 1 \pmod p \Rightarrow order(a^k) \neq d'. So order(a^k) = d.
Case B: gcd(k,d) \neq 1, then exists d'\neq d, d|kd' \Rightarrow order(a^k) = d' \neq d
So |\{a | order(a) = d\}| = \phi(d)
由 Gauss Theorem, \sum\limits_{d|p-1} \phi(d) = p-1 = |Z_p^*| 得 \{a | order(a) = p-1\} = \phi(p-1) \neq0
Therefore, Z_p^* is a cyclic.
2 Likes
感觉也只有每个章节的第一节课能写这么密了 之后的课程基本上都很难分下心来打字（听都跟不上）
2 Likes
羡慕讲课速度和学数论…
1 Like
诶？（哈？
2023 04 25 class2
Problem 1
Prove
\forall n \in \mathbb Z_+, \prod\limits_{k=1}^n lcm(1,2,..., [\dfrac n k ]) =n!
([x] 为向下取整)
Proof:
Consider d = p_1^{e_1}p_2^{e_2}...p_m^{e_m},
Case 1, m \geq 2, p_i^{e_i}|lcm(1,2,...,d-1 )\Rightarrow lcm(1,...d)=lcm(1,...,d-1)
Case 2, m = 1, p_1^{e_1} \not | \ lcm(1,...,d-1), p_1^{e_1-1} | lcm(1,...,d) \Rightarrow lcm(1,...d)= p_1lcm(1,...,d-1)
Consider n = q_1^{t_1}q_2^{t_2}...q_m^{t_m},
\prod_{d|n} lcm(1,...,d) = q_1^{t_1}q_2^{t_2}...q_l^{t_l} \prod_{d|n} lcm(1,...,d-1)
\begin{align*}
\prod_{k=1}^{n+1} lcm(1,...,[\frac {n+1} k]) &= \prod_{1 \leq k \leq n+1}^{k | n+1} lcm(1,...,[\frac {n+1} k]) \prod_{1 \leq k \leq n+1}^{k \nmid n+1} lcm(1,...,[\frac {n} k])
\\ &= \prod_{1 \leq d \leq n+1}^{d | n+1} lcm(1,...,d) \prod_{1 \leq k \leq n+1}^{k \nmid n+1} lcm(1,...,[\frac {n} k])
\\ &=(n+1) \prod_{1 \leq d \leq n}^{d | n} lcm(1,...,d) \prod_{1 \leq k \leq n+1}^{k \nmid n+1} lcm(1,...,[\frac {n} k])
\\ &=(n+1) \prod_{k=1}^{n} lcm(1,...,[\frac {n} k])
\end{align*}
故得证
Defination 1
Quadratic residue（二次剩余系）： \{d|X^2\equiv d \mod p, X \in Z_p^*\}, QR_P
QNR_p: \{d|X^2 \not \equiv d \mod p ,X \in Z_p^* \}
Preposition 1
QR_p \unlhd Z_p^*
For prime p
QR \cdot QR = QR \\
QNR \cdot QR = QNR \\
QNR \cdot QNR = QR \\
Defination 1
Legendre Symbol:
(\dfrac a p) = \left\{ \begin{aligned}
1 \ \ \ \ \ \ \ \ & \text{ if } a \in QR_p \\
-1 \ \ \ \ \ \ \ \ & \text{ if } a \in QNR_p \\
0 \ \ \ \ \ \ \ \ & \text{ if } p|a \\
\end{aligned} \right.
(\dfrac a p) \equiv a^\frac{p-1}2 \pmod p
Preposition
|\{k|k \in QNR_p , k+1 \in QR_p\}| = |\{k|k \in QNR_p , k+1 \in QNR_p\}|
Proof:
|\{k|k \in QNR_p , k+1 \in QNR_p\}| = \dfrac {p-1} 2 - |\{k|k \in QR_p , k+1 \in QNR_p\}| =
Defination 2
Blum prime is a 4k+3 prime.
Proposition
There’re infinately many Blum prime.
Proof: if finate, let p_1, ..., p_n are all blum primes.
q = \prod_p + 4 if n odd, \prod_p + 2 if even.
Therefore, every prime factor \equiv 1 \pmod 4
Preposition
-1 \in QNR_p if p is a blum prime
Lemma
\forall a,b \in \mathbb Z_+, for odd c | a^2+b^2, c \nmid gcd(a,b), c \equiv 1 \pmod 4
a^2+b^2 \equiv 0 \pmod c \Rightarrow (ab^{-1})^2 = -1 \pmod c So c is not a blum prime.
Theorem
(Gauss) For odd prime p ,\forall m \in Z_p^*
(\dfrac m p) = (-1)^{|\{a | a \leq \frac {p-1} 2, ma > \frac {p-1}2, a\in Z_p^* \}|}
昨天图论课上到了 König-Egeváry theorem ，但是没看懂证明
有无天才futa友能帮我证明一下 
König-Egeváry theorem For a bipartite graph G, \kappa'(G) = \Delta(G)
（也就是说，对于一个二部图，其边染色所需最小颜色数等于其最大点度数）
1 Like
显然边染色所需最小颜色数大于等于其最大点度数。不妨设 |X| = |Y| = n 。不妨设 \forall v \in X, \Delta (v) = k 且 \forall v \in Y, \Delta (v) = k 。考虑对 k 归纳。只需证 k \geq 1 时必有 n 条不相邻的边。根据 Hall 定理，这是显然的。
文学少女，您
但是实际上“显然”和“不显然”并不那么显然吧
我也有自己的informal proof，长短和这个差不多，但是其实估计没分
需要说明的显然只有最后一句。若选取 X 中 s 个点，那伸出去 sk 条边一定要至少 sk/k 个点才能接住，所以 Hall 条件成立。
没分是老师的问题，不是我的问题。
对边数进行数学归纳法?
我们教材上好像有证明x）
1 Like
5/12 Class 4
exapmle 1
Prove there are infinity primes p \equiv -1\pmod 8
Pf. we define S= \{2a^2-1 | a \in \mathbb Z_+\} \cup \{ a^2-2 | a\in \mathbb Z_+\}
T = \{p | p is a prime factor of s \in S\}
assum not true, then there is a largest p \in T s.t. p \equiv -1 \pmod 8 let it be p^*
p \in T
u = 2 \prod_{p \le p^*} p^2 -1, v = \prod_{p \le p^*} p^2-2
All their prime factors \in T
\forall p \le p^*, gcd(u,p)=gcd(u,v)=1 \Rightarrow p \nmid u, p \nmid v \Rightarrow prime factors of u,v > p^*
… \prod p^2 \equiv -1 \pmod 8
example 2
\forall p prime, \forall a \in Z_p^*, \exists b \in [1, p-1] s.t. x^2+y^2+a=bp has a integer solution. （ x^2 + y^2 = -a \pmod p )
二次互反律
p, q prime, then
\left( \dfrac p q \right) \left( \dfrac q p \right) \equiv -1^\frac {(p-1)(q-1)} 4
Lemma Zolotorov:
Forall odd prime p, forall a \in Z_p^*, \left(\dfrac a p \right)= -1 if f:f(x)=xa on Z_p^* is odd
(f 为排列，这里是排列的奇偶性)
pf: a = g^d, \left(\dfrac a p \right)= -1 if d is odd.
Z_p^* 同构 (Z_p, +)
这个lemma的证明有些简单，请读者自己完成
Preprosition 49
\forall p odd prime, \forall a \in Z_p^*, \forall b \in Z_p, \left(\dfrac a p \right)= -1 if f:f(x)=xa+b on Z_p is odd.
这就是上个lemma的简单拓展，所以也请读者自己完成。
Preprosition 50
\forall p, q odd prime, p\neq q,\left(\dfrac q p \right)= -1 if f:f(x)=xq+(x \bmod q) on Z_{pq} is odd.
Preprosition 51
\forall p, q odd prime, p\neq q, f:f(x)=xq+(x \bmod q), g:g(x)=xp+(x \bmod p) on Z_{pq}, then g^{-1} \cdot f maps a+bp to aq+b.
(a+bp \mathop{\leftarrow}\limits^{g} ??? \mathop\rightarrow\limits^{f} aq+b)
Pf: \forall p,q odd primes > 1, F:aq+b \rightarrow a+bp on Z_{pq}
Then F has the same parity as \dfrac {(p-1)(q-1)} 4.
\begin{array}{ccc}
\ &0 & 1 & 2 & ... & p-1 \\
0 &0 &1 &2 &... &p-1 \\
1 &p &p+1 &p+2 &... &2p-1 \\
...
\end{array}
建立映射
2 Likes
锦心太强了
Jacobi symbol:
\forall n = p_1^{k_1}p_2^{k_2}\cdots p_l^{k_l} where p_i are distinct primes and k_i \in \mathbb Z_+
\forall a \in Z_n
\left(\dfrac a n\right) = \left(\dfrac {a} {p_1}\right)^{k_1}\left(\dfrac a {p_2}\right)^{k_2}\cdots\left(\dfrac a {p_l}\right)^{k_l}
If a \notin Z_n
\left(\dfrac a n\right) = \left(\dfrac {a \bmod n} n\right)
有
\left(\dfrac {ab} n\right) = \left(\dfrac {a } n\right)\left(\dfrac {b } n\right)
\left(\dfrac {a} {nm}\right) = \left(\dfrac {a } n\right)\left(\dfrac {a } m\right)
\left(\dfrac {n} {m}\right)\left(\dfrac {m} {n}\right) = (-1)^{\frac{(n-1)(m-1)} 4}
Proof:
Temporily assume n is a prime, and m=p_1^{e_1}\cdots p_k^{e_k}
\begin{align*}
\left(\dfrac {n} {m}\right)\left(\dfrac {m} {n}\right) &= \prod_{i=1}^k \left(\dfrac {p_i} {n}\right)^{e_i} \left(\dfrac{n} {p_i} \right)^{e_i} = \prod_{i=1}^k \left[ \left(\dfrac {p_i} {n}\right) \left(\dfrac{n} {p_i} \right) \right]^{e_i} \\
&= \prod_{i=1}^k (-1)^{\frac{(p_i-1)(n-1)e_i} 4} \\
&= (-1)^{\frac{(n-1) \sum_{i=1}^k e_i (p_i-1)} 4} \\
\end{align*}
This is -1 if n is a Blum prime and there is an odd number of (odd e_i, Blum prime p_i)
It happens that (-1)^{\frac{(m-1)(n-1)} 4} = -1 under the same condition…
接下来学到了格
Support v_1,v_2,...,v_n are linear independent vectors in \mathbb R^m, 0 < n \le m
L = \{c_1v_1+c_2v_2+...+c_nv_n | c_1, ..., c_n \in \mathbb Z_+\} is a Lattice
可以作为最大流最小割定理的推论得出。
后者算法导论上有写。
1 Like