初等數論/同餘

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

同餘的定義在第一章已經說明了，即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}}$