索引

同余性质定理: $\forall a,b\in \mathbb{Z}$，有$$a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\iff m|\left(a-b\right)\iff \exists t\in \mathbb{Z},a=b+mt$$定理: 若$A_{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}\equiv B_{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),x_i\equiv y_i\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),i=1,2,\cdots ,k$，则$$\sum _{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}{A}_{{\alpha }_1{\alpha }_2\cdots a_k}{x_1}^{{\alpha }_1}{x_2}^{{\alpha }_2}\cdots {x_k}^{{\alpha }_k}\equiv \sum _{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}{B}_{{\alpha }_1{\alpha }_2\cdots a_k}{y_1}^{{\alpha }_1}{y_2}^{{\alpha }_2}\cdots {y_k}^{{\alpha }_k}\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$$特别地，若$a_i\equiv b_i\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),i=0,1,2,\cdots ,n$，则$$a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots a_0\equiv b_n{x}^n+b_{n-1}{x}^{n-1}+\cdots +b_0\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$$特别地，若$x\equiv y\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$，则$$a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_0\equiv a_n{y}^n+a_{n-1}{y}^{n-1}+\cdots +a_0\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$$若干个正整数的倍数特征（十进制范围内）同余应用：万年历, C.Zeller 1882同余应用：ISBN码验真伪同余应用: 弃九法 检验两数相乘结果正确性同余应用: 判断 某整数是否是某大数的因子定理: 设$a$是任一奇数，则有$$a^{2^n}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{n+2}\right)\left(n\ge 1\right)$$

同余性质

  设$m\in {\mathbb{Z}}_{>0},a,b\in \mathbb{Z}$。

甲：$a\equiv a\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$乙：$a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\Rightarrow b\equiv a\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$丙：$\begin{array}{rl}& a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\\ & b\equiv c\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\end{array}\}\Rightarrow a\equiv c\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$丁：若$a_1\equiv b_1\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),a_2\equiv b_2\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$，则 $a_1+a_2\equiv b_1+b_2\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$$a+b\equiv c\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\Rightarrow a\equiv c-b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$ 戊：$\begin{array}{rl}& a_1\equiv b_1\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\\ & a_2\equiv b_2\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\end{array}\}\Rightarrow a_1{a}_2\equiv b_1{b}_2\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$。 特别地，$a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\Rightarrow ak\equiv bk\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),\forall k\in \mathbb{Z}$己：$a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),\{\begin{array}{rl}& a=a_{1}d\\ & b=b_{1}d\end{array},\gcd \left(d,m\right)=1\Rightarrow a_1\equiv b_1\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$庚：$\{\begin{array}{rl}& a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),k>0\Rightarrow ak\equiv bk\left(\mathrm{m}\mathrm{o}\mathrm{d}mk\right)\\ & a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),d\in {\mathbb{Z}}_{>0},\{\begin{array}{rl}& d|a\\ & d|b\\ & d|m\end{array}\Rightarrow \frac{a}{d}\equiv \frac{b}{d}\left(\mathrm{m}\mathrm{o}\mathrm{d}\frac{m}{d}\right)\end{array}$辛：$\forall i\in \left\{1,2,\cdots ,k\right\},a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i\right)\Rightarrow a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}\left[lcm\left(m_1,m_2\cdots ,m_k\right)\right]\right)$壬：$a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),\{\begin{array}{rl}& d|m\\ & d>0\end{array}\Rightarrow a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}d\right)$癸：$a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\Rightarrow \text{ gcd}\left(a,m\right)=\gcd \left(b,m\right)$ 因而可以成立以下推理关系： $$\{\begin{array}{rl}& d|m\\ & d|a\end{array}\Rightarrow d|\gcd \left(a,m\right)=\gcd \left(b,m\right)\Rightarrow d|b$$

定理: $\forall a,b\in \mathbb{Z}$，有$$a\equiv b\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\iff m|\left(a-b\right)\iff \exists t\in \mathbb{Z},a=b+mt$$

定理: 若$A_{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}\equiv B_{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),x_i\equiv y_i\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),i=1,2,\cdots ,k$，则$$\sum _{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}{A}_{{\alpha }_1{\alpha }_2\cdots a_k}{x_1}^{{\alpha }_1}{x_2}^{{\alpha }_2}\cdots {x_k}^{{\alpha }_k}\equiv \sum _{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}{B}_{{\alpha }_1{\alpha }_2\cdots a_k}{y_1}^{{\alpha }_1}{y_2}^{{\alpha }_2}\cdots {y_k}^{{\alpha }_k}\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$$特别地，若$a_i\equiv b_i\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right),i=0,1,2,\cdots ,n$，则$$a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots a_0\equiv b_n{x}^n+b_{n-1}{x}^{n-1}+\cdots +b_0\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$$特别地，若$x\equiv y\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$，则$$a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_0\equiv a_n{y}^n+a_{n-1}{y}^{n-1}+\cdots +a_0\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$$

