浅谈线性同余及中国剩余定理

我记得在计算机复赛前一天晚上本想看看同余方程的解法,结果第二天就考到了。明天是数学竞赛初赛,简略的复习一下线性同余及中国剩余定理,顺便记下一些笔记。

定理1:令\(m\)为正整数。若\(a \equiv b \pmod m,c \equiv d \pmod m\),那么\(a+c \equiv b+d \pmod m,ac \equiv bd \pmod m\)。

证明:因为\(a \equiv b \pmod m,c \equiv d \pmod m\),所以有整数\(s\)和\(t\)使\(b=a+sm,d=c+tm\)。于是\[b+d=(a+sm)+(c+tm)=(a+c)+m(s+t)\]及\[bd=(a+sm)(c+tm)=ac+m(at+cs+stm)\]因此\[a+c \equiv b+d \pmod m,ac \equiv bd \pmod m\]

例:由于\(7 \equiv 2 \pmod 5,11 \equiv 1 \pmod 5\),从定理1知\[18 = 7+11 \equiv 2+1=3 \pmod 5\]且\[77 = 7 \cdot 11 \equiv 2 \cdot 1=2 \pmod 5\]

定理2:如果\(a\)和\(m\)为互素的整数,\(m > 1\),则存在\(a\)的模\(m\)的逆。而且这个逆模\(m\)是唯一的。(即有小于\(m\)的唯一正整数\(\overline{a}\),如果这样的\(\overline{a}\)存在的话。这样的\(\overline{a}\)称为\(a\)模\(m\)逆,且\(a\)的任何别的模\(m\)逆均和\(\overline{a}\)模\(m\)同余。)

证明:由定理1及\(\gcd \left ( a,m \right )=1\)知,有整数\(s\)和\(t\)使\[sa+tm=1\]于是\[sa+tm \equiv 1 \pmod m\]由于\(tm \equiv 0 \pmod m\),所以\[sa \equiv 1 \pmod m\]结论是\(s\)为\(a\)的模\(m\)逆。

例:求\(3\)的模\(7\)逆。

解:由于\(\gcd \left ( 3,7 \right )=1\),定理3说明存在\(3\)模\(7\)的逆。若用欧几里得算法求\(3\)和\(7\)的最大公约数,算法很快结束:\[7=2 \cdot 3 + 1\]从这一等式看到\[-2 \cdot 3 + 1 \cdot 7=1\]这说明-2是3模7的一个逆。(注意,模\(7\)同余于\(-2\)的每个整数也是\(3\)的逆,例如\(5,-9,12\)等。)

例:求线性同余\(3x \equiv 4 \pmod 7\)的解。

解:易知\(-2\)是\(3\)模\(7\)的逆。在同余式的两边同乘以\(-2\)得\[-2 \cdot 3x \equiv -2 \cdot 4 \pmod 7\]因为\(-6 \equiv 1 \pmod 7\)且\(-8 \equiv 6 \pmod 7\),所以若\(x\)是解,必有\(x \equiv -8 \equiv 6 \pmod 7\)。于是由定理1,有\[3x \equiv 3 \cdot 6 \equiv 18 \equiv 4 \pmod 7\]这说明所有这种\(x\)满足问题中的同余式。结论是,同余方程的解是使\(x \equiv 6 \pmod 7\)的整数。

从有关线性同余系统的中国古典问题而得名的中国剩余定理,可以这样叙述:只要线性同余系统的模数两两互素,则该系统有解,而且以所有模数之乘积取模,解是唯一的。

定理3(中国剩余定理):令\(m_{1},m_{2},\cdots,m_{n}\)为两两互素的正整数,则同余方程组\[\left\{\begin{matrix}
x \equiv a_{1} \pmod {m_{1}}\\
x \equiv a_{2} \pmod {m_{2}}\\
\vdots \\
x \equiv a_{1} \pmod {m_{n}}
\end{matrix}\right.\]有唯一的模\(m=m_{1}m_{2} \cdots m_{n}\)解。(即有一个解\(x\),使\(0 \leq x \leq m\),且所有其他的解均与此解模\(m\)同余。)

证明:要建立这一定理,需要证明有一个解存在,而且是模\(m\)唯一的。下面间给出构造这样一个解的方法以证明解的存在。

要构造一个适合各方程的解,首先对\(k=1,2, \cdots ,n\),令\(M_{k}=\frac{m}{m_{k}}\),即\(M_{k}\)是除\(m_{k}\)以外所有模数的乘积。由于\(i \neq k\)时,\(m_{i}\)和\(m_{k}\)没有大于1的公因子,所以\(\gcd \left ( m_{k},M_{k} \right )=1\)。从而由定理2知有整数\(y_{k}\),即\(M_{k}\)模\(m_{k}\)的逆,使得\[M_{k}y_{k} \equiv 1 \pmod {m_{k}}\]要得到适合所有方程的解,令\[x=a_{1}M_{1}y_{1}+a_{2}M_{2}y_{2}+\cdots+a_{n}M_{n}y_{n}\]现要证明\(x\)就是这样一个解。首先注意,由于只要\(j \neq k\),就有\(M_{j} \equiv 0 \pmod {m_{k}}\),在\(x\)的求和表达式中除第\(k\)项以外的各项模\(m_{k}\)均同余于\(0\).由于\(M_{k}y_{k} \equiv 1 \pmod {m_{k}}\),可以看出对\(k=1,2, \cdots ,n\),均有\[x \equiv a_{n}M_{n}y_{n} \equiv a_{k} \pmod {m_{k}}\]。这就证明了\(x\)是这\(n\)个同余方程的公共解。

例:求同余方程组\(\left\{\begin{matrix}
x \equiv 2 \pmod 3\\
x \equiv 3 \pmod 5\\
x \equiv 2 \pmod 7
\end{matrix}\right.\)的解。

解:首先令\(m=3 \cdot 5 \cdot 7=105\),\(M_{1}=\frac {m} {3}=35\),\(M_{2}=\frac {m} {5}=21\),\(M_{3}=\frac {m} {7}=15\).可看到\(2\)是\(M_{1}=35\)的模\(3\)逆,因为\(35 \equiv 2 \pmod 3\);\(1\)是\(M_{2}=21\)的模\(5\)逆,因为\(21 \equiv 1 \pmod 5\);\(1\)也是\(M_{3}=15\)的模\(7\)逆,因为\(15 \equiv -1 \pmod 4\)。于是这一方程组的解是满足下列式子的那些\(x\):\[x \equiv a_{1}M_{1}y_{1}+a_{2}M_{2}y_{2}+a_{3}M_{3}y_{3}=2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1=233 \equiv 23 \pmod {105}\]可以见\(23\)是所有解当中最小的正整数。结论是\(23\)是最小的正整数,除以\(3\)时余\(2\),除以\(5\)时余\(3\),除以\(7\)时余\(2\)。

2 条评论浅谈线性同余及中国剩余定理

发表评论