【数论】数论四大定理

· · 算法·理论

欧拉函数

设 $n=\prod_{i=1}^kp_i^{c_i}$（$p$ 为 $n$ 的质因数，$n$ 是不为 $0$ 的正整数）， 则 $\varphi(n)=n\prod_{i=1}^k\left(1-\dfrac 1{p_i}\right)=\prod_{i=1}^kp_i^{c_i-1}(p_i-1) \varphi(1)=1

推论：质数的 \varphi 为自己减 1。

枚举质因子计算即可，时间复杂度 \text{O}(\sqrt n)

欧拉定理

\forall a\bot n,a^{\varphi(n)}\equiv1(\bmod\ n)

所以

\forall a\bot n,a^b\equiv a^{b\bmod n}(\bmod\ n)

扩展欧拉定理

a^b\equiv \begin{cases} a^{b\bmod\varphi(m)},&\gcd(a,m)=1\\ a^b,&\gcd(a,m)\ne1,b<\varphi(m)\\ a^{b\bmod\varphi(m)+\varphi(m)},&\gcd(a,m)\ne1,b\ge\varphi(m) \end{cases}\pmod m

快速幂

每次询问给出 a,b,c，快速求出 a^b\%c，不预处理，每次询问 \text{O}(\log b)

\begin{cases} \left(a^{\lfloor\frac b2\rfloor}\right)^2,&b\text{ 是偶数}\\ \\ a\left(a^{\lfloor\frac b2\rfloor}\right)^2,&b\text{ 是奇数} \end{cases}

只要知道 a^{\lfloor\frac b2\rfloor}，就能快速求出 a^b。

ll qmi(ll a,int k,int p){
    res=1;
    for(;k;k>>=1){
        if(k&1)(res*=a)%=p;
        (a*=a)%=p;
    }
    return res;
}

光速幂

给定 a,c，每次询问给出 b，快速求出 a^b\%c，预处理 \text{O}(\sqrt c)，每次询问复杂度 \text{O}(1)

先运用 a^b≡a^{b\%\varphi(c)+\varphi(c)}(\bmod c)，将 b 缩小到 2\varphi(c)(<2c) 的范围内。

a^b=a^{b\%\sqrt c}(a^{\sqrt c})^{\lfloor\frac b{\sqrt c}\rfloor}$，其中 $\left\lfloor\dfrac b{\sqrt c}\right\rfloor<2\sqrt c,b\%\sqrt c<\sqrt c

预处理 \left(a^{\sqrt c}\right)^i,a^j(1\le i<2\sqrt c,1\le j<\sqrt c) 即可。

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll a,b,m;
void read(ll m){
    bool f=0;b=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch<='9'&&ch>='0'){
        b=(b<<3)+(b<<1)+ch-'0';
        if(b>=m)b%=m,f=1;
        ch=getchar();
    }
    if(f)b+=m;
}
ll phi(ll m){
    ll res=m;
    for(int i=2;i<=m/i;i++){
        if(!(m%i)){
            res=res/i*(i-1);
            while(!(m%i))m/=i;
        }
    }
    if(m>1)res=res/m*(m-1);
    return res;
}
ll quick(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)(ans*=a)%=m;
        (a*=a)%=m;
        b>>=1;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&a,&m);
    read(phi(m));
    printf("%lld",quick(a,b)%m);
    return 0;
}

费马小定理

若存在整数a,p，a为整数，p为质数，那么a(p-1)≡1(mod\ p)

费马小定理是欧拉定理的一种特殊情况（当n为质数时\varphi(n)为n-1）

逆元

对于正整数 a,b，如果能找到正整数 x 使得 ax≡1(\bmod\ p)，我们称 x 是 a 在模 p 意义下的逆元，通常记作 a^{-1}。

在这里，实际上 a 与 x 互为模 b 意义下的逆元。

由同余方程可知，a 在模 p 意义下存在逆元，当且仅当 \text{gcd}(a,p)=1，即 a 与 p 互质。

在 [0,p) 的范围内，a 关于模 p 的逆元（若存在）是唯一的。

等价于求解 ax+by=1，直接用扩展欧几里得算法解决。

若 x 是质数，则 \varphi(x)=x-1,aa^{x-2}=a^{x-1}≡1(\bmod\ x)，所以逆元为 a^{x-2}，用快速幂计算。

在取模的意义下是不能直接作除法的，但利用逆元则可以。