若干个正整数的倍数特征（十进制范围内）

  $0$

$0$是任意非零整数的倍数；任意整数都不是$0$的倍数。

补充   引用《初等数论（第四版）》里关于因数和倍数的定义： $\forall a\in \mathbb{Z}$, $\forall b\in {\mathbb{Z}}_{\ne 0}$，若$\exists q\in \mathbb{Z},s.t.a=bq$成立，则称$b$为$a$的因数，$a$为$b$的倍数。

  $1$

任意整数都是$1$的倍数。

  $2$

个位数是偶数$0,2,4,6,8$的整数$\iff$$2$的倍数。因为 $$\begin{array}{c}10\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}2\right)\\ \Rightarrow a_0+\sum _{k=1}^n{10}^k{a}_k\equiv a_0+\sum _{k=1}^n{0}^k{a}_k=a_0\left(\mathrm{m}\mathrm{o}\mathrm{d}2\right)\\ a_{}\equiv a_0\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}2\right)\end{array}$$

  $3$

数字和是3的倍数的整数$\iff$ $3$的倍数。因为 $$\begin{array}{c}10\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}3\right)\\ \Rightarrow a_0+\sum _{k=1}^n{10}^k{a}_k\equiv a_0+\sum _{k=1}^n{1}^k{a}_k=\sum _{k=0}^n{a}_k\left(\mathrm{m}\mathrm{o}\mathrm{d}3\right)\\ \Rightarrow a\equiv \sum _{k=0}^n{a}_k\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}3\right)\end{array}$$

  4

末尾两位是4的倍数的整数$\iff$ $4$的倍数。因为 $$\begin{array}{c}100\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}4\right)\\ \Rightarrow a_0+\sum _{k=1}^n{100}^k{a}_k\equiv a_0+\sum _{k=1}^n{0}^k{a}_k=a_0\left(\mathrm{m}\mathrm{o}\mathrm{d}4\right)\\ \Rightarrow a_{}\equiv a_0\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}4\right)\end{array}$$

  5

个位数是$0$或$5$的整数$\iff$ $5$的倍数。因为 $$\begin{array}{c}10\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}5\right)\\ \Rightarrow a_0+\sum _{k=1}^n{10}^k{a}_k\equiv a_0+\sum _{k=1}^n{0}^k{a}_k=a_0\left(\mathrm{m}\mathrm{o}\mathrm{d}5\right)\\ \Rightarrow a\equiv a_0\left(\mathrm{m}\mathrm{o}\mathrm{d}5\right)\end{array}$$

  6

既是$2$的倍数又是$3$的倍数的整数$\iff$ $6$的倍数，因为$$6=lcm\left(2,3\right)$$

  7

从右至左，每3个数字一组，交错和是$7$的倍数的整数$\iff$ $7$的倍数。因为 $$\begin{array}{c}1000\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)\\ \Rightarrow a_0+\sum _{k=1}^n{1000}^k{a}_k\equiv a_0+\sum _{k=1}^n{\left(-1\right)}^k{a}_k=\sum _{k=0}^n{\left(-1\right)}^k{a}_k\\ \Rightarrow a\equiv \sum _{k=0}^n{\left(-1\right)}^k{a}_k\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)\end{array}$$

补充说明 $$1000=1001-1=7\times 11\times 13-1\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}7/11/13\right)$$

  8

后三位是8的倍数的整数$\iff$ $8$的倍数，因为 $$\begin{array}{c}1000\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}8\right)\\ \Rightarrow a_0+\sum _{k=1}^n{1000}^k{a}_k\equiv a_0+\sum _{k=1}^n{0}^k{a}_k=a_0\left(\mathrm{m}\mathrm{o}\mathrm{d}8\right)\\ \Rightarrow a\equiv a_0\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}8\right)\end{array}$$

  9

