初等数论（Ⅱ）：同余相关

· · 个人记录

基础知识处理

积性函数

定义域为整数的函数称为数论函数

对于一个数论函数 f ,

若 \forall a \bot b,f(ab) = f(a)f(b) ,则称 f 为积性函数(\bot表示互质)；

若 \forall a,b \in Z , f(ab)=f(a)f(b) , 则称 f 为完全积性函数。

同余

定义

若整数 a 和整数 b 除以正整数 m 的余数相等，则称 a,b 模 m 同余，记为 a \equiv b(\text{mod} \ m)。

同余的定理

(1) a\equiv b(\text{mod} \ m) \Leftrightarrow m \mid (a-b)

证明：设 a = k_1 + r_1,b=k_2+r_2(0\leq r1,r2 <m)，下文同。

充分性：

a-b = (k_1-k_2)m + (r_1-r_2) \because a \equiv b(\text{mod} \ m) \ $ $\therefore r_1 = r_2 \therefore a-b = (k_1-k_2)m \ \therefore m \mid (a-b)

必要性：反过来证一次即可。

(2) a\equiv b(\text{mod} \ m) \Leftrightarrow 存在 a=b+km(k\in \mathbb{Z})

充分性：

\because a \equiv b(\text{mod} \ m) \ \therefore r_1=r_2 \therefore k_1m = (k_2+k)m = k_2m + km \therefore k_1m+r_1 = k_2m+r_2 + km$，即 $a = b+km

同余的性质

(1)自反性： a \equiv a(\text{mod} \ m)

(2)对称性： 若 a \equiv b(\text{mod} \ m) ，则 b \equiv a(\text{mod} \ m)

(3)传递性：若 a \equiv b(\text{mod} \ m),b \equiv c(\text{mod} \ m) ， 则 a \equiv c(\text{mod} \ m)

(4)同加性：若 a \equiv b(\text{mod} \ m),c \equiv d(\text{mod} \ m) \Rightarrow a \pm c \equiv b \pm d(\text{mod} \ m)

证明：由定理1得：m \mid (a-b),m \mid (c-d)

再由整除的性质(若a \mid b 且 a \mid c ，则 \forall x,y ，有 a \mid xb+yc) 得

m \mid [(a-b) \pm (c-d)] \therefore a \pm c \equiv b \pm d(\text{mod} \ m)

(5)同乘性：a \equiv b(\text{mod} \ m),c \equiv d(\text{mod} \ m) \Rightarrow ac \equiv bd(\text{mod} \ m)

证明：由定理1得：m \mid (a-b),m \mid (c-d)

\because ac - bd = ac - bc + bc - bd = c(a-b) + b(c-d)

再由整除的性质得

m \mid (ac - bd) \therefore ac \equiv bd(\text{mod} \ m)

(6)同幂性：a \equiv b(\text{mod} \ m) \Rightarrow a^n \equiv b^n(\text{mod} \ m)

证明：由同乘性可知，设 c=a,d=b

\therefore ac \equiv bd(\text{mod} \ m)$，即 $a^2 \equiv b^2(\text{mod} \ m)$，如此反复 $n$ 次，即可得到 $a^n \equiv b^n(\text{mod} \ m)

(7)若 a \equiv b(\text{mod} \ m)，d 为 a,b,m 的公因数，则 \frac{a}{d} \equiv \frac{b}{d}(\text{mod} \ \frac{m}{d})

证明：

由定理1得， m \mid (a-b)。

由整除的性质：若 ma \mid mb (m \ne 0) ，则 a \mid b 得

\frac{m}{d} \mid \frac{(a-b)}{d} = \frac{a}{d} - \frac{b}{d}

再由定理1得，\frac{a}{d} \equiv \frac{b}{d}(\text{mod} \ \frac{d}{m})

(8)若a \equiv b(\text{mod} \ m) , d 是 a,b 的公因数且 \gcd(d,m)=1 ，则 \frac{a}{d} \equiv \frac{b}{d}(\text{mod} \ m)

