數論是一門研究整數的學科。
我們來對初等數論作一個簡單的入門。
我們先來介紹整除。
定義1 如果存在整數c使得 a=bc，那么我們稱b整除a,記作b|a。我們把b叫做a的因數，a叫做b的倍數。
引理1 整除具有如下性質：
1.(反身性) a|a
證：a=1*a，故a|a。
2.(傳遞性) 如果a|b,b|c,那么a|c
證：由定義，設b=am，c=bn，則c=(mn)a。故c|a
3.(反對稱性) 若a|b，b|a,那么a=b
證：設b=am，a=bn=amn顯然mn=1即m=n=1，a=b
4.(線性性)如果a|b,a|c，則a|mb+nc
證：設b=ak，c=al，那么mb+nc=(mk+nl)a。故a|mb+nc
5.ab|c，則a|c，b|c
證：設c=(ma)b=(mb)a，故a|c,b|c。
6.若a|b，則a|bc
證：b=am，bc=(mc)a，故a|bc
定義2 一個正整數p>1，如果它除了1和p以外，沒有別的因數，我們就稱這個p叫做素數。否則這個p>1稱為合數。
例1 2,3,5,7,11,13都是素數。4,6,8,9,10,12,14,15都是合數。1既不是素數也不是合數。
定義3 如果對于a，b，存在一個d,使得d|a,d|b,我們就稱d是a與b的公因數。如果這個d是所有公因數中最大的，我們就稱這個d叫做a與b的最大公因數，記作(a,b)。
定義4 如果(a,b)=1，那么我們稱a與b互質（互素）。或者稱a與b既約。
例2 (3,15)=3,(7,3)=1,即7與3互質，而3與15不互質。
例3 若(a,b)=1,c|a,d|b,那么(c,d)=1 證:如果不是，設(c,d)=D>1.那么 D|c,c|a故D|a,D|d,d|b故D|b,故D為a,b的公因數但不一定是最大公因數，那么(a,b)≥D>1，而這與(a,b)=1矛盾。所以(c,d)=1。
這說明了互質的數的約數也是互質的。
引理2 任何一個自然數n>1，一定可以寫成素數的乘積。(單獨一個素數也視為素數的乘積。)
證：如果命題是錯的，設最小的使命題不成立的n>1為N，那么N一定不是素數，因此N是合數，我們設N=kl,其中N>k>1,N>l>1，由于N是使命題不成立的最小數，那么k和l一定能寫成素數之積，這是一個矛盾。
定理1（算術基本定理）：如果不計素因數的順序，那么引理2中的素因數分解式是唯一的。
這個定理并不像它看起來那么容易證明，我們必須先證明一些其他引理。
欲知后事如何，請聽下回分解。
-----------------------------------------------
上一節里我們向大家介紹了整除性與素數，這里我們將利用整除，建立更多的基本理論，來更深入地探討初等數論。本節的主題是：最大公因數理論、帶余數除法、算術基本定理。
符號聲明：本文中如未聲明，字母總表示整數。p總表示素數。由于在這里打字不能打出公式，我們約定p1,p2,p3…,pk以及q1,q2……總表示編了號的數字，而不是p乘以什么。p乘以k我們總寫成kp而不是pk。
證明算術基本定理的關鍵步驟在于下面這兩個引理：
引理3 如果素數p|ab，那么p|a或p|b至少有一個成立。
有時候這被稱為算術基本引理。但我們之前建立的理論還不足以直接證明它。
引理4 (帶余數除法) 對于任意的整數a和b≠0，存在唯一的整數q,r使得 a = bq + r。其中0≤r＜b。這里r叫做最小非負剩余。
證：
考慮形如a-xb的所有非負整數，其中x為整數。在這些非負整數中，我們把最小的記為r。我們一定有r<b。否則，r≥b，那么r-b也是形如a-xb的非負整數，這與r的最小性矛盾。因此我們有a-xb=r，(0≤r＜b)，即a=bx+r,(0≤r＜b)
為了進一步說明整除的一些深刻性質，我們暫時引進一個新記號，記所有形如ax+by的整數集合為T。(a和b不同時為0。x,y是整數)
引理5 對任意c,d∈T，我們有mc+nd∈T。其中m,n都是整數。
證：由T的定義，設c=ax+by,d=aX+bY,那么mc+nd=(mx+nX)a+(my+nY)b，其中mx+nX，my+nY都是整數。
引理6 存在這樣一個正整數d∈T，對任意的n∈T都有d|n。
證：考慮Q中的最小正整數d，我們來證明Q中所有元素都被d整除。否則，存在這樣一個s∈T，且d不整除s。根據引理4，一定存在唯一的q,r使s=dq+r,0＜r＜d。根據引理5，r=s-dq∈T，這與d是T中的最小正整數矛盾。
引理7 T中的最小正整數d=(a,b)
證：由于a,b∈T，根據引理6我們有d|a，d|b。這說明d是a,b的公因數但不一定是最大的。我們有d≤(a,b)。
設d=ax+by,我們有(a,b)|a，(a,b)|b，故(a,b)|ax+by=d，這說明了(a,b)≤d。所以d=(a,b)
引理8 如果s|a,s|b那么s|(a,b)。即公因數一定是最大公因數的因數。
證：由引理7知可設(a,b)=ax+by，那么s|a,s|b可得s|ax+by=(a,b)。
引理9 如果(a,b)=1，且a|bc那么a|c。
證：設ax+by=1，那么acx+bcy=c，由于a|acx，a|bcy故a|c
引理3的證明
證：設p|ab，且p不整除b，設(p,b)=d，我們來證明d=1。否則設d>1,d|p,因為p是素數,d=p。由于d|b得p|b。矛盾。故(p,b)=1，
由引理9得p|a。
引理10 設p|abcd…，那么p|a，p|b,…至少有一個成立。
證：這可由引理3立刻推得。
現在我們已經有足夠的能力證明：
定理1（算術基本定理）：如果不計素因數的順序，那么自然數n>1的素因數分解式是唯一的。
證：設n=p1 p2 p3 … pm （這里pm表示某個素因數，不是p乘以m）
n=q1 q2 q3 … qk 是n的兩個素因數分解式。我們來證明：k=l，而且這兩種分解式其實是相同的。
由于p1 p2 p3 … pm = q1 q2 q3 … qk
顯然p1|q1 q2 q3 … qk，由引理10得p1一定整除右邊那些素數中的某一個。由于右邊的都是素數，所以在右邊一定存在某一個素數與p1相等。不妨設這個素數是q1，那么約去它們，得到：
p2 p3 … pm = q2 q3 … qk
用相同的辦法，約來約去，最后某一邊只剩下數字1，不妨設m≥k,那么左邊只剩下1。
1 = q(m+1) q(m+2) … qk （這里q(m+1),q(m+2),qk都表示某個素因數，不是q乘以(m+1)。）
而右邊的都是素數，素數必須大于1，所以只有一種可能性：k=m。上式成為：1=1
由于我們在約去時，每次兩邊都約去了相同的素數，故每個素因數在兩邊出現的次數都是相同的。因此，自然數n>1素因數分解式是唯一的。
通過收集相同的素數，我們有n=p1^a1 * p2^a2 * … * pk^ak ，且p1<p2<…<pk，這個式子叫做n的標準分解式。
最主要的定理我們已經證明完成，接下來我們將向大家介紹最大公因數理論的一些更有趣的部分。
定義4 如果a|L,b|L,我們就稱L是a,b的公倍數。如果這個L是最小的，而且L>0，我們就稱L是a,b的最小公倍數，記作[a,b]
引理11 我們有(ma,mb)=m(a,b)
證：設D=(ma,mb),d=(a,b)=ax+by，那么md=max+mby,D|ma,D|mb得D|md。d|a,d|b得md|ma,md|mb,故md|D。因此D=md。
引理12 (a,b)=1，那么(c,ab)=(c,a)(c,b)
證明在最下面。
引理13 我們有(a,b)[a,b]=ab
證法一：設ord(p,n)表示p^k|n但p^(k+1)不整除n中的k。例如ord(2,12)=2，ord(2,7)=0。
我們用min{i,j}表示i,j中的最小值。max{i,j}意義與此相反。
那么我們顯然有ord(p,ab)=ord(p,a)+ord(p,b),
ord(p,(a,b))=min{ord(p,a),ord(p,b)}，ord(p,[a,b])=max{ord(p,a),ord(p,b)}
那么我們只要證明min{i,j}+max{i,j}=i+j即可。但這是顯然的，無需證明。
證法二：……由你來補充。
引理14 如果(a,b)=1，a|c,b|c,則ab|c.
證明在最下面。
時間不夠，暫時先寫到這里吧。
給你來點練習題：
1.給出證明引理13的另一種方法。
2.若(a,b)=1，則(a+b,a-b) = 1 或 2.
3.若(a,b)=1，d|(a+b)，則(a,d)=(b,d)=1.
4.請證明引理12.
5.請證明引理14.
做出來了把證法回復給我，我幫你批改作業。
下一課：http://www.zg4o1577.cn/bbs/dpj-52251-1.html
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
