查看“︁初等數論/同餘”︁的源代码

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

----

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

== 同餘的性質 ==

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

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

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

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

==多項式同餘==

== 經典同餘恆等式 ==
=== 歐拉函數 ===
<math>\phi (n)</math>函數(又稱歐拉函數)是指小於等於n的自然數中與n互質的數的數目。
例子：<math>\phi (6)</math>=2，因為在1,2,3,4,5,6中只有1,5是和6互質

===歐拉函數的特性===
若正整數n個標準分解式為<math>n = p_1^{q_1} p_2^{q_2} ...... p_k^{q_k}</math>，則<math>\phi (n)</math>函數的值為：

<math>\phi (n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})......(1 - \frac{1}{p_k}) </math>

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

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

例子：<math>\phi (36)</math>=<math>\phi (4)</math><math>\phi (9)</math>=12

除了<math>\phi (1)</math>=<math>\phi (2)=1</math>外，對其他的<math>\phi (n)</math>，都有<math>2|\phi (n)</math>

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

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

<math>a^p \equiv a \pmod{p}</math>

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

<math>a^{p-1} \equiv 1 \pmod{p}</math>

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

<math>a^{\phi (m)} \equiv 1 \pmod{m}</math>

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

{{Robox|theme=3|title=利用簡化剩餘系證明歐拉定理}}設<math>\{r_1,r_2,\dots ,r_{\phi (m)}\}</math>為模m的簡化剩餘系<br/>
由於<math>(a,m)=1</math>，<math>\{ar_1,ar_2,\dots ,ar_{\phi (m)}\}</math>也是模m的簡化剩餘系<br/>
<math>(ar_1)(ar_2)\dots(ar_{\phi(m)})\equiv r_1 r_2 \dots r_{\phi(m)}\pmod{m}</math><br/>
<math>a^{\phi(m)}(r_1 r_2 \dots r_{\phi(m)})\equiv r_1 r_2 \dots r_{\phi(m)}\pmod{m}</math><br/>
又<math>(r_1 r_2 \dots r_{\phi(m)},m)=1</math>，得<math>a^{\phi (m)} \equiv 1 \pmod{m}</math>
{{Robox/Close}}

===卡邁克爾函數===
卡邁克爾函數<math>\lambda(n)</math>满足<math>a^{\lambda(n)}\equiv 1\pmod{n}</math>，其中a與n互質。

当n为2、4、奇質数的指數、奇質數的指數的兩倍时为歐拉函數，當n为2,4以外的2的指數時为它的一半。
<math>\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}
</math>

歐拉函數有<math>\varphi(p^k) = p^{k-1}(p-1)</math>

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

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

<math>\lambda(n) = \operatorname{lcm}[\lambda(p_1^{a_1}),\;\lambda(p_2^{a_2}),\dots,\lambda(p_{\omega(n)}^{a_{\omega(n)}}) ]</math>

{{Robox|theme=3|title=證明當a与n互質時，<math>a^{\lambda(n)}\equiv 1\pmod{n}</math>}}由費馬小定理得<math>a^{p-1}=1+hp</math>

<math>a^{p^{k-1}(p-1)}=1+hp^k</math>

<math>a^{p^k(p-1)}=(1+hp^k)^p=1+h^p p^{k+1}+\dots=1+h_0 p^{k+1}</math>

由數學歸納法得<math>a^{p^{k-1}(p-1)}\equiv 1\pmod{p^k}</math>成立，這是一般情況。

<math>a=1+2h</math>

<math>a^2=1+4h(h+1)=1+8C_{h+1}^2</math>

<math>a^{2^{k-2}}=1+2^k h</math>

<math>a^{2^{k-1}}=(1+2^k h)^2=1+2^{k+1}(h+2^{k-1}h^2)</math>

由數學歸納法得當<math>k\ge 3</math>時，<math>a^{2^{k-2}}\equiv 1\pmod{2^k}</math>成立。
{{Robox/Close}}

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

{{Robox|theme=3|title=證明威爾逊定理}}
如果p不是質數，它的正因數必然包含在<math>1,2,3,4,\dots,p-1</math>中，因此<math>((p-1)!,p)\neq 1</math><br/>
<math>(p-1)!\equiv -1\pmod{p}\Rightarrow \exist k\in \mathbb{Z},~ s.t. ~ (p-1)!+pk=-1</math>，與<math>((p-1)!,p)\neq 1</math>矛盾。<br/>
所以<math>(p-1)!\equiv -1\pmod{p}</math>成立時p一定是質數。

若p是質數，<math>A=\{1,2,3,\dots,p-1\}</math>是模p的剩餘系<br/>
<math>\forall i\in A,\exist j\in A,~ s.t. ~ ij\equiv 1 \pmod{p}</math><br/>
當<math>i=j</math>時，<math>i^2\ \equiv\ 1 \pmod{p}\Rightarrow i \equiv \pm1 \pmod{p}</math><br/>
其餘<math>\{2,3,\dots,p-2\}</math>兩兩配對<br/>
<math>(p-1)! \equiv 1\times(p-1) \equiv -1 \pmod{p} </math>
{{Robox/Close}}

===費馬小定理餘式推廣===
<math>p|x^p-x \Rightarrow p^k|(x^p-x)^k</math>

除式：<math>\displaystyle x^{pk} \equiv \sum_{i=1}^k(-1)^{i-1} \binom{k}{i} x^{pk-(p-1)i} \pmod {p^k}</math>

餘式：<math>\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}</math>

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

===階乘冪===
<math>(x)_k \equiv x(x-1)(x-2)\cdots(x-k+1) \equiv 0 \pmod{k!}</math>

由組合數為整數可得。

== 習題 ==
===  第一部份─基礎題  ===

=== 第二部份─進階題 ===

{{Stub}}

[[Category:初等数论]]