由定理1得， m \mid (a-b)。

由整除的性质得

m \mid d(\frac{a}{d} - \frac{b}{d})$，又因为 $\gcd(d,m)=1 \therefore m \mid \frac{a}{d} - \frac{b}{d}

再由定理1得，\frac{a}{d} \equiv \frac{b}{d}(\text{mod} \ m)

（9）若a \equiv b(\text{mod} \ m_i),i=1,2,\dots,k ， 则 a \equiv b(\text{mod} \ \text{lcm}(m_1,m_2,\dots,m_k))

由定理1得， m_i \mid (a-b)。

这表示 a-b 是 m_1,\dots,m_k的公倍数

\therefore \text{lcm}(m_1,m_2,\dots,m_k) \mid a-b

再由定理1得，a \equiv b(\text{mod} \ \text{lcm}(m_1,m_2,\dots,m_k))

(10) 若 a \equiv b(\text{mod} \ m) , d\mid m,d>0 ，则 a \equiv b(\text{mod} \ d)

证明：由定理1得，m \mid (a-b)

a-b = (k_1-k_2)m \ \ \ \ \ \ \ \ \ \ = (k_1-k_2)m_1d \ \ \ \ \ \ \ \ \ \ =(k1m_1-k_2m_1)d \therefore d \mid (a-b) \therefore a \equiv b(\text{mod} \ d)

(11) 若 ac \equiv bc(\text{mod} \ m) , 且 d = \gcd(c,m) ，则有 a \equiv b(\text{mod} \frac{m}{d})

证明：由定理1得，m \mid (ac-bc) = (a-b) c ，存在整数 k 使得 (a-b)c = mk

\therefore \frac{(a-b)c}{d} = \frac{mk}{d} \because \gcd(\frac{c}{d},\frac{m}{d}) = 1 \therefore \frac{m}{d} \mid (a-b) \therefore a \equiv b(\text{mod} \frac{m}{d})

一、裴蜀定理

定义

一定存在整数 x,y ,满足 ax + by = \gcd(a,b)

证明

设取整数 x_0,y_0 , ax + by的最小正整数为s ， 即 ax_0+by_0 = s

\because \gcd(a,b)\mid ax_0 , \gcd(a,b)\mid by_0

又由 x \mid a , x\mid b ,则 x \mid a+b 这个性质得

\therefore \gcd(a,b) \mid s $ $(1)

设 a = qs + r (0 \leq r < s)

r = a-qs \ \ \ = a - q(ax_0+by_0) \ \ \ = a(1-qx_0) + b(-qy_0) \ \ \ = ax + by

(因为1-qx_0是整数，-qy_0也是整数，所以就能写成 ax+by)

$\therefore r=0$(只能取$0$) $\therefore s \mid a $，同理 $s \mid b 由$(1)(2)$得, $s = \gcd(a,b)$ ,证毕。 ### 裴蜀定理推广 一定存在整数 $x,y$，满足 $ax+by = \gcd(a,b) \times n , n \in Z

裴蜀定理再推广

一定存在整数 x_1 \dots x_n , 满足 \Sigma_{i=1}^{n} A_ix_i = \gcd(A_1 ,\dots,A_n)

小细节

欧几里得求 \gcd(a,b)，如果代入负数，结果会是负数。所以在求解的时候，可以带入负数的绝对值。这样并不会影响解，无非就是符号变化了一下。

二、欧几里得相关

一、欧几里得算法

\forall a,b \in N ,b\not= 0 ,\gcd(a,b)=\gcd(b,a\%b)

证明：

若 a<b , 则 \gcd(b,a\% b) = \gcd(b,a),显然成立

若 a \geq b ,设 a = qb + r(0 \leq r < b) , 显然 r = a \% b , 对于 a,b 的任意公约数 d , d \mid a , d\mid qb , 所以d \mid (a-qb),即d \mid r。故 a,b 的公约数集合与 b,a\%b 的公约数集合相同。于是他们的最大公约数自然也相等。

