同余的概念和基本性质

同余的定义和基本性质（定义1，命题1-命题8，定理1-定理2）

定义1

给定一个正整数$m$,把它叫做模。如果用$m$去除任意两个整数$a,b$所得的余数相同，则称$a,b$模$m$同余，记作$a\equiv b(\mathrm{mod}m)$。如果余数不同，则称

$a,b$对模$m$不同余，记作$a\not\equiv b(\mathrm{mod}m)$。

练习1

设$m=6,$试判断下列两个数是否对模$m$同余

1. $1,7$ 可知$1mod6=1,7mod6=1$ 则同余也就是 $1\equiv 7(\mathrm{mod}6)$
2. $17,23$ 这二者的差是$6$，很容易知道也是同余的$17\equiv 23(\mathrm{mod}6)$
3. $23,17$ 一样的 交换了一下位置不影响
4. $112,112$显然同余，数字都一样
5. $0,25$不同余
6. $-37,26$ 对于负数，我们可以转换成整数再取余也就是$5,26$很显然不同余

从练习1中我们可以很容易的知道三个性质

1. 如果$a\equiv b(\mathrm{mod}m)\Rightarrow b\equiv a(\mathrm{mod}m)$
2. $a\equiv a(\mathrm{mod}m)$
3. 如果$\left|a-b\right|=km,$那么$a\equiv b(\mathrm{mod}m)$ 换言之，也就是说如果$m\mid (a-b)$，那么$a\equiv b(\mathrm{mod}m)$

下面来介绍详细的性质

命题1

整数对模$m$同余关系是一个等价关系，即

1. $a\equiv a(\mathrm{mod}m)$ （自反性） 这个是很显然的，刚才的例题也看到了，自己和自己一定是模$m$同余的
2. 若$a\equiv b(\mathrm{mod}m)$，则 $b\equiv a(\mathrm{mod}m)$ (对称性)
3. 若$a\equiv b(\mathrm{mod}m),b\equiv c(\mathrm{mod}m)$,则$a\equiv c(\mathrm{mod}m)$ （传递性）

定理1

整数$m$对模$m$同余的充要条件为$m\mid (a-b)$也即$a=b+mt,t\in \mathbb{Z}$.

换言之$a\equiv b(\mathrm{mod}m)\iff m\mid (a-b)\iff a=b+mt$

命题2

1. 若$a_1\equiv b_1(\mathrm{mod}m),a_2\equiv b_2(\mathrm{mod}m),$则$a_1+a_2\equiv b_1+b_2(\mathrm{mod}m)$
2. 若$a+b\equiv c(\mathrm{mod}m)$,则$a\equiv c-b(\mathrm{mod}m)$

命题3

若$a_1\equiv b_1(\mathrm{mod}m),a_2\equiv b_2(\mathrm{mod}m)$,则$a_1{a}_2\equiv b_1{b}_2(\mathrm{mod}m)$,

特别地

1. 若$a\equiv b(\mathrm{mod}m)$,则$ak\equiv bk(\mathrm{mod}m)$
2. 若$a\equiv b(\mathrm{mod}m)$则$a^n\equiv b^n(\mathrm{mod}m)$

对于2，其实只要连续使用命题3即可得到，这是很容易的。

同余有加减乘，但除法是个意外，需要用到逆元。

下面我们给出定理2

定理2

若$A_{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k}\equiv B_{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k}(\mathrm{mod}m)$,

$x_i\equiv y_i(\mathrm{mod}m),i=1,2,\dots ,k,$

则

$$\sum _{\alpha 1,{\alpha }_2,\dots ,{\alpha }_k}{A}_{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k}{x}_1^{{\alpha }_1}\dots x_k^{{\alpha }_k}=\sum _{\alpha 1,{\alpha }_2,\dots ,{\alpha }_k}{B}_{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k}{y}_1^{{\alpha }_1}\dots y_k^{{\alpha }_k}(\mathrm{mod}m).$$

特别地，若 $a_i\equiv b_i(\mathrm{mod}m),i=1,2,\dots ,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(\mathrm{mod}m).$$

取$k=1,$由$a_{\alpha }=b_{\alpha }(\mathrm{mod}m),x\equiv x(\mathrm{mod}m)$即可证特例

这个证明也好证，把命题2命题3拿来交叉用即可，也不难，就是看着复杂点。

命题4

若$a\equiv b(\mathrm{mod}m),$且$a=a_{1}d,b=b_{1}d,(d,m)=1,$则$a_1\equiv b_1(\mathrm{mod}m)$.

这个有点像除法了，我们可以写的简略一点$a_{1}d\equiv b_{1}d(\mathrm{mod}m),(d,m)=1\Rightarrow a_1\equiv b_1(\mathrm{mod}m)$

是不是就像约分了。 这个体现的就是同余关系式中的除法。

证明：

$a\equiv b(\mathrm{mod}m)\iff m\mid (a-b)=a_{1}d-b_{1}d=d(a_1-b_1),(d,m)=1\Rightarrow m\mid (a_1-b_1)\Rightarrow a_1\equiv b_1(\mathrm{mod}m)$

命题5

1. 若$a\equiv b(\mathrm{mod}m),k>0,$则$ak\equiv bk(\mathrm{mod}mk);$

2. 若$a\equiv b(\mathrm{mod}m),d$是$a,b$及$m$的任一正公因数，则

   $\frac{a}{d}\equiv \frac{b}{d}(\mathrm{mod}\frac{m}{d}).$

下面给出证明

1. $a\equiv b(\mathrm{mod}m)\Rightarrow a=b+mt,ak=bk+mkt\Rightarrow ak\equiv bk(\mathrm{mod}mk)$

2. $d$是$a,b,m$的正公因数,所以有$\frac{a}{d},\frac{b}{d},\frac{m}{d}$都是整数，从而

   $a\equiv b(\mathrm{mod}m)\Rightarrow a=b+mt,\frac{a}{d}=\frac{b}{d}+\frac{m}{d}t\Rightarrow \frac{a}{d}\equiv \frac{b}{d}(\mathrm{mod}\frac{m}{d})$

命题6

若$a\equiv b(\mathrm{mod}{m}_i),i=1,2,\dots ,k,$则

$a\equiv b(\mathrm{mod}[m_1,m_2,\dots ,m_k]).$

证这个的话我们需要用到$a,b$的所有公倍数就是$[a,b]$的所有公倍数

然后还需要$[a_1,a_2]=m_2,[m_2,a_3]=m_3,\dots ,[m_{n-1},a_n]=m_n\Rightarrow [a_1,a_2,\dots ,a_m]=m_n$

于是可以很愉快得到新的一个命题：

$a_1,a_2,\dots ,a_n$的所有公倍数就是$[a_1,a_2,\dots ,a_n]$的所有公倍数。

证明：

$a\equiv b(\mathrm{mod}m)\Rightarrow m_i\mid (a-b)\iff a-b$是$m_i$的倍数$i=1,2,\dots ,k$ 也就是说

$a-b$是$m_1,m_2,\dots ,m_k$的倍数，由此知$a-b$是$[m_1,m_2,\dots ,m_k]$的倍数

从而有$[m_1,m_2,\dots ,m_k]\mid (a-b)\Rightarrow a\equiv b(\mathrm{mod}[m_1,m_2,\dots ,m_k])$

命题7

若$a\equiv b(\mathrm{mod}m),d\mid m,d>0,$则$a\equiv b(\mathrm{mod}d).$

这个的证明还是很容易的，由$a\equiv b(\mathrm{mod}m)\Rightarrow m\mid (a-b),m\mid d\Rightarrow d\mid (a-b)\Rightarrow a\equiv b(\mathrm{mod}d)$

命题8

若$a\equiv b(\mathrm{mod}m),$则$(a,m)=(b,m),$因而若$d$能整数$m$及$a,b$二数之一，则$d$必能整除$a,b$中的另一个。

