Linca の 离散数学笔记

因为自己的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^* 的所有元素相乘,除了某一个 k1 以外,剩余的所有元素 a 都有唯一的 a^{-1} \neq a \in Z^*_paa^{-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 + nb=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 pa^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友能帮我证明一下 :face_holding_back_tears:

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

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