二、扩展欧几里得算法

引入

求 ax+by = \gcd(a,b) 的一组整数解

求解

构造特解

当 b=0 时，ax+by=a , 因此x=1,y=0

当 b\not= 0 时，

\gcd(a,b)=ax+by \gcd(b,a\%b) = bx_1 + (a\%b)y_1 \ \ \ \ \ \ \ \ = bx_1 + (a-\lfloor \frac{a}{b} \rfloor \times b)y_1 \ \ \ \ \ \ \ \ = ay_1+b(x_1-\large \frac{a}{b}y_1) \because \gcd(a,b) = \gcd(b,a\%b) \therefore x = y_1 , y = x_1 - \frac{a}{b}y_1

到这一步，我们就可以递归到最底部，因为最底层时 b=0 ，显然可以构造出 x=1,y=0 使得 a \times 1 + b\times 0 = \gcd(a,0) , 然后一步一步往上回来，求出特解 (x_0,y_0)。

code

il int exgcd(int a,int b,int &x1,int &y1)
{
    if(!b)
    {
        x1 = 1 , y1 = 0;
        return a;
    }
    ans = exgcd(b,a%b,x1,y1);
    int t = x1;
    x1 = y1; y1 = t-a/b*y1;
    return ans;
}

构造通解

\because ax+by = ax_0+by_0 \therefore a(x-x_0)= b(y_0-y)

设\gcd(a,b) = d

\therefore \frac{a}{d}(x-x_0)= \frac{b}{d}(y_0-y) \large \because \frac{a}{d} \nmid \frac{b}{d} \therefore \frac{a}{d} \mid y_0-y

设y_0-y = k \large \frac{a}{d}

\therefore y = y_0 - k \large \frac{a}{d}

同理

\large \because \frac{b}{d} \nmid \frac{a}{d} \therefore \frac{b}{d} \mid x-x_0

设x-x_0 = n \large \frac{b}{d}

\therefore x = x_0 + n \large \frac{b}{d} \therefore ax+by=a(x_0+n\frac{b}{d})+b(y_0-k \frac{a}{d}) =ax_0+by_0+n\frac{ab}{d}-k\frac{ab}{d} \because ax+by=ax_0+by_0 \therefore n = k

所以，通解为

\begin{aligned} x & = & x_0+k\frac{b}{\gcd(a,b)} \\ y & = & y_0-k\frac{a}{\gcd(a,b)} \\ \end{aligned} \right. ,k \in \mathbb{Z}

证毕

三、欧拉相关

(Ⅰ)、欧拉函数

定义

1-n$ 中与 $n$ 互质的数的个数称为欧拉函数，记为 $\varphi(n) e.g.$ $\varphi(1) = 1,\varphi(2)=1,\varphi(3)=2

欧拉函数的性质

性质1： 若 p 是质数，则 \varphi(p)=p-1

性质2: 若 p 是质数，则 \varphi(p^k) = (p-1)p^{k-1} = p^k - p^{k-1}

证明：因为 1\dots p \dots 2p \dots \dots p^2 \dots \dots p^k 一共有 p^k \div p = p^{k-1} 个循环节，而每个循环节中和 p^k 互质的个数都是 p-1 个，所以最后答案就是 (p-1)p^{k-1}

证毕

性质3：\varphi(n) = n \times \prod_{i=1}^{s}(1-\frac{1}{p_i})

证明：

由唯一分解定理分解得,n=\prod_{i=1}^{s}p_i^{a_i}

$\therefore \varphi(n) = \prod_{i=1}^{s}\varphi(p_i^{a_i}) =\prod_{i=1}^{s}p_i^{a_i-1}(p_i-1) =\prod_{i=1}^{s}p_i^{a_i}(1-\frac{1}{p_i}) =\prod_{i=1}^{s}p_i^{a_i} \times \prod_{i=1}^{s}(1-\frac{1}{p_i}) =n\times \prod_{i=1}^{s}(1-\frac{1}{p_i})

证明：

