初等数论/同余

数论 > 初等数论 > 初等数论/同余

---

同余的定义在第一章已经说明了，即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!}}$

由组合数为整数可得。