時(shí)隔一年。。。。。終于轉(zhuǎn)去數(shù)學(xué)系了
然而還是要學(xué)證明（雖然在工程系中已經(jīng)學(xué)了一遍了）
第一部分：首先定義集合：集合包含一系列元素。
它有3種性質(zhì)：互異性，受定義性，無(wú)序性。
比如\(\{1,2,\{1,2,3\}\}\)就是集合。\(\{1,2,3\}\)是元素
通常使用大寫(xiě)字母表示集合，小寫(xiě)字母表示元素。
定義一個(gè)元素包含于某集合：\(x\in A\)
不包含于某個(gè)集合：\(x\not\in A\)
然后定義命題：命題是某個(gè)可能為真/假的語(yǔ)句（不能都取），比如“今天天氣很暖”
用\(\neg A\)表示某命題的取反，讓它的真假性翻轉(zhuǎn)
比如\(\neg(1+2=3)\) 是\(1+2\neq 3\)
接著是命題中的全部和存在符號(hào)。
記作\(\exists x\in A, P(x)\)
和\(\forall x\in A,P(x)\)
分別表示對(duì)于\(A\)里面的所有數(shù)，\(P(x)\)都存在/滿足一個(gè)\(x\)使得\(P(x)\)為真
共有4個(gè)部分：符號(hào)(quantifier)表明這個(gè)表達(dá)式的類(lèi)型
變量（variable）（\(x\)）
范圍（domain）\(A\)規(guī)定\(x\)的范圍
開(kāi)句（open sentence）（\(P(x)\)）如果單獨(dú)一個(gè)\(P(x)\)，需要知道\(x\)的值才能決定\(P(x)\)
比如\(1+a=3\)就是一個(gè)開(kāi)句，變量是\(a\)
開(kāi)句的變量可能有多個(gè)，比如\(x,y\)記作\(P(x,y)\)
全部和存在符號(hào)可以取反：\(\neg(\exists x\in A, P(x))=\forall x\in A,\neg P(x)\)
\(\neg(\forall x\in A,P(x))=\exists x\in A,\neg P(x)\)
有時(shí)，我們會(huì)遇到嵌套的符號(hào)。
比如\(\forall x\in A,\exist y\in B,x>y\)
單純嵌套的符號(hào)交換順序可能會(huì)影響結(jié)果。
比如\(\forall x\in A,\exist y\in B,x>y\neq \exist y\in B,\forall x\in A,x>y\)
但是如果兩個(gè)符號(hào)是相同的，則不會(huì)影響結(jié)果。
比如\(\forall x\in A,\forall y\in B,x>y= \forall y\in B,\forall x\in A,x>y\)
如果有括號(hào)，符號(hào)的作用范圍是從該符號(hào)開(kāi)始到其左邊的第一個(gè)左括號(hào)所匹配的右括號(hào)。（如果沒(méi)有則為語(yǔ)句末）
比如\(\forall x\in A,(\exist y\in B, P(x,y))\Rightarrow(\exist z \in C, Q(z))\)中，\(\exist y\in B\)的作用范圍是\(P(x,y)\)
分析嵌套的符號(hào)的取反，可以按照符號(hào)從外層到里層分析。
比如\(\neg(\forall x\in A,\exist y\in B,\forall z \in C,P(x,y,z))\)
\(=\exist x\in A,\neg(\exist y\in B,\forall z \in C,P(x,y,z))\)
\(=\exist x\in A,\forall y\in B,\neg(\forall z \in C,P(x,y,z))\)
\(=\exist x\in A,\forall y\in B,\exists z \in C,\neg P(x,y,z)\)

第二部分 命題的運(yùn)算
命題是可以進(jìn)行二元運(yùn)算的。
命題可以進(jìn)行與運(yùn)算（conjuction），或運(yùn)算（disjunction）
與運(yùn)算當(dāng)且僅當(dāng)兩個(gè)命題的結(jié)果都是真時(shí)為真。記為\(A\wedge B\)
或運(yùn)算當(dāng)一個(gè)命題的結(jié)果是真時(shí)就都為真，記為\(A\vee B\)
取反運(yùn)算會(huì)翻轉(zhuǎn)原命題的真假性，記為\(\neg A\)
蘊(yùn)含運(yùn)算\(A\Rightarrow B\)表示如果\(A\)為真，那么\(B\)為真這個(gè)命題是否成立。
還有當(dāng)且僅當(dāng)運(yùn)算：\(A\Leftrightarrow B\)表示\((A\Rightarrow B)\wedge(B\Rightarrow A)\)
而且在命題中，通常用\(\equiv\)來(lái)表示命題相等
同時(shí)我們還定義\(A\Rightarrow B\)的逆命題\(B\Rightarrow A\)
運(yùn)算有如下性質(zhì)：
1.交換律：\((A\wedge B)\equiv(B\wedge A),(A\vee B)\equiv (B\vee A)\)
2.結(jié)合律：\(((A\wedge B)\wedge C))\equiv ((A\wedge (B\wedge C)),((A\vee B)\vee C)\equiv ((A\vee (B\vee C))\)
3.分配律：\(((A\wedge B)\vee C)\equiv((A\vee C)\wedge (B\vee C)),((A\vee B)\wedge C)\equiv((A\wedge C)\vee (B\wedge C))\)
4.\(\neg(\neg A)\equiv A\)
5.\(((A\Rightarrow C)\wedge(B\Rightarrow C))\equiv((A\vee B)\Rightarrow C)\)
6.\(\neg(A\wedge B)=((\neg A)\vee(\neg B)),\neg(A\vee B)\equiv((\neg A)\wedge(\neg B))\)
7.命題的逆否命題與原命題相等，即\((A\Rightarrow B)\equiv((\neg B)\Rightarrow(\neg A))\)
8.\((A \Rightarrow B)\equiv ((\neg A)\wedge B)\)
9.\((\forall x\in S, P(x)\Leftrightarrow Q(x))\equiv((\forall x\in S, P(x)\Rightarrow Q(x)))\wedge((\forall x\in S, Q(x)\Rightarrow P(x))))\)
10.命題運(yùn)算符的優(yōu)先級(jí)為：否定，與，或，蘊(yùn)含，等價(jià)
11.\(A \wedge(\neg A)=false\)
為了證明等式，除了使用以前提到的幾種性質(zhì)外，還可以用真值表，枚舉所有可能的情況以證明。

第三部分 證明
1.為了證明\(\forall x\in S, P(x)\)，我們首先提取出\(x\)（注意此處我們除了知道\(x\)屬于\(S\)以外不知道\(x\)的任何信息）
然后使用\(x\in S\)這個(gè)條件推導(dǎo)出\(P(x)\)
注意我們一開(kāi)始不能假設(shè)\(P(x)\)為真，這點(diǎn)非常重要
例子是我們想要證明\(x^2-1\geq 2x\)
我們首先知道\((x-1)^2\geq 0\)
展開(kāi)得到\(x^2-2x+1\geq 0\)
把\(2x\)移到右邊得到\(x^2-1\geq 2x\)，得證
2.我們也可以分類(lèi)討論，把\(S\)拆成集合\(S_1,S_2...S_n\)
要求\(S_1\cup S_2\cup...\cup S_n=S\)
證明\((\forall x\in S_1, P(x))\wedge...\wedge(\forall x\in S_n, P(x))\)
例子如果我們要證明\((k-1)k\geq 0\)對(duì)于所有整數(shù)成立，可以把整數(shù)集拆成\(1,0,x\leq 0,x\geq 0\)求解
3.為了證否\(\forall x\in S, P(x)\)，只需找到\(x1\)，使得\(\neg P(x1)\)為真即可，
4.為了證明\(\exists x\in S, P(x)\)，只需找到\(x1\)，使得\(P(x1)\)為真即可
5.為了證否\(\exists x\in S, P(x)\)，我們知道\(\neg(\exists x\in A, P(x))=\forall x\in A,\neg P(x)\)
所以我們需要證明\(\forall x\in A,\neg P(x)\)
6.為了證明\(A\Rightarrow B\)，我們可以把\(A\)作為已知條件，證明\(B\)成立
例子是如果我們要證明當(dāng)\(s^2+t^2=1,(sx+ty)^2\leq s^2+t^2\)
考慮向量\(\vec{a}=(s,t),\vec{b}=(x,y)\)，設(shè)它們的夾角為\(x\)
因?yàn)橐阎獥l件\(s^2+t^2=1\)，\(|a|=1\)
\(|\vec{a}|^2 |\vec{b}|^2 \cos (x)^2=(\vec{a} \cdot \vec{b})^2=|\vec{b}|^2\cos(x)^2=(sx+ty)^2\leq |\vec{b}|^2=s^2+t^2\)得證
7.利用\((A\Rightarrow B)\equiv((\neg B)\Rightarrow(\neg A))\)
例子是我們要證明如果\(x^3-3x^2+x\geq 0\)那么\(x\geq 0\)
這個(gè)命題的逆否命題是如果\(x<0,x^3-3x^2+x<0\)，與原命題等價(jià)
顯然當(dāng)\(x<0,x^3<0,-3x^2<0,x<0\)，所以\(x^3-3x^2+x<0\)，所以如果\(x<0,x^3-3x^2+x<0\)
8.反證法：利用\(A \wedge(\neg A)=false\)
或者說(shuō)假設(shè)\(A\)為真，推出矛盾。
例子：經(jīng)典的\(\sqrt{2}\)
假設(shè)它是有理數(shù)，設(shè)\(\sqrt{2}=\frac{p}{q},(p,q)=1\)
\(2q^2=p^2\)
假設(shè)\(q\)含\(2\)的次冪是\(x\)，\(p\)是\(y\)
那么有\(2x+1=2y\)且\(x,y\)都是整數(shù)
所以有\(x+\frac{1}{2}=y\)，但是與\(x,y\)都是整數(shù)矛盾，得證
9.如果要證明\(\exists x\in S, P(x)\)，且有且只有1個(gè)，必須先證明\(\exists x\in S, P(x)\)
接下來(lái)通常有2種方法：
第一種是假設(shè)\(P(x),P(y)(x,y\in S)\)為真，證明\(x=y\)
第二種是假設(shè)\(P(x),P(y)(x,y\in S)\)為真且\(x\neq y\)，導(dǎo)出矛盾
比如我們要證明對(duì)于所有奇數(shù)\(x\)，存在且只存在一個(gè)整數(shù)\(k\)使得\(x=2k+1\)
第一種證法：根據(jù)定義顯然存在整數(shù)\(k\)使得\(x=2k+1\)
假設(shè)存在\(a,b,x=2a+1=2b+1\)
那么\(2a+1=2b+1\)所以\(a=b\)
第二種證法：根據(jù)定義顯然存在整數(shù)\(k\)使得\(x=2k+1\)
假設(shè)存在\(a,b,x=2a+1=2b+1,a\neq b\)
那么\(2a+1=2b+1\)所以\(a=b\)，與\(a\neq b\)矛盾
10.證明\(A\Leftrightarrow B\)，就是證明\((A\Rightarrow B)\wedge(B\Rightarrow A)\)

