数论 > 初等数论 > 初等數論/同餘


同餘的定義在第一章已經說明了,即a 當m|a-b時,數論中很多定理和證明用一般帶餘數除法的表示法也能做得出來,但是這些定理和證明若用同餘式表示往往更加地簡便明瞭

同餘的性質 编辑

由同餘的定義和基本的算術運算法則,可推出:

  •   ,則有 ,和 ,但是反過來時不一定成立
  •   ,則 
  •  則存在整數C,使得 

同餘類與剩餘系 编辑

同餘類:對於模m的元素,將所有對模m兩兩同餘的數取出,所形成的集合稱之為模m的同餘類,即若 ,則r和s屬於模m的同一個同餘類

剩餘系:對於模m的不同同餘類的元素,各取一個出來所形成的集合稱之為模m的剩餘系,即模m的一個剩餘系中的所有元素兩兩不同餘

多項式同餘 编辑

經典同餘恆等式 编辑

歐拉函數 编辑

 函數(又稱歐拉函數)是指小於等於n的自然數中與n互質的數的數目。 例子: =2,因為在1,2,3,4,5,6中只有1,5是和6互質

歐拉函數的特性 编辑

若正整數n個標準分解式為 ,則 函數的值為:

 

用邏輯集合的概念、排列組合及算術基本定理可驗證此式的成立

如果(m,n)=1,:  = ,即 函數為一積性函數

例子: =  =12

除了 = 外,對其他的 ,都有 

另一方面,若設m的一個簡化剩餘系為 ,其中對於任何  ,而這個簡化剩餘系的元素有k個,則 

費馬小定理 编辑

費馬小定理:對於任意正整數a,及任意質數p,有以下關係式:

 

其中對任意使(a,p)=1的a,有以下關係式:

 

歐拉定理 编辑

歐拉定理:對於任意的 ,存在有以下的關係式:

 

並且 中的數兩兩不同餘

利用簡化剩餘系證明歐拉定理
 為模m的簡化剩餘系

由於  也是模m的簡化剩餘系
 
 
 ,得 

卡邁克爾函數 编辑

卡邁克爾函數 满足 ,其中a與n互質。

当n为2、4、奇質数的指數、奇質數的指數的兩倍时为歐拉函數,當n为2,4以外的2的指數時为它的一半。  

歐拉函數有 

由算術基本定理,正整數n可寫為質數的積 

對於所有n, 是它們的最小公倍數:

 

證明當a与n互質時, 
由費馬小定理得 

 

 

由數學歸納法得 成立,這是一般情況。

 

 

 

 

由數學歸納法得當 時, 成立。

威爾逊定理 编辑

威爾逊定理:對於所有質數 ,都有 ,且若此式成立,p為質數

證明威爾逊定理

如果p不是質數,它的正因數必然包含在 中,因此 
 ,與 矛盾。
所以 成立時p一定是質數。

若p是質數, 是模p的剩餘系
 
 時, 
其餘 兩兩配對
 

費馬小定理餘式推廣 编辑

 

除式: 

餘式: 

n=0时为除式,用數學歸納法证明余式。

階乘冪 编辑

 

由組合數為整數可得。

習題 编辑

第一部份─基礎題 编辑

第二部份─進階題 编辑