同余(英语:Congruence modulo[1],符号:≡)在数学中是指数论中的一种等价关系[2]。当两个整数除以同一个正整数,若得相同余数,则二整数同余。同馀是抽象代数中的同馀关系的原型[3]。最先引用同余的概念与“≡”符号者为德国数学家高斯。
同余符号
两个整数
,
,若它们除以正整数
所得的余数相等,则称
,
对于模
同余
记作
读作
同余于
模
,或读作
与
关于模
同余。
比如
。
同馀于的符号是同馀相等符号≡。统一码值为U+2261
。
同馀类
如同任何同余关系,对于模
同余是一种等价关系,整数
的等价类是一个集合
,标记为
。由对于模
同馀的所有整数组成的这个集合称为同余类(congruence class或residue class);假若从上下文知道模
,则也可标记为
。
同余类中的每个元素都可以拿来代表该同余类,称为该同余类的代表数(英语:representative)[4]。
剩馀系
剩馀系[5][6](英语:residue system)亦即模
同馀类的代表数的集合,通常使用的代表数是最小非负整数,因为它是除法中的应当馀数。要注意的是,对于同一个模数
,不同的同馀类不等价,亦即,属于不同同馀类的整数不同馀于模数
,或者说,模
剩馀系中的任二元素不同馀于模
;而且,整数域中的每个整数只属于模数
的一个同馀类,因为模
将整数域划分为互斥区块,每个区块是一个同馀类。
一个完全剩馀系(英语:complete residue system)指的是模
的全部同馀类的代表数的集合;因为剩馀系中的任二元素不同馀于模
,所以它也称为非同馀馀数的完整系统(英语:complete system of incongruent residues)。例如,模
有三个同馀类
,其完全剩馀系可以是
。如果该集合是由每个同馀类的最小非负整数所组成,亦即
,则称该集合为模
的最小剩馀系(英语:least residue system)。
模
完全剩馀系中,与模
互质的代表数所构成的集合,称为模
的简约剩馀系(英语:reduced residue system),其元素个数记为
,亦即欧拉函数。例如,模
的简约剩馀系为
或
。如果模
是质数,那么它的最小简约剩馀系是
,只比最小剩馀系少一个
。
性质
整除性
(即是说 a 和 b 之差是 m 的倍数)
换句话说,
[注 1]
同余可以用来检验一个数是否可以整除另外一个数,见整除规则。
传递性
保持基本运算
![{\displaystyle \left.{\begin{matrix}a\equiv b{\pmod {m}}\\c\equiv d{\pmod {m}}\end{matrix}}\right\}\Rightarrow \left\{{\begin{matrix}a\pm c\equiv b\pm d{\pmod {m}}\\ac\equiv bd{\pmod {m}}\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82cc41be2ed3f5dbea92f66220befb60193e26c2)
当
时,则为等量加法、减法:![{\displaystyle a\pm c\equiv b\pm c{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb522cc054afb4b94bb0e56a689be1fc0026c157)
这性质更可进一步引申成为这样:
[注 2]
其中
为任意整系数多项式函数。
放大缩小底数
k为整数,n为正整数,
放大缩小模数
为正整数,
,若且唯若
除法原理一
若
且
互质,则
除法原理二
每个正整数都可以分解为数个因数的乘积,称为整数分解。例如
,因数
与
都可以整除
,记为
与
。如果
可以整除某正整数
,亦即
,那么
就是
的因数:
,其中
为另一因数。
,因此,
的因数也可以整除
:
。
等价于
,也就是
。亦即,如果
,那么它可以写成
,因此有以下除法原理:
的因数也可以整除
。亦即,
是
的倍数:
,
。因为
,所以
。
![{\displaystyle a\equiv b{\pmod {cn}}\Rightarrow a\equiv b{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/beeab72ed2e40954c58cd3e8f0fd073fc9247dde)
[注 1]
- 现假设
可以整除
的倍数
。如果
和
互质(记为
),那么
必定可以整除
:
。
[注 3]
- 如果
而且
,那么
与
的最小公倍数必定可以整除
,记为
。这可以推广成以下性质:
[注 4]
- 上面的最后一个性质可以使用算术基本定理与集合来解释。一个大于1的正整数
可以分解为一串质数幂的乘积:
(
两两相异,且
),令
为所有能整除
的质数幂的集合,即
。设
为正整数,则
整除
,当且仅当
是
的子集。令
且
,则
与
的联集必定也是
的子集。取这个联集中幂次最高的各个元素,它们的乘积就是
与
的最小公倍数
。事实上,有
,所以
也能够整除
。
同余关系式
威尔逊定理
费马小定理
欧拉定理
卡迈克尔函数
阶乘幂
卢卡斯定理
组合数最小周期
设
,则
,其中
[7]
相关概念
模反元素
可用辗转相除法、欧拉定理、卡迈克尔函数求解。
原根
存在最小的正整数d使得
成立,且
。
同余方程
线性同余方程
考虑最大公约数,有解时用辗转相除法等方法求解。
线性同余方程组
先求解每一个线性同余方程,再用中国剩余定理解方程组。
二次剩余
勒让德符号、雅可比符号、克罗内克符号、二次互反律用于判别d是否为模n的二次剩余。
高次剩馀
例子
- 求自然数a的个位数字,就是求a与哪一个数对于模10同余。
。
应用
模数算术在数论、群论、环论、纽结理论、抽象代数、计算机代数、密码学、计算机科学、化学、视觉和音乐等学科中皆有应用。
它是数论的立基点之一,与其各个面向都相关。
模数算术经常被用于计算标识符中所使用的校验和,比如国际银行账户号码(IBANs)就用到了模97的算术,来捕获用户在输入银行帐户号码时的错误。
于密码学中,模数算术是RSA与迪菲-赫尔曼密钥交换等公钥系统的基础,它同时也提供有限域,应用于 椭圆加密,且用于许多对称密钥加密中,包括高级加密标准、国际资料加密演算法等。
于计算机科学, 同馀被应用于位元运算或其他与固定宽度之循环资料结构相关的操作。
于化学中, CAS号(一个对各种化合物皆异之的识别码)的最后一码为校验码,将CAS号首二部分最后的数字乘上一,下一码乘上二,下一码乘上三以此类推,将所有积加起来再取模10。
在音乐领域,模12用于十二平均律系统。
星期的计算中取模7算术极重要。
更广泛而言,同馀在法律、经济(见赛局理论)或其他社会科学领域中也有应用。
范例
以下为快速展示小于63位元无号整数之模数乘法的C程式,且转换过程中不发生溢位。计算 a * b (mod m)之演算法:
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
uint64_t d = 0, mp2 = m >> 1;
int i;
if (a >= m) a %= m;
if (b >= m) b %= m;
for (i = 0; i < 64; ++i)
{
d = (d > mp2) ? (d << 1) - m : d << 1;
if (a & 0x8000000000000000ULL)
d += b;
if (d > m) d -= m;
a <<= 1;
}
return d%m;
}
注释
参考文献
参见