离散数学 Discrete Mathematics
part 3 Number Theory 数论
basic knowledge 基础知识
Let $Z$ be the set of integers. Let $a,b\in Z$ and $a\neq 0$
- a devides b (整除): there is an integer $c\in Z$ such that $b=ac$
- a is a divisor(因子)of b;b is mutiple of a
- $a \mid b$: a divides b ;$a\nmid b$: a does not divide b
- $n \in {2,3,\ldots}$is a prime if the only positive divisors of n are 1 and n.
- if n is not a prime , n is a composite(合数)(不讨论0,1)
- 素数无穷多构造。N=最大素数以下所有数字素数只和加一,和所有已知素数互质,矛盾。
- a devides b (整除): there is an integer $c\in Z$ such that $b=ac$
The Well-Ordering Property良序公理:
every non-empty subset of $N(Z^+)$ has a least element .$//\forall S\in p(N) \backslash {\emptyset},\exists s_0\in S$ such that $s_0\leqslant s$ for all $s \in S$.
Division Algorithm带余除法:
let $a,b\in Z$and b>0.Then there are unique integers q,r such that $0\leqslant r<b$ and $a=bq+r$.
prove:
existence:
let $S=\{a-bx:x\in Z \ and\ a-bx\geqslant0\}.$Then$S\neq \emptyset \ and\ S \subseteq N$,$S$ has a least element , say $r=a-bq\geqslant0$
if $r\geqslant b$,then $r-b=a-b(q+1)\in S$ and $r-b<r$.The contradiction shows that $0\leqslant r<b.$
uniqueness:Suppose that $q’,r’\in Z,0\leqslant r’<b$ and $a=bq’+r’$
Recall that $a=bq+r,0\leqslant r<b$.Then $b(q-q’)=r’-r\in (-b,b)$. It must be the case that $q=q’$ and thus $r=r’$.
mod: a mod b is defined as r(let $a,b\in Z$and b>0.Then there are unique integers q,r such that $0\leqslant r<b$ and $a=bq+r$.)
$\lfloor \alpha \rfloor$:floor of $\alpha$,$\leqslant \alpha$
$\lceil \alpha \rceil$:ceil of $\alpha$,$\geqslant \alpha$
Greatest Common Divisor(GCD):
common divisor 公因子: a integer d such that $d|a,d|b$
greatest common divisor 最大公因子(GCD),gcd(a,b) : the largest common divisor of a,b
relatively prime 互素:gcd(a,b)=1
$\exists s,t\in Z,st\ gcd(a,b)=as+bt.$
$d=gcd(a,b)=gcd(a/d,b/d)=1$
计算gcd,辗转相除法,
properties :
or 可兼有的或 \lor
theorem(Congruence): Let $n\in Z^+$. For any $a\in Z$, there is a unique integer $r$, such that $0\leqslant r< n$ and $a\equiv r \pmod n$.
prove:
Existence: by division algorithm,$\exists q,r\in Z$ such that $0\leqslant r<n,a=qn+r$
$a\equiv r\pmod n$
Uniqueness:Suppose that $0\leqslant r’ <n$ and $a\equiv r’\pmod n$
$|r-r’|<n$ and $r\equiv r’\pmod n$
$|r-r’|<n$ and $n|(r-r’)$
$r=r’$
加减乘除法时间复杂度
Prime Number Theorem : for $x\in R^+,\pi(x)=\sum_{p\leqslant x }1$:the number of primes $\leqslant x$
theorem: every intr=eger n>1 can be uniquely written as $n=p_1^{e_1}\cdots p_r^{e_r}$,where $p_1,\dots,p_r$ are distinct primes ,$p_1<\cdots <p_r$ and $e_1,\ldots,e_r \geqslant 1$.
prove: 第二类数学归纳法 mathematical induction
existence:
显然n=2,3,4,5满足
假设n$\leqslant$k满足, Induction hypothesis: suppose true for integers $2\leqslant n \leqslant k$
Prove the statement for n=k+1
if(n=k+1 is a prime) $n=(k+1)^1$ QED
else n=k+1 is composite ,$n=n_1n_2$,by introduction hypothesis,
$n1=p_1^{\alpha_1 }\cdots p_r^{\alpha_r},n2=q_1^{\beta_1 }\cdots q_s^{\beta_s}$
$n=n_1n_2=p_1^{\alpha_1 }\cdots p_r^{\alpha_r}\cdot q_1^{\beta_1 }\cdots q_s^{\beta_s}$has the expected form.
uniqueness:
- Suppose that $n=p_1\cdots p_r=q_1\cdots q_s$,where $p_i,q_i$ are all primes.
- $p_1|n \Rightarrow p_1|q_1\cdots q_s \Rightarrow p_1|q_j$ for some $j\Rightarrow p_1=q_j$
- Without loss of generality, we suppose that j=1
- Then $p_2\cdots p_r=q_2\cdots q_s$
- The theorem is true by induction
Ideal 理想
Definion:Let $\emptyset \neq I \subseteq Z$.I is called an ideal of Z if
- $a,b\in I\Rightarrow a+b\in I$;and
- $a\in I,r\in Z \Rightarrow ra\in I$
example:$kZ={\ldots , -2k,-k,0,k,2k,\ldots}$is an ideal of Z for every $k\in Z$
- theorem:Let I be an ideal of Z. Then $\exists d \in Z$ such that $I=dZ$
- prove:
- prove:
- theorem:Let I be an ideal of Z. Then $\exists d \in Z$ such that $I=dZ$
Definion:Let $I_1,I_2$ be ideals of Z. Then the sum of $I_1$ and $I_2$ is define as $I_1+I_2={x+y:x\in I_1 ,y\in I_2}$
theorem:$I_1+I_2$ is an ideal of Z
- $$\forall a,b\in I_1+I_2,a+b\in I_1+I_2$$
- $\exists x_1,x_2\in I_1,y_1,y_2\in I_2$ such that $a=x_1+y_1;b=x_2+y_2$
- $$a+b=(x_1+x_2)+(y_1+y_2)\in I_1+I_2$$
- $$\forall a \in I_1+I_2 ,r\in Z ,ra\in I_1+I_2 $$
- $\exists x\in I_1,y\in I_2$ such that $a=x+y$
- $ra=(rx)+(ry)\in I_1+I_2$
- $$\forall a,b\in I_1+I_2,a+b\in I_1+I_2$$
example:$3Z+5Z=Z;4Z+6Z=2Z$
$aZ+bZ=gcd(a,b)Z$
prove:
PS: w.l.o.g.:without loss of generality (不失一般性)
二元关系指,R是A$\times$B 的子集,具体我感觉怪怪的,不是很明白。
Congruence
definition: Let $a\in Z ,n\in Z^+$
$[a]_n=a+nZ={a+nx:x\in Z}$ is called the residue class 剩余类of $a$ mod $n$
any element in this class is called a representative代表元.
example: n=6,$[0]_6={\ldots,-12,-6,0,6,12,\ldots};[1]_6={\ldots,-11,-5,1,7,13,\ldots}$
$Z_n,Z_n^*$
$Z_n$:
Define: Letn be any positive integer. $Z_n$ is defined as the set of all residue classes modulo n.
$Z_n={[0]_n,[1]_n,\ldots,[n-1]_n}={[1]_n,[2]_n,\ldots,[n-1]_n,[n]_n}=\cdots$
- addition: $[a]_n+[b]_n=[a+b]_n$
- subtraction:$[a]_n-[b]_n=[a-b]_n$
- multiplication:$[a]_n\cdot [b]_n=[a\cdot b]_n$
Remark(well-defined):if $a\equiv a’\pmod n$ and $b\equiv b’\pmod n$,then$a\pm b\equiv a’\pm b’\pmod n$ and $ab=a’b’\pmod n$.
Hence,$[a]_n\pm [b]_n=[a’]_n+[b’]_n;[a]_n\cdot [b]_n=[a’]_n\cdot [b’]_n$
- $$
a\equiv a’\pmod n\Rightarrow n|(a-a’) \Rightarrow \exists x \ such\ that\ a-a’=nx\
b\equiv b’\pmod n\Rightarrow n|(b-b’) \Rightarrow \exists x \ such\ that\ b-b’=ny\
(a+b)-(a’+b’)=nx+ny\
(a-b)-(a’-b’)=nx-ny\
ab-a’b’=a(b-b’)+b’(a-a’)=any+b’nx
$$
- $$
$Z_n^*$:
- inverse:Let $n\in Z^+$ and let $[a]_n \in Z_n$.$[s]_n\in Z_n$ is called an inverse of $[a]_n$ if $[a]_n[s]_n=[1]_n$.
- division:if $[a]_n$ has an inverse $[s]_n$,define $\frac{[b]_n}{[a]_n}=[b]_n\cdot [s]_n$
- theorem: Let $n\in Z^+$.$[a]_n\in Z_n$ has an inverse if and only if $gcd(a,n)=1$
- Only if: $\exists s\ s.t.[a]_n[s]_n\equiv [1];\exists t,as-1=nt;gcd(a,n)=1$
- if:$\exists s,t\ s.t.as+nt=1;as\equiv 1\pmod n$
- Let $n\in Z^+$.Define $Z_n^*={[a]_n\in Z_n:gcd(a,n)=1}$
$\phi(n)=|Z_n^*|$ for every $n\in Z^+$ ($\phi (n)$ is the number of intergers $a\in [n]$ such that $gcd(a,n)=1$)
property:
- if p is a prime, then $\phi(p^e)=p^{e-1}(p-1)$ for any $e\in Z^+$
- prove:let $x\in [p^e]$. Then $gcd(x,p^e)\neq 1$ iff$p|x$ iff$x=p,2p,\ldots,p^{e-1}\cdot p$
- $\phi(p^e)=p^e-p^{e-1}=p^{e-1}(p-1)$
- if n=pq for two different primes p and q ,then $\phi(n)=(p-1)(q-1)$.
- prove容斥: $A={1,2,\ldots,pq},A_p={x\in A:p|x},A_q={x\in A:q|x}$
- $Z_n^*=A-A_p\cup A_q$
- $|Z_n^*|=|A-A_p\cup A_q|=|A|-|A_p\cup A_q|=|A|-|A_p|-|A_q|+|A_p\cap A_q|=(p-1)(q-1)$
- if p is a prime, then $\phi(p^e)=p^{e-1}(p-1)$ for any $e\in Z^+$
Euler’s Theorem:Let $n\geqslant1$ and $\alpha \in Z_n^*$. Then$\alpha^{\phi(n)}\equiv 1 \pmod n$
Fermat’s Little Theorem:if p is a prime and $\alpha \in Z_p$. Then $\alpha^p \equiv \alpha \pmod p$.
• This is a corollary of Euler’s theorem for $n=p$
Cryptography_rsa
- 凭空产生两个质数$p,q$
- 设$N=p \times q$
- 根据欧拉函数$r=\phi(N)=(p-1)(q-1)$
- 凭空产生一个小于r的整数$e$使得$e$和$r$互质
- 求$d$使得$ed\equiv1\pmod r$
- 销毁$p,q$,没有人知道$p,q$是多少
得出$(N,e)$是公钥,$(N,d)$是私钥
参考链接
Alice得到公钥和私钥,Alice把公钥告诉Bob,自己把私钥藏起来不告诉任何人。Bob给Alice发消息。
加密:
假设Bob的消息是$n$,密码是$c$,手上有公钥$(N,e)$
$$
c\equiv n^e \pmod N
$$
Bob将加密后的$c$发给Alice解密:
Alice得到密码$c$,根据私钥$(N,d)$
$$
n \equiv c^d \pmod N
$$
解码得到$n$原理:
$$
c\equiv n^e \pmod N \
c^d \equiv n^{e\cdot d} \pmod N
$$
因为$e\cdot d \equiv 1 \pmod r$,即$e\cdot d \equiv h \cdot r +1 \pmod N$,其中$h$是自然数
$$
c^d\equiv n^{h\cdot r+1}\pmod N\
c^d\equiv n^{h\cdot \phi(n)+1}\pmod N\
c^d\equiv n\cdot n^{h\cdot \phi(n)}\pmod N\
c^d\equiv n\cdot (n^{\phi(n)})^h\pmod N\
$$
根据欧拉定理$a^{\phi(n)}\equiv 1 \pmod n$
$$
c^d \equiv n\times 1^h \pmod N\
c^d \equiv n \pmod N
$$
快速幂,取模Modulo Exponentiation(Square-and-Multiply Algorithm)
Euclidean Algorithm (EA)辗转相除算gcd
Extended Euclidean Algorithm (EEA) 算as+bt的s和t
1 | #gcd |
图论 Graph
basis knowledge
graph图 $G=(V,E)$ is defined by a non empty set V of vertices and aset of E of edges.
vertices顶点 $|V|$ is called the order(阶数) of G.
edges边
endpoint端点
Infinite Graph 无限图 $|V|=\infty$ or$|E|=\infty$
Finite Graph 有限图 $|V|< \infty$ or $|E| < \infty$
Types of Graphs
- are edges of G directed ?
- directed graph 有向图
- undirected graph 无向图
- multiple edges
- simple graph 简单图
- multigraph 多重图
- loops自环
- pseudograph伪图
- are edges of G directed ?
Special Simple Graph:
complete graph完全图:
$K_n:V={v_1,\ldots,v_n};E=\Large{$${v_i,v_j}$ $:i\neq j\leq n$ $\Large}$
cycle环,圈:
- $C_n:V={v_1,\ldots,v_n};E=\Large{$${v_1,v_2},{v_2,v_3},\ldots,{v_n,v_1}$$\Large}$
wheel轮:
- $W_n:V={v_0,v_1,v_2,\ldots,v_n};E=$$\Large{$${v_1,v_2},\ldots,{v_n,v_1}$$\Large}$$\bigcup$$\Large{$${v_0,v_1},\ldots,{v_0,v_n}$$\Large}$
n-Cubes方体:
- $Q_n:V={0,1}^n;E={$${u,v}:d(u,v)=1}$即u,v二进制只有一位不一样
- $d(u,v)=|{i\in [n] :u_i \neq v_i}|$即u,v二进制有几位不一样
Adjacency List邻接表:
Let $G = (V, E)$ be a graph with no multiple edges. The adjacency list of $G$ is a list the vertices of the graph and all adjacent vertices
$v_i,v_j \in V$ are adjacent if ${v_i,v_j}$ or $(v_i,v_j)$ is an edgeadjacency matrix邻接矩阵 :
let $G=(V={v_1,\dots,v_n},E)$ be a simple graph. The adjacency matrix of $G$ is an $n\times n$ matrix $A=(a_{ij})$, where
$$
a_{ij}=\left{ \begin{array}\ 1 & {v_i,v_j}\in E \ 0 & {v_i,v_j}\notin E\end{array}\right.
$$multiplicity重数:
let $G=(V={v_1,\dots,v_n},E)$ be an undirected graph. The adjacency matrix of $G$ is an $n\times n$ matrix $A=(a_{ij})$, where:- $a_{ij}=$ multiplicity of ${v_i,v_j}$ when $i \neq j$
- $a_{ii}=$ the number of loops from $v_i$ to itself.
remark: the adjacentcy matrix of a simple graph is always symmetric.
incidence matrix关联矩阵:
let $G=(V={v_1,\dots,v_n},E={e_1,\ldots,e_m})$ be undirected.THe incidence matrix of $G$ is an $n\times m$ matrix $B=(b_{ij})$,where
$$
b_{ij}=\left{ \begin{array}\ 1 & if\ e_j\ is\ incident\ with\ v_i\ 0 & otherwise\end{array}\right.
$$subgraph:
edge or vertex operation
remove/add an edge or vertex
edge:
vertex:
edge contyractions
union
complement graph补图:
$G\cup \overline{G}$ is a complete graph($K_n$).
degree and connection
degree:
two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v.
Neighbor:
the set of adjacent vertices.
degree:
the number of neighbors.
- isolated: $degree = 0$
- pendant: $degree = 1$
- 对上面的图片,⑤ is pendant;⑥ is isolated
Handshaking Theorem:
- Let $G=(V,E)$ be an undirected graph with m edges. Then
$$
2m=\sum_{v \in V}deg(v)
$$
(Note: all undirected graph including simple graph,multigraph(multiple edges),pseudograph(loops)) - An undirected graph has an even number of vertices of odd degree.
sketch of pf:Let $V_1$ and $V_2$ be the set of vertices of even degree and theset of vertices of odd degree,respectively,in an undirected graph $G=(V,E)$ with m edges.Then
$$2m=\sum_{v \in V}deg(v)=\sum_{v \in V_1}deg(v)+\sum_{v \in V_2}deg(v)$$
- Let $G=(V,E)$ be an undirected graph with m edges. Then
degree for directed graph:
Let $G=(V,E)$ be a directed graph. If $(u,v)\in E$, we say that $u$ is adjacent to $v$ and $v$ is adjacent from $u$.- $u$ is the initial vertex of $(u,v)$; $v$ is the terminal vertex of $(u,v)$.
- in-degree
- out-degree
Handshaking Theorem for directed graph:
- Let $G=(V,E)$ be a directed graph. Then
$$
\sum_{v \in V}deg^-(v)=\sum_{v \in V}deg^+(v)=|E|
$$
- Let $G=(V,E)$ be a directed graph. Then
Isomorphism
- Definition:The simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic同构 if there is a bijection $\sigma :V_1\rightarrow V_2$ such that ${u,v}\in E_1 \Leftrightarrow {\sigma(u),\sigma(v)}\in E_2$
• $\sigma$ is called an isomorphism同构映射
• nonisomorphic: not isomorphic

- Determine whether two graphs are isomorphic:
Definition: Graph invariants are properties preserved by graph isomorphism. For example,
• The number of vertices
• The number of edges
• The number of vertices of each number of degrees
REAMRKS: The graph invariants can be used to determine if two graphs are isomorphic or not.
Bipartite Graph and Match
Bipartite Graph二分图、二部图
- V can be devided to two disjoint part,such that there are not any edges in each part and all edges are connect two parts.
- Definition: $G=(V,E)$ is a bipartitie graph if $V$ has a partition ${V_1,V_2}$ such that $E\subseteq {$${u_1,u_2}:u_1\in V_1,u_2\in V_2}$.
- $(V_1,V_2)$ is a bipartition of the vertex set $V$.
Complete Bipartite Graph完全二部图:
- A complete bipartite graph is a graph $K_{m,n}=(V,E)$ with $V={x_1,\ldots,x_m}\cup {y_1,\ldots,y_n}$ and $E={$${x_i,y_j}:i\in [m],j\in [n]}$
Matching
Definition:
A matching in a simple graph $G=(V,E)$ is a subset $M\subset E$ such that no two edges in M are incident with the same vertex.
A maximum matching is a matching with the largestnumber of edges.
A matching in a bipartite graph with $V=V_1\cup V_2$ is a complete matching from $V_1$ to $V_2$ if every vertex in $V_1$ is the endpoint of an edge in the matching.Hall’s Marriage Theorem:
A bipartitie graph $G=(X\cup Y,E)$ has a complete matching from $X$ to $Y$ iff $|N(A)|\geqslant |A|$ for any $A\subseteq X$
详细证明略去,这次不考
Path,connected, disconnected
Path
Definition:
for directed path:
Connectivity
- Definition:
An undirected graph $G$ is said to be connected if there is a path between any pair of distinct vertices.
• Graph of order 1 is connected; the complete graph $K_n$ is connected
• disconnected非连通的: not connected
• disconnect G: remove vertices or edges to produce a disconnected subgraph - Theorem:Let $G=(V,E)$ be a connected undirected graph. Then there is a simple path between any pair of distinct vertices.
证明同上略。 - Connected Component:
- • $v\in V$ is a cut vertex割点if $G-v$ has more connected components than G
• $e\in E$ is a cut edge割边、bridge桥if $G-e$ has more connected components than G
- Definition:
Find cut vertices and cut edge(s)
Vertex Connectivity
- Definition:A connected undirected graph $G=(V,E)$ is said to be nonseparable不可分的if $G$ has no cut vertex.(one point)
- Let $G=(V,E)$ be a connected simple graph.
• vertex cut点割集: A subset $V’\subseteq V$ such that $G-V’$ is disconnected
• vertex connectivity点连通度$\kappa(G)$ : the minimum number of vertices whose
removal disconnect $G$ or results in $K_1$; equivalently,
• if $G$ is disconnected, $\kappa(G)=0$; //additional definition
• if $G=K_n$,$\kappa(G)=n-1$ //$K_n$ has no vertex cut
• else,$\kappa(G)$ is the minimum size of a vertex cut of $G$
Theorem:
Property:
Edge connectivity
- Definition:Let $G=(V,E)$ be a connected simple graph. $E’\subseteq E$ is an edge cut边割集of $G$ if $G-E’$ is disconnected.
- Let $G=(V,E)$ be a connected simple graph.
The edge connectivity边连通度($\lambda(G)$) of $G$ is defined as below:
• $G$ disconnected: $\lambda(G)$ = 0
• $G$ connected:
• $|V|=1$: $\lambda(G)$ = 0
• $|V|>1$: $\lambda(G)$ is the minimum size of edge cuts of $G$.
Theorem:
Let $G=(V,E)$ be a simple graph. Then $\kappa(G)\leqslant\lambda(G)\leqslant\delta(G)$,where $\delta(G)=min_{v\in V} deg(v)$ is the least degree of $G’s$ vertices.
prove(homework)
Connected Directed Graphs
路径同构不变性
Euler circuit, Euler path, Hamilton Circuits, Hamilton path
Counting Paths Between Vertices
证明详细分析见后,期末1/5
Euler circuit and Euler path
Necessary and sufficient condition for Euler circuit
证明后面详细分析,期末2/5欧拉循环算法
欧拉路径
Hamilton Paths and Circuits
Definition: Let $G=(V,E)$ be a graph.
• Hamilton Path: A simple path that passes through every vertex
exactly once.
• Hamilton Circuit: A simple circuit that passes through every
vertex exactly once.Determine if there is a Hamilton circuit in a given graph 0?
• This problem is NP-Complete. //that means very difficultNecessary conditions on Hamilton circuit.
• If 0 has a Hamilton circuit, then G doesn’t have a vertex of degree 1
• If 0 has a Hamilton circuit and a vertex of degree 2, then a Hamilton circuit of 0 traverses both edges.Sufficient conditions for existence
Planar Graph
$K_{3,3},K_5$ 都不是planar
Regions:
- DEFINITION: Let $G=(V,E)$ be a planar graph. Then the plane is divided into several regions面by the edges of $G$.
大括号无序点对,无向边;小括号有序点对,有向边。
已整理ppt:lec1,2,3,4(未举例);lec7,8,9,10,11,12
lec5,lec6(简要)
lec13,14,15,16,17
lec18,19,20,21,22,23,24,25,26