$\varphi(n) \times \varphi(m) = n \times \prod_{i=1}^{cnt_n}(1-\frac{1}{p_i}) \times m \times \prod_{i=1}^{cnt_m}(1-\frac{1}{p_i}) =n \times m \times \prod_{i=1}^{cnt_n+cnt_m}(1-\frac{1}{p_i}) =\varphi(nm)

证毕

证明：因为 b 里面包含了所有 a 的质因子，所以 \prod_{i=1}^{m}(1-\frac{1}{p_i}) 是相同的，只是多了一个 a ，所以性质5成立。

\varphi(ab) = ab \times \prod_{k=1}^{s}(1-\frac{1}{p_k}) \ \ \ \ \ \ \ = a \times b \times \prod_{k=1}^{s}(1-\frac{1}{p_k}) \ \ \ \ \ \ \ = a \times \varphi(b)

设 p 为质数且 p|n ,则

\begin{aligned} & p \times \varphi(\frac{n}{p}),p^2 \mid n \\ & (p-1) \times \varphi(\frac{n}{p}),p^2 \nmid n \\ \end{aligned} \right. 若 $\frac{n}{p}$ 不能被 $p$ 整除，说明 $\frac{n}{p}$ 中不含 $p$ 这个质因子了， 则说明它俩互质，应用积性函数的性质，再应用性质1，得到下面那个等式。 - **性质7(欧拉反演)** $\sum_{d \mid n}\varphi(d) = n

证明：设 f(n) = \sum_{d \mid n}\varphi(d) , 若n \bot m ,则 f(n) \times f(m) = \sum_{i \mid n}\varphi(i)\sum_{j \mid m}\varphi(j)

=\sum_{i \mid n}\sum_{j \mid m}\varphi(i)\varphi(j) =\sum_{i \mid n}\sum_{j \mid m}\varphi(i\times j) =\sum_{d \mid nm}\varphi(d) = f(nm)

所以 f(n) 是积性函数。

对于单个质因子 p ，应用性质2可得：

f(p^k) = \varphi(1) + \varphi(p) + \varphi(p^2) + \dots + \varphi(p^k) =1 + (p-1) + (p^2-p) + \dots + (p^k-p^{k-1}) =p^k

因为 n = p_1^{k_1}p_2^{k_2}\dots p_m^{k_m}

所以 f(n)=f(p_1^{k_1})f(p_2^{k_2})\dots f(p_m^{k_m})

=p_1^{k_1}p_2^{k_2}\dots p_m^{k_m} = n

证毕

证明：设 x \bot n , 则\gcd(x,n) = 1, 由更相减损得，\gcd(x,n) = \gcd(n,x-n) = \gcd(n,n-x) = 1

则 n-x \bot n ，说明这些质数是一一配对的。一个特例是 x=n-x 时，x = \frac{n}{2} ，此时 \gcd(n,x) = x \not= 1 ，所以不会出现这种情况。证毕。

求欧拉函数

试除法

int phi(int n)
{
    int res = n;
    for(re int i=2;i*i<=n;i++)
    {
        if(n % i == 0)
        {
            res = res/i*(i-1);
            while(n%i == 0) n/=i;
        }
    }
    if(n > 1) res = res/n*(n-1);
    return res;
}

时间复杂度 O(\sqrt{n}),适用于规模较小的情况。

线性筛欧拉函数

在线性筛中，每个合数 m 都是被 最小的质因子筛掉的。

设 p_j 是 m 的最小质因子，则 m 通过 m = p_j \times i 筛掉。

三种情况：

\ \ \ \ \ \ \ \ \ \varphi(m) = p_j \times \varphi(i) \ \ \ \varphi(m) = \varphi(p_j) \times \varphi(i) = (p_j-1)\varphi(i)

Code