第四部分：數(shù)學(xué)歸納法
首先定義數(shù)列的求和，求積：\(x_m+...+x_n(m\leq n)=\sum_{i=m}^n x_i,x_mx_{m+1}...x_n=\prod_{i=m}^nx_i\)
求和的性質(zhì)有：
1.\(c\sum_{i=m}^n x_i=\sum_{i=m}^n cx_i\)
2.\(\sum_{i=m}^n x_i+\sum_{i=m}^n y_i=\sum_{i=m}^n (x_i+y_i)\)
3.\(\sum_{i=m}^n x_i=\sum_{i=m+l}^{n+l} x_{i-l}\)
\(\sum_{i=m}^n x_i=\sum_{i=m}^{l} x_{i}=\sum_{i=l+1}^{n} x_{i}\)
定義數(shù)列的遞推關(guān)系（recurrence relation）：給定某數(shù)列的初始值，數(shù)列的后面的項(xiàng)與前面的項(xiàng)有關(guān)，比如斐波那契數(shù)列。
定義公理：假設(shè)為真（且不用證明）的假設(shè)。
定義數(shù)學(xué)歸納法（Mathematical induction）：首先我們知道\(P(1)\)為真
然后我們證明對(duì)于所有自然數(shù)\(n\)，\(P(n)\Rightarrow P(n+1)\)
我們就知道了對(duì)于所有自然數(shù)\(n\)，\(P(n)\)成立。
記作induction on n
\(P(1)\)不一定為真，但是如果我們知道\(P(a)\)為真，且對(duì)于對(duì)于所有自然數(shù)\(n\geq a\)，\(P(n)\Rightarrow P(n+1)\)
通常記作induction with base case b
我們就能知道對(duì)于所有自然數(shù)\(n\geq a\)，\(P(n)\)成立。
定義強(qiáng)歸納法（strong induction）：首先我們知道\(P(1)\)為真
然后我們證明了對(duì)于所有自然數(shù)\(n\)，\((P(1)\vee P(2)\vee....\vee P(n))\Rightarrow P(n+1)\)
我們就知道了對(duì)于所有自然數(shù)\(n\)，\(P(n)\)成立。
記作strong induction on n
例子：對(duì)于斐波那契數(shù)列證明\(f_n\leq (\frac{7}{4})^n\)
顯然對(duì)于\(f_1,f_2\)命題成立
假設(shè)我們知道對(duì)于\(f_1...f_n\)命題成立，證明\(f_{n+1}\leq (\frac{7}{4})^{n+1}\)
\(f_{n+1}=f_n+f_{n-1}< (\frac{7}{4})^n+(\frac{7}{4})^{n-1}=\frac{11}{4}(\frac{7}{4})^{n-1}<(\frac{7}{4})^2\frac{7}{4}^{n-1}=(\frac{7}{4})^{n+1}\)，得證
\(P(1)\)不一定為真，但是假設(shè)我們知道\(P(a),P(a+1)...P(b),b\geq a\)為真，且對(duì)于對(duì)于所有自然數(shù)\(n\geq b\)，\((P(b)\vee P(b+1)\vee....\vee P(n))\Rightarrow P(n+1)\Rightarrow P(n+1)\)
我們就能知道對(duì)于所有自然數(shù)\(n\geq a\)，\(P(n)\)成立。
通常記作strong induction with base case b
例子：證明對(duì)于所有\(n\geq 6,\)一定存在\(x,y\)（\(x,y\)都是正整數(shù)）使\(3x+4y=n\)
通過(guò)枚舉可得\(n=6,7,8\)都成立
假設(shè)\(n>8,P(6)...P(n)\)成立，我們要證明\(3x+4y=n\)有解
根據(jù)歸納假設(shè)，\(n>8,n-2>6\)，所以存在\(3x_0+4y_0=n+1-3=n-2,x_0>0,y_0>0\)
\(3(x_0+1)+4y_0=n+1\)是\(3x+4y=n+1\)的一組解
\(x_0>0\)所以\(x_0+1>0\)，得證
事實(shí)上本題基于如下結(jié)論：考慮方程組\(ax+by=k\)（\(\gcd(a,b)=1\)）
這個(gè)方程組存在非負(fù)解的充要條件是\(k>ab-a-b\)
對(duì)于這個(gè)結(jié)論的證明超出了本文的范圍

第五部分：集合
構(gòu)建集合除了使用列舉法，還可以使用描述法
通常有3種方法：\(\{x\in S:P(x)\},\{f(x):x\in S\},\{f(x):x\in S,P(x)\}\)
如果在集合里使用\(|\)，容易和整除符號(hào)混淆，所以通常使用冒號(hào)
第一種方法是對(duì)于所有屬于\(S\)且\(P(x)\)為真的\(x\)構(gòu)造集合。
第二種方法是對(duì)于所有屬于\(S\)的\(f(x)\)構(gòu)造集合。
第三種方法是對(duì)于所有屬于\(S\)且\(P(x)\)為真的\(f(x)\)構(gòu)造集合。
有理數(shù)的定義：考慮\(\{\frac{a}{b}:a\in \mathbb{Z},b\in \mathbb{Z},b\neq 0\}\)
這說(shuō)明多個(gè)\(x\in S\)是可以同時(shí)出現(xiàn)在集合定義中的。
定義集合的運(yùn)算并，交，差，補(bǔ)集如下：
1.\(S\cup T=\{x:(x\in S)\wedge(x\in T)\}\)
2.\(S\cap T=\{x:(x\in S)\vee(x\in T)\}\)
3.\(S-T=\{x:(x\in S)\wedge(x\notin T)\}\)
4.\(\overline S\)補(bǔ)集是相對(duì)于全集\(U\)而言的：
有兩種寫(xiě)法\(\overline S={x:x\notin S}\)或者\(\overline S={x\in U:x\notin S}\)
它也等于\(U-S\)
定義集合不相交：\(S\cup T=\varnothing\)
定義集合\(S\)包含于\(T\)為命題\(\forall x\in U,(x\in S)\Rightarrow(x\in T)\)，記作\(S\subseteq T\)
定義集合\(S,T\)相等：\(S\subseteq T\)并且\(T\subseteq S\)，或者說(shuō)\(\forall x\in U,(x\in S)\Rightarrow(x\in T)\)
證明集合相等除了證明\(\forall x\in U,(x\in S)\Rightarrow(x\in T)\)外，還可以證明兩個(gè)集合可以使用相同的方式表達(dá)。
比如我們要證明\(S=T,S=\{x\in S:P(x)\},T=\{x\in S:Q(x)\}\)，我們可以證明\(P(x)=Q(x)\)
定義集合\(S\)的大小為\(|S|\)（或者\(card(S)\)）

第六部分：整除和取余
先定義整除（divisibility）\(a|b\)：（\(a,b\)都是整數(shù)但不一定為正數(shù)）\(\exists k\in \mathbb{Z},ka=b\)
一個(gè)整數(shù)顯然整除自己，并且\(0\)能被任何數(shù)整除。
整除和取余有如下性質(zhì)：1.傳遞性，\(a,b,c\in \mathbb{Z},((a|b) \wedge(b|c))\Rightarrow (a|c)\)
證明：根據(jù)條件我們知道存在\(k,l\in \mathbb{z}\)使得\(b=ka,c=lb\)那么\(c=kla\)
顯然\(kl\)是整數(shù)，則\(a|c\)成立
2.如果\(a,b,c\in \mathbb{Z},(a|b\vee a|c)\)，則\(a|bc\)
根據(jù)第二部分，\(((A\Rightarrow C)\wedge(B\Rightarrow C))\equiv((A\vee B)\Rightarrow C)\)
我們需要證明\((a|b)\Rightarrow(a|bc)\)以及\((a|c)\Rightarrow(a|bc)\)
先證明\((a|b)\Rightarrow(a|bc)\)，設(shè)\(b=ka,bc=kac=a(kc)\)
\(kc\)顯然是整數(shù)，所以得證
\((a|c)\Rightarrow(a|bc)\)同理。
3.\(a,b,c,d,e\in \mathbb{Z},((a|b)\vee (a|c))\Rightarrow((a|db+ec))\)（Divisibility of integer combination）
由于\(a|b,a|c\)，存在\(k,l\in \mathbb{z}\)使得\(b=ka,c=la\)，
\(db+ec=dka+ela=(dk+el)a\)
\((dk+el)\)顯然是整數(shù)，所以得證。
這個(gè)定理的逆定理也是成立的。
考慮\(a|db+ec,a|(d+1)b+ec\)，根據(jù)題意，存在\(l1,l2\in \mathbb{Z}\)使得\(l_1a=db+ec,l_2a=(d+1)b+ec\)
\((l_2-l_1)a=b\)，由于\(l_1,l_2\)都是整數(shù)得證。
4.\(((b|a)\wedge(a\neq 0))\Rightarrow(b\leq |a|)\)（bounds by divisibility）
反證法，假設(shè)\(b>|a|\)，根據(jù)題意存在整數(shù)\(k\)讓\(kb=a,b\neq 0\)
由于\(a\neq 0,k\neq 0\)由于\(k\)是整數(shù)，\(|k|\geq 1,|b|>|kb|\)
然而\(|kb|=|k||b|\geq |b|,\)矛盾
還有唯一取余定理：對(duì)于\(a,b\)存在唯一的一對(duì)\((k,r),a=kb+r,0\leq r<b\)（Division algorithm）
首先假設(shè)一定存在一對(duì)\((k,r)\)（在此課程中不用證明）
根據(jù)前面所提到的證明方法，可以假設(shè)存在\((k_1,r_1),(k_2,r_2)\)滿足要求
有\(a=k_1b+r_1=k_2b+r_2,r1-r2=(k_2-k_1)b,0\leq r_1,r_2\leq b\)
顯然有\(-b<r_1-r_2<b,|r_1-r_2|<b\)。
假設(shè)\(|k_2-k_1|=0(k_2=k_1)\)，那么\(r_1=r_2\)，矛盾
由于\(k_2,k_1\)都是整數(shù)，要么\(|k_2-k_1|=0\)或者\(|k_2-k_1|\geq 1\)，假設(shè)\(|k_2-k_1|\geq 1,|r_1-r_2|=|b(k_2-k_1)|\geq b\)矛盾

