同余性质

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

1. 甲：$a\equiv a\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$
2. 乙：$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)$
3. 丙：$\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)$
4. 丁：若$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)$，则
   1. $a_1+a_2\equiv b_1+b_2\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)$
   2. $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)$
5. 戊：$\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}$
6. 己：$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)$
7. 庚：$\{\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}$
8. 辛：$\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)$
9. 壬：$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)$
10. 癸：$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$

1. $0$是任意非零整数的倍数；
2. 任意整数都不是$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. 任意整数都是$1$的倍数。
   
   

$2$

1. 个位数是偶数$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$

1. 数字和是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

1. 末尾两位是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

1. 个位数是$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

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

7

1. 从右至左，每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

1. 后三位是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

1. 各位数的数字之和是$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

1. 个位数是$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

1. 从右至左，每三个数字一组，交错和是$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}$$

2. 从右至左，各位数交错和是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

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

13

1. 从右至左，每三个数字一组，交错和是$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

1. 从右至左，每三个数字一组，其和是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

1. 从右至左，每两个数字一组，交错和是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}$$

2. 从右至左，每四个数字一组，其和是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}$$
   
   

例子

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

   1. 个位数为$3$，非偶，因此非2倍数，（当然也非4，8倍数）。
   2. $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倍数）。
   3. $4\nmid 93\Rightarrow$非4倍数。
   4. 个位数非0非5，因此非5倍数，非10倍数。
   5. 非2倍数，非3倍数，因此非6倍数。
   6. $693-637=56,7|56,11\nmid 56,13\nmid 56$，因此是7倍数，非11倍数，非13倍数。
   7. 非3倍数，非4倍数，因此非12倍数。
      
      

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

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

3. 应用检查因数的方法写出$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$$

4. 应用检查因数的方法写出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$表示两个月前的年份（的后两位）。

例子

1. 计算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}$$
   因此这一天是星期二。

2. 计算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码不满上述式子，则一定为非正版。

例子

1. 学校购买的《初等数论（第四版）》（闵嗣鹤 严士健 编）的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)$$

2. 某本书的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)​
   因此该书一定为盗版书。

3. 某正版书的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(\cancel{-1}\cancel{-2}-3\cancel{+2}+5+\cancel{1}+x\right)+3\times \left(\cancel{-3}+0-1+2\cancel{+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+\cancel{9}+\cancel{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+\cancel{9}+4+\cancel{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)$$

1. 对$P_1$,
   $$\begin{array}{rl}& P_1\equiv 1+1+\cancel{4+5}+2+\cancel{3+6}+\cancel{4}+1+\cancel{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$不通过弃九法的检验。

2. 对$P_2$.
   $$\begin{array}{rl}& P_2\equiv \cancel{1+1}+\cancel{4+5}+\cancel{2}+\cancel{3+6}+\cancel{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$通过弃九法的检验。

3. 对$P_3$,
   $$\begin{array}{rl}& P_3\equiv \cancel{1+1}+\cancel{4+5}+\cancel{2}+\cancel{3}+\cancel{5}+\cancel{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$。
注：

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)$$
2. 在①的基础上，该题的第二个思想是不断将大数同绝对值小于除数（641）的整数建立起同余关系，使得计算在笔算层面一直保持在可控量级上；
3. 由于${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\}$为全体奇数集合。

1. 先证明$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)$
2. $\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)$$