0%

应用韩信点兵求余数

问:$$123456\cdots787980\div88$$的余数?

析:

令$$x=123456\cdots787980$$,则:

$$x\div88=x\div8\div11\quad\tag{1}$$

$$x(mod8)\equiv980(mod8)\equiv4(mod8)\quad\tag{2}$$

$$
\begin{multline}
x(mod11)\equiv\mbox{两位一截断求余求和}(mod11)\
\equiv10(mod11)\quad\tag{3}
\end{multline}
$$

应用韩信点兵法求得最终余数76。

流程图

graph TD;
A[x]-->B[对8求余];
A-->C[对11求余];
B-->D[韩信点兵];
C-->D;
D-->E{76};

孙子定理(中国剩余定理)

设$$m_1,m_2,\cdots,m_k\mbox{是}k$$个两两互质的正整数,$$M=m_1m_2\cdots m_k,\quad M_i=\frac{M}{m_i}, i=1,2,\cdots k$$,则同余式组

$$\begin{cases}\begin{gather}x\equiv b_1(mod m_1)\x\equiv b_2(mod m_2)\ \cdots\x\equiv b_k(mod m_k)\end{gather}\end{cases}$$

的解是

$$x\equiv b_{1} M^{‘}{1}M{1}+b_{2}M^{‘}{2}M{2}+\cdots b_{k}M^{‘}{k}M{k}(mod M)$$

其中

$$M^{‘}{i}M{i}\equiv 1(mod m_i),(i=1,2,\cdots k)$$

解:

设$$x=123456\cdots787980$$

$$x\div88=x\div8\div11$$

$$\because x(mod8)\equiv980(mod8)\equiv4(mod8)\ \therefore x(mod8)\equiv4(mod8)$$

又$$123456\cdots787980$$对11求余可用两位截断法,即从右向左划分$$1|23|45|67|89|10|11|12|\cdots|78|79|80$$,分别除以11后各余数相加再对11求余

$$\begin{align}
&5\times1\\
&+6\times(10+0+1+2+3+\cdots+9)\\
&+(10+0+1+2+3)\\
&=351
\end{align}$$

$$351(mod11)\equiv10(mod11)$$

$$\therefore x(mod11)\equiv10(mod11)$$

由此,本题转化为求解同余式组
$$\begin{cases}\begin{gather}x\equiv4(mod8)\\ x\equiv10(mod11)\end{gather}\end{cases}$$

套用孙子定理,

$$M=88, M_1=88\div8=11,M_2=88\div11=8,\\ \mbox{此处是关键} M^{‘}_1=3,M^{‘}_2=7$$

$$x\equiv4\times11\times3+10\times8\times7(mod88)$$

$$x\equiv692(mod88)\equiv76(mod88)$$

答:

余数为76。

欢迎关注我的其它发布渠道