本页使用了标题或全文手工转换

同余

维基百科,自由的百科全书
跳到导航 跳到搜索
各种各样的
基本

NumberSetinC.svg

延伸
其他

圆周率
自然对数的底
虚数单位
无穷大

数学上,同余(英语:congruence modulo[1]符号:≡)是数论中的一种等价关系[2]。当两个整数以同一个整数,若得相同余数,则二整数同余。同余是抽象代数中的同余关系的原型[3]。最先引用同余的概念与“≡”符号者为德国数学家高斯

同余符号

两个整数,若它们以正整数所得的余数相等,则称对于模同余

记作

读作同余于,或读作关于模同余。

比如

同余于的符号是同余相等符号。统一码值为U+2261

同余类

如同任何同余关系,对于模同余是一种等价关系,整数等价类是一个集合,标记为。由对于模同余的所有整数组成的这个集合称为同余类congruence classresidue class);假若从上下文知道模,则也可标记为

同余类中的每个元素都可以拿来代表该同余类,称为该同余类的代表数(英语:representative[4]

余数系统

余数系统(英语:residue system)亦即模同余类的代表数的集合,通常使用的代表数是最小非负整数,因为它是除法中的应当余数。要注意的是,对于同一个模数,不同的同余类不等价,亦即,属于不同同余类的整数不同余于模数,或者说,模余数系统中的任二元素不同余于模;而且,整数域中的每个整数只属于模数的一个同余类,因为模将整数域划分为互斥区块,每个区块是一个同余类。

一个完整余数系统(英语:complete residue system)指的是模的全部同余类的代表数的集合;因为余数系统中的任二元素不同余于模,所以它也称为非同余余数的完整系统(英语:complete system of incongruent residues)。例如,模有三个同余类,其完整余数系统可以是。如果该集合是由每个同余类的最小非负整数所组成,亦即,则称该集合为模最小余数系统(英语:least residue system)。

完整余数系统中,与模互质的代表数所构成的集合,称为模简约余数系统(英语:reduced residue system),其元素个数记为,亦即欧拉函数。例如,模的简约余数系统为。如果模质数,那么它的最小简约余数系统是,只比最小余数系统少一个

性质

整除性

(即是说 a 和 b 之差是 m 的倍数)
换句话说,[注 1]

同余可以用来检验一个数是否可以整除另外一个数,见整除规则

传递性

保持基本运算


时,则为等量加法、减法:
这性质更可进一步引申成为这样:
[注 2]

放大缩小底数

k为整数,n为正整数,

放大缩小模数

为正整数,当且仅当

除法原理一

互质,则

除法原理二

每个正整数都可以分解为数个因数的乘积,称为整数分解。例如 ,因数 都可以整除 ,记为 。如果 可以整除某正整数 ,亦即 ,那么 就是 的因数:,其中 为另一因数。,因此, 的因数也可以整除

等价于 ,也就是 。亦即,如果 ,那么它可以写成 ,因此有以下除法原理:

的因数也可以整除 。亦即,倍数。因为 ,所以

[注 1]
现假设 可以整除 的倍数 。如果 互质(记为 ),那么 必定可以整除
[注 3]
如果 而且 ,那么 最小公倍数必定可以整除 ,记为 。这可以推广成以下性质:
[注 4]
上面的最后一个性质可以使用算术基本定理集合来解释。一个大于1的正整数 可以分解为一串质数幂的乘积: 两两相异,且),令 为所有能整除 的质数幂的集合,即 。设 为正整数,则 整除 ,当且仅当 子集。令 ,则联集必定也是 的子集。取这个联集中幂次最高的各个元素,它们的乘积就是 最小公倍数。事实上,有 ,所以 也能够整除

同余关系式

威尔逊定理

费马小定理

欧拉定理

卡迈克尔函数

阶乘幂

卢卡斯定理

组合数最小周期

,则,其中[5]

相关概念

模反元素

可用辗转相除法欧拉定理卡迈克尔函数求解。

原根

存在最小的正整数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;
}


注释

参考文献

参见