数论 > 初等数论 > 初等數論/同餘
同餘的定義在第一章已經說明了,即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时为除式,用數學歸納法证明余式。
由組合數為整數可得。
|
此讀本或頁面內容似未齊全,宜加改進。 当內容獲充分扩展后,请移除本模板。如需要協助,请至互助客棧。
|