各位数的数字之和是$9$的倍数的整数$\iff$ $9$的倍数。因为 $$\begin{array}{c}10\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\\ \Rightarrow a_0+\sum _{k=1}^n{10}^k{a}_k\equiv a_0+\sum _{k=1}^n{1}^k{a}_k=\sum _{k=0}^n{a}_k\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\\ \Rightarrow a\equiv \sum _{k=0}^n{a}_k\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\end{array}$$

  10

个位数是$0$的整数$\iff$ $10$的倍数。因为 $$\begin{array}{c}10\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)\\ \Rightarrow a_0+\sum _{k=1}^n{10}^k{a}_k\equiv a_0+\sum _{k=1}^n{0}^k{a}_k=a_0\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)\\ \Rightarrow a\equiv a_0\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)\iff a_0=0\end{array}$$

  11

从右至左，每三个数字一组，交错和是$11$的倍数的整数$\iff$ $11$的倍数。因为 $$\begin{array}{c}1000\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}11\right)\\ \Rightarrow a_0+\sum _{k=1}^n{1000}^k{a}_k\equiv a_0+\sum _{k=1}^n{\left(-1\right)}^k{a}_k=\sum _{k=0}^n{\left(-1\right)}^k{a}_k\\ \Rightarrow a\equiv \sum _{k=0}^n{\left(-1\right)}^k{a}_k\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}11\right)\end{array}$$

从右至左，各位数交错和是11的倍数的整数$\iff 11$的倍数，因为 $$\begin{array}{c}10\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}11\right)\\ \Rightarrow a_0+\sum _{k=1}^n{10}^k{a}_k\equiv a_0+\sum _{k=1}^n{\left(-1\right)}^k{a}_k=\sum _{k=0}^n{\left(-1\right)}^k{a}_k\left(\mathrm{m}\mathrm{o}\mathrm{d}11\right)\\ \Rightarrow a\equiv \sum _{k=0}^n{\left(-1\right)}^k{a}_k\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}11\right)\end{array}$$

  12

既是$3$的倍数也是$4$的倍数的整数$\iff$ $12$的倍数，因为 $$12=lcm\left(3,4\right)$$

  13

从右至左，每三个数字一组，交错和是$13$的倍数的整数$\iff$ $13$的倍数，因为 $$\begin{array}{c}1000\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}13\right)\\ \Rightarrow a_0+\sum _{k=1}^n{1000}^k{a}_k\equiv a_0+\sum _{k=1}^n{\left(-1\right)}^k{a}_k=\sum _{k=0}^n{\left(-1\right)}^k{a}_k\left(\mathrm{m}\mathrm{o}\mathrm{d}13\right)\\ \Rightarrow a\equiv \sum _{k=0}^n{\left(-1\right)}^k{a}_k\left(\mathrm{m}\mathrm{o}\mathrm{d}13\right)\end{array}$$

  37

从右至左，每三个数字一组，其和是37的倍数的整数$\iff$ 37的倍数，因为 $$\begin{array}{c}1000=37\times 27+1\Rightarrow 1000\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}37\right)\\ \Rightarrow a_0+\sum _{k=1}^n{1000}^k{a}_k\equiv a_0+\sum _{k=1}^n{1}^k{a}_k=\sum _{k=0}^n{a}_k\left(\mathrm{m}\mathrm{o}\mathrm{d}37\right)\\ \Rightarrow a\equiv \sum _{k=0}^n{a}_k\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}37\right)\end{array}$$

  101

从右至左，每两个数字一组，交错和是101倍数的整数 $\iff$ 101的倍数，因为 $$\begin{array}{c}100\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}101\right)\\ \Rightarrow a_0+\sum _{k=1}^n{100}^k{a}_k\equiv a_0+\sum _{k=1}^n{\left(-1\right)}^k{a}_k=\sum _{k=1}^n{\left(-1\right)}^k{a}_k\left(\mathrm{m}\mathrm{o}\mathrm{d}101\right)\\ \Rightarrow a\equiv \sum _{k=1}^n{\left(-1\right)}^k{a}_k\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}101\right)\end{array}$$

从右至左，每四个数字一组，其和是101倍数的整数$\iff 101$的倍数，因为 $$\begin{array}{c}10000=101\times 99+1\Rightarrow 10000\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}101\right)\\ \Rightarrow a_0+\sum _{k=1}^n{10000}^k{a}_k\equiv a_0+\sum _{k=1}^n{1}^k{a}_k=\sum _{k=0}^n{a}_k\left(\mathrm{m}\mathrm{o}\mathrm{d}101\right)\\ \Rightarrow a\equiv \sum _{k=0}^n{a}_k\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}101\right)\end{array}$$