il void get_phi(int n)
{
    memset(isprime , 1 ,sizeof isprime);
    isprime[1]=0; phi[1] = 1;
    for(int i=2;i<=n;i++)
    {
        if(isprime[i]) 
        {
            prime[++cnt]=i;
            phi[i] = i-1;//情况1
        }
        for(int j=1;j<=cnt && prime[j]*i <=n ;j++)
        {
            int m = i*prime[j];
            isprime[m]=0;
            if(i%prime[j] == 0) 
            {
                phi[m] = prime[j] * phi[i];//情况2
                break;
            }
            else phi[m] = (prime[j]-1)*phi[i];//情况3
        }
    }
}

时间复杂度 O(n)

(Ⅱ):欧拉定理

前置知识

定义

欧拉定理:若 \gcd(a,m) = 1 , 则 a^{\varphi(m)} \equiv 1 (mod \ m)

证明:构造一个与 m 互质的序列。

设\{r_1,r_2,\dots,r_{\varphi(m)} \} 是一个模 m 的简化剩余系。

由乘法封闭得，\{ar_1,ar_2,\dots,ar_{\varphi(m)} \} 也是一个模 m 的简化剩余系。

\therefore \prod_{i=1}^{\varphi(m)}r_i \equiv \prod_{i=1}^{\varphi(m)}ar_i \equiv a^{\varphi(m)}\prod_{i=1}^{\varphi(m)}r_i(mod \ m)

因为 \gcd(\prod_{i=1}^{\varphi(m)}r_i,m) = 1 ，由同余的性质(11)得

a^{\varphi(m)} \equiv 1 (mod \ m)

特别的，当 m 为质数时 , 因为 \varphi(m) = m-1 ,带入欧拉定理我们可以得到

a^{m-1} \equiv 1 (mod \ m)

这也就是我们的费马小定理

(Ⅲ):扩展欧拉定理

\begin{aligned} & a ^ {b \ mod \ \varphi(p)} \ \ \ \ \ \ \ \ \ \ \gcd(a,p)=1 \\ & a^b \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \gcd(a,p) \not= 1 ,b<\varphi(p) \\ & a^{b \ mod \ \varphi(p)+\varphi(p)} \ \ \ \gcd(a,p) \not=1,b \geq \varphi(p) \end{aligned} \right. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (mod \ p)

(第二三个互质与否都可)

证明：

对于第一个式子 , 设 b = q * \varphi(p) + r(0\leq r < \varphi(p)) ， r = b \ mod \ \varphi(p)

于是就有 a^b \equiv a^{q*\varphi(p)+r} \equiv (a^{\varphi(p)})^q \times a^r \equiv 1^q \times a^r \equiv a^r \equiv a^{b \ mod \ \varphi(n)}

对于第二个式子,啥也没变，当然同余。

对于第三个式子,感性证明 \text{by Alex\_wei}

"当 \gcd(a,p)\not= 1 时，不断乘以 a 会让 a^i 和 p 的 \gcd 不断变大，直到某个特定的 a^r 之后 \gcd 不再变化，因为此时 \gcd(a^r,p) 受到 p 的每个与 a 相同的质因子的次数的限制。令这个 gcd 为 d，考虑 a^r \ mod \ p,a^{r+1} \ mod \ p,⋯显然它们均为 d 的倍数，且除以 d 之后会取遍所有与 \frac{p}{d} 互质的数，这是因为 a \bot \frac{p}{d}。根据欧拉定理，a^k \ mod \ \frac{p}{d} 有循环节 \varphi(\frac{p}{d})，因此 (a^k \ mod \ \frac{p}{d})\times d 即 a^k \ mod \ p 也有循环节 \varphi(\frac{p}{d})。故从 a^r 开始，a^{r+k} \ mod \ p 有循环节 \varphi(p)。"

四、威尔逊定理

定义：(p-1)! \equiv -1 (\text{mod} \ p) 是 p 为质数的充要条件。

证明

充分性(反证法)

若 p 不是质数

当 p=1 时,(1-1)! \equiv 0 (\text{mod} \ 1)

当 p=4 时,(4-1)! \equiv 2 (\text{mod} \ 4)

当 p > 4 时，

(1)当 p 是完全平方数

