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