初等數論/同餘

维基教科书,自由的教学读本

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


同餘的定義在第一章已經說明了,即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时为除式,用數學歸納法证明余式。

階乘冪[编辑]

由組合數為整數可得。

習題[编辑]

第一部份─基礎題[编辑]

第二部份─進階題[编辑]