「同余数论」学习笔记

欧几里得算法(GCD)

(gcd(a,b) = gcd(b, a \% b))

扩展欧几里得算法(EXGCD)

求不定方程：$ ax + by = gcd(a,b) $

求特解

当(b = 0)时，(gcd(a,0) = a)，故解得(x = 1, y = 0)

设：

[egin{cases} ax_1 + by_1 = gcd(a,b) \ bx_2 + (a\%b)y_2 = gcd(b,a\%b) end{cases} ]

因为(gcd(a,b) = gcd(b, a\%b))，所以：

[egin{aligned} ax_1 + by_1 &= bx_2 + (a\%b)y_2 \ &= bx_2 + (a - left lfloor a / b ight floor*b)y_2 \ &= bx_2 + ay_2 - left lfloor a / b ight floor*by_2 \ &= ay_2 + b(x_2 - left lfloor a / b ight floor y_2) end{aligned} ]

因此$$ax_1 + by_1 = ay_2 + b(x_2 - left lfloor a / b ight floor y_2)$$

特解：

[egin{cases} x_1 = y_2 \ y_1 = x_2 - left lfloor a / b ight floor * y_2 \ end{cases} ]

void exgcd(int a, int b, int &g, int &x, int &y){
    if(!b){
        g = a; x = 1, y = 0;
        return;
    }
    exgcd(b,a%b,g,y,x);
    y -= x*(a/b);
}

求通解

设$ k_1 = a / gcd(a,b) , k_2 = b / gcd(a,b) $ 。(k_1, k_2)一定互质

在原方程两边同时除以(gcd(a,b))，得(ax / gcd(a,b) + by / gcd(a,b) = 1)，即$ k_1x + k_2y = 1 $

显然其他解相对于特解，(x, y)的大小变化相反。设(x)增大(d_1)，(y)减小(d_2), 可得$$k_1(x + d_1) + k_2(y - d_2) = 1$$

由于(k_1x + k_2y = 1), 所以$$k_1d_1 = k_2d_2$$

由于(k_1, k_2)互质，故$$d_1 = k_2, d_2 = k_1$$

故解得通解为$$ (x + k ast left lfloor b / gcd(a,b) ight floor, y - k ast left lfloor a / gcd(a,b) ight floor) $$

求线性不定方程

求(ax + by = c)

裴蜀定理

(ax+by=c)有解当且仅当(gcd(a,b)|c)

求特解

扩大 (c / gcd(a,b)) 倍即可。即：

[egin{cases} x' = x * c / gcd(a,b) \ y' = y * c / gcd(a,b) end{cases} ]

求最小正整数解

由于(x)的通解是(x + k * b / gcd(a,b))。最小正整数解直接让特解模(b / gcd(a,b))取正的值即可。

求线性同余方程

求(ax≡b (mod m))

等价于$ ax + my = b $，求不定方程即可。

思想

以上两个例子告诉我们，当存在一个不定系数(k)时，等式和同余式是可以相互转化的。

费马小定理

当(P)为质数时，对正整数(a)有

[a^{P-1} equiv 1 pmod P ]

欧拉定理

欧拉定理将费马小定理推广到了(P)不会质数的情况。

[a^{varphi(P)} equiv 1 pmod P, a perp P ]

此时指数对(varphi(P))取模不影响答案。

[a^b mod P = a^{b mod varphi(P)} mod P ]

扩展欧拉定理

可以将欧拉定理推广到(a,P)不互质的情况。

[a^b mod P = egin{cases}a^b mod P & b < varphi(P) \a^{left (b mod varphi(P) ight ) + varphi(P)} mod P & b geq varphi(P)end{cases} ]

乘法逆元

如果两个整数(a,b)满足(ab equiv 1 pmod P)，则称(b)是(a)在模(P)意义下的乘法逆元（反之亦然）。

乘法逆元可以直接用(exgcd)求解同余方程，或者使用欧拉定理。

线性递推求逆元：

设(P = k ast i + r)，有$$k * i + r ≡ 0 pmod P$$。记为(a^{-1})或(inv(a))

两边同时乘以(i^{-1} * r^{-1})可得

[egin{aligned} k * i * i^{-1} * r ^ {-1} + r * i^{-1} * r^{-1} ≡ 0 pmod P \ k * r^{-1} + i^{-1} ≡ 0 pmod P \ i^{-1} ≡ -left lfloor dfrac{p}{i} ight floor * (p \% i)^{-1} pmod P \ end{aligned} ]

扩展中国剩余定理(EXCRT)

求同余方程组：

[left { egin{matrix} x ≡ a_1 pmod {m_1} \ x ≡ a_2 pmod {m_2} \ cdots \ x ≡ a_r pmod {m_r} \ end{matrix} ight. ]

这里不介绍中国剩余定理，因为扩展中国剩余定理的功能完全包含它。

我们一个一个方程按顺序来解，每一次都利用上一次的解。假设我们已经求出前(i-1)个方程的解(ans)。设(M=prodlimits_{j=1}^{i-1}m_j)，显然(ans+k ast M)都满足前(i-1)个方程。我们要让它满足第(i)个方程，等价于

[ans+k ast M equiv a_i pmod {m_i} ]

我们用(exgcd)求出(k)，带入更新(M)和(ans)即可。如果此同余方程无解，则代表整个问题无解。

复杂度(O(n log m))。

inline int EXCRT(){
    int ans=a[1],M=m[1],g,x,y,c;
    for(int i = 2; i <= n; ++i){
        c = (a[i]-ans%m[i]+m[i])%m[i];
        exgcd(M,m[i],g,x,y);
        if(c%g != 0) return -1;
        x = qmul(x,c/g,m[i]);
        ans += x*M;
        M *= m[i]/g;
        ans = (ans+M)%M;
    }
    return ans;
}