数论 > 初等数论 > 初等數論/同餘
同餘的定義在第一章已經說明了,即a
當m|a-b時,數論中很多定理和證明用一般帶餘數除法的表示法也能做得出來,但是這些定理和證明若用同餘式表示往往更加地簡便明瞭
由同餘的定義和基本的算術運算法則,可推出:
- 若
且
,則有
,和
,但是反過來時不一定成立
- 若
且
,則![{\displaystyle a\equiv b{\pmod {m/|n|}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a92dacd3a97230441545570d59bb231ea04296fe)
- 若
則存在整數C,使得![{\displaystyle Ca=1{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/021429d68d60d4d97dd0e78b8fdcc86307a3c67d)
同餘類:對於模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,:![{\displaystyle \phi (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52ddd8905bfc0ea59762651f0d18b1ec147006c2)
=
,即
函數為一積性函數
例子:
=![{\displaystyle \phi (4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e5be571730352f6cc7d44ea313ad8706f8704ae)
=12
除了
=
外,對其他的
,都有
另一方面,若設m的一個簡化剩餘系為
,其中對於任何
有
,而這個簡化剩餘系的元素有k個,則
費馬小定理:對於任意正整數a,及任意質數p,有以下關係式:
其中對任意使(a,p)=1的a,有以下關係式:
歐拉定理:對於任意的
,存在有以下的關係式:
並且
中的數兩兩不同餘
利用簡化剩餘系證明歐拉定理 設 ![{\displaystyle \{r_{1},r_{2},\dots ,r_{\phi (m)}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/066773bbdb4f558dad5ec226e53bde3e5e734d56) 為模m的簡化剩餘系
由於 , 也是模m的簡化剩餘系
![{\displaystyle (ar_{1})(ar_{2})\dots (ar_{\phi (m)})\equiv r_{1}r_{2}\dots r_{\phi (m)}{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a3aa64e6d5e4e5d5ad58180d13d8cf7372f0099)
![{\displaystyle a^{\phi (m)}(r_{1}r_{2}\dots r_{\phi (m)})\equiv r_{1}r_{2}\dots r_{\phi (m)}{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45f6c0f2fa162ad8eb7f690da7ceebe8e609a6e9)
又 ,得
|
卡邁克爾函數
满足
,其中a與n互質。
当n为2、4、奇質数的指數、奇質數的指數的兩倍时为歐拉函數,當n为2,4以外的2的指數時为它的一半。
歐拉函數有
由算術基本定理,正整數n可寫為質數的積
對於所有n,
是它們的最小公倍數:
證明當a与n互質時, ![{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e475506bcb72caae57599e0ccafa7efe023be9c) 由費馬小定理得
由數學歸納法得 成立,這是一般情況。
由數學歸納法得當 時, 成立。
|
威爾逊定理:對於所有質數
,都有
,且若此式成立,p為質數
證明威爾逊定理
如果p不是質數,它的正因數必然包含在 中,因此![{\displaystyle ((p-1)!,p)\neq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f72f57cc5299753da28782adfdf3e73cada38f2)
,與 矛盾。
所以 成立時p一定是質數。
若p是質數, 是模p的剩餘系
![{\displaystyle \forall i\in A,\exists j\in A,~s.t.~ij\equiv 1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10f4494f944fed876be3e614d949fa8d890789a2)
當 時,![{\displaystyle i^{2}\ \equiv \ 1{\pmod {p}}\Rightarrow i\equiv \pm 1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b5c577b9b01722c33338ae15f05b8da51c4b6e5)
其餘 兩兩配對
|
除式:
餘式:
n=0时为除式,用數學歸納法证明余式。
由組合數為整數可得。
![](//upload.wikimedia.org/wikipedia/commons/thumb/9/91/Book_important2.svg/45px-Book_important2.svg.png) |
此讀本或頁面內容似未齊全,宜加改進。 当內容獲充分扩展后,请移除本模板。如需要協助,请至互助客棧。
|