Feb 16

这里的同余包含了同余和同余方程两个章节。

基本的同余概念可以从带余除法中推导出来。使用带余除法,我们可以得到同余式的相关运算性质。

接下来,我们引入同余类剩余系的概念。剩余系主要是介绍了既约剩余系。我们从既约剩余系的定义中引出了Euler函数。Euler函数是一个积性函数,也就是说如果(m1,m2)=1,那么$\varphi(m_1m_2)=\varphi(m_1)\varphi(m_2)$。Euler函数有如下的计算式 $\varphi(m)=m\prod_{p|m}(1-\frac{1}{p})$,特别的,当m=pk时,我们有$\varphi(p^k)=p^{k-1}(p-1)$。我们还有\sum_{d|m}\varphi(d)=m,我们可以从中看出Mobius函数的一点影子。

接下来,我们由一个性质得到了一个重要的定理:Fermat-Euler定理。这个性质是,对于一个模m,它的任何一个既约剩余系中所有元素的乘积模m是相同的,也可以表述为(a,m)=1时,x遍历m的既约剩余系当且仅当ax遍历m的既约剩余系。我们得到$a^{\varphi(m)}\equiv 1\pmod{m}$,以及当m=p时,对于任意的a,我们有$a^p\equiv a\pmod{p}$。前面的式子被称为Fermat小定理,后面的式子被称为Euler定理。

Wilson定理是如下的内容$r_1\cdots r_{p-1}\equiv -1\pmod{p}$,也就是对于一个素数p>3,它的既约剩余系中所有数的乘积模p为-1。特别的,我们有$(p-1)!\equiv -1\pmod{p}$。事实上,p不取1,2,4,pk,2pk时,p的既约剩余系的积模p得1。Wilson虽然不能用来高效地检验素数,但是可以被用来简化运算。

同余方程是多项式同余的形式。其最简单的形式是一次同余方程。我们可以用带余除法和辗转相除法得到其解。中国剩余定理用来求解一次同余方程组。对于一个一次同余方程组$x\equiv a_j\pmod{m_j},1\leq j\leq k$,这里m1,...,mk两两既约。那么其解为$x\equiv M_1M_1^{-1}a_1+\cdots+M_kM_k^{-1}a_k\pmod{m}$,m=m1...mk,m=mjMj,以及$M_j^{-1}$是Mj模mj的逆。这个解的正确性容易带入验证。如果m1,...,mk并非两两既约,则可以化为各个方程都是模pk的形式更加方便。

关于模为素数的二次同余方程,我们只需要讨论$x^2\equiv d\pmod{p}$的形式。对于模p,如果一个d能使得方程有解,那么我们称d为模p的二次剩余;否则d就是模p的二次非剩余。我们可以用Euler判别法来进行判断。如果$d^{(p-1)/2}\equiv 1\pmod{p}$,那么d就是模p的二次剩余;如果$d^{(p-1)/2}\equiv -1\pmod{p}$,那么d就是模p的二次非剩余。

我们还可以引进Legendre符号Jacobi符号来进行进一步的研究。Gauss二次互反律也是进一步的探讨对象。具体内容可以参见原书或者nmbr.rar