第七部分：GCD
定義整數(shù)\((a,b)\)的公約數(shù)\(\gcd(a,b)\)：最大的正整數(shù)\(c\)使得\((c|a)\wedge(c|b)\)
比如\(\gcd(a,-a)=|a|\),\(\gcd(2,-6)=2,\gcd(a,0)=|a|\)
特別的，假設(shè)\(a=b=0,\gcd(a,b)=0\)（因?yàn)槿绻苯影凑斩x的話，\(\gcd\)不存在），我們?cè)诜诸?lèi)討論時(shí)需要特別討論\(a=0,b=0\)的情況
GCD有如下基本定理，對(duì)于所有整數(shù)\(a,b,q,r\)，如果\(a=qb+r\)，則\(\gcd(a,b)=gcd(b,r)\)
證明：我們要證明\(\gcd(b,qb+r)=\gcd(b,r)\)
考慮\(\gcd(b,qb+r)=c,\gcd(b,r)=d,d|b,d|r,c|b,c|qb+r\)，根據(jù)整除的第三條性質(zhì)有\(d|qb+r\)
由于\(c\)是\(b,qb+r\)最大的公約數(shù)，\(d\leq c\)
根據(jù)整除的第三條性質(zhì)有\(c|qb+r-qb,c|r\)，所以\(c\)也是\(r\)，\(|b|\)的約數(shù)，\(c\leq d\)
所以\(d=c\)
當(dāng)\(a=b=0,r=0\)，所以\(\gcd(a,b)=\gcd(b,r)\)
（要注意\(a=b=0\)的情況，因?yàn)榇藭r(shí)上面討論的\(c,d\)不存在）
根據(jù)如下定律，我們可以推出輾轉(zhuǎn)相除法：
假設(shè)我們要求\(\gcd(a,b),a,b>0\)，我們可以先求出\(a\mod b=r\)，然后遞歸求\(gcd(b,r)\)，直到\(b=0,\)此時(shí)\(\gcd(a,b)=1\)
注意當(dāng)\(b=1,\gcd(a,b)=1\)
比如我們想證明\(\gcd(22a+7,3a+1)=1\)，根據(jù)上面的定理\(\gcd(22a+7,3a+1)=\gcd(a,3a+1)=\gcd(a,1)=1\)，得證
\(\gcd\)有如下性質(zhì)：
1.（GCD characterization theorem）對(duì)于所有整數(shù)\((a,b,d),d\geq 0\)，假如\(d|a,d|b\)，而且存在整數(shù)\(x,y\)使得\(ax+by=d\)，那么\(d=\gcd(a,b)\)
假設(shè)\(a=b=0,d=0=\gcd(a,b)\)得證
假設(shè)\(a,b\)不全為\(0\)，\(d\neq \gcd(a,b)\)，那么根據(jù)\(\gcd\)的定義，\(d<\gcd(a,b)\)
設(shè)\(e=\gcd(a,b)\)，那么存在整數(shù)\(f,g\)使\(a=fe,b=ge\)
\(fex+gey=d,fx+gy=\fracw0obha2h00{e}\)
因?yàn)?span id="w0obha2h00" class="math inline">\(d<e,0<fx+gy<1\)，然而\(f,x,g,y\)都是整數(shù)，所以矛盾。
2.bezout引理：對(duì)于所有整數(shù)\(a,b\)，總存在整數(shù)\(x,y\)使\(ax+by=\gcd(a,b)\)
考慮使用拓展Euclid算法證明：
假設(shè)\(a>b\)
該算法維護(hù)了四元組的序列\(a_1=(x_i,y_i,r_i,q_i)\)，\(ax_i+by_i=r_i,q_i=\lfloor \frac{r_{i-2}}{r_{i-1}}\rfloor\)
\(a_1=(1,0,a,0),a_2=(0,1,b,0)\)
在計(jì)算\(r_i\)時(shí)，先計(jì)算\(q_i\)，我們知道\(ax_{i-2}+by_{i-2}=r_{i-2},ax_{i-1}+by_{i-1}=r_{i-1}\)
把1式減去\(q_i\)倍的2式得到\(a(x_{i-2}-q_ix_{i-1})+b(y_{i-2}-q_iy_{i-1})=r_{i-2}-q_ir_{i-1}=r_i\)
容易發(fā)現(xiàn)\(r_i=r_{i-2}\mod r_{i-1}\)，所以這就是輾轉(zhuǎn)相除的過(guò)程。
令\(x_i=x_{i-2}-q_ix_{i-1},y_i=y_{i-2}-q_iy_{i-1}\)，我們就能通過(guò)\(a_{i-2},a_{i-1}\)推出\(a_i\)
當(dāng)\(y_i=0\)時(shí)可以停止該過(guò)程。
此時(shí)\(r_{i-1}|r_{i-2},r_{i-1}=\gcd(a,b),x_{i-1},y_{i-1}\)就是一組解。
所以通過(guò)該過(guò)程我們證明了bezout引理。
3.對(duì)于所有整數(shù)\(a,b,c,((c|a)\wedge(c|b))\Rightarrow(c|\gcd(a,b))\)
考慮使用bezout引理證明
考慮方程\(ax+by=\gcd(a,b)\)，顯然存在一組解。
因?yàn)?span id="w0obha2h00" class="math inline">\(c|a,c|b\)，根據(jù)整除的性質(zhì)\(c|ax+by,c|\gcd(a,b)\)，得證。
4.\(\gcd(ca,cb)=c\gcd(a,b)\)
考慮構(gòu)造方程\(ax+by=\gcd(a,b)\)，顯然存在一組解，設(shè)\(\gcd(a,b)=z\)。
假設(shè)解為\(x_0,y_0\)，這個(gè)解同樣也是\(cax+cby=cz\)這個(gè)方程的解。
\(z|a,z|b\)，設(shè)整數(shù)\(d,e,dz=a,ez=b\)
\(cz|ca=cdz,cz|cb=cez\)，根據(jù)第一條性質(zhì)可得\(\gcd(ca,cb)=cz=c\gcd(a,b)\)，得證