我们需要用到这个结论: 若$a=bq+c,$则$(a,b)=(b,c)$这个在1.2节的定理3

证明：

$a\equiv b(\mathrm{mod}m)\Rightarrow a=b+mt\Rightarrow (a,m)=(b,m)$

后面那半句我们只证一种情况，另一种类似

若$d\mid m,d\mid a\Rightarrow d\mid (a,m)=(b,m)\Rightarrow d\mid b$另外一种类似可证。

同余的应用（检验因数的方法，弃九法）

检出因数的一些方法（可整除性特征）

引理1

一切能被$3$或$9$整除的充要条件是它的十进制数码的和能被$3$或$9$整除。

这个结论小学应该都知道，我们使用同余来证明一下。

$\forall a\in \mathbb{Z},a=a_n{a}_{n-1}\dots a_1{a}_0$(十进制)$=a_{n}10^n+a_{n-1}10^{n-1}+\cdots +a_{1}10+a_0=\sum _{i=0}^n{a}_{i}10^i$

$10\equiv 1(\mathrm{mod}3)\Rightarrow 10^i\equiv 1^i=1(\mathrm{mod}3),i=1,2,\dots ,n$

$a_{i}10^i\equiv a_i(\mathrm{mod}3)\Rightarrow \sum _{i=0}^n{a}_{i}10^i\equiv \sum _{i=0}^n{a}_i(\mathrm{mod}3)$

证毕。9的话类似可证，把3换成9即可。

例1

$a=5874192$,试判断$a$是否能被$3$或$9$整除

这是显然的，因为数位和为$36$根据引理1显然是成立的。

例2

$a=435693$,试判断$a$是否能被$3$或$9$整除。

$sum=4+3+5+6+9+3=30$显然是可以被$3$整除的，但是不能被$9$整除。

引理2

设正整数

$$a=a_{n}1000^n+a_{n-1}1000^{n-1}+\cdots +a_0,0\le a_i<1000,$$

则$7$（或$11$或$13$）整除$a$的充要条件是$7$（或$11$或$13$）整除

$$(a_0+a_2+\dots )-(a_1+a_3+\dots )=\sum _{i=0}^n(-1{)}^i{a}_i$$.

举个例子

$123456789=123\times 1000^2+456\times 1000^1+789\times 1000^0$

相当于是$1000$进制。 其实就相当于把这个数三位三位的截断。

从低位到高位依次为$a_0,a_1,\dots$

我们先来个具体例子熟悉一下 然后给出它的证明

例3

设$a=637693$,试判断$a$是否能被$7,11$或$13$整除。

$a_0-a_1=693-637=56$这个数可以整除$7$但不能整除$11,13$

所以$a$可以被$7$整除，但不能被$11,13$整除。

例4

设$a=75312289$，试判断$a$是否能被$7,11$或$13$整除。

$a_0-a_1+a_2=289-312+75=52$ 显然这个数可以整除$13$

下面来证明一下这个引理

显然的$1000\equiv (-1)(\mathrm{mod}7)\Rightarrow 1000^i\equiv (-1{)}^i(\mathrm{mod}7)$

从而有$a_{i}1000^i\equiv (-1{)}^i{a}_i(\mathrm{mod}7)\Rightarrow \sum _{i=0}^n{a}_{i}1000^i\equiv \sum _{i=0}^n(-1{)}^i{a}_i(\mathrm{mod}7)$

$11,13$同理可证。

引理3

1. 一个整数能被$2$整除当且仅当它的末位数字是偶数。
2. 一个整数能被$5$整除当且仅当它的末位数字是$0$或$5$。
3. 一个整数能被$4$或$25$整除当且仅当它的末两位数字能被$4$或$25$整除。
4. 一个整除能被$8$或$125$整除当且仅当它的末三位数字能被$8$或$125$整除
5. 一个数字能被$99$整除当且仅当它从个位起两位一段，所有数段之和能被$99$整除。