例子

对$637693$进行简单的因子分析。

个位数为$3$，非偶，因此非2倍数，（当然也非4，8倍数）。$3|6,3|3,3\nmid 7,3|9\Rightarrow \left(6+3+7+6+9+3\right)\not\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}3\right)$，非3倍数（当然也非9倍数）。$4\nmid 93\Rightarrow$非4倍数。个位数非0非5，因此非5倍数，非10倍数。非2倍数，非3倍数，因此非6倍数。$693-637=56,7|56,11\nmid 56,13\nmid 56$，因此是7倍数，非11倍数，非13倍数。非3倍数，非4倍数，因此非12倍数。

对$75312289$进行简单的因子分析。

个位数为9，非偶，因此非2倍数（当然也非4, 8倍数）。$7+5+3+1+2+2+8+9\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}3\right)$，因此非3倍数（当然也非9倍数）。$4|89$，因此非4倍数。个位数非0非5，因此非5倍数，非10倍数。非2倍数且非3倍数，因此非6倍数。$289-312+75=52=4\times 13$，是13倍数，非7倍数，非11倍数。非3倍数，非4倍数，因此非12倍数。

应用检查因数的方法写出$1535625$的标准分解式。 1535625个位数是5，因此可分解出因子5，$1535625=5\times 307125$。 307125个位数是5，因此可分解出因子5，$307125=5\times 61425$。 61425个位数是5，因此可分解出因子5，$61425=5\times 12285$。 12285个位数是5，因此可分解出因子5，$12285=5\times 2457$。 $2+4+5+7\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)$，因此可分解出因子9，$2457=3^2\times 273$。 $2+7+3\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}3\right)$，因此可分解出因子3，$273=3\times 91$。 最后$91$可分解为$91=7\times 13$。 因此$1535625$的标准分解式为 $$1535625=3^3\times 5^4\times 7\times 13$$

应用检查因数的方法写出1158066的标准分解式。 1158066个位数是6，因此有因子2，$1158066=2\times 579033$。 $5+7+9+0+3+3\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)$，因此有因子9，$579033=3^2\times 64337$。 $337-64=273=3\times 7\times 13$，因此有因子7，$64337=7\times 9191$。 $191-9=182=2\times 7\times 13$，因此有因子7，$9191=7\times 1313$。 $313-1=312=2^3\times 3\times 13$，因此有因子13，$1313=13\times 101$。 （$101<121={11}^2$，小于11的数均非101的因子，于是101是素数） 基于此，我们有1158066的标准分解式为 $$1158066=2\times 3^2\times 7^2\times 13\times 101$$

同余应用：万年历, C.Zeller 1882

   内容   1582年10月4日之后，第$C+1$世纪中的第$Y\left(0\le Y\le 99\right)$年$M$月$D$日，这一天是星期$Z$，$Z$满足以下关系 $$Z\equiv D+\left[2.6m-0.2\right]-2C+y+\left[\frac{y}{4}\right]+\left[\frac{C}{4}\right]\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)$$ 其中$m$表示两个月前的月份，$y$表示两个月前的年份（的后两位）。

例子

计算2020年9月29日是星期几。 按照公式，有 $$\begin{array}{rl}& C+1=21\Rightarrow C=20\\ & Y=20\\ & M=9\\ & D=29\\ & m=M-2=7\\ & y=20\end{array}$$ 代入公式得 $$\begin{array}{rl}& 29+\left[2.6\times 7-0.2\right]-2\times 20+20+\left[\frac{20}{4}\right]+\left[\frac{20}{4}\right]\\ & =29+18-40+20+5+5\\ & =37\equiv 2\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)\end{array}$$ 因此这一天是星期二。

计算2021年春节（2月12日）是星期几。 按照公式，有 $$\begin{array}{rl}& C+1=21\Rightarrow C=20\\ & Y=21\\ & M=2\\ & D=12\\ & m=12\\ & y=20\end{array}$$ 代入公式，有 $$\begin{array}{rl}& 12+\left[2.6\times 12-0.2\right]-2\times 20+20+\left[\frac{20}{4}\right]+\left[\frac{20}{4}\right]\\ & =12+31-40+20+5+5\\ & =33\equiv 5\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)\end{array}$$ 因此这一天是星期五。

