同余符号

两个整数a{\displaystyle a}，b{\displaystyle b}，若它们除以正整数m{\displaystyle m}所得的余数相等，则称a{\displaystyle a}，b{\displaystyle b}对于模m{\displaystyle m}同余

记作a≡ ≡ -->b(modm){\displaystyle a\equiv b{\pmod {m}}}

读作a{\displaystyle a}同余于b{\displaystyle b}模m{\displaystyle m}，或读作a{\displaystyle a}与b{\displaystyle b}关于模m{\displaystyle m}同余。

比如26≡ ≡ -->14(mod12){\displaystyle 26\equiv 14{\pmod {12}}}。

同余于的符号是同余相等符号 ≡。统一码值为 U+2261。但因为方便理由，人们有时会把它(误)写为普通等号 (=)。

同余类

如同任何同余关系，对于模n{\displaystyle n}同余是一种等价关系，整数a{\displaystyle a}的等价类是一个集合{… … -->,a− − -->2n,a− − -->n,a,a+n,a+2n,… … -->}{\displaystyle \left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}}，标记为a¯ ¯ -->n{\displaystyle {\overline {a}}_{n}}。由对于模n{\displaystyle n}同余的所有整数组成的这个集合称为同余类（congruence class或residue class）；假若从上下文知道模n{\displaystyle n}，则也可标记为[a]{\displaystyle \displaystyle [a]}。

同余类中的每个元素都可以拿来代表该同余类，称为该同余类的代表数（英语：representative）。

余数系统

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

一个完整余数系统（英语：complete residue system）指的是模n{\displaystyle n}的全部同余类的代表数的集合；因为余数系统中的任二元素不同余于模n{\displaystyle n}，所以它也称为非同余余数的完整系统（英语：complete system of incongruent residues）。例如，模3{\displaystyle 3}有三个同余类[0],[1],[2]{\displaystyle [0],[1],[2]}，其完整余数系统可以是{9,12+1,15+2}{\displaystyle \{9,12+1,15+2\}}。如果该集合是由每个同余类的最小非负整数所组成，亦即{0,1,2,...,n− − -->1}{\displaystyle \{0,1,2,...,n-1\}}，则称该集合为模n{\displaystyle n}的最小余数系统（英语：least residue system）。

模n{\displaystyle n}完整余数系统中，与模n{\displaystyle n}互质的代表数所构成的集合，称为模n{\displaystyle n}的简约余数系统（英语：reduced residue system），其元素个数记为ϕ ϕ -->(n){\displaystyle \phi (n)}欧拉函数拉函数。例如，模6{\displaystyle 6}的简约余数系统为{1,5}{\displaystyle \{1,5\}}或{7,11}{\displaystyle \{7,11\}}。如果模n{\displaystyle n}是质数，那么它的最小简约余数系统是{1,2,...,n− − -->1}{\displaystyle \{1,2,...,n-1\}}，只比最小余数系统少一个0{\displaystyle 0}。

性质

整除性

a≡ ≡ -->b(modm)⇒ ⇒ -->c⋅ ⋅ -->m=a− − -->b,c∈ ∈ -->Z{\displaystyle a\equiv b{\pmod {m}}\Rightarrow c\cdot m=a-b,c\in \mathbb {Z} } （即是说 a 和 b 之差是 m 的倍数） 换句话说，a≡ ≡ -->b(modm)⇒ ⇒ -->m∣ ∣ -->(a− − -->b){\displaystyle a\equiv b{\pmod {m}}\Rightarrow m\mid (a-b)}

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

传递性

a≡ ≡ -->b(modm)b≡ ≡ -->c(modm)}⇒ ⇒ -->a≡ ≡ -->c(modm){\displaystyle \left.{\begin{matrix}a\equiv b{\pmod {m}}\\b\equiv c{\pmod {m}}\end{matrix}}\right\}\Rightarrow a\equiv c{\pmod {m}}}

保持基本运算

a≡ ≡ -->b(modm)c≡ ≡ -->d(modm)}⇒ ⇒ -->{a± ± -->c≡ ≡ -->b± ± -->d(modm)ac≡ ≡ -->bd(modm){\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.} 这性质更可进一步引申成为这样：a≡ ≡ -->b(modm)⇒ ⇒ -->{an≡ ≡ -->bn(modm),∀ ∀ -->n∈ ∈ -->Zan≡ ≡ -->bn(modm),∀ ∀ -->n∈ ∈ -->N0{\displaystyle a\equiv b{\pmod {m}}\Rightarrow {\begin{cases}an\equiv bn{\pmod {m}},\forall n\in \mathbb {Z} \\a^{n}\equiv b^{n}{\pmod {m}},\forall n\in \mathbb {N} ^{0}\end{cases}}}

放大缩小模数

k{\displaystyle k}为正整数，a≡ ≡ -->b(modm){\displaystyle a\equiv b{\pmod {m}}}，当且仅当ka≡ ≡ -->kb(modkm){\displaystyle ka\equiv kb{\pmod {km}}}

除法原理一

若ka≡ ≡ -->kb(modm){\displaystyle ka\equiv kb{\pmod {m}}}且k,m{\displaystyle k,m}互质，则a≡ ≡ -->b(modm){\displaystyle a\equiv b{\pmod {m}}}

除法原理二

每个正整数都可以分解为数个因数的乘积，称为整数分解。例如 15=3× × -->5{\displaystyle 15=3\times 5}，因数 3{\displaystyle 3} 与 5{\displaystyle 5} 都可以整除 15{\displaystyle 15}，记为 3|15{\displaystyle 3|15} 与 5|15{\displaystyle 5|15}。如果 15{\displaystyle 15} 可以整除某正整数 a{\displaystyle a}，亦即 15|a{\displaystyle 15|a}，那么 15{\displaystyle 15} 就是 a{\displaystyle a} 的因数：a=15× × -->b{\displaystyle a=15\times b}，其中 b{\displaystyle b} 为另一因数。a=15× × -->b=(3× × -->5)× × -->b{\displaystyle a=15\times b=(3\times 5)\times b}，因此，15{\displaystyle 15} 的因数也可以整除 a{\displaystyle a}：(3|15)∧ ∧ -->(15|a)⇒ ⇒ -->3|a{\displaystyle (3|15)\wedge (15|a)\Rightarrow 3|a}。

a≡ ≡ -->b(modm){\displaystyle a\equiv b{\pmod {m}}} 等价于 (a− − -->b)≡ ≡ -->0(modm){\displaystyle (a-b)\equiv 0{\pmod {m}}}，也就是 m|(a− − -->b){\displaystyle m|(a-b)}。亦即，如果 m|(a− − -->b){\displaystyle m|(a-b)}，那么它可以写成 a≡ ≡ -->b(modm){\displaystyle a\equiv b{\pmod {m}}}，因此有以下除法原理：

同余关系式

威尔逊定理

(p− − -->1)! ≡ ≡ --> − − -->1 (mod p){\displaystyle (p-1)!\ \equiv \ -1\ ({\mbox{mod}}\ p)}

费马小定理

ap≡ ≡ -->a(modp){\displaystyle a^{p}\equiv a{\pmod {p}}}

欧拉定理

aφ φ -->(n)≡ ≡ -->1(modn){\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}

卡迈克尔函数

aλ λ -->(n)≡ ≡ -->1(modn){\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}

阶乘幂

(x)k≡ ≡ -->x(x− − -->1)(x− − -->2)⋯ ⋯ -->(x− − -->k+1)≡ ≡ -->0(modk!){\displaystyle (x)_{k}\equiv x(x-1)(x-2)\cdots (x-k+1)\equiv 0{\pmod {k!}}}

相关概念

模反元素

a− − -->1a˙ ˙ -->≡ ≡ -->1(modn){\displaystyle a^{-1}{\dot {a}}\equiv 1{\pmod {n}}}

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

原根

存在最小的正整数d使得ad≡ ≡ -->1(modn){\displaystyle a^{d}\equiv 1{\pmod {n}}}成立，且d=φ φ -->(n){\displaystyle d=\varphi (n)}。

同余方程

线性同余方程

ax≡ ≡ -->b(modn){\displaystyle ax\equiv b{\pmod {n}}}

考虑最大公约数，有解时用辗转相除法等方法求解。

线性同余方程组

{a1x≡ ≡ -->b1(modm1)a2x≡ ≡ -->b2(modm2)⋮ ⋮ -->anx≡ ≡ -->bn(modmn){\displaystyle {\begin{cases}a_{1}x\equiv b_{1}{\pmod {m_{1}}}\\a_{2}x\equiv b_{2}{\pmod {m_{2}}}\\\qquad \qquad \vdots \\a_{n}x\equiv b_{n}{\pmod {m_{n}}}\\\end{cases}}}

先求解每一个线性同余方程，再用中国剩余定理解方程组。

二次剩余

x2≡ ≡ -->d(modp){\displaystyle x^{2}\equiv d{\pmod {p}}}

勒让德符号、雅可比符号、克罗内克符号、二次互反律用于判别d是否为模n的二次剩余。

高次剩余

xn≡ ≡ -->d(modp){\displaystyle x^{n}\equiv d{\pmod {p}}}

例子

求自然数a的个位数字，就是求a与哪一个数对于模10同余。

10≡ ≡ -->1(mod 3),10n≡ ≡ -->1(mod 3),10001≡ ≡ -->104+1≡ ≡ -->1+1(mod 3){\displaystyle 10\equiv 1({\textrm {mod}}\ 3),10^{n}\equiv 1({\textrm {mod}}\ 3),10001\equiv 10^{4}+1\equiv 1+1({\textrm {mod}}\ 3)}。

应用

模数算术在数论、群论、环论、纽结理论、抽象代数、计算机代数、密码学、计算机科学、化学、视觉和音乐等学科中皆有应用。

它是数论的立基点之一，与其各个面向都相关。

模数算术经常被用于计算标识符中所使用的校验和，比如国际银行账户号码（IBANs）就用到了模97的算术，来捕获用户在输入银行账户号码时的错误。

于密码学中，模数算术是RSA与迪菲－赫尔曼密钥交换等公钥系统的基础，它同时也提供有限域，应用于椭圆加密，且用于许多对称密钥加密中，包括高级加密标准、国际资料加密算法等。

于计算机科学, 同余被应用于位元运算或其他与固定宽度之循环数据结构相关的操作。

于化学中,CAS号（一个对各种化合物皆异之的识别码）的最后一码为校验码，将CAS号首二部分最后的数字乘上一，下一码乘上二，下一码乘上三以此类推，将所有积加起来再取模10。

在音乐领域，模12用于十二平均律系统。

星期的计算中取模7算术极重要。

更广泛而言，同余在法律、经济（见赛局理论）或其他社会科学领域中也有应用。

范例

以下为快速展示小于63位元无号整数之模数乘法的C程式，且转换过程中不发生溢位。计算 a * b (mod m)之算法:

uint64_tmul_mod(uint64_ta,uint64_tb,uint64_tm){uint64_td=0,mp2=m>>1;inti;if(a>=m)a%=m;if(b>=m)b%=m;for(i=0;imp2)?(d<<1)-m:d<m)d-=m;a<<=1;}returnd%m;}

注释

^1.01.1m∣ ∣ -->x{\displaystyle m\mid x} 表示 m 能整除x，或者说 x 能被 m 整除。

^但是an≡ ≡ -->bn(modm){\displaystyle a^{n}\equiv b^{n}{\pmod {m}}}不能推论a≡ ≡ -->b(modm){\displaystyle a\equiv b{\pmod {m}}}

^(m1,m2,⋯ ⋯ -->,mn){\displaystyle (m_{1},m_{2},\cdots ,m_{n})}表示m1,m2,⋯ ⋯ -->,mn{\displaystyle m_{1},m_{2},\cdots ,m_{n}}的最大公约数。

^[m1,m2,⋯ ⋯ -->,mn]{\displaystyle [m_{1},m_{2},\cdots ,m_{n}]}表示m1,m2,⋯ ⋯ -->,mn{\displaystyle m_{1},m_{2},\cdots ,m_{n}}的最小公倍数。

参见

合同_(数学)

等价关系

模除

不定方程

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。