因为自己的Surface Pen丢了,决定拿Futarino写离散数学课的笔记)
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.
感觉也只有每个章节的第一节课能写这么密了 之后的课程基本上都很难分下心来打字(听都跟不上)
羡慕讲课速度和学数论…
诶?(哈?
2023 04 25 class2
Problem 1
Prove
([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},
故得证
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
Defination 1
Legendre Symbol:
Preposition
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^*
昨天图论课上到了 König-Egeváry theorem ,但是没看懂证明
有无天才futa友能帮我证明一下
König-Egeváry theorem For a bipartite graph G, \kappa'(G) = \Delta(G)
(也就是说,对于一个二部图,其边染色所需最小颜色数等于其最大点度数)
显然边染色所需最小颜色数大于等于其最大点度数。不妨设 |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)
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
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.
建立映射
锦心太强了
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
If a \notin Z_n
有
Proof:
Temporily assume n is a prime, and m=p_1^{e_1}\cdots p_k^{e_k}
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
可以作为最大流最小割定理的推论得出。
后者算法导论上有写。