模运算总结

Published on 2016-02-29

模运算是一个高深的地方,初来乍到,还是写一下为敬QAQ。。。

记号

我们把 aa 除以 mm 所得的余数记作 amodma \bmod m
如果 amodm=bmodma \bmod m = b \bmod m,即 aa, bb 除以 mm 所得的余数相等,那么我们记作:

ab(modm) a\equiv b\pmod{m}

基本性质

模运算有一些基本性质:如果 ab(modm)a\equiv b\pmod{m} 且有 cd(modm)c\equiv d\pmod{m},那么下面的模运算律成立:

a+cb+d(modm)acbd(modm)a×cb×d(modm) \begin{aligned}a + c\equiv b + d\pmod{m}\\a - c\equiv b - d\pmod{m}\\a \times c\equiv b \times d\pmod{m}\end{aligned}

这就是我们平常经常利用的性质,如果答案对一个数取模,那么模了再加,乘,减都是不影响答案的。特别注意除法是没有这个性质的!

剩余系

如果一个剩余系中包含了这个正整数 nn 所有可能的余数(一般地,对于任意正整数 nn,有 nn 个余数:0,1,2,...,n10,1,2,...,n-1),那么就被称为是模 nn 的一个完全剩余系,记作 ZnZ_n;而简化剩余系就是完全剩余系中与 nn 互素的数的那些元素,记作 ZnZ_n^*
ZnZ_n 里面的每一个元素代表所有模 nn 意义下与它同余的整数。例如 n=5n = 5 时,Z5Z_5 的元素 33 实际上代表了 3,8,13,18,....,5k+3(kN)3, 8, 13, 18,....,5k + 3(k\in N) 这些模 5533 的数。 我们把满足同余关系的所有整数看作一个同余等价类
自然地,在 ZnZ_n 中的加法,减法,乘法,结果全部要在模 nn 意义下面了,例如在 Z5Z_5 中,3+2=0,3×2=13 + 2 = 0, 3 \times 2 = 1

逆元

在实数运算下面,如果 ab=1ab = 1,那么可以说 a,ba, b 互为倒数,它们相乘永远得 11。不幸的是,modm\bmod m 的运算下面也有倒数的概念,而且要恐怖的多。
如果在 ZnZ_n 中的两元素 aa, bb 满足 ab=1ab = 1,比如在 Z15Z_{15} 中,713=17*13 = 1,那么我们就说 a,ba,b 互为模 nn 意义下乘法的逆!记作 a=b1,b=a1a = b^{-1}, b = a^{-1}
我们知道,除以一个数的等于乘这个数的倒数,在模运算中,除以一个数等于乘上这个数的逆(如果这个数存在乘法逆的话)!举例说明,在 Z5Z_5 中,4÷3=4×31=4×2=34 \div 3 = 4 \times 3^{-1} = 4 \times 2 = 3
看上有点神乎其神,4÷34 \div 3 甚至不是整数,怎么可能答案是 33???别忘了,剩余系中的每一个元素都对应一个同余等价类,所以 4÷3=34 \div 3 = 3 的实际含义是:“假定有两个整数 a,ba, b, 满足 ab\frac{a}{b} 是整数,且 a,ba, b 除以 55 的余数分别是 4433,那么 ab\frac{a}{b} 除以 55 的余数等于 33”,比如 a=9,b=3a = 9, b = 3 时就成立。

线性模方程

线性模方程是下面这个玩意,其中 xx 是未知数,我们要干的事情就是求出 xxZmZ_m 中的解集。

axb(modm) ax\equiv b \pmod{m}

因为同余,所以有 axb=ymax - b = ym,即 axmy=bax - my = b,这个方程有解当且仅当 gcd(a,m)b\gcd(a, m) \mid b。这是第一步。
假设 aa 的逆在模 mm 意义下存在,为 a1a^{-1},那么根据基本性质,两边可以同乘 a1a^{-1},则得到 xb×a1(modm)x\equiv b\times a^{-1} \pmod{m},是不是这样,问题就轻松解决了呢?并不是,aa 的逆极有可能在模 mm 意义下不存在,我们试着求一下在模 mm 意义下 aa 的逆。即解

ax1(modm) ax \equiv 1 \pmod m

转化:

ax1=my ax - 1 = my

移项:

axmy=1 ax - my = 1

根据扩展欧几里得算法,当且仅当 gcd(a,m)=1\gcd(a, m) = 1,模 mm 意义下 aa 的逆存在。所以,我们要解 axb(modm)ax\equiv b \pmod{m},必须将其转化,使得 aa 的乘法逆存在。

axmy=bax - my = b 两边同时除以 gcd(a,m)\gcd(a, m),得到:

