初等数论/同余

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

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