令 p=k^2 ，则 k>2 ，可得 2k < p

\therefore (p-1)!=1\times 2 \times 3 \times \dots \times k \times \dots \times 2k \times (p-1) =k^2 \times n = p \times n

故(p-1)! \equiv 0 (\text{mod} \ p)

(2)当 p 不是完全平方数

令 p=a \times b ， 1 < a < b < p

\therefore (p-1)!=1\times 2 \times 3 \times \dots \times a \times \dots \times b \times (p-1) =a \times b \times n = p \times n

故(p-1)! \equiv 0 (\text{mod} \ p)

必要性

若 p 是质数

则集合 \{1,2,3,\dots,p-1\}是模 p 的简化剩余系

当 a \in [1,p-1] ，则 a,p 互质

所以集合 \{a,2a,3a,\dots,(p-1)a\}也是一个模 p 的简化剩余系。

对于 x \in [1,p-1] ，只有一个 ka 满足 kax \equiv 1(\text{mod} \ p),k \in [1,p-1]

暂且先用 a 来代表 ka

(1) a=x时,即 x^2 \equiv 1(\text{mod} \ p)

即 (x-1)(x+1) \equiv 0(\text{mod} \ p)

x_1=1 , x_2 = p-1

(2) a \not= x 时，满足 ax \equiv 1(\text{mod} \ p)的取值范围就是 2\leq a,x \leq p-2

所以必然有 \frac{p-3}{2} 对数的乘积模 p 为 1

即(p-2)! \equiv 1(\text{mod} \ p)

同乘 p-1，得到 (p-1)! \equiv p-1(\text{mod} \ p) \equiv -1(\text{mod} \ p)

命题得证。

五、乘法逆元

定义

若整数 b,m 互质 ，并且 b \mid a ，则存在一个整数 x , 使得 a / b \equiv a \times x(\text{mod} \ m) ，则称 x 为 b 的模 m 乘法逆元，记为 b^{-1}(\text{mod} \ m)。

因为 a / b \equiv a \times b^{-1} \equiv a / b \times b \times b^{-1}(\text{mod} \ m) (二式三式之间，除个 b 在乘个 b )，所以 b \times b^{-1} \equiv 1(\text{mod} \ m)

实际上，乘法逆元的意义就是在模 m 意义下，除以 b 等效于乘以 x ，这样就可以化除为乘，而乘法就比除法有着更好的性质了。

性质

证明：假设 x 是 a 在模 m 意义下的乘法逆元，则有 a \times x \equiv 1(\text{mod} \ m) ，这可以转化成一个不定方程 ax + by = 1 ，运用裴蜀定理的推广，我们知道 ax+by 的最小正整数解是 \gcd(a,b) ，要保证有解，就要使得 \gcd(a,b) \mid 1 ，显然 \gcd(a,b) 只能为 1 ，所以 a,b 必须互质。

逆元求法

求解同余方程

在上文我们已经提到了可以将 则有 a \times x \equiv 1(\text{mod} \ m) ，转化成一个不定方程 ax + by = 1。我们通过扩展欧几里得求出 x 的一个特解后 ，再通过 (a \% m + m) \% m 的 trick 得到最小整数解。

费马小定理

当 \gcd(a,p) = 1 且 p 是质数的时候，我们可以更简单的求出逆元。

根据费马小定理我们有 a^{p-1} \equiv 1(\text{mod} \ p)

所以a \times a^{p-2} \equiv 1(\text{mod} \ p)

所以 a 在模 p 意义下的乘法逆元就是 a^{p-2} ，其可以通过快速幂求出。

线性求逆元

这里仅介绍一种比较好理解的 O(n) 求 1-n 中所有数的阶乘求逆元。

设 inv_i 表示 i! 的逆元，即 \frac{1}{i!} 。

那么就有这样一个递推关系：inv_{i+1} \times (i+1) = \frac{1}{i!} = inv_i 。

我们可以求出 n! 的逆元，然后再倒推，就能求出 1\dots n! 所有的逆元。