同余应用：ISBN码验真伪

内容   任何正版图书的ISBN代码，如果是13位的话，依次记从左到右的数字为$a_1$到$a_{13}$，则必须满足下式 $$a_1+3a_2+a_3+3a_4+a_5+3a_6+a_7+3a_8+a_9+3a_{10}+a_{11}+3a_{12}+a_{13}\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)$$ 即 $$\sum _{i=1}^7{a}_{2i-1}+3\sum _{j=1}^6{a}_{2j}\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)$$ 若一本书的13位ISBN码不满上述式子，则一定为非正版。

例子

学校购买的《初等数论（第四版）》（闵嗣鹤 严士健 编）的ISBN码为978-7-04-053446-7。 $$\left(9+8+0+0+3+4+7\right)+3\times \left(7+7+4+5+4+6\right)=130\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)$$

某本书的ISBN码为9780061353289。   ( 9 + 8 + 0 + 1 + 5 + 2 + 9 ) + 3 × ( 7 + 0 + 6 + 3 + 3 + 8 ) ≡ ( − 1 − 2 + 0 + 1 + 5 + 2 − 1 ) + 3 × ( − 3 + 0 − 4 + 3 + 3 − 2 ) (   m o d   10 ) = 4 + 3 × ( − 3 ) = − 5 ≡ 5 (   m o d   10 ) \begin{aligned} & \text{ }\left( 9+8+0+1+5+2+9 \right)+3\times \left( 7+0+6+3+3+8 \right) \\ & \equiv \left( \cancel{-1}\cancel{-2}+0\cancel{+1}+5\cancel{+2}-1 \right)+3\times \left( \cancel{-3}+0-4\cancel{+3}+3-2 \right)\left( \bmod 10 \right)\\ & =4+3\times \left( -3 \right) \\ & =-5 \\ & \equiv 5\left( \bmod 10 \right) \\ \end{aligned} ​ (9+8+0+1+5+2+9)+3×(7+0+6+3+3+8)≡(−1 ​−2 ​+0+1 ​+5+2 ​−1)+3×(−3 ​+0−4+3 ​+3−2)(mod10)=4+3×(−3)=−5≡5(mod10)​ 因此该书一定为盗版书。

某正版书的ISBN码前12位为978079225314，求其最后一位（校验位）。 设最后一位为$x\in \mathbb{Z}$ ，$0\le x\le 9$。列得 $$\begin{array}{rl}& \left(9+8+7+2+5+1+x\right)+3\times \left(7+0+9+2+3+4\right)\\ & \equiv \left(-1-2-3+2+5+1+x\right)+3\times \left(-3+0-1+2+3+4\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)\\ & =\left(x+2\right)+3\times 5\\ & =x+17\\ & \equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)\\ & \Rightarrow x=3\end{array}$$ 因此最后一位是3。

同余应用: 弃九法 检验两数相乘结果正确性

内容   假设由普通乘法的运算方法求出整数$a,b$的乘积是$P$，并令 $$\begin{array}{rl}& a=a_n{10}^n+a_{n-1}{10}^{n-1}+\cdots +a_0,0\le a_i<10\\ & b=b_m{10}^m+b_{m-1}{10}^{m-1}+\cdots +b_0,0\le b_j<10\\ & P=c_k{10}^k+c_{k-1}{10}^{k-1}+\cdots +c_0,0\le c_l<10\end{array}$$ 则$P=ab$的必要条件是 $$\left(\sum _{i=0}^n{a}_i\right)\left(\sum _{j=0}^m{b}_j\right)\equiv \left(\sum _{l=0}^k{c}_l\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)$$

例子   考虑$a=28997,b=39495$。 $$\begin{array}{rl}& P_1=1145236415\\ & P_2=1145236515\\ & P_3=1145235615\end{array}$$ 其中$P_2$是$a\times b$的正确结果。下面逐个利用弃九法进行分析。 $$\begin{array}{cc}\begin{array}{rl}& a\equiv 2+8+9+9+7\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\\ & \equiv 1+7\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\\ & \equiv 8\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\end{array}& \begin{array}{rl}& b\equiv 3+9+4+9+5\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\\ & \equiv 12\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\\ & \equiv 3\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\end{array}\end{array}$$ $$8\times 3=24\equiv 6\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)$$

