数论入门:逆元

逆元的理解

数论中的逆元即数论倒数，既一个正整数a，存在另一个正整数x使得$a\times x≡1(\mod p)$（其中a与p互素），则称x为a的一个关于p的逆元。

逆元的由来

为什么要有逆元这个说法呢，类比到矩阵中去，在矩阵乘法中，两个乘积为单位矩阵的矩阵，其中一个矩阵就是另一个矩阵的逆矩阵，这样就解决了矩阵中没有定义除法的问题。

而类似的，在数论中也没有除法的相关定义（学过线代会知道整数集对于除法是不封闭的），于是我们就思考如何将乘法转换为除法（参考实数集中的分数）。

再来举几个取模中的例子来说明一下：

再取模运算的规律中，有如下几个定义：

$(a + b) \mod p = (a\mod p + b\mod p) \mod p$

$(a - b) \mod p = (a\mod p - b\mod p) \mod p$

$(a \times b) \mod p = (a\mod p \times b\mod p) \mod p $

为什么其中没有定义除法相关的取模运算呢？

来举个例子

对于$(100/50)\mod 20$来说，结果应该是2；

那么如果使用上述定义的方法来计算这个值，也就是$((100\mod 20) /(50\mod 20))\mod 20$，
那么结果应该是0，显然是矛盾的，也就是说对于除法来说，取模运算时非常复杂的，而在计算机中，通常需要计算两个很大的数字相除的时候，是存不下的，但这个时候又不能使用取模公式使分子和分母变小，于是就有了逆元

逆元的概念

在实数集中我们如何将除法转化为乘法呢，我们定义了分数，也就是

若$a\times x=1$，就令$x=1/a$，如果a不为1，x就为小数。

而在数论中要考虑的问题就变成了$a\times x≡1(\mod p)$，而这里的x还是1/x嘛？答案是不是，举个例子：

$2\times 3\mod 5=1$

所以逆元也叫数论倒数。这里我们令$x=inv(a,p)$，也就是表示a模p运算时的逆元。

那么我们再来思考这个问题$(a/b)\mod p$要如何来转化，我们先将除法变为乘法，也就是$(a\times inv(a,p))\mod p$。

于是我们就能使用乘法公式进行展开，变为$(a\mod p\times inv(a,p)\mod p)\mod p$，于是我们缩小a的目的就达到了。

下面介绍如何计算逆元

逆元的计算

首先明确只有当a与p互质时，a才存在关于p的逆元。求逆元的方法主要时利用费马小定理和拓展欧几里得定理

费马小定理

证明

数论四大定理中的费马小定理是这样定义的：

$a^{p-1}≡1(\mod p)$,其中p为素数，a与p互素。

那么我们两边同时乘以a关于p的逆元，也就得到了$a^{p-1} \times inv(a,p)≡inv(a,p)(\mod p)$

于是由逆元的性质得到了逆元的计算方法：

$a^{p-2}≡inv(a,p)(\mod p)$

也就是$a^{p-2}=inv(a,p)(\mod p)$，再使用一次快速幂就能得到逆元了

代码

1
2
3
4
5
6
7
8
9
10
11
12

LL pow_mod(LL a, LL b, LL p){//a的b次方求余p 
    LL ret = 1;
    while(b){
        if(b & 1) ret = (ret * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ret;
}
LL Fermat(LL a, LL p){//费马求a关于b的逆元 
        return pow_mod(a, p-2, p);
}

拓展欧几里得算法

当a，b互质的时候，贝祖定理得到的结果应该是长这样的：

$a\times x+b\times y=1$

贝祖定理证明了这个式子是有解的。接下来我们让两边同时取模b，得到：

$a\times x\mod b+b\times y\mod b=1\mod b$

也就是

$a\times x\mod b=1\mod b$

于是得到同余方程：

$a\times x≡1(\mod b)$

于是x就是inv(a,b)。于是就能通过拓展欧几里得算法，求出x。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include<cstdio>
typedef long long LL;
void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){
    if (!b) {d = a, x = 1, y = 0;}
    else{
        ex_gcd(b, a % b, y, x, d);
        y -= x * (a / b);
    }
}
LL inv(LL t, LL p){//如果不存在，返回-1 
    LL d, x, y;
    ex_gcd(t, p, x, y, d);
    return d == 1 ? (x % p + p) % p : -1;
}
int main(){
    LL a, p;
    while(~scanf("%lld%lld", &a, &p)){
        printf("%lld\n", inv(a, p));
    }
}

参考链接

境外之主