第八部分 素?cái)?shù)和互素
當(dāng)整數(shù)\(a,b\)滿足\(\gcd(a,b)=1\)，定義\((a,b)\)互素
互素有如下性質(zhì)：
1.（coprimeness charaterization theorem）\(\gcd(a,b)=1\)當(dāng)且僅當(dāng)存在\(x,y\)使得\(ax+by=1\)
先證明當(dāng)\(\gcd(a,b)=1\)，存在\(x,y\)使得\(ax+by=1\)，根據(jù)bezout定理得證。
再證明當(dāng)存在\(x,y\)使得\(ax+by=1\)，\(\gcd(a,b)=1\)
顯然\(1|a,1|b\)，所以根據(jù)第一條性質(zhì)\(\gcd(a,b)|1\)，得證
例子：證明如果\(\gcd(a,b)=1,\gcd(a^n,b)=1\)
使用數(shù)學(xué)歸納法，設(shè)\(P(n)\)為命題\((\gcd(a^n,b)=1)\)，當(dāng)\(n=1\)顯然成立
我們需要證明對(duì)于所有\(n\geq 1,P(n)\Rightarrow P(n+1)\)。
根據(jù)第五條性質(zhì)，我們已經(jīng)知道\(a^nx+by=1\)有解，所以\(a^{n+1}+aby=a\)有解。
反證法，假設(shè)\(\gcd(a^{n+1},b)=k>1\)，那么\(k|b,k|a^{b+1}\)
所以根據(jù)整除的性質(zhì)，\(k|a^{n+1}+ab\)。所以\(k|a\)
所以\(k\)是\(a,b\)的公約數(shù)，和\(\gcd(a,b)=1\)矛盾。
2.\((d=\gcd(a,b))\Rightarrow \gcd(\frac{a}w0obha2h00,\frac{b}w0obha2h00)=1\)
根據(jù)性質(zhì)4可得\(\gcd(\frac{a}w0obha2h00*d,\frac{b}w0obha2h00*d)=d\gcd(\frac{a}w0obha2h00,\frac{b}w0obha2h00)=\gcd(a,b)\)，得證
3.對(duì)于所有整數(shù)\(a,b,c\)，如果\(c|ab\)并且\(\gcd(a,c)=1\)，則\(c|b\)
考慮方程\(ax+cy=1\)"，根據(jù)第五條性質(zhì)CCT可得方程有解，設(shè)為(x_0,y_0)。
兩側(cè)乘以\(b\)得到\(abx_0+cby_0=b\)，由于\(c|ab,c|cb\)，可得\(c|ab_x0+cb_y0=b\)，得證。
定義素?cái)?shù)\(p\)：\(p>1\)，而且約數(shù)只有它自己和\(1\)的整數(shù)。
同樣也可以定義素?cái)?shù)\(p\)：小于它的素?cái)?shù)都無(wú)法整除它。
素?cái)?shù)有如下性質(zhì)：
1.（Prime Factorization）每一個(gè)大于等于\(2\)的自然數(shù)都能分解成若干素?cái)?shù)的乘積。
證明：使用強(qiáng)數(shù)學(xué)歸納法，以\(n=2\)開(kāi)始
\(n=2\)顯然成立，因?yàn)?span id="w0obha2h00" class="math inline">\(2\)是素?cái)?shù)。
考慮我們已知\(n=2...k-1(k>2)\)成立，要證明\(n=k\)成立。
分類(lèi)討論：假設(shè)\(k\)是素?cái)?shù)，那么分解成它自己即可。
當(dāng)\(k\)不是素?cái)?shù)，那么一定存在一個(gè)數(shù)\(z\)是\(k\)的約數(shù)。
找到最小的\(z\)，\(z\)一定是素?cái)?shù)。
因?yàn)槿绻?span id="w0obha2h00" class="math inline">\(z\)是合數(shù)，那么肯定存在\(l\)使\(l<z\)且\(l|z\)，根據(jù)整除的傳遞性可得\(l|k\)，矛盾
把分解寫(xiě)成素?cái)?shù)\(z\)和\(\frac{k}{z}\)的乘積，對(duì)\(\frac{k}{z}<k\)應(yīng)用歸納假設(shè)即可。
2.素?cái)?shù)有無(wú)限個(gè)（Euclid定理）
反證法，假設(shè)有有限個(gè)，設(shè)他們?yōu)?span id="w0obha2h00" class="math inline">\(p_1...p_n\)
考慮\(l=p_1p_2...p_n+1\)，那么對(duì)于所有\(1\leq i\leq n\)，\(\gcd(p_i,p_1p_2...p_n+1)=\gcd(p_i,1)=1\)，矛盾。
3.Euclid引理：設(shè)素?cái)?shù)\(p\)和整數(shù)\(a,b\)，如果\(p|ab\)，那么\(p|a\)或者\(p|b\)成立
分類(lèi)討論：假設(shè)\(p|a\)成立，那么得證
假設(shè)\(p|a\)不成立，顯然\(\gcd(p,a)=1\)
根據(jù)\(\gcd\)的性質(zhì)，存在\((x_0,y_0)\)使得\(ax_0+py_0=1\)
\(abx_0+pby_0=b\)，由于\(p|ab,p|pb\)，\(p|(abx_0+pby_0)=b\)，得證
我們可以拓展這個(gè)引理，得到如下結(jié)果（Extended Euclid lemma）：
設(shè)素?cái)?shù)\(p\)和整數(shù)\(a_1,a_2...a_n\)，如果\(p|a_1a_2...a_n\)，那么對(duì)于任何\(1\leq i\leq n\)，\(p|a_i\)至少會(huì)有一個(gè)成立。
我們可以對(duì)\(p|a_1(a_2...a_n)\)應(yīng)用Euclid引理，這樣子我們就可以證明\(p|a_1\)或者\(p|a_2...a_n\)成立
重復(fù)對(duì)\(p|a2(a_3...a_n)\)類(lèi)似此方式應(yīng)用Euclid引理即可得證。
4.唯一分解定理：對(duì)于一個(gè)整數(shù)有唯一的素?cái)?shù)分解。
根據(jù)定理1，一個(gè)數(shù)\(n\)肯定能分解成若干個(gè)素?cái)?shù)。
使用強(qiáng)數(shù)學(xué)歸納法，當(dāng)\(n=2\)顯然成立。
接下來(lái)我們需要證明對(duì)于所有正整數(shù)\(k(k>2)\)，當(dāng)\(n=2...k-1\)時(shí)命題成立可以推出\(n=k\)時(shí)命題成立。
反證法，假設(shè)\(n\)有2種分解方法。
假設(shè)第一種分解方法為\(p_1^{a_1}...p_n^{a_n}=n\)，第二種為\(q_1^{b_1}...q_n^{b_n}=n\)，將\(p,q\)從小到大排序并且合并相同項(xiàng)。
假設(shè)\(p_1<q_1\)（\(p_1>q_1\)同理），因?yàn)?span id="w0obha2h00" class="math inline">\(p_1|n\)，那\(p_1|q_1^{b_1}...q_n^{b_n}\)
根據(jù)拓展Euclid定理，\(p_1|q_i^{b_i}\)肯定有至少一個(gè)成立。
這說(shuō)明\(\gcd(p_1,q_i^{b_i})>1\)
然而\(q_i\)都是素?cái)?shù)，且\(q_i\geq q_1>p\)，所以\(\gcd(p_1,q_i)=1\)
根據(jù)第一個(gè)性質(zhì)所提到的例子，我們知道\(\gcd(p_1,q_i^{b_i})=1\)，矛盾
假設(shè)\(p_1=q_1\)，但是\(a_1\neq b_1\)
假設(shè)\(a_1<b_1\)（\(a_1>b_1\)同理），那么\(\frac{n}{p_1^{a_1}}=p_2^{a_2}...p_n^{a_n}=\frac{q_1^{b_1}...q_n^{b_n}}{p_1^{a_1}}=p_1^{b_1-a_1}...q_n^{b_n}\)
此時(shí)\(p_1\neq p_2\)，可以轉(zhuǎn)化成第一種情況證明。
假設(shè)\(a_1=b_1\)，那么\(\frac{n}{p_1^{a_1}}=p_2^{a_2}...p_n^{a_n}=\frac{q_1^{b_1}...q_n^{b_n}}{p_1^{a_1}}=q_2^{b_2}...q_n^{b_n}\)
并且\(p_2^{a_2}...p_n^{a_n},q_2^{b_2}...q_n^{b_n}\)不相同。
但是\(\frac{n}{p_1^{a_1}}\)根據(jù)歸納假設(shè)有唯一分解，矛盾
也可以使用下面的證明方法（上面是我想到的，但是有點(diǎn)復(fù)雜）：
還是強(qiáng)數(shù)學(xué)歸納法，
如果\(n\)是素?cái)?shù)立刻得證。（要討論素?cái)?shù)的情況，因?yàn)槿绻?span id="w0obha2h00" class="math inline">\(a_1\)并且\(n\)是素?cái)?shù)的話，那么會(huì)得到\(1\)（唯一分解定理未在\(n=1\)處被定義））
如果\(n\)不是素?cái)?shù)，假設(shè)\(n=a_1...a_l=b_1...b_m\)（\(a_i,b_i\)都是素?cái)?shù)）
那么\(a_1|b_1...b_m\)，所以\(b_i\)中至少有一個(gè)滿足\(a_1|b_i\)
由于\(a_i,b_i\)都是素?cái)?shù)，\(a_1=b_i\)
兩邊同除以\(a_1\)得到\(\frac{n}{a_1}=a_2...a_l=b_1...b_{i-1}b_{i+1}....b_m\)
根據(jù)歸納假設(shè)，\(\frac{n}{a_1}\)有唯一分解方法
并且\(a_1=b_i\)，所以加上\(a_1,b_i\)后分解方法也是相同的。得證。
這也說(shuō)明對(duì)于任何正整數(shù)\(n>2\)，存在唯一的分解\(n=p_1^{a_1}...p_n^{a_n}\)，并且\(p_n\)互不相同
5.一個(gè)數(shù)\(n\)要么是素?cái)?shù)，要么至少有一個(gè)\(\leq \sqrt{n}\)的素因子。
假設(shè)\(n\)的唯一分解為\(p_1^{a_1}...p_k^{a_k},k\geq 2\)，\(a_1+...+a_k\geq 2\)且\(p_1<p_2<...p_n\)
假設(shè)\(p_1>\sqrt{n}\)，那么\(p_2...p_k>\sqrt{n},p_1^{a_1}...p_k^{a_k}>(\sqrt{n})^{a_1+...+a_k}\geq n\)，矛盾
6.一個(gè)數(shù)\(n\)最多有1個(gè)素因子\(>\sqrt{n}\)
7.假設(shè)\(n\)的唯一分解為\(p_1^{a_1}...p_k^{a_k}\),\(m\)的唯一分解為\(p_1^{b_1}...p_k^{b_k}\)
\(m|n\)的充要條件為對(duì)于所有\(k,0\leq b_k\leq a_k\)
先證明必要性：設(shè)\(ml=n,l=\frac{n}{m}=p_1^{a_1-b_1}p_2^{a_2-b_2}...p_n^{a_n-b_n}\)
由于對(duì)于所有\(k,0\leq b_k\leq a_k\)，所以\(a_1\geq b_1...a_n\geq b_n\)
所以\(p_1^{a_1-b_1},p_2^{a_2-b_2}...,p_n^{a_n-b_n}\)都是整數(shù)，\(l\)是整數(shù)，證畢。
再證明充分性：使用反證法，設(shè)整數(shù)\(s\)為任意一個(gè)滿足\(b_s>a_s\)的數(shù)，重排\(p\)讓\(p_s\)變?yōu)榈谝晃弧?br> 由于\(m|n\)，存在整數(shù)\(c\)使得\(mc=n\)。
\(\frac{m}{p_1^{a_1}}c=\frac{n}{p_1^{a_1}}=p_1^{b_1-a_1}...p_k^{b_k}c\)
而且\(b_1>a_1\)，這說(shuō)明\(p_1|\frac{n}{p_1^{a_1}}\)
\(\frac{n}{p_1^{a_1}}=p_1^0p_2^{a_2}...p_k^{a_k}\)，且\(p_1\neq p_2....p_k\)
根據(jù)拓展Euclid定理存在\(p_i\)使得\(p_1|p_i^{a_i}\)，然而\(p_1\neq p_i\)，所以無(wú)法整除，矛盾。
8.假設(shè)一個(gè)正整數(shù)\(n\)的唯一分解為\(p_1^{a_1}...p_k^{a_k}\)，那么約數(shù)有\((a_1+1)(a_2+1)...(a_k+1)\)個(gè)
假設(shè)其約數(shù)為\(m\)，\(m\)的唯一分解為\(p_1^{b_1}...p_k^{b_k}\)
\(m|n\)的充要條件為對(duì)于所有\(k,0\leq b_k\leq a_k\)
所以每個(gè)\(b_k\)有\(a_k+1\)種取值，根據(jù)乘法原理約數(shù)有\((a_1+1)(a_2+1)...(a_k+1)\)個(gè)
9.假設(shè)\(n\)的唯一分解為\(p_1^{a_1}...p_k^{a_k}\),\(m\)的唯一分解為\(p_1^{b_1}...p_k^{b_k}\)
那么\(\gcd(n,m)=p_1^{\min(a_1,b_1)}...p_k^{\min(a_k,b_k)}\)
證明：對(duì)于\(n,m\)的每個(gè)公約數(shù)\(q\)，設(shè)其唯一分解為\(p_1^{c_1}...p_k^{c_k}\)
根據(jù)第七個(gè)性質(zhì)，對(duì)于每個(gè)\(1\leq i\leq k\)有條件\(0\leq c_i\leq a_i,b_i\)
所以\(0\leq c_i\leq \min(a_i,b_i)\)
考慮其\(n,m\)的約數(shù)\(p_1^{\min(a_1,b_1)}...p_k^{\min(a_k,b_k)}=l\)
對(duì)于\(q\)的每個(gè)約數(shù)，有條件\(0\leq c_i\leq \min(a_i,b_i)\)
這說(shuō)明\(q\)是\(l\)的約數(shù)，所以根據(jù)整除的性質(zhì)有\(c\leq |l|\)
由于\(k,l\geq 0\)，\(q\leq l\)，所以\(l\)是最大公約數(shù)。
10.假設(shè)一個(gè)正整數(shù)\(n\)的唯一分解為\(p_1^{a_1}...p_k^{a_k}\)，那么其約數(shù)個(gè)數(shù)和為\((1+p_1+...+p_1^{a_1})(1+p_2+...+p_2^{a_2})...(1+p_k+...+p_k^{a_k})\)個(gè)
應(yīng)該可以構(gòu)造雙射證明。

第九部分：不定方程
不定方程有2個(gè)性質(zhì)：
1.對(duì)于所有整數(shù)\(a,b,c\)，方程\(ax+by=c\)存在整數(shù)解當(dāng)且僅當(dāng)\(d|c\)（\(d=\gcd(a,b)\)）（Linear Diophantine Equation Theorem）
先證明當(dāng)\(ax+by=c\)存在整數(shù)解，\(d|c\)
由于\(d|a,d|b\)，所以\(d|ax+by=c\)
再證明當(dāng)\(d|c\)，\(ax+by=c\)存在整數(shù)解。
考慮方程\(ax+by=d\)，根據(jù)\(bezout\)引理其存在整數(shù)解，設(shè)其為\(x_0,y_0\)
由于\(d|c\)，\(\frac{c}w0obha2h00\)是整數(shù)
考慮方程\(a(x_0\frac{c}w0obha2h00)+b(y_0\frac{c}w0obha2h00)=c\)，所以\((x_0\frac{c}w0obha2h00,y0\frac{c}w0obha2h00)\)是方程\(ax+by=c\)的一組整數(shù)解，證畢。
這個(gè)證明過(guò)程說(shuō)明我們?nèi)绻胝业椒匠?span id="w0obha2h00" class="math inline">\(ax+by=c\)的整數(shù)解，我們可以先找到\(ax+by=\gcd(a,b)\)的解，再把兩個(gè)解乘以\(\frac{c}{\gcd(a,b)}\)即可得到原方程的解。
2.考慮方程\(ax+by=c\)（\(a,b\)都不等于\(0\)）
首先找到方程的任意一個(gè)整數(shù)解\(x_0,y_0\)，設(shè)\(d=\gcd(a,b)\)
則不定方程\(ax+by=c\)的解\((x,y)\)可以通過(guò)如下方式全部得到：\(x=x_0+\frac{b}w0obha2h00n,y=y_0-\frac{a}w0obha2h00n\)（\(n\)是整數(shù)）
證明：我們事實(shí)上需要證明兩個(gè)集合\(A=\{(x,y):x,y\in \mathbb{R},ax+by=c\}\)，\(B=\{(x,y),x=x_0+\frac{b}w0obha2h00n,y=y_0-\frac{a}w0obha2h00n,x,y,n\in \mathbb{R}\}\)相等。
先證明\(B\subseteq A\)，我們要證明如果\((x,y)\)屬于\(B\)，那么屬于\(A\)
也就是我們要證明如果\(x=x_0+\frac{b}w0obha2h00n,y=y_0-\frac{a}w0obha2h00n\)且\(n\)是整數(shù)，那么\((x,y)\)屬于集合\(A\)
把\(x,y\)帶入\(ax+by\)，得到\(a(x_0+\frac{b}w0obha2h00n)+b(y_0-\frac{a}w0obha2h00n)=ax_0+by_0+\frac{abn}w0obha2h00-\frac{abn}w0obha2h00=ax_0+by_0=c\)
所以\((x,y)\)屬于集合\(A\)
然后證明\(B\subseteq A\)我們要證明如果\((x,y)\)屬于\(A\)，那么屬于\(B\)
我們要證明如果\(ax+by=c\)，那么存在整數(shù)\(n\)，使得\(x=x_0+\frac{b}w0obha2h00n,y=y_0-\frac{a}w0obha2h00n\)
考慮方程\(ax+by=c\)的解\((x,y)\)，\(ax+by=ax_0+by_0,a(x-x_0)=b(y_0-y)\)
\(\frac{a}w0obha2h00(x-x_0)=\frac{b}w0obha2h00(y_0-y)\)
根據(jù)\(\gcd\)的性質(zhì)有\(\gcd(\frac{a}w0obha2h00,\frac{b}w0obha2h00)=1\)
由于\(\frac{a}w0obha2h00(x-x_0)|\frac{b}w0obha2h00(y_0-y)\)，所以根據(jù)整除的性質(zhì)有\(\frac{a}w0obha2h00|y_0-y\)
所以存在整數(shù)\(n\)使得\(y_0-k\frac{a}w0obha2h00=y\)
將\(y\)帶入\(ax+by=c\)，得到\(x=x_0+\frac{b}w0obha2h00n\)。得證。

