乘法逆元

发表于 分类于 阅读次数：

问题的提出

求 $(m \times \frac{a}{b}) \% c$ 的值。 一般情况下，我们可能会先算出 $m \times a$ 的值，然后除 $b$ 取模得出结果。但是，在 $ma$ 较大，不易存储时，我们就不得不在进行除法前先对 $ma$ 取模，但这又会导致取模的结果若小于 $b$，或者不能被 $b$ 整除，就会得出错误的结果；但直接用浮点数计算 $\frac{a}{b}$ 的数据误差较大，这就引出了乘法逆元。乘法逆元是解决取模意义下分数数值的重要手段。 我们可以假设存在这么一个数 $x$ 使得对于任意的 $n$，有 $xn \% p = \frac{n}{m} \% p$，这样就解决了上述的问题。称 $x$ 为 $m$ 在模 $p$ 意义下的（乘法）逆元，记作 $x=m^{-1}$ 或 $x=inv(m,p)$。例如，$2$ 是 $2$ 在模 $3$ 意义下的逆元。 注意 $xn\%p = \frac{n}{m} \% p$ 也可以被写成 $x\%p=\frac{1}{m}\%p$，即 $x \equiv \frac {1}{m} (mod \ p)$ 即 $xm \equiv 1 (mod \ p)$，这也是逆元较为常见的定义。

逆元的性质

自反性 $x=m^{-1},m=x^{-1}$

如何求逆元

单个逆元的求解

扩展欧几里得算法

已知 $m, p$ 求满足 $xm \equiv 1 (mod \ p)$ 的 $x$。 注意到 $xm \equiv 1 (mod \ p) \Leftrightarrow mx+py=1$，当 $gcd(m,p)=1$ 时有解，可以利用扩展欧几里得算法求解。

快速幂（费马小定理）

费马小定理：若 $p$ 是素数，$p \perp a$，则 $a^{p-1} \equiv 1 (mod \ p)$ 若 $xm \equiv 1 (mod \ p)$，则 $xm \equiv m^{p-1} (mod \ p), x \equiv m^{p-2} (mod \ p)$ 显然 $x=m^{p-2}$，这个数可以用快速幂求出。

多个逆元的求解

首先有 $1^{-1} = 1$ 假设 $p=ki+r$ 显然 $ki+r \equiv 0 (mod \ p)$ 同乘 $r^{-1}, i^{-1}$ 得 $kr^{-1} + i^{-1} \equiv 0 (mod \ p)$ $i^{-1} \equiv -kr^{-1} (mod \ p)$ $i^{-1} \equiv -\left \lfloor \frac{p}{i} \right \rfloor (p \% i)^{-1} (mod \ p)$ $i^{-1} \equiv (p - \left \lfloor \frac{p}{i} \right \rfloor )(p \% i)^{-1} (mod \ p)$

欧几里得算法

$gcd(a,b)=gcd(b,a \% b)$，当 $b=0$ 时 $gcd(a,b)=a$

1
int gcd(int a,int b) { return b?gcd(b,a%b):a; }

扩展欧几里得算法

现在考虑这样一个方程的求解： $ax+by=gcd(a,b)$ 当 $b=0$ 时，显然 $ax=gcd(a,b)=a \Rightarrow x=1$ 考虑当 $b \neq 0$ 的情况 $ax_1+by_1=gcd(a,b)$ $bx_2+(a\%b)y_2=gcd(b,a\%b)$ $gcd(a,b)=gcd(b,a\%b)$ 得 $ax_1+by_1=bx_2+(a\%b)y_2$ 带入 $a\%b=a-\frac{a}{b} \times b$ 得到 $ax_1+by_1=ay_2+b(x_2-\frac{a}{b} y_2)$ 显然 $x_1=y_2, y_1=x_2-\frac{a}{b} y_2$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int a,b,x,y;
exgcd(a,b,&x,&y);
...
void exgcd(int a,int b,int *x,int *y)
{
    if (b==0)
    {
        *x=1,*y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    int tmp=*x;
    *x=*y;
    *y=tmp-(a/b)(*y);
}

接下来考虑更普遍的情况 $ax+by=c$

注意这个方程等价于 $ax \equiv c (mod \ b)$，若存在特解 $x^\star $ 则存在通解 $x=x^\star +kb$。由此可知，若方程有解，那么一定在 $[0,b)$ 上有解，因此一般只考虑在这个区间的情况。

这个方程有几个性质：

性质一：若 $gcd(a,b)=1$ 则方程有唯一解

证明：若 $ax_1+by_1=c, ax_2 + by_2 = c$ 两式相减得 $a(x_1-x_2)=b(y_1-y_2)$ 因此 $x_1=x_2,y_1=y_2$

性质二：若 $gcd(a,b)=d$ 则方程在 $[0,b/d)$ 上有唯一解

证明：证明类似性质一

由此可知，上述方程有解当且仅当 $gcd(a,b) c$ 当满足这个条件时，将上述方程变换为 $\frac{a}{gcd(a,b)} x+\frac{b}{gcd(a,b)} y=\frac{c}{gcd(a,b)}$ 此时有 $gcd(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)})=1$ 即 $\frac{a}{gcd(a,b)} x+\frac{b}{gcd(a,b)} y=1$ 有解 $x_0,y_0$ 显然方程 $\frac{a}{gcd(a,b)} x+\frac{b}{gcd(a,b)} y=\frac{c}{gcd(a,b)}$ 的解即为 $\frac{c}{gcd(a,b)} x_0, \frac{c}{gcd(a,b)} y_0$ 也即为原方程的解