问:$$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。