同余式和同余方程

在整数环$\bf Z$中我们引进一个基本的等价关系，即同余概念.它和整数的运算是相容的，从而产生新的代数结构.同余概念在代数中产生了广泛的影响.

定义2 设$n$为一正整数，$a,b$为任意整数.如果$n\mid a-b$，则$a,b$叫做模$n$同余，记作

$$a\equiv b\pmod{n},$$

$n$叫做模数.否则，$a,b$叫做模$n$非同余，记作$a\not\equiv b\pmod{n} $.以下的讨论恒固定一个模数或几个模数.

容易证明$a\equiv b\pmod{n}$的充要条件是除法算式$a=q_1 n+r_1 $和$b=q_2 n+r_2 $有相同的余数$r_1 =r_2 $.

同余概念以最适宜于描写一种有限多个状态的周期现象.例如计算某一天是星期几，可以取$7$作模数.计算一个整数是否偶数，可以取$2$作模数.取$2$作模做，余数$0$和$1$还可以描写电路的连接和断开.同余概念和整数的运算是相容的，表现在下列基本性质中.模数固定时，$a\equiv b\pmod{n}$可简写成$a\equiv b$.如果不写出模数，表示是对同一个模数而言的.

$1$.同余是一个等价关系.

$2$.若$a\equiv b$，$c\equiv d$，则$a\pm c\equiv b\pm d\pmod{n} $.

$3$.若$a\equiv b$，$c\equiv d$，则$a\cdot c\equiv b\cdot d\pmod{n} $.

$4$.若$ac\equiv bc\pmod{n} $，$(c,n)=1$，则$a\equiv b\pmod{n} $.

$5$.若$a\equiv b\pmod{n} $，$m\mid n$，则$a\equiv b\pmod{m} $.

$6$.若$a\equiv b\pmod{n} $，则$(a,n)=(b,n)$.

$7$.若$a\equiv b\pmod{n} $，$d$为$a,b,n$的一个公因子，$a=da_1$，$b=db_1 $，$n=dn_1 $，则$a_1 \equiv b_1 \pmod{n_1} $.

例1 $716\cdot 93$和$543\cdot 93$模$61$是否同余？假设$716\cdot 93\equiv 543\cdot 93\pmod{61}$，根据性质$4$，因$(93,61)=1$，有$716\equiv 543\pmod{61} $.但$61\nmid (716-543)=173$，所以$716\cdot 93\not\equiv 543\cdot 93\pmod{61} $.

例2 设复数$\varepsilon =\cos{\dfrac{2\pi }{17} } +i\sin{\dfrac{2\pi }{17} } $.计算$\varepsilon $的整数幂$\varepsilon ^m$等于计算$\varepsilon ^r$，其中$r$是$m$模$17$的余数，$0\leq r < 17$.

对于一个给定的模数$n$，全体整数按模$n$同余分成一些等价类，此时的等价类叫做整数模$n$的剩余类，含整数$a$的剩余类记作$\overline{a} $，剩余类$\overline{a} $的任一个元素叫做$\overline{a} $的一个代表.在每个剩余类中任取一个代表$r_i$，由这些代表组成的集合叫做整数模$n$的一个完全剩余代表系.整数模$n$的一个完全代表系$S$也可以这样来刻画：$1)$每个整数和$S$中一个元素模$n$同余，$2)S$中元素两两互不同余.根据除法算式可知，集合$S=\lbrace 0,1,2,\cdots ,n-1\rbrace$是模$n$的一个完全剩余类代表系.

由模$n$的剩余类组成的商集记作${\bf Z}/(n)$.在${\bf Z}/(n)$中可以定义加法和乘法如下：

$$\overline{a} +\overline{b} =\overline{a+b} ,$$

$$\overline{a} \cdot \overline{b} =\overline{a\cdot b}.$$

根据同余式的性质，定义与代表的取法无关而且加法和乘法还满足结合律、交换律和分配律，加法有零元素$\overline{0}$，每个$\overline{a}$有负元素：$\overline{-a}$：$\overline{a}+\overline{-a}=\overline{0}$.${\bf Z}/(n)$叫做整数模$n$的环.

这一节剩下的部分来讨论一次同余方程和方程组.同余式

$$ax\equiv b\pmod{n},a\not\equiv 0\pmod{0}$$

是含有一个未知量$x$的一次式，叫做一次同余方程.若$x=c\in \bf Z$代入上方程使两边同余，则$c$叫做上方程的一个解.上方程的两个解$c_1,c_2$看作相同当而且仅当$c_1 \equiv c_2\pmod{n}$.

定理4 设$(a,n)=1$，则一次同余方程

$$ax\equiv b\pmod{n}$$

有解而且只有一个解.

证明 由于$(a,n)=1$，存在整数$u,v$使得$ua+vn=1$.两边乘$b$，$uba+vbn=b$，令$ub=c$，于是$ca\equiv uba\equiv b\pmod{n},x\equiv c$为其一解.其次，令$c_1,c_2$为任意两个解，于是

$$ac_1\equiv b\pmod{n},$$

$$ac_2\equiv b\pmod{n}.$$

相减得$a(c_1-c_2)\equiv 0\pmod{n}$，由于$(a,n)=1$，根据同余的性质$4$，有$c_1\equiv c_2\pmod{n}$，$c_1,c_2$为同一解.

考虑下列一次同余方程组

$$\begin{cases} x\equiv b_1\pmod{n_1}, \\ x\equiv b_2\pmod{n_2}, \\ \cdots \cdots \cdots \cdots \cdots \\ x\equiv b_r\pmod{n_r}. \end{cases} \tag{1}$$

其中$n_1,n_2,\cdots ,n_r$为大于$1$的整数，两两互素，$b_1,b_2,\cdots ,b_r$是任意给定的整数.如果$x=c\in \bf Z$代入方程组使得同余式同时都成立，则$c$叫做方程组$(1)$的一个解.上方程组的两个解$c_1$和$c_2$看作相同当而且仅当

$$c_1 \equiv c_2 \pmod{\prod \limits_{i=1}^rn_i}.$$

定理5 (孙子定理) 设一次同余方程组$(1)$中大于$1$的整数$n_1,n_2,\cdots ,n_r$两两互素，$b_1,b_2,\cdots ,b_r$是任意给定的整数，则$(1)$有解而且只有一解.

证明 这里只证明$r=2$的情况，读者可以应用数学归纳法去证明一般情况.设$r=2$，由于$(n_1,n_2)=1$，存在一对整数$u_1,u_2$使得$u_1n_1+u_2n_2=1$.令$e_2=u_1n_1$，$e_1=u_2n_2$.于是$e_i\equiv 1\pmod{n_i},i=1,2$，而$e_i\equiv 0\pmod{n_j},i\neq j$.取$c=b_1e_1+b_2e_2$，则$c$为方程组$(1)$的解.其次证明解的唯一性，设$c_1,c_2$为任意两解，于是

$$c_1\equiv b_1,c_2\equiv b_1\pmod{n_1},$$

$$c_1\equiv b_2,c_2\equiv b_2\pmod{n_2}.$$

同余式相减得

$$c_1-c_2\equiv 0\pmod{n_1},$$

$$c_1-c_2\equiv 0\pmod{n_2}.$$

由于$(n_1,n_2)=1$，根据互素性质$(3)c_1-c_2\equiv 0\pmod{n_1n_2}$，所以$c_1,c_2$为同一解.$\blacksquare$

孙子定理在国际上叫做中国剩余定理.