初等數論學習筆記（一）

09-21

初等數論學習筆記（一）

來自專欄 sola的數學筆記27 人贊了文章

前言：

暑假在校選了張益唐老師教授的初等數論進行學習，感覺收穫頗豐。說實話，之前一直沒有接觸過數論這塊內容，但是學習的過程中發現了很多有趣的結論和方法。寫下這篇學習筆記一方面是想幫助自己理清思路，另一方面也是想能夠將一些思路和有趣的結果展示給大家。本篇筆記寫得比較基礎，之前沒有過數論學習經驗的同學也能夠讀懂並有所收穫。另外，每篇筆記後附有習題，並有提示或解答，感興趣的話可以嘗試，都能得到一些比較有趣的結果。

另外，這也是我第一次在知乎上發文（也是第一次用latex編輯公式（打了一晚上好累www）。本人才疏學淺，若有錯誤歡迎各位指正，若有更好的解法歡迎各位與我討論，若有能做得更好之處歡迎各位指點，在此先謝過各位了！

整除等數論基本概念

一、整除

定義：

$a|b(a eq 0)Leftrightarrow exists l,s.t. b=al$

容易知道整除有著以下性質：（證明略）

1、 $a|b,b|cRightarrow a|c$

2、 $a_1+a_2+...+a_n=0,k|a_2,k|a_3,...,k|a_nRightarrow k|a_1$

3、（帶余除法） $forall a,b(b>0),exists q,r,s.t.a=bq+r(0leq r<b)$

二、最大公因數（gcd）

定義：

給定 $a_1,a_2,...,a_n$ 不全為0，易知集合 $left { d:d>0,d|a_1,d|a_2,...d|a_n ight }$ 為有限集合，則其極大元存在且唯一，稱為 $a_1,a_2,...,a_n$ 最大公因數（gcd），記為 $(a_1,a_2,...,a_n)$ 。

下面給出gcd的比較重要的性質：

1、在帶余除法 $forall a,b(b>0),exists q,r,s.t.a=bq+r(0leq r<b)$ 中， $(a,b)=(b,r)$

證明：

記 $S_1$ 為a與b所有公因子組成的集合， $S_2$ 為b與r所有公因子組成的集合。

若 $din S_1, d|a,d|bRightarrow d|rRightarrow din S_2$

同理地， $din S_2, d|r,d|bRightarrow d|aRightarrow din S_1$

故 $S_1=S_2$ ，極大元相同， $(a,b)=(b,r)$

2、基於性質1，可以得到求最大公因數的Euclid演算法（輾轉相除法）。

$a=bq_1+r_1(0leq r_1<b)$

若 $r_1 e0$ ， $b=r_1q_2+r_2(0leq r_2<r_1)$

以此類推，直到 $r_{n-1}=r_nq_{n+1}$ 終止，則 $r_n=(a,b)$ 。

3、 $(a,b)$ 為a與b的公因數（雖然簡單但是很常用）

三、最小公倍數（lcm）

定義：

$[a_1,a_2,...,a_n]=minleft { m:a_1|m,a_2|m,...,a_n|m ight }$

那麼問題是，最大公因數與最小公倍數與兩個數之間有什麼聯繫呢？

定理： $(a,b)[a,b]=ab$

$M=[a,b],exists k, M=ak$

$d=(a,b),a_1=frac{a}{d},b_1=frac{b}{d}Rightarrow frac{ak}{b}=frac{a_1k}{b_1}in mathbb{N}$

又 $(a_1,b_1)=(frac{a}{(a,b)},frac{b}{(a,b)})=1$ （此性質會在習題中證明）

$b_1|a_1kRightarrow b_1|kRightarrow exists t, k=b_1tRightarrow frac{ak}{b}=a_1tRightarrow M=a_1bt$

而 $M=frac{ab}{(a,b)}t$ ，M為a與b的公倍數

