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