同余的性质及逆元

makerY · 2023-06-10 09:51:30 · 个人记录

同余

定义

设 n 为正整数， a 和 b 为整数，如果 a 和 b 被 n 除后余数相同，那么称 a 和 b 模 n 同余，记作 a\equiv b\pmod n

性质

由定义，显然有a \equiv b \bmod n \Leftrightarrow n \mid a - b。

• 性质1 【前提：若 a\equiv b\pmod n 且 c\equiv d\pmod n 】

  1. a + c \equiv b + d \pmod n。

  2. ac\equiv bd\pmod n。

  3. ka\equiv kb\pmod n , k为任意整数。

  4. a^m\equiv b^m\pmod n , m 为任意正整数。

• 性质2

若 ab\equiv ac\pmod n 且 \gcd(a,n)=1，则 b\equiv c\pmod n。

即 同余式两边同时数可以同时除以a的条件是 a\perp n。

推论： \large a\equiv b\pmod n \Leftrightarrow \frac{a}{k} \equiv \frac{b}{k}\pmod {\frac{n}{\gcd(n,k)}} 。

乘法逆元

定义

若 \gcd(a,n)=1 且满足 ax\equiv 1\pmod p ，则称 x 为 a 模 b 的乘法逆元,记作 x=a^{-1}。

所以 a 存在模 n 的逆元 \Leftrightarrow \gcd(a,n)=1。

性质

则有 \frac{a}{b}\equiv m \pmod p

由性质1.2 ，两边同时乘 b\cdot b^{-1}，得 a\cdot b^{-1} \equiv b\cdot b^{-1}\cdot m \pmod p

又由逆元的定义，b \cdot b^{-1} \equiv 1 \pmod p

代入，显然有 a\cdot b^{-1} \equiv m \pmod p

得证。

作用

计算 \frac{a}{b} \bmod p 时，如果 a 在计算中会很大，就必须要先模 p 再计算，上式结果可直接通过 a \bmod p\cdot b^{-1} 计算。

求逆元

单个数的逆元

1. 费马小定理

要求 a 在模p意义下的一个逆元 x 满足 ax\equiv 1\pmod p

由费马小定理 a^{p-1}\equiv 1 \pmod p

得 a\cdot a^{p-2}\equiv 1 \pmod p

故显然 a 有一个逆元 x = a^{p-2}

2. 扩展欧几里得

由 ax \equiv 1 \pmod p \Leftrightarrow \exists y , ax+py=1，直接带入 exgcd 求出 x 即可。

线性递推求 1 \sim n 的逆元

P3811 【模板】乘法逆元

1. 递推

初始情况：当 i=1 时，i^{-1}\equiv 1 \pmod p

由余数的性质，显然有：p=i \times \lfloor \frac{p}{i} \rfloor + p \bmod i \equiv 0 \pmod p

由于 p 是质数，且有 0 \lt p \bmod i \lt i，故 i 和 p \mod i 的逆元一定存在（证明略）。

同余式两边同时乘这两者的逆元之积（目的是引入所求的 i^{-1} 并去除其系数），得到：

移项，得到：

每次都能用已经求过逆元的 p \bmod i 来推出 i 的逆元。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+100;
long long  inv[N],n,p;
int main()
{
    scanf("%lld%lld",&n,&p);printf("%lld\n",inv[1]=1);
    for(int i=2;i<=n;i++) printf("%lld\n",inv[i]=(p-inv[p%i]*(p/i)%p)%p);//注意括号不能少 
    return 0;
}

2. 倒推

若已知 inv_{i+1}，则有公式 inv_i=inv_{i+1}\times (i+1)。

证明：

由 fac_{i}\times inv_{i}=1

故得证。