第10部分：同余和模算術(shù)
定義\((a,b)\)關(guān)于\(m\)同余：\(m|(a-b)\)，記作\(a\equiv b(\mod m)\)
同余有如下性質(zhì)：
1.對(duì)于所有正整數(shù)\(a,b,m\)，\(a\equiv a(\mod m)\)
我們就是要證明\(m|(a-a)=0\)，顯然得證。
2.對(duì)于所有正整數(shù)\(a,b,m\)，如果\(a\equiv b(\mod m)\)，那么\(b\equiv a(\mod m)\)
我們就是要證明如果\(m|(a-b)\)，那么\(m|(b-a)\)
這說(shuō)明存在整數(shù)\(c\)使得\(cm=a-b\)，所以\((-c)m=(b-a)\)，所以\(m|(b-a)\)，得證。
3.對(duì)于所有正整數(shù)\(a,b,m\)，如果\(a\equiv b(\mod m)\)，\(b\equiv c(\mod m)\)那么\(a\equiv c(\mod m)\)
我們就是要證明如果\(m|(a-b)\)，\(m|(b-c)\)，那么\(m|(a-c)\)
根據(jù)整除的性質(zhì)，\(m|(a-b+b-c)=a-c\)，得證。
4.對(duì)于所有正整數(shù)\(a_1,b_1,a_2,b_2,m\)
如果\(a_1\equiv b_1(\mod m),a_2\equiv b_2(\mod m)\)，那么\(a_1+a_2\equiv b_1+b_2(\mod m),a_1-a_2\equiv b_1-b_2(\mod m),a_1a_2\equiv b_1b_2(\mod m)\)
先證明第一個(gè)：我們需要證明\(m|a_1+a_2-b_1-b_2\)，已知\(m|a_1-b_1,m|a_2-b_2\)
根據(jù)整除的性質(zhì)，\(m|a_1-b_1+a_2-b_2=a_1+a_2-b_1-b_2\)，得證。
同理可以證明第二個(gè)。
再證明第三個(gè)。我們已知\(m|a_1-b_1,m|a_2-b_2\)，需要證明\(m|a_1a_2-b_1b_2\)
根據(jù)整除的定義，存在整數(shù)\(c,d\)使得\(mc=a_1-b_1,md=a_2-b_2\)
所以\(mc+b_1=a_1,md+b_2=a_2\)
\(a_1a_2-b_1b_2=(mc+b_1)(md+b_2)-b_1b_2=m^2cd+m(b_1d+b_2c)=m(mcd+b_1d+b_2c)\)
因?yàn)?span id="w0obha2h00" class="math inline">\(c,d,m,b_1,b_2\)都是整數(shù)，所以\(mcd+b_1d+b_2c\)也是整數(shù)。
所以根據(jù)整除的定義有\(m|a_1a_2-b_1b_2\)
5.對(duì)于所有正整數(shù)\(a_1...a_n,b_1...b_n,m\)（Congruence add and multiply）
如果\(a_1\equiv b_1(\mod m)...a_n\equiv b_n(\mod m)\)，那么\(a_1+...+a_n\equiv b_1+...+b_n(\mod m),a_1a_2...a_n\equiv b_1b_2...n_n(\mod m)\)（Congruence add and multiply）
證明第一個(gè)性質(zhì)可以重復(fù)應(yīng)用第四條性質(zhì)：就是要證明\(a_1+(a_2+...+a_n)\equiv b_1+(b_2...+b_n)(\mod m)\)。
如果我們知道\((a_2+...+a_n)\equiv (b_2...+b_n)(\mod m)\)，那么命題得證。
繼續(xù)對(duì)\(a_2+(a_3...+a_n)\equiv b_2+(b_3...+b_n)(\mod m)\)應(yīng)用定理即可。
證明第二條性質(zhì)同理可以重復(fù)應(yīng)用第四條性質(zhì)的乘法部分。
6.對(duì)于所有正整數(shù)\(c,d,n,m\)，如果\(c\equiv d(\mod m)\)，那么\(c^n\equiv d^n(\mod m)\)（Congruence power）
這是上一個(gè)性質(zhì)當(dāng)\(a_i=c,b_i=d\)的特殊情況
利用上面的性質(zhì)，在剩余系中可以將所有常數(shù)對(duì)模數(shù)取模后計(jì)算，可以減少計(jì)算量。
在一定意義下，在模意義下也可以除法：（Congruence divide）
7.對(duì)于所有正整數(shù)\(a,b,c,m\)，如果\(ac\equiv bc(\mod m)\)并且\(\gcd(c,m)=1\)，那么\(a\equiv b(\mod m)\)
根據(jù)條件\(ac\equiv bc(\mod m)\)我們可以知道存在整數(shù)\(d\)使得\(md=ac-bc\)，要證明存在整數(shù)\(n\)使得\(mn=a-b\)
\(md=c(a-b)\)，這說(shuō)明\(m|c(a-b)\)。由于\(\gcd(c,m)=1\)，根據(jù)整除的性質(zhì)有\(m|(a-b)\)，也就是\(a\equiv b(\mod m)\)，得證
8.\(a\equiv b(\mod m)\) 當(dāng)且僅當(dāng)\(a,b\)對(duì)\(m\)取余相等。（Congruent Iff same Remainder）
先證明充分性，假設(shè)\(a=mq_1+r_1,b=mq_2+r_2,0\leq r_1,r_2<m\)且\(q_1,q_2,r_1,r_2\)都是整數(shù)
根據(jù)題意有\(m|a-b,m|mq_1+r_1-mq_2+r_2,m|m(q_1-q_2)+r_1-r_2\)
根據(jù)整除的性質(zhì)有\(m|m(q_1-q_2)+r_1-r_2-m(q_1-q_2),m|r_1-r_2\)
分類(lèi)討論，假設(shè)\(r_1=r_2\)，得證。
假設(shè)\(r_1\neq r_2\)，則根據(jù)整除的性質(zhì)有\(m\leq|r_1-r_2|\)
然而由于\(0\leq r_1,r_2<m,|r_1-r_2|<m\)，所以不可能。
所以\(r_1=r_2\)。
再證明必要性，假設(shè)\(a=mq_1+r_1,b=mq_2+r_2,r_1=r_2\)且\(q_1,q_2,r_1,r_2\)都是整數(shù)
那么\(a-b=m(q_1-q_2)\),而\(q_2,q_1\)都是整數(shù)，所以\(q_1-q_2\)都是整數(shù)。
所以\(m|m(q_1-q_2)=b-a\)，得證。
該定理對(duì)于\(0\leq b<m\)也成立，所以我們可以把\(a\)對(duì)\(m\)取模參與運(yùn)算，得到性質(zhì)9
9.\(a\equiv b(\mod m)(0\leq b<m)\) 當(dāng)且僅當(dāng)\(a\)對(duì)\(m\)取余等于\(b\)（Congruent To Remainder）
（PS：在答題時(shí)，利用取余除法解題應(yīng)該寫(xiě)：using propositions Congruence Add and multiply, and Congruence power
然后我們?cè)谑褂猛喾?hào)的性質(zhì)求出\(f(x)\equiv b\mod m,0\leq b<m\)后，應(yīng)該寫(xiě)we conclude from the proposition Congruent To Remainder）
10.對(duì)于某整數(shù)，其各位數(shù)字之和能被\(3\)整除是其能被\(3\)整除的充要條件。
考慮其等于\(\overline{a_n...a_1}=10^{n-1}a_n+...+a_1\)
先證明對(duì)于所有\(n\)，\(10^n\equiv 1(\mod 3)\)
使用數(shù)學(xué)歸納法：當(dāng)\(n=1\)時(shí)，根據(jù)帶余除法，\(10 \equiv 1(\mod 3)\)成立
當(dāng)\(n>1\)，我們已知\(10^{n-1}\equiv 1(\mod 3)\)成立，要證明\(10^n\equiv 1(\mod 3)\)。
根據(jù)propositions Congruence Add and multiply, and Congruence power，\(10^n\equiv 10^{n-1}*10\equiv 1*10\equiv 10(\mod 3)\)。得證。
\(10^{n-1}a_n+...+a_1\equiv 1*a_n+...+1*a_1\equiv a_n+...+a_1(\mod 3)\)，得證。
11.對(duì)于某整數(shù)，其各位數(shù)字之和能被\(9\)整除是其能被\(9\)整除的充要條件。
證明和10類(lèi)似。
12.對(duì)于某整數(shù)，其能被\(11\)整除的充要條件是：
設(shè)\(s_1\)為該數(shù)偶數(shù)位的位值，\(s_2\)為該數(shù)奇數(shù)位的位值，那么\(11|s_1-s_2\)。
考慮其等于\(\overline{a_n...a_1}=10^{n-1}a_n+...+a_1\)
\(10\equiv -1(\mod 11)\)，所以有\(10^n\equiv (-1)^n(\mod 11)\)
\(10^{n-1}a_1+...+a_n\equiv (-1)^{n-1}*a_n+...+1*a_1\equiv(1*a_1+1*a_3+...)-(1*a_2+1*a_4+...)(\mod 11)\)
\((1*a_1+1*a_3+...)-(1*a_2+1*a_4+...)=s_1-s_2\)，得證。