而當 $t=1$ 時，M即為所有公倍數中最小的，為最小公倍數，故得證。

這個定理雖然簡短，但是卻告訴了我們gcd與lcm之間深刻的內在聯繫。（在講到算數基本定理時，我們會有辦法更簡單地重新審視這個定理）

四、連分數的簡要探討

定義：

$ain mathbb{R}, q_1$ 為小於 $a$ 的最大整數

則 $0<a-q_1<1,a=q_1+frac{1}{a_2}(a_2>1)$

同樣地 $a_2$ 不為整數時， $a_2=q_2+frac{1}{a_3}(a_3>1)$

以此類推， $a$ 可以寫成 $a=q_1+frac{1}{q_2+frac{1}{q_3+...}}$ 的連分數形式。 $(forall i,q_iin mathbb{Z})$

當 $a_nin mathbb{Z}$ 時過程終止。

容易發現的是，當一個數的連分數表達式有限，即 $a=q_1+frac{1}{q_2+frac{1}{q_3+...+frac{1}{q_n}}}$ 時， $ain mathbb{Q}$ 。問題是：逆命題是否成立呢？答案是肯定的。我們可以利用上文提及的Euclid演算法給出證明。

定理： $ain mathbb{Q}Leftrightarrow exists q_n,s.t. a=q_1+frac{1}{q_2+frac{1}{q_3+...+frac{1}{q_n}}}$

證明：（僅證 $Rightarrow$ ）

$alpha=frac{a}{b}$ 不妨設 $a>b$ ，由Euclid演算法， $a=bq_1+r_2(0 leq r_2<b)$ ，故 $frac{a}{b}=q_1+frac{r_2}{b}(0 leq frac{r_2}{b}<1)$

同理地， $frac{b}{r_2}=q_2+frac{r_3}{r_2}(0 leq frac{r_3}{r_2}<1)$

則 $frac{a}{b}=q_1+frac{1}{q_2+frac{r_3}{r_2}}$

以此類推，由於Euclid演算法總會在有限步終止，故 $alpha$ 的連分數表達式有限。

特別地，任何一個正數都能寫成連分數形式，故都對應著唯一的一串自然數。有理數對應的自然數串是有限的，無理數對應的自然數串則是無限的。

例： $frac{105}{38}=2+frac{1}{1+frac{1}{3+frac{1}{4+frac{1}{2}}}}$

對應著自然數串 $left langle 2,1,3,4,2 ight angle$ （事實上就是Euclid演算法中每一步得到的商）

五、素數

定義：

若一個數恰好有兩個正整數因子，則為素數。

素數的性質：

1、一個大於1的正整數的大於1的最小因子為素數。（反證，證略）

這條性質看上去十分簡單，然而在之後構造素數進行證明時十分常用。

2、若 $n$ 為合數， $d$ 為其大於1的最小因子，則 $d leq sqrt{n}$ 。（注意到 $frac{n}{d}$ 為小於 $n$ 的最大因子，證略）

接下來，我們給出一個重要的定理：素數是有無窮多個的。（這裡僅用初等方法證明，類似的方法可用來證明有無窮多個 $4n+3$ 與 $6n+5$ 型素數，之後會用黎曼 $zeta$ 函數另給出一個證明）

定理：存在無窮多個素數

證明：

$forall p_1,p_2,...,p_n$ 均為素數，則僅需證明能夠利用這些素數構造出一個新的素數，即可無限多次進行這個過程，從而得到無窮多個素數。

$N=p_1p_2...p_n+1$ ，由性質1，取 $p$ 為 $N$ 的大於1的最小因子，則 $p$ 為素數。

若 $exists i, s.t. p=p_i$ ，由 $p|NRightarrow p_i|NRightarrow p_i|p_1p_2...p_n+1Rightarrow p_i|1$ ，矛盾。

故 $p$ 為新構造出的異於所有 $p_i$ 的素數，得證。

