同余及乘法逆元

定义

若整数 \(a\) 于整数 \(b\) 除以整数 \(m\) 的余数相等，则称 \(a,b\) 模 \(m\) 同余，记为：

\[a \equiv b \pmod{m} \]

同余类与剩余系

对于 \(\forall a\in [0,m-1]\)，集合 \(\{x|x=a+km,k\in \Z\}\) 的所有元素模 \(m\) 同余，且余数都是 \(a\) ，则称该集合为一个模 \(m\) 的同余类，简记为 \(\overline{a}\)。
模 \(m\) 的同余类一共有 \(m-1\) 个，分别为 \(\overline{0},\overline{1},\overline{2},\dots,\overline{m-1}\)，这些共同构成 \(m\) 的完全剩余系。
\(1 \sim m\) 中与 \(m\) 互质的数有 \(\varphi(m)\) 个，这些共同构成 \(m\) 的简化剩余系。
并不知道这些东西对OI有什么用

同余式的性质

1. 同加性 \(a \equiv b \pmod{m} \implies a+c \equiv b+c \pmod{m}\)
2. 同减性 \(a \equiv b \pmod{m} \implies a-c \equiv b-c \pmod{m}\)
3. 同乘性 \(a \equiv b \pmod{m} \implies ac \equiv bc \pmod{m}\)

but它好像并不满足同除性

\[a \equiv b \pmod{m}\nLeftrightarrow \frac{a}{c} \equiv \frac{b}{c} \pmod{m} \]

在我们计算模数的时候又不可避免地需要使用除法，这怎么办呢？

乘法逆元

数学家们无法接受这个事实，于是抛出了乘法逆元这个概念。

定义

若 \(\frac{b}{a}\bmod m = b\times c\bmod m\)，则称 \(c\) 为 \(a\) 在模 \(m\) 意义下的乘法逆元，记为 \(a^{-1}\)，读作 a的逆可不要读成a的负一次方。
可以发现乘法逆元很好地解决了同余式不满足同除性的问题。

求解

貌似并不是很好求的样子
如果 \(a^{-1}\) 是 \(a\) 在模 \(m\) 意义下的逆元。
则 \(a\times a^{-1} \equiv 1 \pmod{m}\)。

费马小定理

若 \(p\) 为质数，对于任意的整数 \(a\) 都有：

\[a^p \equiv a \pmod{p} \]

我们假设 \(a<p\)，那么我们可以退出：

\[a^{p-1} \equiv 1 \pmod{p} \]

在进行一下变形：

\[a\times a^{p-2} \equiv 1 \pmod{p} \]

所以你就发现，\(a^{p-2}\) 正式 \(a\) 在模 \(p\) 意义下的一个逆元。
事实上用费马小定理求逆元是最常用的方法。

扩展欧几里得

还记得我在最大公约数 & 最小公倍数这篇文章中说过：

用于求解 \(ax+by=\gcd(a,b)\) 的一组整数特解，并可用于求解逆元和线性同余方程。

但当时我并没有说到具体怎么求逆元。
我们构建方程：

\[ax+my=\gcd(a,m) \]

若 \(\gcd(a,m)=1\) 则解出来的 \(x\) 就是 \(a^{-1}\)，否则逆元不存在。
这种算法适合求解仅保证 \(a\) 与 \(m\) 互质的情况

线性同余方程

中国剩余定理 (Chinese Remainder Theorem, CRT)：

引入：

用于求解「物不知数」问题：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二．问物几何？

就是求同时满足：除以 \(3\) 余 \(2\)，除以 \(5\) 余 \(3\)，除以 \(7\) 余 \(2\) 的整数。
该问题最早见于《孙子算经》中，并有该问题的具体解法．宋朝数学家秦九韶于 1247 年《数书九章》卷一、二《大衍类》对「物不知数」问题做出了完整系统的解答。
摘自OI-wiki

定义：

对于上面的问题，可以写成同余方程组：

\[\left\{\begin{array}{l} x \equiv 2 \pmod{3}\\ x \equiv 3 \pmod{5}\\ x \equiv 2 \pmod{7} \end{array}\right. \]

而中国剩余定理正是求解模数互质的一元线性方程组：

\[\left\{\begin{gather*} x \equiv a_1 \pmod{m_1}\\ x \equiv a_2 \pmod{m_2}\\ \vdots\\ x \equiv a_n \pmod{m_n} \end{gather*}\right. \]

其中对于\(\forall i,j \in[1,n]\cap\N,i \neq j\) 满足 \(\gcd(m_i,m_j)=1\)，即 \(m_i\) 与 \(m_j\) 互质。
设 \(M=\prod_{i=1}^{n} m_i\)，\(b_i=m/m_i\)，\(t_i\) 是 \(b_it_i\equiv 1\pmod{m_i}\) 的一个解，那么上述方程组的解为：

\[x=\sum_{i=1}^{n}{a_ib_it_i} \]

证明

因为 \(b_i=M/m_i\)，即 \(b_i\) 是除 \(b_i\) 以外所有模数的倍数，所以 \(\forall j\neq i，a_ib_it_i \equiv 0\pmod{m_j}\)。
又因为 \(b_it_i\equiv 1\pmod{m_i} \implies a_ib_it_i\equiv a_i\pmod{m_i}\)，带入原方程 \(x=\sum_{i=1}^{n}{a_ib_it_i}\) 成立。

代码

int crt(int a[],int m[]){int M=1,ans=0;for(int i=1;i<=n;++i) M*=m[i];for(int i=1;i<=n;++i){int mi=M/m[i],ti,y;exgcd(mi,m[i],ti,y);ans=(ans+a[i]*mi*ti)%M;}return ans;
}