同余

N ⊆ Z ⊆ Q ⊆ R ⊆ C {displaystyle mathbb {N} subseteq mathbb {Z} subseteq mathbb {Q} subseteq mathbb {R} subseteq mathbb {C} }正数 R + {displaystyle mathbb {R} ^{+}} 自然数 N {displaystyle mathbb {N} } 正整数 Z + {displaystyle mathbb {Z} ^{+}} 小数 有限小数 无限小数 循环小数 有理数 Q {displaystyle mathbb {Q} } 代数数 A {displaystyle mathbb {A} } 实数 R {displaystyle mathbb {R} } 复数 C {displaystyle mathbb {C} } 高斯整数 Z [ i ] {displaystyle mathbb {Z} }负数 R − {displaystyle mathbb {R} ^{-}} 整数 Z {displaystyle mathbb {Z} } 负整数 Z − {displaystyle mathbb {Z} ^{-}} 分数 单位分数 二进分数 规矩数 无理数 超越数 虚数 I {displaystyle mathbb {I} } 二次无理数 艾森斯坦整数 Z [ ω ] {displaystyle mathbb {Z} }二元数 四元数 H {displaystyle mathbb {H} } 八元数 O {displaystyle mathbb {O} } 十六元数 S {displaystyle mathbb {S} } 超实数 ∗ R {displaystyle ^{*}mathbb {R} } 大实数 上超实数双曲复数 双复数 复四元数 共四元数（英语：Dual quaternion） 超复数 超数 超现实数质数 P {displaystyle mathbb {P} } 可计算数 基数 阿列夫数 同余 整数数列 公称值规矩数 可定义数 序数 超限数 '"`UNIQ--templatestyles-00000015-QINU`"' p进数 数学常数圆周率 π = 3.141592653 … {displaystyle pi =3.141592653dots } 自然对数的底 e = 2.718281828 … {displaystyle e=2.718281828dots } 虚数单位 i = − 1 {displaystyle i={sqrt {-1}}} 无穷大 ∞ {displaystyle infty }数学上，同余（英语：congruence modulo，符号：≡）是数论中的一种等价关系。当两个整数除以同一个正整数，若得相同余数，则二整数同余。同余是抽象代数中的同余关系的原型。最先引用同余的概念与“≡”符号者为德国数学家高斯。两个整数 a {displaystyle a} ， b {displaystyle b} ，若它们除以正整数 m {displaystyle m} 所得的余数相等，则称 a {displaystyle a} ， b {displaystyle b} 对于模 m {displaystyle m} 同余记作 a ≡ b ( mod m ) {displaystyle aequiv b{pmod {m}}}读作 a {displaystyle a} 同余于 b {displaystyle b} 模 m {displaystyle m} ，或读作 a {displaystyle a} 与 b {displaystyle b} 关于模 m {displaystyle m} 同余。比如 26 ≡ 14 ( mod 12 ) {displaystyle 26equiv 14{pmod {12}}} 。同余于的符号是同余相等符号≡。统一码值为U+2261。如同任何同余关系，对于模 n {displaystyle n} 同余是一种等价关系，整数 a {displaystyle a} 的等价类是一个集合 { … , a − 2 n , a − n , a , a + n , a + 2 n , … } {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 } 。同余类中的每个元素都可以拿来代表该同余类，称为该同余类的代表数（英语：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 ,,} ，其完整余数系统可以是 { 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 ( mod m ) ⇒ c ⋅ m = a − b , c ∈ Z {displaystyle aequiv b{pmod {m}}Rightarrow ccdot m=a-b,cin mathbb {Z} } （即是说 a 和 b 之差是 m 的倍数）换句话说， a ≡ b ( mod m ) ⇒ m ∣ ( a − b ) {displaystyle aequiv b{pmod {m}}Rightarrow mmid (a-b)}同余可以用来检验一个数是否可以整除另外一个数，见整除规则。a ≡ b ( mod m ) b ≡ c ( mod m ) } ⇒ a ≡ c ( mod m ) {displaystyle left.{begin{matrix}aequiv b{pmod {m}}\bequiv c{pmod {m}}end{matrix}}right}Rightarrow aequiv c{pmod {m}}}a ≡ b ( mod m ) c ≡ d ( mod m ) } ⇒ { a ± c ≡ b ± d ( mod m ) a c ≡ b d ( mod m ) {displaystyle left.{begin{matrix}aequiv b{pmod {m}}\cequiv d{pmod {m}}end{matrix}}right}Rightarrow left{{begin{matrix}apm cequiv bpm d{pmod {m}}\acequiv bd{pmod {m}}end{matrix}}right.} 这性质更可进一步引申成为这样： a ≡ b ( mod m ) ⇒ { a n ≡ b n ( mod m ) , ∀ n ∈ Z a n ≡ b n ( mod m ) , ∀ n ∈ N 0 {displaystyle aequiv b{pmod {m}}Rightarrow {begin{cases}anequiv bn{pmod {m}},forall nin mathbb {Z} \a^{n}equiv b^{n}{pmod {m}},forall nin mathbb {N} ^{0}end{cases}}}k为整数，n为正整数， ( k m ± a ) n ≡ ( ± a ) n ( mod m ) {displaystyle (kmpm a)^{n}equiv (pm a)^{n}{pmod {m}}}k {displaystyle k} 为正整数， a ≡ b ( mod m ) {displaystyle aequiv b{pmod {m}}} ，当且仅当 k a ≡ k b ( mod k m ) {displaystyle kaequiv kb{pmod {km}}}若 k a ≡ k b ( mod m ) {displaystyle kaequiv kb{pmod {m}}} 且 k , m {displaystyle k,m} 互质，则 a ≡ b ( mod m ) {displaystyle aequiv b{pmod {m}}}每个正整数都可以分解为数个因数的乘积，称为整数分解。例如 15 = 3 × 5 {displaystyle 15=3times 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=15times b} ，其中 b {displaystyle b} 为另一因数。 a = 15 × b = ( 3 × 5 ) × b {displaystyle a=15times b=(3times 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 ( mod m ) {displaystyle aequiv b{pmod {m}}} 等价于 ( a − b ) ≡ 0 ( mod m ) {displaystyle (a-b)equiv 0{pmod {m}}} ，也就是 m | ( a − b ) {displaystyle m|(a-b)} 。亦即，如果 m | ( a − b ) {displaystyle m|(a-b)} ，那么它可以写成 a ≡ b ( mod m ) {displaystyle aequiv b{pmod {m}}} ，因此有以下除法原理：( p − 1 ) !   ≡   − 1   ( mod   p ) {displaystyle (p-1)! equiv -1 ({mbox{mod}} p)}a p ≡ a ( mod p ) {displaystyle a^{p}equiv a{pmod {p}}}a φ ( n ) ≡ 1 ( mod n ) {displaystyle a^{varphi (n)}equiv 1{pmod {n}}}a λ ( n ) ≡ 1 ( mod n ) {displaystyle a^{lambda (n)}equiv 1{pmod {n}}}( x ) k ≡ x ( x − 1 ) ( x − 2 ) ⋯ ( x − k + 1 ) ≡ 0 ( mod k ! ) {displaystyle (x)_{k}equiv x(x-1)(x-2)cdots (x-k+1)equiv 0{pmod {k!}}}( m n ) ≡ ∏ i = 0 k ( m i n i ) ( mod p ) , {displaystyle {binom {m}{n}}equiv prod _{i=0}^{k}{binom {m_{i}}{n_{i}}}{pmod {p}},}( m + p k + [ l o g p n ] n ) ≡ ( m n ) ( mod p k ) {displaystyle {binom {m+p^{k+}}{n}}equiv {binom {m}{n}}{pmod {p^{k}}}}设 N = ∏ i p i k i {displaystyle N=prod _{i}p_{i}^{k_{i}}} ，则 ( m + L ( n , N ) n ) ≡ ( m n ) ( mod N ) {displaystyle {binom {m+L(n,N)}{n}}equiv {binom {m}{n}}{pmod {N}}} ，其中 L ( n , N ) = ∏ i p i k i + [ l o g p n ] = N ∏ i p i [ l o g p n ] {displaystyle L(n,N)=prod _{i}p_{i}^{k_{i}+}=Nprod _{i}p_{i}^{}}a − 1 a ˙ ≡ 1 ( mod n ) {displaystyle a^{-1}{dot {a}}equiv 1{pmod {n}}}可用辗转相除法、欧拉定理、卡迈克尔函数求解。存在最小的正整数d使得 a d ≡ 1 ( mod n ) {displaystyle a^{d}equiv 1{pmod {n}}} 成立，且 d = φ ( n ) {displaystyle d=varphi (n)} 。a x ≡ b ( mod n ) {displaystyle axequiv b{pmod {n}}}考虑最大公约数，有解时用辗转相除法等方法求解。{ a 1 x ≡ b 1 ( mod m 1 ) a 2 x ≡ b 2 ( mod m 2 ) ⋮ a n x ≡ b n ( mod m n ) {displaystyle {begin{cases}a_{1}xequiv b_{1}{pmod {m_{1}}}\a_{2}xequiv b_{2}{pmod {m_{2}}}\qquad qquad vdots \a_{n}xequiv b_{n}{pmod {m_{n}}}\end{cases}}}先求解每一个线性同余方程，再用中国剩余定理解方程组。x 2 ≡ d ( mod p ) {displaystyle x^{2}equiv d{pmod {p}}}勒让德符号、雅可比符号、克罗内克符号、二次互反律用于判别d是否为模n的二次剩余。x n ≡ d ( mod p ) {displaystyle x^{n}equiv d{pmod {p}}}模数算术在数论、群论、环论、纽结理论、抽象代数、计算机代数、密码学、计算机科学、化学、视觉和音乐等学科中皆有应用。它是数论的立基点之一，与其各个面向都相关。模数算术经常被用于计算标识符中所使用的校验和，比如国际银行账户号码（IBANs）就用到了模97的算术，来捕获用户在输入银行账户号码时的错误。于密码学中，模数算术是RSA与迪菲－赫尔曼密钥交换等公钥系统的基础，它同时也提供有限域，应用于 椭圆加密，且用于许多对称密钥加密中，包括高级加密标准、国际资料加密算法等。于计算机科学, 同余被应用于位元运算或其他与固定宽度之循环数据结构相关的操作。于化学中, CAS号（一个对各种化合物皆异之的识别码）的最后一码为校验码，将CAS号首二部分最后的数字乘上一，下一码乘上二，下一码乘上三以此类推，将所有积加起来再取模10。在音乐领域，模12用于十二平均律系统。星期的计算中取模7算术极重要。更广泛而言，同余在法律、经济（见赛局理论）或其他社会科学领域中也有应用。以下为快速展示小于63位元无号整数之模数乘法的C程式，且转换过程中不发生溢位。计算 a * b (mod m)之算法: