集合、映射
集合
* 集合元素要有明确定义
交（Interaction）$A\cap B$
并（Union）$A\cup B$
$A\setminus B=\{x\in X | x \in A,x \notin B\}$ (A-B)
$\overline{A}(A^c)={x\in X |x\in A}$
$A\triangle B=(A\cup B)\setminus(A\cap B)$
$(A\cup B)^c=A^c \cap B^c$
映射（mapping）
定义
$\forall a\in A,按照一定的规则f，\exists!\;b\in B,s.t. b=f(a)$
- b为a在f下的像(image)
- a为原像(preimage)
单射(injective)
$f(a_1)=f(a_2)\;\Rightarrow\; a_1=a_2$
满射（surjective）
$\forall b \in B,\exists a\in A \; s.t.b=f(a)$
双射（bijective）
一一映射，既单又满
映射的复合（乘积）
*高代研究线性映射
$\forall a\in A,h(a)=g(f(a))$
$h=g·f=gf$
可逆映射
$给定f:A\to B$
$如果存在一个映射g:B\to A\; s.t.$
$gf=Id_A(A的单位映射)$
$fg=Id_B$
* $Id:A\to A,Id(a)=a,\forall a \in A$
映射乘法具有结合律，不具有交换律。
通常，$f·g\neq g·f$
* 笛卡尔乘积
$A\times B \triangleq \{(a,b)|a\in A,b\in B\}$
整数
$Z=\{0,\pm1,\pm 2,\cdots\}$
定义
$b整除a\Leftrightarrow\exists c\in Z \; s.t.\; a=bc$
a可被b整除
b是a的因子(division)
* 0可整除0
带余除法
$a,b\in Z,b\neq 0$
$a=bq+r$ q ,存在且唯一
$\exists !\;q,r\in Z \;且0 \le r< |b|$
唯一性
$设a=bq_1+r_1=bq_2+r_2$
$|b||q_1-q_2|=|r_1-r_2|$
$易知|r_1-r_2|<b$
$若q_1\neq q_2则|b||q_1-q_2|>|b|,矛盾$
$\therefore q_1=q_2,r_1=r_2$
* $b\neq 0,b \mid a \Leftrightarrow r=0$
公因子
$d是a,b公因子\Leftrightarrow d\mid a且 d \mid b$
最大公因子
- d是公因子
- $d_1 \mid a,d_2 \mid b\Rightarrow d_1\mid d$
* $d\mid d’,d’\mid d\Rightarrow d=\pm d’$
$d=(a,b)=\gcd(a,b)$
* greateat common division
贝朱定理
$a,b \in Z ,且不全为零，令$
$S=\{|ax+by|,x,y\in Z\}$
$令d为S中非零中最小的(d>0)$
$则d为a,b的最大公因子且d=ax+by,x,y\in Z$
证明(反证法)
$d\mid a,d\mid b$
$不妨设d\not \mid a$
$则有 \; a=dq+r,0<r<d$
$r=a-dq,d=ax_2+by_2$
$r=a-(ax_2+by_2)=(1-qx_2)a+(-qy_2)b$
$r=|au+by|\in S$
$又因为r<d与假设矛盾，所以d是a，b的因子$
$\begin{cases}d=ax_2+by_2\\d’|a,d’|b\end{cases}\Rightarrow d’\mid d$
$\therefore d是a,b的最大公因子$
求最大公因子
欧几里得算法（辗转相除法）
命题：
$a,b\in X,b\neq 0,a=bq+r$
$则a,b的最大公因子就等于b,r的最大公因子$
证明：
$d|a,d|b,d_1|b,d_1|r$
$r=a-bq\Rightarrow d|r$
$\begin{cases}d|r\\d|b\end{cases}\Rightarrow d|d_1$
$d_1|b,d_1|r\Rightarrow d_1|a$
$\begin{cases}d_1|a\\d_1|b\end{cases}\Rightarrow d_1|d$
$\therefore d_1=\pm d,即d_1=d$
$(a,b)=(b,r_1)=(r_1,r_2)=\cdots=(r_{s-1},r_s)=(r_s,0)=r_s$