下面我们来证明一下

1. 设$a=a_n{a}_{n-1}\dots a_1{a}_0=a_n{a}_{n-1}\dots a_1\times 10+a_0,a_0=a-a_n{a}_{n-1}\dots a_1\times 10$

$"\Rightarrow :"$ 已知$2\mid a,2\mid 10,$故有$2\mid 10\cdot a_n{a}_{n-1}\dots a_1$,从而有$2\mid (a-a_n{a}_{n-1}\dots a_1)=a_0$从而我们可以得到它的末位数字$a_0$是一个偶数。

$"\Leftarrow :"$ 已知$a_0$是偶数，$2\mid a,2\mid 10,2\mid 10\cdot a_n{a}_{n-1}\cdots a_1$,从而有$2\mid (a_0+10\times a_n{a}_{n-1}\cdots a_1)=a$

类似的2,3,4同理可证。

下面来证一下5 这个证明和引理2的证明很像

我们可以把$a$写成这样的形式$a=a_{n}100^n+a_{n-1}100^{n-1}+\cdots +a_{1}100+a_0,0\le a_i<100$

$100\equiv 1(\mathrm{mod}99)\Rightarrow 100^i\equiv 1(\mathrm{mod}99)\Rightarrow a_{i}100^i\equiv a_i(\mathrm{mod}99)$

$\Rightarrow \sum _{i=0}^n{a}_{i}100^i\equiv \sum _{i=0}^n{a}_i(\mathrm{mod}99)$

从而$99\mid a\iff 99\mid \sum _{i=0}^n{a}_i=(a_0+a_1+a_2+\cdots +a_n)$

下面看点题

例5

1. 设$2a+b=16$,证明$5ab$能被$4$整除
2. 设$4b+2c+d=32,$证明$3bcd$能被$8$整除

对于1，我们只需要$ab$能被$4$整除即可，下面来证，

$ab=100a+b=8a+2a+b=8a+16=4(2a+4)$这显然是可以被$4$整除的

然后我们看一下2

也只需要证$bcd$能被$8$整除

$bcd=100b+10c+d=96b+8c+4b+2c+d=96b+8c+32=8(12b+c+4)$ 这显然也能被$8$整除

练习2

应用检查因数的方法求出下列各数的标准分解式。

1. $1535625$
2. $1158066$

来看1，$1535625$这个数一看就能被$5$整除，后三位可以被$125$整除

所以$a=1535625=125\times 12285=125\times 5\times 2457=5^4\times 2457=5^4\times 9\times 273$

$=5^4\times 3^2\times 3\times 7\times 13=3^3\times 5^4\times 7\times 13$

然后来看2

首先可以被$2$整除，如何看是否能被$3$整除，加起来是可以的，于是我们可以先一直做除法

然后我们看是否可以被$7$整除，根据引理2，$66-158+1=-91$这是可以被$7$和$13$整除的

于是我们就有了

$1158066=2\times 3^2\times 7^2\times 13\times 101$

下面来看命题9和弃九法（验算两个整数相乘计算结果对错的方法）

命题9

设$abcde,$那么

1. 若$b=d=9,$则$abcde\equiv a+c+e(\mathrm{mod}9)$ 十位和千位
2. 若$b+d=9,$则$abcde=a+c+e(\mathrm{mod}9)$

特别地，若1或2的条件满足，则$9\mid abcde$当且仅当$9\mid (a+c+e).$

$abcde=a+b+c+d+e(\mathrm{mod}9)$

这个证明由引理1可知$abcde=10000a+1000b+100c+10d+e\equiv a+b+c+d+e(\mathrm{mod}9)$

对于1，好证的很，

$b=9,0\equiv -b=-9(\mathrm{mod}9)$

$d=9,0\equiv -d=-9(\mathrm{mod}9)$

由上面三个式子得$abcde+0+0=a+b+c+d+e-b-d$

化简即得。

对于2