在模意义下，除以一个数，相当于乘上这个数的逆元；或者说乘以一个数，等于除以这个数的逆元。

分数取模：\dfrac ax≡ax^{-1}(\bmod\ p)

$$i\left\lfloor\dfrac pi\right\rfloor+p\%i=p≡0 (\bmod\ p)\Leftrightarrow p\%i≡-i\left\lfloor\dfrac pi\right\rfloor\Leftrightarrow i^{-1}≡-\left\lfloor\dfrac pi\right\rfloor(p\%i)^{-1}$$ ```cpp //O(n) 求 1~n 模质数 p 的逆元 #include<iostream> #include<cstdio> #define ll long long using namespace std; const int N=3e6+5; ll n,p,inv[N]; int main(){ scanf("%lld%lld",&n,&p); inv[1]=1;puts("1"); for(int i=2;i<=n;i++){ inv[i]=(p-p/i)*inv[p%i]%p; printf("%lld\n",inv[i]); } return 0; } ``` **威尔逊定理** 在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。 即当 $p$ 为素数时，$(p-1)!+1$ 能被$p$整除. 用同余方程表示为， $(p-1)!\equiv -1\pmod p$，为 $p$ 是素数的充分必要条件。 $x^2≡1(\bmod\ p)$ 的解仅有 $x≡1,x≡-1(\bmod\ p)

所以 2~p-2 和逆元两两对应，剩下 p-1≡-1(\bmod\ p)

充分性证明

对于 p 不是素数的情况，我们分为以下几种情况来讨论：

当p=1时，直接带入，(1-1)!\equiv 0\pmod 1；

当p=4时，直接带入，(4-1)!\equiv 2\pmod 4；

当p>4且p为完全平方数时,

当p>4且p不是完全平方数时,

必要性证明

或

中国剩余定理（CRT）

设正整数 m_i 两两互质，则同余方程组：

\left\{\begin{matrix}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\x\equiv a_3\pmod{m_3}\\...\ ...\\x\equiv a_k\pmod{m_k}\end{matrix}\right.

有整数解，并且在模 M=m_1m_2...m_k 下的解是唯一的。

令 M=m_1m_2...m_k,M_i=M/m_i，

显然 (M_i,m_i)=1，所以 M_i 关于模 m_i 的逆元存在，不妨将此逆元设为 t_i，

于是有：

M_it_i≡1(\bmod\ m_i),M_it_i≡0(\bmod\ m_j)(i\ne j)

进一步：

a_iM_it_i≡a_i(\bmod\ m_i),a_iM_it_i≡0(\bmod\ m_j)(i\ne j)

因此解为：

x\equiv a_1M_1t_1+a_2M_2t_2+...+a_kM_kt_k(\bmod\ M)

且在 \bmod\ M 的意义下是唯一解。

扩展中国剩余定理（EXCRT）

求解 x，满足方程组 x≡a_i(\bmod\ m_i)，其中 m_i 不一定两两互质。

同样，在 \bmod\ \text{lcm}\{m_i\} 意义下有唯一解。

考虑如何每次将两个方程 \left\{\begin{matrix}x≡a_1(\bmod\ m_1)\\x≡a_2(\bmod\ m_2)\end{matrix}\right. 合并成一个方程。

\left\{\begin{matrix}x≡a_1(\bmod\ m_1)\\x≡a_2(\bmod\ m_2)\end{matrix}\right.\Leftrightarrow\left\{\begin{matrix}x≡a_1+k_1m_1\\x≡a_2+k_2m_2\end{matrix}\right.\Leftrightarrow k_1m_1-k_2m_2=a_2-a_1

先用扩展欧几里得算法求出 k_1m_1-k_2m_2=a_2-a_1 的一组特解 K1,K2，

\left\{\begin{matrix}x≡a_1+K_1m_1\dfrac{a_2-a_1}{\gcd(m_1,m_2)}\\x≡a_2+K_2m_2\dfrac{a_2-a_1}{\gcd(m_1,m_2)}\end{matrix}\right.

可以发现两个不同的解 x 的差一定是 \text{lcm}(m_1,m_2) 的倍数，

所以 x≡a_1+K_1m_1\dfrac{a_2-a_1}{\gcd(m_1,m_2)}≡a_2+K_2m_2\dfrac{a_2-a_1}{\gcd(m_1,m_2)}(\bmod\ \text{lcm}(m_1,m_2))