第11部分：同余方程（linear congruence），同余類(lèi)和費(fèi)馬小定理
定義同余方程：對(duì)于整數(shù)\(a,c\)要找到整數(shù)\(x\)，使\(ax\equiv c(\mod m)\)
同余方程有如下性質(zhì)（Linear Congruence Theorem）：設(shè)\(d=\gcd(a,m)\)
當(dāng)且僅當(dāng)\(d|c\)時(shí)有解。設(shè)\(x_0\)為該方程的一個(gè)特解，那么解\(x\)滿足\(x\equiv x_0,x_0+\frac{m}w0obha2h00...x_0+(d-1)\frac{m}w0obha2h00(\mod m)\)
證明：先證明當(dāng)且僅當(dāng)\(d|c\)時(shí)有解。
根據(jù)題意，\(m|ax-c\)，設(shè)整數(shù)\(e\)滿足\(em=ax-c\)，\(c=ax-em\)
根據(jù)不定方程的性質(zhì)，這說(shuō)明\(c\)必須能被\(\gcd(a,-m)=d\)整除
然后考慮證明后面的命題。我們需要解不定方程\(c=ax-em\)
考慮特解\(x_0,e_0\)，那么根據(jù)不定方程的性質(zhì)，\(x_0+n\frac{m}w0obha2h00\)（\(n\)是整數(shù)）生成了該方程的所有解。
考慮將\(n\)對(duì)\(d\)作帶余除法，得到\(n=dq+r\)，\(0\leq r<d\)
\(x_0+n\frac{m}w0obha2h00=x_0+(dq+r)\frac{m}w0obha2h00=x_0+md+r\frac{m}w0obha2h00\)
\(x_0+md+r\frac{m}w0obha2h00\equiv x_0+r\frac{m}w0obha2h00(\mod m)\)，而且\(0\leq r<d\)，所以我們就得到了題目中的結(jié)果。
這說(shuō)明在解同余方程\(ax\equiv c(\mod m)\)時(shí)，我們可以構(gòu)造方程\(ax+my=c\)
用exgcd解這個(gè)方程得到\(x=x_0\)，然后使用\(x_0+n\frac{m}w0obha2h00\)就可以得到這個(gè)方程的所有解。
非線性同余方程：比如\(x^2\equiv c(\mod m)\)
這種方程不能使用上面提到的方式解決，但是可以用枚舉法/費(fèi)馬小定理（可以?xún)煞N方法同時(shí)使用）解決。
可以使用二次剩余相關(guān)知識(shí)解決部分非線性同余方程，但是與本文無(wú)關(guān)。
在此基礎(chǔ)上定義整數(shù)\(a\)的同余類(lèi)：\(\mathbb{Z}_m={[0],[1]...[m-1]}\)
\([a]=\{x\in \mathbb{Z},x\equiv a(\mod m)\}\)
同余類(lèi)可以類(lèi)似普通整數(shù)那樣運(yùn)算（除了第七條性質(zhì)以外），滿足如下性質(zhì)：
1.\([a]+[b]=[a+b]\)
2.\([a][b]=[ab]\)
3.\([a][0]=[0]=[0][a]\)
4.\([a]+[0]=[a]=[0]+[a]\)
5.\([a][1]=[a]=[1][a]\)
6.\([a]+[-a]=[-a]+[a]=0\)
7.\([a]=[a-m]\)
運(yùn)算后結(jié)果中的常數(shù)可以對(duì)\(m\)取余，最好多寫(xiě)一步。
例子是假設(shè)我們有同余類(lèi)\(\mathbb{Z}_4\)，在該同余類(lèi)中\([2]+[3]=[5]=[1]\)
定義\([0]\)是加法單位元（additive identity），\([1]\)是乘法單位元（multiplicative identity），某整數(shù)的加法逆元\([-a]\)（additive inverse）
同余類(lèi)和同余方程關(guān)系密切：有定理\([a][x]=[c]\)有解，設(shè)\(d=\gcd(a,m)\)，只有\(d|c\)時(shí)才有解。
并且定義一個(gè)特解是\(x_0\)，其所有解滿足\(x=x_0+\frac{m}w0obha2h00n,0\leq n<d\)
證明：這定義了一個(gè)同余方恒\(ax\equiv c(\mod m)\)
而且設(shè)\(x_0\)是特解，其所有解\(x\)滿足\(x\equiv x_0,x_0+\frac{m}w0obha2h00...x_0+(d-1)\frac{m}w0obha2h00(\mod m)\)，也就是命題中所提到的。
這說(shuō)明在解方程\([a][x]=[c]\)時(shí)，我們需要求出線性方程\(ax+my=c\)的解。
定義某同余類(lèi)\([a]\)的乘法逆元\([b]\)，滿足\([a][b]=[b][a]=[1]\)
乘法逆元有2個(gè)性質(zhì)：
1.對(duì)于所有整數(shù)\(1\leq a\leq m-1\)，如果\(\gcd(a,m)=1\)，那么\([a]\)存在乘法逆元并且唯一
2.對(duì)于所有整數(shù)\(1\leq a\leq m-1\)，如果\(m\)是素?cái)?shù)，那么\([a]\)一定存在乘法逆元并且唯一
例子：在\(\mathbb{Z}_{11}\)我們要求方程\([2x]+[7y]=[4],[3x]+[2y]=[9]\)的解。
為了解這個(gè)方程，我們可以類(lèi)似普通二元一次方程那樣子解。
但是在解的時(shí)候，如果想要對(duì)于兩邊乘以某數(shù)\(x\)，必須寫(xiě)\([x]\)，因?yàn)橹挥?span id="w0obha2h00" class="math inline">\([x]\)才能和另一個(gè)同余類(lèi)運(yùn)算。
比如我們可以將第一個(gè)方程乘以\([3]\)減去第二個(gè)方程乘以\([2]\)，得到\([17y]=[-6]\)
由于\([17]\)在\(\mathbb{z}_{11}\)下等于\([6]\)，我們得到了\([6y]=[-6]\)
求乘法逆元可以用費(fèi)馬小定理：對(duì)于素?cái)?shù)\(p\)，整數(shù)\(a>0\)有\(a^{p-1}\equiv 1(\mod p)\)（這說(shuō)明想要使用費(fèi)馬小定理，需要考慮\(a\equiv 0(\mod p)\)的情況）
為了證明費(fèi)馬小定理，我們首先證明威爾遜定理：對(duì)于素?cái)?shù)\(p\)有\((p-1)!\equiv -1(\mod p)\)
顯然當(dāng)\(p=2\)時(shí)成立。
考慮\(1...p-1\)中的兩個(gè)不同的數(shù)\(x,y\)，他們對(duì)應(yīng)的逆元是唯一的，而且是不同的。
假設(shè)相同，那么\(xa\equiv ya(\mod p)\)，顯然\(\gcd(a,p)=1\)，那么\(x\equiv y(\mod p)\)，矛盾。
所以\(1...p-1\)的逆元也構(gòu)成集合\(\{1...p-1\}\)
這說(shuō)明除了\(1,p-1\)，\(\{1...p-1\}\)中的其他數(shù)都能兩兩配對(duì)，并且乘積為\(1\)
\((p-1)!\equiv 1*1*(p-1)\equiv p-1(\mod p)\)，得證。
考慮數(shù)列\(a,2a...(p-1)a\)，它們是兩兩不同的。
因?yàn)榧僭O(shè)存在\(xa\equiv ya(\mod p)\)且\(x,y\)不同，根據(jù)上面的證明結(jié)論可以得知這是不可能的。
考慮\(a*(2a)*...*(p-1)a=a^{p-1}(p-1)!\)，\(a^{p-1}(p-1)!\equiv -a^{p-1}(\mod p)\)
而且\(a,2a...(p-1)a\)兩兩不同，所以根據(jù)威爾遜定理可得\(a*(2a)*...*(p-1)a\equiv -1(\mod p)\)
所以\(p-1 \equiv (p-1)a^{p-1}(\mod p)\)，兩邊乘以\(p-1\)的逆元得到\(a^{p-1}\equiv 1(\mod p)\)，得證。
推論：對(duì)于素?cái)?shù)\(p\)，有\(a^p\equiv a(\mod p)\)
\(a^{p-2}\)對(duì)\(m\)取余的余數(shù)是一個(gè)素?cái)?shù)的逆元。

第12部分：同余方程組
解若干個(gè)同余方程，可以使用中國(guó)剩余定理：
設(shè)\(n\)是整數(shù)（也可以是函數(shù)），設(shè)整數(shù)\(m_1,m_2,a_1,a_2\)，滿足\(\gcd(m_1,m_2)=1\)
假設(shè)關(guān)系\(n\equiv a_1(\mod m_1)\)
\(n\equiv a_2(\mod m_2)\)存在唯一解\(x_0\)
那么該系統(tǒng)的所有解由\(x\equiv x_0(\mod m_1m_2)\)給出。
證明：根據(jù)條件，設(shè)\(n=m_1k+a_1\)
\(m_1k+a_1\equiv a_2(\mod m_2)\)，這說(shuō)明\(m_1k\equiv a_2-a_1(\mod m_2)\)
由于\(\gcd(m_2,m_1)=1|m_2\)，該方程一定有解，設(shè)為\(k_1\)
這個(gè)方程所有的解\(k\)滿足\(k=k+m_2s\)（\(s\)是整數(shù)）
\(m_1(k+m_2s)+a_1=m_1k+m_1m_2s+a_1=n+m_1m_2s\)，\(n+m_1m_2s\equiv n(\mod m_1m_2)\)，得證。
該定理可以推廣至多個(gè)變量：設(shè)\(x\)是整數(shù)（也可以是函數(shù)），設(shè)整數(shù)\(m_1...m_n,a_1...a_n\)，滿足\(m\)數(shù)組兩兩互素
假設(shè)關(guān)系\(x\equiv a_1(\mod m_1)...x\equiv a_n(\mod m_n)\)存在唯一解\(x_0\)
那么該系統(tǒng)的所有解由\(x\equiv x_0(\mod m_1m_2...m_n)\)給出。
考慮將方程兩兩合并成\(x\equiv x_0(\mod m_1m_2)\)即可證明。
解兩個(gè)線性同余方程組，可以用excrt：
\(a_1x\equiv b_1(\mod m_1),a_2x\equiv b_2(\mod m_2)\)
我們可以先設(shè)\(a1_x=m_1k+b_1\)，獲得一個(gè)特解\(x_0\)
設(shè)\(\gcd(a_1,m_1)=d\)，那么所有解都可以被表示成\(x_0+\frac{m_1}w0obha2h00n\)的形式。
將這個(gè)解帶入第二個(gè)方程，得到\(a_2x_0\equiv b_2-a_1\frac{m_1}w0obha2h00n(\mod m_2)\)
這樣子就能合并兩個(gè)方程組。
對(duì)于多個(gè)方程組兩兩合并即可。
CRT有如下推論（Splitting modulus theorem）：設(shè)整數(shù)\(m_1,m_2,a\)，滿足\(\gcd(m_1,m_2)=1\)
方程\(n\equiv a(\mod m_1)\)
\(n\equiv a(\mod m_2)\)的解和\(n\equiv a(\mod m_1m_2)\)相同。
證明：考慮第三個(gè)方程的解，可以表示成\(n=a+m_1m_2k\)（\(k\)是整數(shù)）的形式
\(a+m_1m_2k\equiv a(\mod m_1),a+m_1m_2k\equiv a(\mod m_2)\)，所以第三個(gè)方程的解也是第一個(gè)和第二個(gè)方程的解。
考慮第一個(gè)方程的解\(n=m_1k+a\)（\(k\)是整數(shù)），可得\(m_1k+a\equiv a(\mod m_2),m_1k\equiv 0(\mod m_2)\)
這說(shuō)明\(m_2|m_1k\)，由于\(\gcd(m_1,m_2)=1\)，\(m_2|k\)
設(shè)\(m_2c=k\)，那么\(n=a+m_1m_2c\)，\(a+m_1m_2c\equiv a(\mod m_1m_2)\)，所以第一個(gè)方程和第二個(gè)方程的解也是第三個(gè)方程的解。
利用這個(gè)推論，考慮方程\(n\equiv a(\mod m)\)（\(n\)可以是關(guān)于某數(shù)\(x\)的函數(shù)），如果我們將\(m_1\)唯一分解得到\(p_1^{k_1}...p_n^{k_n}\)
那么我們事實(shí)上等于解方程\(n\equiv a(\mod p_1^{k_1})...n\equiv a(\mod p_n^{k_n})\)（因?yàn)?span id="w0obha2h00" class="math inline">\(p_1^{k_1}...p_n^{k_n}\)顯然兩兩互素）
而\(p_i^{k_i}\)可能較小，所以可以結(jié)合費(fèi)馬小定理/暴力等方法解決。