$0\equiv b+d=9(\mathrm{mod}9)$

由最上面那个也可以证得。

命题9是可以推广到$n$位数的

这个其实就是说，有9的直接划掉不看，看其他三位数即可

总的来说就是找9以及加和等于9的然后划去看剩下的数

弃九法的本质：一个十进制整数对 9 的余数，等于它的各位数字之和对 9 的余数。

下面来看一个题

例7

计算$a=28997,b=39459,c=1135236415$被$9$除所得的余数

对于$a$,我们只需要看$287$如何我们用第二条把2和7划掉，最后只剩一个$8$，显然余数是$8$。

然后我们来看$b=39459$，最后剩个$3$

最后看$c=1135236415$,划掉之后剩$1121$加起来等于$5$所以余数是$5$。

再看弃九法之前，我们给出这样的一个命题：

如果$ab=p$,则$ab\equiv p(\mathrm{mod}m)$

逆否命题: 如果 $ab\not\equiv p(\mathrm{mod}m)$,那么$ab\ne p$

把这个命题和引理1结合到一起就是所谓的弃九法

弃九法

设某人计算$a\cdot b=P$,且

$$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_{t}10^t+c_{t-1}10^{t-1}+\cdots +c_0,0\le c_k<10$$

则如果

$$(\sum _{i=0}^n{a}_i)(\sum _{j=0}^m{b}_j)\not\equiv \sum _{k=0}^t{c}_k(\mathrm{mod}9)$$

那么所求得的结果是错误的。 这个方法可以判断你做错了，但是不保证你做的一定是对的。

比如 $123\times 3=369$, 我把$369$直接换成$9$也是满足的，但显然我计算错误了。

使用 弃九法 检验加法是否正确的 C++ 代码

#include <bits/stdc++.h>using namespace std;using ll = long long;// 这段 lambda 内部的代码会在 main() 调用之前被执行。
int __OI_INIT__ = []() {ios::sync_with_stdio(0), cin.tie(0);cout.tie(0);cout << fixed << setprecision(12); // 设置输出浮点数默认精度为 12 位。return 0;
}();// 用法
/*int a = 1;double k = 2.0;string s = "hello world";_(a, k, s);输出 --->1 2.000000000000 hello world
*/
template<class... Args> void _(Args... args) {auto _ = [&](auto x) { cout << x << " "; };cout << "--->";int arr[] = {(_(args), 0)...};cout << "\n";
}// 计算数字和（数字和再 mod 9）
// 特殊处理：如果结果是 0，则返回 9（因为 9 ≡ 0 mod 9，但在弃九法中我们通常保留 9）
int digital_root(int n) {if (n == 0) return 0;int r = n % 9;return (r == 0) ? 9 : r;
}// 弃九法验证运算准确性
bool check_by_discarding_9(int a, int b, int user_sum) {int a_root = digital_root(a);int b_root = digital_root(b);int sum_root = digital_root(user_sum);// 使用弃九法return digital_root(a_root * b_root) == sum_root;
}void solve() {int a, b, user_sum;cout << "输入两个加数 a 和 b：" << endl;cin >> a >> b;cout << "输入你计算的积（用于验算）：" << endl;cin >> user_sum;if (check_by_discarding_9(a, b, user_sum)) {cout << "弃九法验算通过：可能正确（不能保证）" << endl;} else {cout << "弃九法验算失败：一定有误！" << endl;}
}int main() {int tt = 1;// cin >> tt;while (tt--) {solve();}}

下面看个例8

例8

设$a=28977,b=39495,$某人计算$a\cdot b=1145236415$,试用弃九法验证此结果是否正确。

显然是错误的啦

我们先用命题9划掉一些数字，易得

$a\equiv 8(\mathrm{mod}9),b\equiv 3(\mathrm{mod}9),ab\equiv 24(\mathrm{mod}9)$

而$c\equiv 5(\mathrm{mod}9)$

这是不正确的。

我们使用上诉程序验证也是如此。