逆元的理解
数论中的逆元即数论倒数,既一个正整数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 | LL pow_mod(LL a, LL b, LL p){//a的b次方求余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 |
|