初等數論/同餘

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

---

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

同餘的性質

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

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

同餘類與剩餘系

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

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

經典同餘恆等式

歐拉函數

$\phi (n)$函數(又稱歐拉函數)是指小於等於n的自然數中與n互質的數的數目。 例子：$\phi (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}}$，則$\phi (n)$函數的值為：

$\phi (n)=n(1-{\frac {1}{p_{1}}})(1-{\frac {1}{p_{2}}})......(1-{\frac {1}{p_{k}}})$

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

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

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

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

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

費馬小定理

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

$a^{p}\equiv a{\pmod {p}}$

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

$a^{p-1}\equiv 1{\pmod {p}}$

歐拉定理

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

$a^{\phi (m)}\equiv 1{\pmod {m}}$

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

利用簡化剩餘系證明歐拉定理 設$\{r_{1},r_{2},\dots ,r_{\phi (m)}\}$為模m的簡化剩餘系 由於$(a,m)=1$，$\{ar_{1},ar_{2},\dots ,ar_{\phi (m)}\}$也是模m的簡化剩餘系 $(ar_{1})(ar_{2})\dots (ar_{\phi (m)})\equiv r_{1}r_{2}\dots r_{\phi (m)}{\pmod {m}}$ $a^{\phi (m)}(r_{1}r_{2}\dots r_{\phi (m)})\equiv r_{1}r_{2}\dots r_{\phi (m)}{\pmod {m}}$ 又$(r_{1}r_{2}\dots r_{\phi (m)},m)=1$，得$a^{\phi (m)}\equiv 1{\pmod {m}}$

卡邁克爾函數

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

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

歐拉函數有$\varphi (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)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})]$

證明當a與n互質時，$a^{\lambda (n)}\equiv 1{\pmod {n}}$ 由費馬小定理得$a^{p-1}=1+hp$ $a^{p^{k-1}(p-1)}=1+hp^{k}$ $a^{p^{k}(p-1)}=(1+hp^{k})^{p}=1+h^{p}p^{k+1}+\dots =1+h_{0}p^{k+1}$ 由數學歸納法得$a^{p^{k-1}(p-1)}\equiv 1{\pmod {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\geq 3$時，$a^{2^{k-2}}\equiv 1{\pmod {2^{k}}}$成立。

威爾遜定理

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

證明威爾遜定理 如果p不是質數，它的正因數必然包含在$1,2,3,4,\dots ,p-1$中，因此$((p-1)!,p)\neq 1$ $(p-1)!\equiv -1{\pmod {p}}\Rightarrow \exists k\in \mathbb {Z} ,~s.t.~(p-1)!+pk=-1$，與$((p-1)!,p)\neq 1$矛盾。 所以$(p-1)!\equiv -1{\pmod {p}}$成立時p一定是質數。 若p是質數，$A=\{1,2,3,\dots ,p-1\}$是模p的剩餘系 $\forall i\in A,\exists j\in A,~s.t.~ij\equiv 1{\pmod {p}}$ 當$i=j$時，$i^{2}\ \equiv \ 1{\pmod {p}}\Rightarrow i\equiv \pm 1{\pmod {p}}$ 其餘$\{2,3,\dots ,p-2\}$兩兩配對 $(p-1)!\equiv 1\times (p-1)\equiv -1{\pmod {p}}$

費馬小定理餘式推廣

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

除式：$\displaystyle x^{pk}\equiv \sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}x^{pk-(p-1)i}{\pmod {p^{k}}}$

餘式：$\displaystyle x^{pk+(p-1)n}\equiv \sum _{i=1}^{k}(-1)^{i-1}{\binom {n+i-1}{i-1}}{\binom {n+k}{k-i}}x^{pk-(p-1)i}{\pmod {p^{k}}}$

n=0時為除式，用數學歸納法證明餘式。

階乘冪

$(x)_{k}\equiv x(x-1)(x-2)\cdots (x-k+1)\equiv 0{\pmod {k!}}$

由組合數為整數可得。

習題