axmy=b(a=agcd(a,m),m=mgcd(a,m),b=bgcd(a,m)) a'x - m'y = b'(a' = \frac{a}{\gcd(a, m)}, m' = \frac{m}{\gcd(a, m)}, b' = \frac{b}{\gcd(a, m)})

于是问题回到了求解:

axb(modm) a'x \equiv b' \pmod {m'}

这一回,我们能保证 gcd(a,m)=1\gcd(a', m') = 1,所以 aa 在这里一定有乘法逆!

那么这个方程的解是在 ZmZ_{m'} 剩余系内的:

x(a)1b(modm) x\equiv (a')^{-1}b' \pmod {m'}

但是我们需要求解的是 ZmZ_{m} 剩余系内的元素,怎么转换过去呢?设 p=(a)1bp = (a')^{-1}b',那么我们有无穷多个实数解:x=p,p+m,p+2m,p+3m...x = p, p + m', p + 2m', p + 3m'...。我们想要知道,这无穷多个实数解,在模 mm 意义下究竟有多少个等价类(即模 nn 会有多少个不同的余数)?大家可能已经发现了,正好 d=gcd(a,m)d = \gcd(a, m) 个,分别为 p,p+m,p+2m,...,p+(d1)mp, p + m', p + 2m',...,p + (d - 1)m'
为什么呢?假设 p+imp + im'p+jmp + jm'mm 同余,那么 (p+im)(p+jm)=(ij)m(p + im') - (p + jm') = (i - j)m',必定是 mm 的倍数,也就是 iji - jdd 的倍数。所以是 dd 个一轮回的!
p,p+dm,p+2dm,...p, p + dm', p + 2dm',... 这些数模 mm 同余;
p+m,p+(d+1)m,p+(2d+1)m,...p + m', p + (d + 1)m', p + (2d + 1)m',... 这些数模 mm 同余;
...
p+(d1)m,p+(d+d1)m,p+(2d+d1)m,...p + (d - 1)m', p + (d + d - 1)m', p + (2d + d - 1)m',... 这些数模 mm 同余;
之间不可能同余,因为不满足 iji - jdd 的倍数。所以,方程 axb(modm)ax\equiv b \pmod{m} 要么无解,要么恰有 gcd(a,m)\gcd(a, m) 个解。

总结起来,解线性同余方程只需要求 aa 的乘法逆,但分析过程还是有些恼人的。

中国剩余定理

现在如果有多个同余方程,即同余方程组,变量只有一个,且 xx 前面系数为 11, 任意 mim_i 之间互素,该怎么做呢?
中国剩余定理在这里派上用场了,它并不是一种算法,而是一种思考、构造的方法。

现在有方程组 xai(modmi)x\equiv a_i \pmod {m_i}。我们令 M=miM = \prod m_iwi=Mmiw_i = \frac{M}{m_i}。那么解一定可以表示为 ZMZ_M 剩余系中的一个元素,即 xb(modM)x\equiv b\pmod M。我们来构造这个解。

由于 mim_i 之间互素,可以得到 gcd(mi,wi)=1\gcd(m_i, w_i) = 1,构造出这样一个方程 wipi+miqi=1w_ip_i + m_iq_i = 1,由于 gcd(mi,wi)=1\gcd(m_i, w_i) = 1,此方程一定有解。用扩展欧几里得算法解出 pi,qip_i, q_i,令 ei=wipie_i = w_ip_i,现在有一些有趣的性质,方程两边都模 mim_i,得到 eimodmi+0=1e_i \bmod m_i + 0 = 1eimodmi=1e_i \bmod m_i = 1

依据这一性质,我们构造得到方程在 ZMZ_M 剩余系中的唯一解 xe1a1+e2a2+...+enan(modM)x \equiv e_1a_1 +e_2a_2 +...+e_na_n\pmod M。验证一下,只需把每个方程带进去,看是否都成立即可。对于 xai(modmi)x\equiv a_i \pmod {m_i},将得到的解右边模 mim_i,惊奇的发现,除了 eiaie_ia_i 这一项的结果为 aia_i 之外,其余项的结果都是 00

x0+0+..+1×ai+0+..+0(modmi) x \equiv 0 + 0 + ..+ 1 \times a_i + 0 + .. + 0 \pmod {m_i}

原因是 eimodmi=1e_i \bmod m_i = 1 一模变成 11,还有 wjw_j 必定含有因子 mim_i,所以一模就成 00 了。

则对于每一个 mim_i,我们都能得到一个与原方程组一模一样的同余等式,所以这个解是正确的。

所以 x0=e1a1+e2a2+...+enanx_0 = e_1a_1 +e_2a_2 +...+e_na_n 显然是一个实数解,x0+M,x0+2M,x0+3M....x_0 + M, x_0 +2M, x_0 + 3M.... 都是解,原方程组有无穷组实数解。

欧拉定理

在数论中,欧拉定理是一个关于同余的性质。欧拉定理表明,若 n,an, a 为正整数,且 n,an,a 互素,则:

aφ(n)1(modn)a^{\varphi(n)} \equiv 1 \pmod n

特别的,当 nn 为素数的时候,aa 可取任意 ZnZ_n 内元素。由于 φ(n)=n1\varphi(n) = n - 1,故有:

an11(modn)ana(modn) \begin{aligned}a^{n - 1} \equiv 1 \pmod n\\a^n \equiv a \pmod n\end{aligned}

这就是费马小定理。观察到右边 11 的存在,发现与之前所说的逆元有一点相似:

ax1(modn) ax\equiv 1\pmod n

xx 是逆元,根据费马小定理,有 xan2(modn)x \equiv a^{n-2} \pmod n,故可以快速幂在 O(logn)O(\log n) 的时间内快速求出任意 ZnZ_n 内元素的逆元,但只有在 nn 是素数的时候才起作用。

离散对数

nn 为素数的时候,解模方程:

axb(modn)a^x\equiv b\pmod n

如果是实数范围内,答案是 logab\log_ab,可惜并不是,这里采用一种精妙的解决办法。
解:根据欧拉定理有:an11(modn)a^{n - 1}\equiv 1\pmod n,又 a01(modn)a^0\equiv 1\pmod n,所以 axa^x 在模 nn 剩余系内的值无限循环,以 a0,a1,...,an2a^0, a^1,...,a^{n-2} 为循环节。
所以,只需检查 x=0,1,2,...,n2x = 0, 1, 2,..., n - 2 时是不是解即可。但这样复杂度是 O(n)O(n) 的,下面用一种构造手段将复杂度降下来:
我们先检查前 mm 项(mm 取值稍后说明),即 a0,a1,...,am1a^0, a^1,...,a^{m - 1}nn 的值是否为 bb,并把 aimodna^i\bmod n 的值保存在 eie_i 中,求出 ama^mama^{-m}
下面接着考虑 am,am+1,...,a2m1a^m, a^{m + 1},...,a^{2m - 1},这次不需要检查,如果他们当中存在解,说明存在 i(0i<m)i(0\le i<m) 使得 eiamb(modn)e_ia^m\equiv b\pmod n。两边乘 ama^{-m},得到 eibam(modn)e_i\equiv ba^{-m}\pmod n,也就是说我们只需要检查有没有一个 ii,使得 eibam(modn)e_i\equiv ba^{-m}\pmod n,这相当于依次检查了 am,am+1,...,a2m1a^m, a^{m + 1},...,a^{2m - 1}
如果仍然没有检查到解,这回考虑 a2m,a2m+1,...,a3m1a^{2m}, a^{2m + 1},...,a^{3m - 1},同样的,我们只需要检查有没有一个 ii,使得 eib(am)2(modn)e_i\equiv b(a^{-m})^2\pmod n,这相当于依次检查了 a2m,a2m+1,...,a3m1a^{2m}, a^{2m + 1},...,a^{3m - 1}
显然使用 STL 中的 MAP 可以帮我们快速完成检测操作。预处理出 eie_i 的复杂度是 O(mlogm)O(m\log m),求出 ama^{-m} 的复杂度是 logn\log n,一共有 n/mn/m 轮检测,每轮复杂度 logm\log m。总复杂度 O((m+nm)logm)O((m + \frac{n}{m})\log m),当 m=nm = \sqrt n 时,复杂度最低为:O(nlogn)O(\sqrt n\log n)

指数循环节

axb(modn)a^{x} \equiv b \pmod n

xx 大到一定程度的时候,我们没有办法算 bb 了,这时需要用到指数循环节。
如果 gcd(a,n)=1\gcd(a, n) = 1,由欧拉定理 aφ(n)1(modn)a^{\varphi(n)} \equiv 1 \pmod n 可知指数以 [0,φ(n)1][0, \varphi(n) - 1] 为循环节不断循环,故有

axaxmodφ(n)(modn)a^{x} \equiv a^{x \bmod \varphi(n)} \pmod n

如果 ,似乎不好做了,不过也有公式!

axaxmodφ(n)+φ(n)(modn)(xφ(n))a^x\equiv a^{x \bmod \varphi(n) + \varphi(n)} \pmod n (x\ge \varphi(n))

需要声明一下,只有 xφ(n)x\ge \varphi(n) 时此公式成立,所以千万不要盲目的取余了再加!