那么 i^{-1} = \frac{1}{i!} \times (i-1)! = inv_i \times (i-1)!

六、线性同余方程

定义

给定整数 a,b,m ，求一个整数 x 满足 a \times x \equiv b(\text{mod} \ m) ，或者无解。因为未知数的指数为 1 , 所以叫做一次同余方程，也叫线性同余方程。

其实上文已经有类似的思路了 a \times x \equiv b(\text{mod} \ m) 等价于 ax + my = b。根据裴蜀定理，线性同余方程有解当且仅当 \gcd(a,m) \mid b。

求解同余方程

跟求逆元类似的，我们把它转成不定方程之后用扩展欧几里得算法求出一组整数解 x_0,y_0 满足 ax_0 + by_0 = \gcd(a,m) ，然后 x = x_0 \times b/ \gcd(a,m) 就是原线性同余方程的一个解。

方程的通解则是 x + k\frac{m}{\gcd(a,m)},k\in \mathbb{Z} 。

七、中国剩余定理(CRT)

用途

中国剩余定理是用来求解形如

\begin{cases} x \equiv r_1 ,& (\text{mod} \ m_1) \\ x \equiv r_2 ,& (\text{mod} \ m_2) \\ \dots \\ x \equiv r_n ,& (\text{mod} \ m_n) \end{cases}

的线性同余方程组的，其中模数两两互质。

思路

这其实是一个构造的过程。

先证明 \sum_{i=1}^n r_ic_ic_i^{-1} 满足每个 x \equiv r_i(\text{mod} \ m_i)

当 i \not= j 时 ，因为 c_j 中并没有去掉 m_i ，所以 c_j 是 m_i 的倍数，因此 c_j \equiv 0(\text{mod} \ m_i) ，故有 c_jc_j^{-1} \equiv 0(\text{mod} \ m_i)。

当 i = j 时 ，因为 c_i 中去掉了 m_i ， 所以 c_i 肯定不是 m_i 的倍数，因此 c_i \not\equiv 0(\text{mod} \ m_i) ，故有 c_ic_i^{-1} \equiv 1(\text{mod} \ m_i)。

所以 x \equiv r_i (\text{mod} \ m_i)

\ \ \ \ \ \ \ \ \ \ \ \equiv r_ic_ic_i^{-1}(\text{mod} \ m_i) \ \ \ \ \ \ \ \ \ \ \ \equiv \sum_{i=1}^n r_ic_ic_i^{-1}(\text{mod} \ m_i)

而 \sum_{i=1}^n r_ic_ic_i^{-1}(\text{mod}\ M) 对 m_i 来说，只是减去了 m_i 的若干倍，并不影响余数 r_i ，这就是它构造的巧妙之处。

总之就是 \text{mod} \ M 后剩下的是一个 r_i + km_i(0\leq k < \frac{M}{m_i}) 状物，模完 m_i 依旧只剩下 r_i 。

一般来说，题目里的范围类似 \prod a_i \leq 10^{18} 这样很特别的范围，我们可以考虑往中国剩余定理这方面想。

八、扩展中国剩余定理(exCRT)

用途

扩展中国剩余定理是用来求解形如

\begin{cases} x \equiv r_1 ,& (\text{mod} \ m_1) \\ x \equiv r_2 ,& (\text{mod} \ m_2) \\ \dots \\ x \equiv r_n ,& (\text{mod} \ m_n) \end{cases}

的线性同余方程组的，但是其中模数不一定互质。

思路

同样是求解线性同余方程组，为什么不能用 CRT 呢？从原理说起，CRT 中会用到逆元，但是如果 m_i 不互质，那么 c_i 在 m_i 意义下就没有逆元。这是一个根本性的问题，我们不能对 CRT 修改一些 bug 来解决问题，只能新找思路。

exCRT 是一个合并同余方程的过程，步骤如下。

这就是 exCRT 的本质：合并同余方程。对于 n 个同余方程，我们只需合并 n-1 次，时间复杂度 O(n\log{m}) 。