Modular Arithmetic 模算术
我们都见过时钟，在时钟上有12个刻度。假设某天晚上时针指向6的位置，那么它表示的是晚上六点钟，可是到了第二天早上，当时针再次指向6时，它表示的又是早上六点钟。
在上述例子中，我们实际上是用同一个刻度来表示两个不同的“六点钟”，这就是模算术的基本思路–用同一个刻度表示不同的值（也可以用轮回来理解）。
模算术的定义
令 a a a， b b b和 n n n为整数且 n > 0 n>0 n>0，那么当且仅当 n n n可以整除 ( a − b ) (a-b) (a−b)时， a a a和 b b b是模 n n n同余的，写作：
a ≡ b ( m o d n ) ⟺ n ∣ ( a − b ) a \equiv b\ (\mathrm{mod} \ n) \iff n|(a-b) a≡b (mod n)⟺n∣(a−b)
这里的 n ∣ ( a − b ) n|(a-b) n∣(a−b) 表示 k n = ( a − b ) , k kn = (a-b), k kn=(a−b),k为整数。
什么是同余 Congruence Modulo
当 k n = ( a − b ) kn = (a-b) kn=(a−b)时， a a a和 b b b可写为：
a = p n + r b = q n + r \begin{aligned} a &= pn+r \\ b &= qn+r \\ \end{aligned} ab=pn+r=qn+r
r r r是他们共同的余数， n n n为同余的模数（也就是除数）。
例如： 7 ( = 1 × 6 + 1 ) 7( = 1\times6+1) 7(=1×6+1)和 13 ( = 2 × 6 + 1 ) 13 ( = 2 \times 6 + 1) 13(=2×6+1)对模数6同余。 类似的数还有19，25，31， … \dots …， ( n × 6 + 1 ) (n\times 6 + 1) (n×6+1)。将这些数画在数轴上，我们可以发现在每一个长度为6的区间上，都只有一个这样的数存在，并且他们都出现在各自区间内“相同的位置”上。因此我们可以在不同区间内用同一个刻度表示不同的值。
讯享网
由对于模 n n n同余的所有整数组成的集合称为同余类。
同余类 Congruence Class
给定任意整数 b > 0 b>0 b>0，我们可以将数轴上的整数划分到长度为 b b b的区间内。对于 a ∈ [ 0 , b − 1 ] a \in [0,b-1] a∈[0,b−1]，集合 { a + k b } \{a + kb\} {
a+kb}的所有数对于模 b b b同余，余数为 a a a，构成一个同余类，记作：
[ a ] b = { a + k b ∣ k ∈ Z } [a]_b = \{a+kb | k \in \mathbb{Z} \} [a]b={
a+kb∣k∈Z}
模算术的规则
- 加法：如果有 a ≡ c ( m o d n ) a \equiv c \ (\mathrm{mod} \ n) a≡c (mod n)和 b ≡ d ( m o d n ) b \equiv d \ (\mathrm{mod} \ n) b≡d (mod n)，那么 a + b ≡ c + d ( m o d n ) a+b \equiv c+d\ (\mathrm{mod} \ n) a+b≡c+d (mod n)
- 乘法：如果有 a ≡ c ( m o d n ) a \equiv c\ (\mathrm{mod} \ n) a≡c (mod n)和 b ≡ d ( m o d n ) b \equiv d \ (\mathrm{mod} \ n) b≡d (mod n)，那么 a b ≡ c d ( m o d n ) ab \equiv cd \ (\mathrm{mod} \ n) ab≡cd (mod n)
- ∀ a , a ≡ a ( m o d n ) \forall a, a \equiv a\ (\mathrm{mod}\ n) ∀a,a≡a (mod n)
- 如果有 a ≡ b ( m o d n ) a \equiv b\ (\mathrm{mod}\ n) a≡b (mod n)，那么 b ≡ a ( m o d n ) b \equiv a\ (\mathrm{mod}\ n) b≡a (mod n)
- 如果有 a ≡ b ( m o d n ) a \equiv b\ (\mathrm{mod}\ n) a≡b (mod n)和 b ≡ c ( m o d n ) b \equiv c\ (\mathrm{mod}\ n) b≡c (mod n)，那么 a ≡ c ( m o d n ) a \equiv c\ (\mathrm{mod}\ n) a≡c (mod n)
- 如果有 a ≡ b ( m o d n ) a \equiv b\ (\mathrm{mod}\ n) a≡b (mod n)和 n ≡ 0 ( m o d m ) n \equiv 0\ (\mathrm{mod}\ m) n≡0 (mod m)，那么 a ≡ b ( m o d m ) a \equiv b\ (\mathrm{mod}\ m) a≡b (mod m)
- 如果有 a ≡ b ( m o d n ) a \equiv b\ (\mathrm{mod}\ n) a≡b (mod n)，那么 a m ≡ b m ( m o d n ) am \equiv bm\ (\mathrm{mod}\ n) am≡bm (mod n)和 a m ≡ b m ( m o d n ) a^m \equiv b^m\ (\mathrm{mod}\ n) am≡bm (mod n)
模的倒数 Multiplicative Inverse
对于 a ≢ 0 ( m o d n ) a \not \equiv 0\ (\mathrm{mod} \ n) a≡0 (mod n)，若有整数 a ′ a' a′满足 a a ′ ≡ 1 ( m o d n ) aa' \equiv 1\ (\mathrm{mod} \ n) aa′≡1 (mod n)，则称 a ′ a' a′为 a a a的倒数。例如： 2 × 5 ≡ 1 ( m o d 3 ) 2 \times 5 \equiv 1 \ (\mathrm{mod} \ 3) 2×5≡1 (mod 3)，所以 a ′ = 5 a' = 5 a′=5是整数 2 ( m o d 3 ) 2\ (\mathrm{mod} \ 3) 2 (mod 3)的倒数（反之亦然）。
并不是所有的整数对于任意模数都有倒数。对于 a ( m o d n ) a\ (\mathrm{mod} \ n) a (mod n)，如果整数 a a a和 n n n不互质，那么 a a a就没有对于模数 n n n的倒数。
中国余数定理
古时有一位将军统领着一支1500人的军队，一场大战过后，大约400~500人死亡。为了统计剩下的人数，将军让士兵们站成方阵。当剩下的人3个站成一行时，多余2个人。当剩下的人5个站成一行时，多余4个人。当剩下的人7个站成一行时，多余6个人。那么这支军队总共还有多少士兵？
这个问题实际上就是求解同余方程组
{ c 1 x ≡ d 1 ( m o d m 1 ) c 2 x ≡ d 2 ( m o d m 2 ) … c k x ≡ d k ( m o d m k ) \left\{ \begin{aligned} c_1x \equiv d_1\ (\mathrm{mod} \ m_1) \\ c_2x \equiv d_2\ (\mathrm{mod} \ m_2) \\ \dots \\ c_kx \equiv d_k\ (\mathrm{mod} \ m_k) \end{aligned} \right. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧c1x≡d1 (mod m1)c2x≡d2 (mod m2)…ckx≡dk (mod mk)
先来思考如何求解 a x ≡ b ( m o d n ) ax \equiv b \ (\mathrm{mod} \ n) ax≡b (mod n)，
- 当 g c d ( a , n ) = 1 \mathrm{gcd}(a, n) = 1 gcd(a,n)=1时： a a a和 n n n互质，因此存在 a ′ a' a′使得 a a ′ ≡ 1 ( m o d n ) aa' \equiv 1 \ (\mathrm{mod} \ n) aa′≡1 (mod n)。我们对式子两边同乘 a ′ a' a′，得
x ≡ a ′ b ( m o d n ) x \equiv a'b \ (\mathrm{mod} \ n) x≡a′b (mod n) - 当 g c d ( a , n ) = c > 1 \mathrm{gcd}(a, n) = c > 1 gcd(a,n)=c>1时：
2.1. 如果 c c c可以整除 b b b：对于 a x ≡ b ( m o d n ) ax \equiv b \ (\mathrm{mod} \ n) ax≡b (mod n)可得
a x ≡ b ( m o d n ) ⟺ a x = b + n k ⟺ a 1 c x = b 1 c + n 1 c k ⟺ a 1 x = b 1 x + n 1 k \begin{aligned} &ax \equiv b \ (\mathrm{mod} \ n) \\ \iff &ax = b + nk \\ \iff &a_1cx = b_1c + n_1ck \\ \iff &a_1x = b_1x + n_1k \\ \end{aligned} ⟺⟺⟺ax≡b (mod n)ax=b+nka1cx=b1c+n1cka1x=b1x+n1k
此时 a 1 , n 1 a_1, n_1 a1,n1互质，因此可以归为 a , n a, n a,n互质一类。
2.2. 如果 c c c不能整除 b b b：
a x ≡ b ( m o d n ) ⟺ a x = b + n k ⟺ a 1 c x = b + n 1 c k ⟺ b = c ( a 1 x − n 1 k ) \begin{aligned} &ax \equiv b \ (\mathrm{mod} \ n) \\ \iff &ax = b + nk \\ \iff &a_1cx = b + n_1ck \\ \iff &b = c(a_1x-n_1k) \\ \end{aligned} ⟺⟺⟺ax≡b (mod n)ax=b+nka1cx=b+n1ckb=c(a1x−n1k)
与假设矛盾，无解。
经过化简（当然，也存在无法化简的情况）以后，方程组可写为
{ x ≡ a 1 ( m o d n 1 ) x ≡ a 2 ( m o d n 2 ) … x ≡ a k ( m o d n k ) \left\{ \begin{aligned} x \equiv a_1\ (\mathrm{mod} \ n_1) \\ x \equiv a_2\ (\mathrm{mod} \ n_2) \\ \dots \\ x \equiv a_k\ (\mathrm{mod} \ n_k) \end{aligned} \right. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧x≡a1 (mod n1)x≡a2 (mod n2)…x≡ak (mod nk)
假设 n 1 , n 2 , … , n k n_1, n_2, \dots, n_k n1,n2,…,nk之间两两互质，则该方程组对于模 N = n 1 n 2 … n k N = n_1n_2\dots n_k N=n1n2…nk有唯一解，解为
x ≡ ( N 1 N 1 ′ a 1 + N 2 N 2 ′ a 2 + ⋯ + N k N k ′ a k ) ( m o d N ) x \equiv (N_1N_1'a_1 + N_2N_2'a_2 + \dots + N_kN_k'a_k) (\mathrm{mod} \ N) x≡(N1N1′a1+N2N2′a2+⋯+NkNk′ak)(mod N)
其中 N i = N n i N_i = \frac{N}{n_i} Ni=niN， N i ′ N_i' Ni′为 N i N_i Ni对于模 n i n_i ni的倒数。
取模运算
在计算机中，给定整数 a a a， b b b，取模运算就是求 a a a除以 b b b的余数： a a a% b b b
关于取余运算的实现逻辑可参考汇编除法原理
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/62351.html