初等數論/同餘

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

---

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

同餘的性質

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

• 若$a\equiv b(\mathrm{mod}m)$且$c\equiv d(\mathrm{mod}m)$，則有$a\pm c\equiv b\pm d(\mathrm{mod}m)$，和$ac\equiv bd(\mathrm{mod}m)$，但是反過來時不一定成立
• 若$na\equiv nb(\mathrm{mod}m)$且$n|m$，則$a\equiv b(\mathrm{mod}m/|n|)$
• 若$(a,m)=1$則存在整數C，使得$Ca=1(\mathrm{mod}m)$

同餘類與剩餘系

同餘類：對於模m的元素，將所有對模m兩兩同餘的數取出，所形成的集合稱之為模m的同餘類，即若$s\equiv r(\mathrm{mod}m)$，則r和s屬於模m的同一個同餘類

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

經典同餘恆等式

歐拉函數

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

歐拉函數的特性

若正整數n個標準分解式為$n=p_1^{q_1}{p}_2^{q_2}......p_k^{q_k}$，則$\varphi (n)$函數的值為：

$\varphi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})......(1-\frac{1}{p_k})$

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

如果(m,n)=1，：$\varphi (m)$$\varphi (n)$=$\varphi (mn)$，即$\varphi (n)$函數為一積性函數

例子：$\varphi (36)$=$\varphi (4)$$\varphi (9)$=12

除了$\varphi (1)$=$\varphi (2)=1$外，對其他的$\varphi (n)$，都有$2|\varphi (n)$

另一方面，若設m的一個簡化剩餘系為$\{r_1,r_2,\dots ,r_{\varphi (m)}\}$，其中對於任何$r_j$有$(r_j,m)=1$，而這個簡化剩餘系的元素有k個，則$\varphi (m)=k$

費馬小定理

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

$a^p\equiv a(\mathrm{mod}p)$

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

$a^{p-1}\equiv 1(\mathrm{mod}p)$

歐拉定理

歐拉定理：對於任意的$(a,m)=1$，存在有以下的關係式：

$a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$

並且$a,a^2,a^3,\dots ,a^{\varphi (m)}$中的數兩兩不同餘

Template:Robox設$\{r_1,r_2,\dots ,r_{\varphi (m)}\}$為模m的簡化剩餘系
由於$(a,m)=1$，$\{a{r}_1,a{r}_2,\dots ,a{r}_{\varphi (m)}\}$也是模m的簡化剩餘系
$(a{r}_1)(a{r}_2)\dots (a{r}_{\varphi (m)})\equiv r_1{r}_2\dots r_{\varphi (m)}(\mathrm{mod}m)$
$a^{\varphi (m)}(r_1{r}_2\dots r_{\varphi (m)})\equiv r_1{r}_2\dots r_{\varphi (m)}(\mathrm{mod}m)$
又$(r_1{r}_2\dots r_{\varphi (m)},m)=1$，得$a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$ Template:Robox/Close

卡邁克爾函數

卡邁克爾函數$\lambda (n)$满足$a^{\lambda (n)}\equiv 1(\mathrm{mod}n)$，其中a與n互質。

当n为2、4、奇質数的指數、奇質數的指數的兩倍时为歐拉函數，當n为2,4以外的2的指數時为它的一半。 $\lambda (n)=\{\begin{array}{cc}\phi (n)& n=2,3,4,5,6,7,9,10,11,13,14,17,19,22,23,25,26,27,29\dots \\ \frac{1}{2}\phi (n)& n=8,16,32,64,128,256\dots \end{array}$

歐拉函數有$\phi (p^k)=p^{k-1}(p-1)$

由算術基本定理，正整數n可寫為質數的積$n=p_1^{a_1}{p}_2^{a_2}\dots p_{\omega (n)}^{a_{\omega (n)}}$

對於所有n，$\lambda (n)$是它們的最小公倍數：

$\lambda (n)=\mathrm{lcm}[\lambda (p_1^{a_1}),\lambda (p_2^{a_2}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})]$

Template:Robox由費馬小定理得$a^{p-1}=1+hp$

$a^{p^{k-1}(p-1)}=1+h{p}^k$

$a^{p^k(p-1)}=(1+h{p}^k{)}^p=1+h^p{p}^{k+1}+\dots =1+h_0{p}^{k+1}$

由數學歸納法得$a^{p^{k-1}(p-1)}\equiv 1(\mathrm{mod}{p}^k)$成立，這是一般情況。

$a=1+2h$

$a^2=1+4h(h+1)=1+8C_{h+1}^2$

$a^{2^{k-2}}=1+2^{k}h$

$a^{2^{k-1}}=(1+2^{k}h{)}^2=1+2^{k+1}(h+2^{k-1}{h}^2)$

由數學歸納法得當$k\ge 3$時，$a^{2^{k-2}}\equiv 1(\mathrm{mod}{2}^k)$成立。 Template:Robox/Close

威爾逊定理

威爾逊定理：對於所有質數$p$，都有$p|(p-1)!+1$，且若此式成立，p為質數

Template:Robox 如果p不是質數，它的正因數必然包含在$1,2,3,4,\dots ,p-1$中，因此$((p-1)!,p)\ne 1$
$(p-1)!\equiv -1(\mathrm{mod}p)\Rightarrow \mathrm{\exists }k\in \mathbb{Z},s.t.(p-1)!+pk=-1$，與$((p-1)!,p)\ne 1$矛盾。
所以$(p-1)!\equiv -1(\mathrm{mod}p)$成立時p一定是質數。

若p是質數，$A=\{1,2,3,\dots ,p-1\}$是模p的剩餘系
$\mathrm{\forall }i\in A,\mathrm{\exists }j\in A,s.t.ij\equiv 1(\mathrm{mod}p)$
當$i=j$時，$i^2\equiv 1(\mathrm{mod}p)\Rightarrow i\equiv \pm 1(\mathrm{mod}p)$
其餘$\{2,3,\dots ,p-2\}$兩兩配對
$(p-1)!\equiv 1\times (p-1)\equiv -1(\mathrm{mod}p)$ Template:Robox/Close

費馬小定理餘式推廣

$p|x^p-x\Rightarrow p^k|(x^p-x{)}^k$

除式：$x^{pk}\equiv \sum _{i=1}^k(-1{)}^{i-1}(\genfrac{}{}{0ex}{}{k}{i})x^{pk-(p-1)i}(\mathrm{mod}{p}^k)$

餘式：$x^{pk+(p-1)n}\equiv \sum _{i=1}^k(-1{)}^{i-1}(\genfrac{}{}{0ex}{}{n+i-1}{i-1})(\genfrac{}{}{0ex}{}{n+k}{k-i})x^{pk-(p-1)i}(\mathrm{mod}{p}^k)$

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

階乘冪

$(x{)}_k\equiv x(x-1)(x-2)\cdots (x-k+1)\equiv 0(\mathrm{mod}k!)$

由組合數為整數可得。