对$P_1$, $$\begin{array}{rl}& P_1\equiv 1+1+4+5+2+3+6+4+1+5\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\\ & \equiv 5\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\end{array}$$ 因此错误答案$P_1$不通过弃九法的检验。

对$P_2$. $$\begin{array}{rl}& P_2\equiv 1+1+4+5+2+3+6+5+1+5\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\\ & \equiv 6\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\end{array}$$ 因此正确答案$P_2$通过弃九法的检验。

对$P_3$, $$\begin{array}{rl}& P_3\equiv 1+1+4+5+2+3+5+6+1+5\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\\ & \equiv 6\left(\mathrm{m}\mathrm{o}\mathrm{d}9\right)\end{array}$$ 因此错误答案$P_3$通过了弃九法的检验。

同余应用: 判断 某整数是否是某大数的因子

例题   证明$641|2^{32}+1$。 证明: $$\begin{array}{rl}& 2^{16}=65536\Rightarrow 2^{16}\equiv 65536\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)\\ & \{\begin{array}{rl}& 65536=641\times 102+154\\ & 154<641\Rightarrow 154=641\times 0+154\end{array}\Rightarrow \text{ 65536}\equiv \text{154}\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)\end{array}$$ 因此有$2^{16}\equiv 154\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)$。 $$\begin{array}{rl}& 2^{32}={\left(2^{16}\right)}^2\equiv {154}^2=23716\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)\\ & \{\begin{array}{rl}& 23716=641\times 36+640\\ & 640<641\Rightarrow 640=641\times 0+640\\ & -1=641\times \left(-1\right)+640\end{array}\Rightarrow 23716\equiv 640\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)\end{array}$$ 因此有$2^{32}\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)\Rightarrow 2^{32}+1\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)\Rightarrow 641|2^{32}+1$。 注：

该题的第一个思想是将整除转化为同余，体现在$$641|2^{32}\text{+1 }\iff {\text{2}}^{32}+1\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)\iff {\text{2}}^{32}\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)$$在①的基础上，该题的第二个思想是不断将大数同绝对值小于除数（641）的整数建立起同余关系，使得计算在笔算层面一直保持在可控量级上；由于${10}^5=641\times 156+2^2$，因此有${10}^5\equiv 2^2\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)\Rightarrow {\left({10}^5\right)}^{16}+1\equiv {\left(2^2\right)}^{16}+1\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)$即 $${10}^{80}+1\equiv 2^{32}+1\left(\mathrm{m}\mathrm{o}\mathrm{d}641\right)$$ 所以也有$641|{10}^{80}+1$。

定理: 设$a$是任一奇数，则有$$a^{2^n}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{n+2}\right)\left(n\ge 1\right)$$

证明   令$G=\left\{2m+1|m\in \mathbb{Z}\right\}$为全体奇数集合。

先证明$n=1$时，$\forall a\in G$，均有$a^{2^1}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{1+2}\right)$即$a^2\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}8\right)$。 $a=2m+1\Rightarrow a^2=4m^2+4m+1=4\left(m^2+m\right)+1$。 $m$是奇数时，$m^2,m$均为奇数，$m^2+m$为偶数，因此$\exists q_1\in \mathbb{Z}$，使得$m^2+m=2q_1$，也就有 $a^2=8q_1+1\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}8\right)$ $m$是偶数时，$m^2,m$均为偶数，$m^2+m$为偶数，因此$\exists q_2\in \mathbb{Z}$，使得$m^2+m=2q_2$，也就有 $a^2=8q_2+1\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}8\right)$$\forall a\in G$，假设$n=k$时有$a^{2^k}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{k+2}\right)$，则有 $$a^{2^k}-1\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{k+2}\right)\Rightarrow 2^{k+2}|a^{2^k}-1$$ 因此$\exists t\in \mathbb{Z},s.t.a^{2^k}-1=2^{k+2}t$，即$a^{2^k}=1+2^{k+2}t$，于是有 $$\begin{array}{c}{a}^{2^{k+1}}={\left(a^{2^k}\right)}^2={\left(1+2^{k+2}t\right)}^2=2^{k+3}\left(2^{k+1}{t}^2+t\right)+1,2^{k+1}{t}^2+t\in \mathbb{Z}\\ \Rightarrow a^{2^{k+1}}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{k+3}\right)\end{array}$$ 由数学第一归纳法最终得到，$\forall a\in G$，$\forall n\in {\mathbb{Z}}_{\ge 1}$，有 $$a^{2^n}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{n+2}\right)$$