因數與倍數

要知道符號是數學上幫助我們能簡明表達事情的必要工具, ... 討論一些整數之間的關係時公因數和最大公因數以及公倍數和最小公倍數是很重要的工具. 下一頁:除法原理 上一頁:整數的基本性質 前一頁:整數的基本性質 因數與倍數 首先我們介紹幾個符號順便複習一下集合的概念. 要知道符號是數學上幫助我們能簡明表達事情的必要工具, 大家應該要學習如何適切的使用符號. 在本講義中我們用 來表示所有整數所成的集合.所以0在 中,2也在 中,2007和-365也在 中. 這樣一來當我們要說一個數a是整數時,我們只要說a在 中就好了.在數學上我們要說一個東西在一個集合中就用``"這個符號, 也就是``屬於"的意思.所以以後我們要表達a是一個整數就直接說 a即可.我們也常只考慮正整數,在本講義中我們用 表示所有正整數所成的集合.所以我們用 a來表示a 是一個正整數. 對於整數一開始是由自然數出發，利用數數的方法我們定義了加法，接著有了負的概念整個整數加法的體系就建立起來了。

給定 a,我們用2a表示.a+a一般來說若 n我們將 n個a相加的結果表為na.我們也將(-n)a看成n個-a 相加所得之值.若我們再將0a定為0,如此一來對任意的 m, ma都有了定義. 如此定義出來的乘法和加法之間所滿足的運算規則如交換率, 結合率和分配率等此處就不再贅述.我們將可以寫成ma其中 m 的數稱為a的倍數(multiple).另一方面若b是a的倍數, 我們也稱a是b的因數(divisor).符號記為a|b. 我們將a的倍數所成的集合用 a來表示.也就是說 a 中的元素都是ma這樣的形式其中 m.這樣的集合可用 a={ma|m}來表示.因此我們可以說 ba和b 是a的倍數(或a是b的因數)是一樣的意思. 接下來我們想用集合的角度處理因數倍數的一些性質. 要注意這些性質大家高中時都已證過, 我們用集合的角度處理並沒有比較方便，介紹這樣的處理方法僅是利用它讓大家熟悉一下集合的語言. 首先注意若 a, a這一個集合並不單單是一個集合. 由於整數在加法和乘法之下有所謂的封閉性, a 也有以下兩個重要的封閉性. Proposition1.1.1  假設 a且 b,ca.則我們有以下之性質. b+ca. 對任意 m皆有 mba. 証明. 因為 b,ca依定義知存在 n,n'使得b=na且c=n'a. (1)由分配率知 b+c=na+n'a=(n+n')a.又由於 n,n'我們知 n+n',故得 b+ca. (2)由結合率知 mb=m(na)=(mn)a.又由於 m,n我們知 mn,故得 mba. 結合Proposition1.1.1的結果我們有以下之性質. Corollary1.1.2  假設 a且 b,ca.若 m,n則 mb+nca. 換言之,若a|b且a|c,則對任意 m,n皆有a|mb+nc. 証明. 因為 b,ca以及 m,n,由Proposition1.1.1(2) 知 mb,nca.再利用Proposition1.1.1(1)知 mb+nca.也就是說a|mb+nc. 大部分一個重要的性質我們都會用Proposition 來稱呼再冠上編號以便以後引用.而直接套用Proposition 所得的性質我們都用Corollary來稱呼. 接著我們來看集合單純的性質.若A,B是集合且A中的元素都在B 中,則我們就用 AB來表示(稱A包含於B). 很容易有以下之性質: 若 AB且 BA則A=B. 若 AB且 BC則 AC. 結合這集合的性質以及前面提的封閉性我們有以下之結果. Proposition1.1.3  假設 a,b,c.我們有以下之結果. ba若且唯若a|b. 若a|b且b|a則a=±b. 若a|b且b|c則a|c. 証明. (1)若 ba,由於 bb,我們得 ba. 故知a|b.反之,若a|b,我們要證明 ba. 一般來說要證明一個集合B包含於另一個集合A,我們要證明的是B 中任取一個元素都會在A中.因此此處我們要證的是任取 b 中的一個元素mb,其中 m都可以得到 mba.然而由 a|b的假設我們知 ba.接著我們就可利用Proposition 1.1.1(2)知對任意 m皆有 mba.也就是說 b的元素都在 a中.故得證 ba. (2)若a|b且b|a,由(1)知 ba且 ab.因此由集合性質知 a=b.也就是說 a 和 b是相同的集合.由此,很容易看出當a=0時b=0.反之亦然. 因此我們只剩考慮a0且b0的情況.此時 a 中最小的正數a(當a>0)或-a(當a<0)會等於 b 中最小的正數b或-b.故得證a=±b. (3)若a|b且b|c,則由(1)知 ba且 cb.因此由集合性質知 ca.故再由 (1)的等價關係知a|c. Remark1.1.4  對於整數有一個很重要的性質``well-orderingprinciple''.這一個 principle就是說給定一個非空的整數的子集合S,如果S有下界( 若有一數小於S中所有的數,則稱S有下界),則S 中必含有一個最小的整數(通常用minS來表示). 同理若整數的非空子集合S有上界(若有一數大於S中所有的數,則稱 S有上界),則此集合中必含有一個最大的整數(通常用maxS 來表示).例如剛才Proposition1.1.3(2)的證明中我們考慮 a 中最小的正整數,當a>0時a就是 a中最小的正整數. 這裡因為我們確實知道 a這個集合長什麼樣, 所以並不需這個性質直接可知a就是最小的. 以後我們常會碰到一些抽象的正整數子集合, 那時就得經常用到整數的這個性質來確知此集合存在一個最小的正數. 另外要注意此性質在其他的情況如有理數就不對了. 事實上正有理數是有下界的(0小於所有的正有理數), 但並沒有所謂最小的正有理數. 再次強調一下前面我們用集合較抽象的方法證明整除的性質主要是要大家習慣集合的語言以及學習一些抽象的論證方法. 它並不是什麼特別的好方法.比方說大家熟知的a|b則ma|mb 就很難用類似上面集合的方法來處理.總之, 要處裡一個問題並沒有說一定要用什麼方法. 你只要使用一個你認為可行且正確的方法處理. 所以學習數學絕不要僅是背誦定理的證明. 如何將繁瑣的證明整理成你自己習慣且能理解的語言才是重點. 接下來我們就回歸定義來證明前述之性質. Lemma1.1.5  假設 a,b且a|b,我們有以下之性質. 若 m,則ma|mb. 若d|a且d|b,則 (a/d)|(b/d). 証明. 由假設a|b知存在 n使得b=na. (1)將等式兩邊同乘以m可得 mb=mna=n(ma)故知ma|mb. (2)d|a且d|b即表示存在 a',b'使得a=a'd且b=b'd. 故由b=na得b'd=na'd.因為d0,兩邊同除以d可得 b'=na',即a'|b'.因為a/d=a'且b/d=b'故得證 (a/d)|(b/d). Lemma1.1.5是一個簡單的性質.它本身並不算什麼重大的性質, 但是以後討論許多性質時都要用到它,我們便用Lemma稱呼之以方便引用. 在Lemma1.1.5(2)中d|a且d|b的假設就是說d同時是a 和b的因數,我們簡稱之為a,b的公因數. 討論一些整數之間的關係時公因數和最大公因數以及公倍數和最小公倍數是很重要的工具. 接下來我們是給它們下一個定義. Definition1.1.6  令 a1,a2,...,an. 若 c,且 c|a1, c|a2,..., c|an,則稱c為 a1,a2,...,an的 公因數(commondivisor). 若 d是 a1,a2,...,an的公因數中最大的,則稱d為 a1,a2,...,an的最大公因數greatestcommon divisor,通常我們會用 gcd(a1,a2,...,an)來表示之. 若 m,且 a1|m, a2|m,..., an|m,則稱m為 a1,a2,...,an的 公倍數(commonmultiple). 若 l是 a1,a2,...,an的正的公倍數中最小的,則稱l為 a1,a2,...,an的最小公倍數leastcommon divisor,通常我們會用 lcm(a1,a2,...,an)來表示之. 通常當有一個符號或名詞需要介紹時,為了方便找到我們會特別用 Definition來標示之. 當要下一個定義時要注意是否合理. 不要給的定義的東西根本不存在或沒有用.Definition1.1.6 中就要注意最大公因數及最小公倍數是否存在:因為1整除所有的整數, 所以若 a1,a2,...,an則其公因數必存在.又因為 a1,a2,...,an有有限多個公因數,所以我們知 a1,a2,...,an 的最大公因數必存在.不過 a1,a2,...,an的最大公因數有可能是 1.若如此(即 gcd(a1,a2,...,an)=1),則稱 a1,a2,...,an互質(relativelyprime).另一方面因為 a1a2...an是 a1,a2,...,an的公倍數, 所以適當的乘上正負號可知 a1,a2,...,an正的公倍數必存在, 因此由well-orderingprinciple知 a1,a2,...,an 的最小公倍數必存在. 下一節我們將會談論最大公因數及最小公倍數的一些基本性質. 下一頁:除法原理 上一頁:整數的基本性質 前一頁:整數的基本性質 Li 2007-06-28