初等數論/整數的基本性質

数论 > 初等数论 > 初等數論/整數的基本性質


數論是奠基於算術之上的,所以在學習數論之前,要先知道以下關於整數的性質:

整數集合

编辑

整數集合,即所有的整數,像0,1,-1,2,-2,......這一些整數形成的集合,就叫整數集合,或以 表示,自然數 為其子集,但奇怪的是,整數集合和正整數集合內部的元素數量竟相等


整數集合的性質符合環的性質,意即其加減乘法皆自封(若對一種定義在X上的運算Y,當a和b皆為X的元素時,aYb亦為X的元素,則稱運算Y自封),以下將說明整數集合的性質

數學歸納法

编辑

若有一個命題 ,若能證明  或其他給定的起始正整數 成立,且在假設對一個正整數 (或前面給定的正整數 ),命題 成立時,亦能證明 時命題 成立,則命題 對所有  皆成立,除了本法以外,尚有第二種數學歸納法,第二種數學歸納法將在稍後說明

加法篇

编辑

加法使用符號+,  ,或稱  相加可記為 

整數集合的加法(和減法)是封閉的(若 裡面的元素透過一個定義在 上的運算,所得的結果的元素依然存在於 ,且對所有 的元素都是如此,那麼這個二元運算就是在 上封閉的),以下為加法(和減法)的性質:

  • 加法有結合律,即對於任意整數 , ,  
  • 加法有交換律,即對於任意整數 ,  
  • 加法有相消律,即對於任意整數 , , ,若 ,則可推出 
  • 減法,若對整數 , ,c有 ,則亦可記做 ,但是減法無交換律
  • 在整數中有一個元素0,使得對任意整數   

乘法篇

编辑

乘法使用符號‧,  ,或稱  相乘可記為 ,但是若  至少有一個為未知數 ,則乘號‧可省略(但若  皆為已知數,且皆以數字(非英文字母)表示,則乘號「‧」不可省略

整數集合的乘法也是封閉的,以下為它的性質:

  • 乘法有結合律,即對於任意整數 , ,  
  • 乘法有交換律,即對於任意整數 ,  
  • 乘法有相消律,即對於任意整數 , , ,若 ,則可推出  (a不能為零)
  • 在整數中有一元素1,使得對任意整數  
  • 任意整數 和0相乘為0

大小關係

编辑

整數集合是一個有序集合,以下為整數中的序的關係(即一般所說的大小關係)

  •  ,則必有正整數 ,使 
  •  ,且 ,則 
  •  ,且 , 為正整數,則必有正整數 ,使得 
  •   ,則 
  • 對於任意整數 ,有 
  • 對於兩個整數    有且僅有一個成立

最大自然數原理與最小自然數原理

编辑
  • 最小自然數原理:對於任意自然數的非空子集 ,存在一元素 ,使得任意的 ,都有 

事實上,對於任意有下界的非空集合 ,若 為整數集合Z的一個子集,則在 中必存在一最小的數n,使得任意的 ,都有 

  • 最大自然數原理:對於任意有上界的非空子集 ,存在一元素 ,使得任意的 ,都有 


除法篇

编辑

除法使用符號 ,若 除以 ,或  ,記做 

  •  可被 整除,則記做 ,或 
  • 若不能整除,即會剩餘某數 ,則記做 
  •  不能整除 ,但是能找得到一數,使 ,則此 , , 可記做 ( ),後者亦可稱 除以 同餘於 

其他的一些名詞的定義

编辑
  • 因數:若 成立,則  的因數
  • 倍數:若 ,則  的倍數
  • 質數:若一個大於1的正數 的正因數只有1, ,則稱這個數 為質數

第二種數學歸納法

编辑

雖然比起前面所說的數學歸納法,第二種數學歸納法比較少用,但是第二種數學歸納法仍然為重要的證明方法,茲將之說明如下: 若對一個命題 ,在 (或指定的正整數 )時成立,在假設對所有符合 的正整數都成立時,能證明  亦成立,則 對所有正整數(或正整數集合 )都成立

第二種數學歸納法可以用最小自然數原理和反證法證明其為真

算術基本定理

编辑

任意大於1的正整數都能唯一地表示成由指定數量的特定質數的乘積

標準分解式

编辑

根據算術基本定理,任意正整數皆可表為唯一的若干个正质数的乘積,且因為這些質數沒有次序上的問題,因此,可將相同的質數寫成該質數的冪方也是沒問題的,意即上面的a可改寫為: a= 

算術基本定理的證明

编辑

先證明幾個引理:

  • 引理1:每個大於一的數都可以表示成質數的乘積,或本身為質數

引理1證明:用第二種數學歸納來證明,設正整數 時,2為質數,故成立,再假設當 時此引理成立,則當 時,若 為質數,則引理成立,若 不為質數時, 為合數,因此 ,其中 ,因而由假設知  可表為質數的乘積,因而 亦可表為質數的乘積,因此引理亦對 成立,因此由數學歸納法得知,此引理對所有的正整數 成立

  • 引理2:若 ,且 是質數,則p|a或p|b至少有一個成立,另一方面,若 是質數,且若 成立,則   、...... 至少有一成立

引理2證明:

  • 由引理2引出的引理3:若 皆為質數,且 則至少有一個 使 

引理3證明:

算術基本定理證明:存在性由引理1可得知,現在來證唯一性:設有一數n,它的分解式為 ,其中 皆為質數,再設n存在另一個分解式 ,設 ,且 亦皆為質數,而且  ,則很明顯地有 ,由引理3知,必有一些  相等,且可推知這個關係是唯一的,因此現在將和 相等的數設為 ,其他的也照做,意即  、‧‧‧、 ,而剩下來的則記為 ,則由此及 可推出 意即此兩個分解式之中所有的質數相等,與原假設矛盾,故n的分解式為唯一的

最大公因數與最小公倍數

编辑

最大公因數

编辑

假若對兩個整數 ,有一整數 ,使  ,則稱   公因數,若在  的公因數所形成的集合中, 是為其中最大的數字,則稱這個   最大公因數,或記做 ,若 ,則稱  互質

最小公倍數

编辑

若有整數 ,使得  ,則稱   公倍數,若在  所有的正公倍數所形成的集合中, 是其中最小的數字,則稱   最小公倍數,或記做 ,且若 ,則 


最大公因數和最小公倍數的性質

编辑
  • 最大公因數:
    •  
    •   ,且在此 為任意整數, 為任意正整數
    •   ,且在此 為任意整數, 為任意正整數

輾轉相除法

编辑

對於兩個數  ,有以下算法:

我们可以 表示 的公约数则 并且 
所以 并且   
也就是说当 时,  的最大公约数和  相等。于是我们有:

 

 

......

 

其中( , )=( , )=......=( , )

習題

编辑

第一部份─基礎題

编辑

第二部份─進階題

编辑