六、算數基本定理

下設 $p,q$ 為素數

先給出兩個關於素數性質的命題

命題1、 $forall a,p, p|a or (p,a)=1$ （證略）

命題2、若 $p|a_1a_2...a_nRightarrow exists a_i, p|a_i$

證明：

反證。若 $forall 1leq i leq n,p$ 不整除 $a_i$ $Rightarrow forall 1leq i leq n,(p,a_i)=1$

則 $(p,a_1a_2...a_n)=1$ （習題中證明此結論），矛盾。

上述兩個命題都向我們展示了素數的不可分性，而這恰恰是算數基本定理成立的基礎。

下面用數學歸納法給出非常重要的算數基本定理的簡略證明。

定理（算數基本定理）：任意一個大於1的正整數都能表示成 $a=p_1^{alpha_1}p_2^{alpha_2}...p_k^{alpha_k}(alpha_1,alpha_2,...,alpha_k>0)$ 的形式，其中 $p_1<p_2<...<p_k$ 均為素數，且這種表示方法是唯一的。

證明：

存在性：

若對於 $b_1>1$ ， $forall bin[1,b_1]$ 能進行上述表示， $a=b_1+1,p$ 為 $a$ 的大於1的最小因子。則 $p$ 為素數，且 $1leq frac{a}{p} leq b_1$

若 $frac{a}{p}=1$ ，結論顯然成立。

若 $frac{a}{p}>1$ ， $frac{a}{p}=p_1^{alpha_1}p_2^{alpha_2}...p_k^{alpha_k}$ ，則 $a=pp_1^{alpha_1}p_2^{alpha_2}...p_k^{alpha_k}$ 可以被表示。

唯一性：

若 $a=p_1^{alpha_1}p_2^{alpha_2}...p_k^{alpha_k}=q_1^{eta_1}q_2^{eta_2}...q_l^{eta_l}$

記 $alpha=alpha_1+...+alpha_k$ ，對 $alpha$ 歸納。

若結論對 $alpha<A$ 成立，當 $alpha=A$ 時，

$p_1|q_1^{eta_1}q_2^{eta_2}...q_l^{eta_l}$ $Rightarrow exists 1leq s leq l, p_1|q_s$

則 $frac{a}{p_1}=p_1^{alpha_1-1}p_2^{alpha_2}...p_k^{alpha_k}=q_1^{eta_1}q_2^{eta_2}...q_s^{eta_s-1}...q_l^{eta_l}$

由歸納假設， $frac{a}{p_1}$ 表達式唯一 $Rightarrow a$ 表達式唯一。

算數基本定理告訴我們可以將任何一個整數看作素數的乘積，而得以運用素數的一些優良性質。有了算數基本定理，我們也得以再一次審視整除、最大公因數、最小公倍數等基本概念。

推論：給定 $a,b>1$ ，則有 $egin{cases} a=p_1^{alpha_1}p_2^{alpha_2}...p_k^{alpha_k} \ b=p_1^{eta_1}p_2^{eta_2}...p_k^{eta_k} end{cases} (alpha_1,...,alpha_k,eta1,...,eta_k geq 0)$ ，其中 $p_1<p_2<...<p_k$ 均為素數，則有 $egin{cases} (a,b)=p_1^{minleft {alpha_1 ,eta_1 ight }}p_2^{minleft {alpha_2 ,eta_2 ight }}...p_k^{minleft {alpha_k ,eta_k ight }}\ [a,b]=p_1^{maxleft {alpha_1 ,eta_1 ight }}p_2^{maxleft {alpha_2 ,eta_2 ight }}...p_k^{maxleft {alpha_k ,eta_k ight }}\ b|aLeftrightarrow forall 1 leq i leq n, 0leq eta_i leq alpha_i end{cases}$ ，且 $a$ 有 $(1+alpha_1)(1+alpha_2)...(1+alpha_k)$ 個不同正因子。