第13部分：RSA加密算法
考慮兩個(gè)人A,B，B進(jìn)行了如下加密算法：
隨機(jī)生成兩個(gè)大素?cái)?shù)\(p,q\)，首先求出\(e=(p-1)(q-1),n=pq\)
然后求出\(k\)使得\(k,e\)互素。
由于\(k,e\)互素，所以在模\(e\)意義下\(k\)存在乘法逆元\(l\)。
B向A公開(kāi)發(fā)送公鑰\((k,n)\)，并且保存私鑰\((l,n)\)
如果A要向B發(fā)送信息（假設(shè)是整數(shù)\(F\)），那么A可以生成加密后的信息\(C\)，\(C\)是\(F^k\)對(duì)\(n\)取余的結(jié)果
B使用獲得的加密后的信息\(C\)，然后計(jì)算\(C^l\)對(duì)\(n\)取余的結(jié)果就能得到\(F\)。
證明：我們就是要證明\(F^{lk}\equiv F(\mod n)\)
\(lk\equiv 1(\mod e)\)，這說(shuō)明存在整數(shù)\(s\)使得\(lk=(p-1)(q-1)s+1\)
就是要證明\(F^{(p-1)(q-1)s+1}\equiv F(\mod n)\)
假設(shè)\(F\)不能被\(p,q\)中任何一個(gè)整除，考慮證明\(F^{(p-1)(q-1)}\equiv 1(\mod n)\)，我們可以使用中國(guó)剩余定理的推論。
考慮方程\(F^{(p-1)(q-1)}\equiv 1(\mod n)\)，其解滿足\(F^{(p-1)(q-1)}\equiv 1(\mod p),F^{(p-1)(q-1)}\equiv 1(\mod q)\)
根據(jù)費(fèi)馬小定理，可得\(F^{(p-1)(q-1)}\equiv(F^{(p-1)})^{q-1} \equiv 1^{q-1}\equiv 1(\mod p)\)
對(duì)于所有\(F\)成立，同理，\(F^{(p-1)(q-1)}\equiv 1(\mod q)\)對(duì)于所有\(F\)成立。
所以\(F^{(p-1)(q-1)}\equiv 1(\mod n)\)對(duì)于所有\(F\)恒成立。
假設(shè)\(F\)能被\(p,q\)中恰好一個(gè)整除，假設(shè)\(p|F\)（\(q|F\)）同理。
使用中國(guó)剩余定理的推論，我們就是要證明\(F^{(p-1)(q-1)s+1}\equiv F(\mod p)\)，\(F^{(p-1)(q-1)s+1}\equiv F(\mod q)\)恒成立
由于\(p|F\)，\(F^{(p-1)(q-1)s+1}\equiv 0\equiv F(\mod p)\)
根據(jù)費(fèi)馬小定理可得\((F^{(q-1)})^{s(p-1)}\equiv 1(\mod q)\)對(duì)于所有\(F\)成立。
所以\((F^{(q-1)s(p-1)+1})\equiv F(\mod q)\)對(duì)于所有\(F\)成立，得證。
假設(shè)\(F\)能被\(p,q\)同時(shí)整除，顯然有\(F^{(p-1)(q-1)s+1}\equiv 0\equiv F(\mod n)\)成立，得證。

第14部分：復(fù)數(shù)
先定義復(fù)數(shù)\(a=x+yi\)的標(biāo)準(zhǔn)形式\(x+yi\)（\(x,y\)都要是實(shí)數(shù)。），\(i=\sqrt{-1}\)是虛數(shù)單位
定義復(fù)數(shù)的實(shí)部\(Re(x+yi)=x\)，虛部\(Im(x+yi)=y\)
定義兩個(gè)復(fù)數(shù)\(x+yi,u+vi\)相等：\(x=u,y=v\)
定義2個(gè)復(fù)數(shù)\(a=x+yi,b=u+vi\)的加，減，乘法:
\(a+b=(x+u)+(y+v)i,a-b=(x-u)+(y-v)i,ab=(xy-uv)+(uy+xv)i\)
定義除法：\(\frac{x+yi}{u+vi}=\frac{(u-vi)(x+yi)}{(u+vi)(u-vi)}=\frac{(u-vi)(x+yi)}{u^2+v^2}\)
\(=\frac{ux+vy}{u^2+v^2}+i\frac{-vx+uy}{u^2+v^2}\)
除法公式通過(guò)給分母乘以分母的共軛以使分母變?yōu)閷?shí)數(shù)，從而能化為標(biāo)準(zhǔn)形式。
復(fù)數(shù)滿足如下性質(zhì)：
1.乘法單位元（Multiplicative identity）\(1=1+0i\)，加法單位元（additive identity）\(0=0+0i\)
有\(z+0=0+z=z,0*z=z*0=0,1*z=z*1=1\)
2.定義一個(gè)復(fù)數(shù)\(z=a+bi\)的加法逆\(-z=-a-bi\)
\(z+(-z)=(-z)+z=0\)
3.結(jié)合律：\((x+y)+z=x+(y+z),(xy)z=x(yz)\)
4.交換律：\(x+y=y+x,xy=yx\)
5.定義復(fù)數(shù)\(z=a+bi\)的乘法逆\(z^{-1}=\frac{a-bi}{a^2+b^2}\)
\(zz^{-1}=1\)
6.分配律：\((x+y)z=xz+yz\)
定義復(fù)數(shù)\(a=x+yi\)的共軛\(\overline a=x-yi\)
復(fù)數(shù)的共軛有如下性質(zhì)：
1.\(\overline{(\overline{a})}=a\)
2.\(\overline{a}+\overline{b}=\overline{a+b}\)
可以推出\(\overline{a_1+a_2+...+a_n}=\overline{a_1}+\overline{a_2}+...+\overline{a_n}\)
3.\(\overline{a}+a=2Re(a),\overline{a}-a=2Im(a)i\)
4.\(\overline{a}\overline{b}=\overline{ab}\)
可以推出\(\overline{a_1a_2...a_n}=\overline{a_1}\overline{a_2}...\overline{a_n}\)
5.如果\(a\neq 0,\overline{a^{-1}}=(\overline{a})^{-1}\)
定義復(fù)數(shù)\(a=x+yi\)的模長(zhǎng)：\(\sqrt{x^2+y^2}\)
復(fù)數(shù)的模長(zhǎng)有如下性質(zhì)：
1.\(|a|=0\)當(dāng)且僅當(dāng)\(a=0\)
2.\(|\overline{a}|=|a|\)
3.\(\overline{a}a=|a|^2\)
4.\(|a||b|=|ab|\)
可以推出\(|a_1a_2...a_n|=|a_1||a_2|...|a_n|\)
5.如果\(a\neq 0,|a^{-1}|=|a|^{-1}\)
6.三角形不等式：\(|a+b|\leq |a|+|b|\)
定義復(fù)平面：一個(gè)平面，考慮復(fù)數(shù)\(a+bi\)，在這個(gè)平面的點(diǎn)\((b,a)\)處。
通過(guò)復(fù)平面，我們可以證明三角形不等式：
假設(shè)\(a=x+yi,b=u+vi\)，考慮點(diǎn)\(A(x,y),B(-u,-v)\)
那么\(AB=|a+b|,OA=|a|,OB=|b|\)
根據(jù)三角形的性質(zhì)有\(AB\leq OA+OB,|a+b|\leq |a|+|b|\)
定義復(fù)數(shù)\(a=x+yi\)的三角表示（polar form）：
設(shè)\(a\)的模長(zhǎng)為\(r\)，\(a=r(\cos(\theta)+i\sin(\theta))\)
\(\theta\)被稱(chēng)為它的幅角（Argument）
比如復(fù)數(shù)\(5-5i\)的三角表示是\(5\sqrt{2}(\cos(-\frac{pi}{4})+i\sin(-\frac{pi}{4}))\)
定義復(fù)數(shù)的三角形式的乘法（polar multiplication）：復(fù)數(shù)\(a=r_1(\cos(\theta_1)+i\sin(\theta_1)),b=r_2(\cos(\theta_2)+i\sin(\theta_2))\)
\(a*b=r_1r_2(\cos(\theta_1+\theta_1),i\sin(\theta_1+\theta_2))\)
因?yàn)?span id="w0obha2h00" class="math inline">\(ab=r1r2((\cos(\theta_1)\cos(\theta_2)-\sin(\theta_1)\sin(\theta_1))+i(\sin(\theta_1)\cos(\theta_2)+\sin(\theta_2)\cos(\theta_1)))\)
根據(jù)和角公式有\(a*b=r_1r_2(\cos(\theta_1+\theta_1),i\sin(\theta_1+\theta_2))\)
也就是說(shuō)乘法就是幅角相加，模長(zhǎng)相乘。
同理定義除法：\(\frac{a}{b}=\frac{r_1}{r_2}(\cos(\theta_1-\theta_1),i\sin(\theta_1-\theta_2))\)
根據(jù)乘法我們可以推出De Moivre 定理：\((\cos(\theta)+i\sin(\theta))^n=(\cos(n\theta)+i\sin(n\theta))\)
可以使用歸納法證明：\(n=1\)顯然成立
對(duì)于所有整數(shù)\(n>1\)，我們已知\((\cos(\theta)+i\sin(\theta))^{n-1}=(\cos((n-1)\theta)+i\sin((n-1)\theta))\)
\((\cos((n-1)\theta)+i\sin((n-1)\theta))(\cos(\theta)+i\sin(\theta))=(\cos(\theta)+i\sin(\theta))^n\)
根據(jù)復(fù)數(shù)乘法的定義，上式等于\((\cos(n\theta)+i\sin(n\theta))\)，等于\((\cos(\theta)+i\sin(\theta))^n\)，得證。
同樣我們可以推出對(duì)于復(fù)數(shù)\(a=r(\cos(\theta)+i\sin(\theta))\)，除非\(a=r=0\)，有\(a^n=r^n(\cos(n\theta)+i\sin(n\theta))\)
例子：證明三倍角公式：\(\cos(3\theta)=(4\cos(\theta)^3-3\cos(\theta)),\sin(3\theta)=(3\sin(\theta)-4\sin(\theta)^3)\)
考慮復(fù)數(shù)\(a=\cos(\theta)+i\sin(\theta),a^3=\cos(3\theta)+i\sin(3\theta)=\cos(\theta)^3+3i\cos(\theta)^2\sin(\theta)-3\cos(\theta)\sin(\theta)^2-i\sin(\theta)^3\)
\(=\cos(\theta)^3-3\cos(\theta)\sin(\theta)^2+i(3\cos(\theta)^2\sin(\theta)-\sin(\theta)^3)\)
對(duì)比系數(shù)可得\(\cos(3\theta)=\cos(\theta)^3-3\cos(\theta)\sin(\theta)^2=\cos(\theta)^3-3\cos(\theta)(1-\cos(\theta)^2)\)
\(=4\cos(\theta)^3-3\cos(\theta)\)
\(\sin(3\theta)=3\cos(\theta)^2\sin(\theta)-\sin(\theta)^3=3(1-\sin(\theta)^2)\sin(\theta)-\sin(\theta)^3=3\sin(\theta)-4\sin(\theta)^3\)，得證。
除此之外，容易發(fā)現(xiàn)復(fù)數(shù)乘法對(duì)幅角的影響和冪的乘運(yùn)算時(shí)相同的。
所以可以想到歐拉公式：\(\cos(\theta)+i\sin(\theta)=e^{i\theta}\)
復(fù)數(shù)\(n\)次方根：考慮方程\(z^n=a\)（\(a\)是復(fù)數(shù)\(k(\cos(\theta)+i\sin(\theta))\)），它有\(n\)個(gè)解。
設(shè)\(|z|=l\)，\(l\)是實(shí)數(shù)且\(l^n=a\)，所以\(l=\sqrt[n]{a}\)
考慮\(z=l(\cos(x)+i\sin(x)),z^n=l^n(\cos(nx)+i\sin(nx))=a\)
所以\((\cos(nx)+i\sin(nx))=\cos(\theta)+i\sin(\theta)\)
所以\(nx=2k\pi+\theta,k\)是任意整數(shù)
所以\(\theta=\frac{2k\pi+\theta}{n}\)
這個(gè)證明似乎是不嚴(yán)謹(jǐn)?shù)模瑖?yán)謹(jǐn)證明需要用到集合相等（待填）
容易發(fā)現(xiàn)，所有解均分一個(gè)圓。
考慮二次方程\(ax^2+bx+c\)，\(x\)可能是復(fù)數(shù)。
我們知道解是\(\frac{-b+\sqrt{b^2-4ac}}{2a}\)，當(dāng)判別式小于\(0\)時(shí)，我們可以用復(fù)數(shù)表示\(\sqrt{b^2-4ac}\)，得到這個(gè)方程的復(fù)數(shù)解。

第15部分：多項(xiàng)式
定義在數(shù)域\(\mathbb{R}\)或者\(\mathbb{C}\)的多項(xiàng)式\(f(x)=a_nx^n+a_{n-1}x^{n-1}...+a_0\)。
\(n\geq 0\)且是整數(shù)。定義\(x\)是未知數(shù)（indeterminate），\(a_0,a_1...a_n\)是\(\mathbb{R}\)或者\(\mathbb{C}\)的元素。
\(a_i\)稱(chēng)為多項(xiàng)式的系數(shù)（coefficient），\(a_ix^i\)稱(chēng)為多項(xiàng)式的項(xiàng)（terms）
如果多項(xiàng)式的所有元素都屬于\(\mathbb{R}\)，則稱(chēng)其為實(shí)多項(xiàng)式（real polynomials）
如果多項(xiàng)式的所有元素都屬于\(\mathbb{C}\)，則稱(chēng)其為復(fù)多項(xiàng)式（complex polynomials）
定義多項(xiàng)式\(f(x)\)的度\(\deg f(x)\)：最大的\(n\)滿足\(a_n>0\)。
如果\(f(x)\)的每項(xiàng)都是\(0\)，則稱(chēng)為零多項(xiàng)式（zero polynomial）
把\(\deg f(x)=1,2,3\)的多項(xiàng)式分別稱(chēng)為linear polynomials, quadratic
polynomials, and cubic polynomials。
定義多項(xiàng)式\(f(x)=a_nx^n+a_{n-1}x^{n-1}...a_0,g(x)=b_nx^n+b_{n-1}x^{n-1}...+b_0\)相等：對(duì)于所有\(0\leq i\leq n\)的整數(shù)\(i\)，\(a_i=b_i\)且\(\deg f(x)=\deg g(x)\)
定義多項(xiàng)式\(f(x)=a_nx^n+a_{n-1}x^{n-1}...a_0,g(x)=b_mx^n+b_{n-1}x^{n-1}...+b_0\)并且\(a_n,b_n>0\)的加法：\(\sum_{i=0}^{\max(m,n)}x^i(a_i+b_i)=f(x)+g(x)\)
加法后多項(xiàng)式的度為\(\max(m,n)\)
當(dāng)\(i>n,a_i=0\)，當(dāng)\(i>m,b_i=0\)
定義多項(xiàng)式\(f(x)=a_nx^n+a_{n-1}x^{n-1}...a_0,g(x)=b_mx^n+b_{n-1}x^{n-1}...+b_0\)并且\(a_n,b_n>0\)的乘法：
\(\sum_{i=0}^{n}\sum_{j=0}^{m}x^{i+j}(a_ib_j)=f(x)g(x)=\sum_{i=0}^{n+m}x^ic_i\)
\(c_i=\sum_{j=0}^{i}a_{i}b_{j-i}\)。
同樣當(dāng)\(i>n,a_i=0\)，當(dāng)\(i>m,b_i=0\)。
乘法后多項(xiàng)式的度為\(m+n\)。
定義實(shí)數(shù)多項(xiàng)式整除：\(\frac{f(x)}{g(x)}\)，當(dāng)且僅當(dāng)存在實(shí)多項(xiàng)式\(h(x)\)使得\(f(x)=g(x)h(x)\)成立，記作\(g(x)|f(x)\)（稱(chēng)作 \(g(x)\) divides \(f(x)\) or \(g(x)\) is a factor of \(f(x)\)）
同理定義復(fù)數(shù)多項(xiàng)式整除：\(\frac{f(x)}{g(x)}\)，當(dāng)且僅當(dāng)存在復(fù)多項(xiàng)式\(h(x)\)使得\(f(x)=g(x)h(x)\)成立，記作\(g(x)|f(x)\)（稱(chēng)作 \(g(x)\) divides \(f(x)\) or \(g(x)\) is a factor of \(f(x)\)）
在已知\(g(x)\)時(shí)，求多項(xiàng)式除法可以用長(zhǎng)除法。
定義實(shí)/復(fù)多項(xiàng)式\(f(x)=a_nx^n+a_{n-1}x^{n-1}...a_0\)的方程（polynomial equation）：\(a_nx^n+a_{n-1}x^{n-1}...a_0=0\)
如果\(f(c)=0\)（\(c\)是實(shí)數(shù)/復(fù)數(shù)，與該多項(xiàng)式的類(lèi)型相同），那么\(c\)是這個(gè)多項(xiàng)式的根（root）
多項(xiàng)式的根有如下性質(zhì)：
1.分解定理（Factor Theorem）對(duì)于所有實(shí)/復(fù)多項(xiàng)式\(f(x)\)以及所有的實(shí)數(shù)/復(fù)數(shù)\(c\)，\((x-c)|f(x)\)當(dāng)且僅當(dāng)\(f(c)=0\)
2.代數(shù)基本定理（Fundamental Theorem of Algebra）：對(duì)于所有復(fù)多項(xiàng)式\(f(x)\)，一定存在至少一個(gè)根（可以是實(shí)數(shù)，可以是復(fù)數(shù)）。
這個(gè)定理的證明超出了本文的范圍。
3.（Complex Polynomials of Degree \(n\) Have \(n\) Roots）：
對(duì)于所有復(fù)多項(xiàng)式\(f(x)\)，設(shè)\(\deg f(x)=n\)，存在實(shí)數(shù)\(c,c_1...c_n\)，使得\(f(x)=c(x-c_1)...(x-c_n)\)
所以它一定存在\(n\)個(gè)解（可能相同）。
這個(gè)定理的證明也超出了本文的范圍。
4.3的推論可得對(duì)于所有復(fù)多項(xiàng)式\(f(x)\)，設(shè)\(\deg f(x)=n\)，它最多有\(n\)個(gè)根。
把\(3\)中的\(c\)數(shù)列去重后就是所有根，由于去重后數(shù)列的元素個(gè)數(shù)只會(huì)減少，所以根最多有\(n\)個(gè)。
5.雖然尋找三次及以上的多項(xiàng)式的根超越了本文的范圍，但是我們還有方法能確定多項(xiàng)式的根：
對(duì)于實(shí)多項(xiàng)式\(f(x)\)，如果\(x_0\)是解，那么\(\overline{x_0}\)也是解。
證明：\(f(x_0)=a_nx_0^n+a_{n-1}x_0^{n-1}...+a_0=0\)
兩邊取共軛得到\(\overline{a_n(x_0^n+a_{n-1}x_0^{n-1}...+a_0}=\overline{0}\)
也就是\(\overline{a_n(x_0^n)}+\overline{a_{n-1}x_0^{n-1}}...+\overline{a_0}=\overline{0}\)
根據(jù)共軛的性質(zhì)有\(\overline{a_n}(\overline{x_0})^n+\overline{a_{n-1}}(\overline{x_0})^{n-1}...+\overline{a_0}=\overline{0}\)
實(shí)數(shù)的共軛等于自己，所以\(a_n(\overline{x_0})^n+a_{n-1}(\overline{x_0})^{n-1}...+a_0=0\)
所以\(f(\overline{x_0})=0\)，得證。
6.對(duì)于所有復(fù)數(shù)\(c,(x-c)(x-\overline{c})\)是實(shí)多項(xiàng)式
證明：\((x-c)(x-\overline{c})=x^2-x(c+\overline{c})+c\overline{c}\)
根據(jù)共軛的性質(zhì)，\(c+\overline{c}=2Re(c)\)，\(c\overline{c}=|c|^2\)都是實(shí)數(shù)，得證。
7.對(duì)于所有非\(0\)實(shí)多項(xiàng)式，那么它可以被寫(xiě)成若干個(gè)一次和二次多項(xiàng)式的乘積。
8.考慮\(f(x)=a_nx^n+a_{n-1}x^{n-1}...+a_0\)，假設(shè)\(a_i\)都為有理數(shù)
考慮它的某個(gè)因式\(px-q\)，那么\(p|a_n,q|a_0\)
這說(shuō)明它的有理數(shù)解（不一定存在）\(\frac{p}{q}\)滿足\(p|a_n,q|a_0\)