去模运算（逆元）

diary

1.最近这几天连着训练,累s了,咸鱼属性正在觉醒.....

attention

文章逻辑较为繁琐,请仔细耐心阅读
建议放大后远距离阅读,感受最佳

引入

许多题目中要用到除法取模
但在取模等式等价变形中没有除法,为啥?

\((6\div3)\bmod 4 \not= (6 \bmod 4\div 3 \bmod 4) \bmod 4\)

说明如果在计算数字过大时可能超范围,那么应该怎么办呢?

前置知识 快速幂

不懂可以去看鄙人的博客关于位运算

同余符号

\(a\equiv1\pmod{n}\) 这个三条横线的符号表示\(a\)对\(n\)取模等于1对\(n\)取模

单位元 \(a\equiv1\pmod{n}\)

在一个集合中，对于某种运算，如果对于任何的集合元素 \(a\)，和元素 \(e\) 运算，得到还是集合元素 \(a\) 本身，则称 \(e\) 为这个运算下的单位元。

加法

\(a\)为任意实数,若\(a\) + \(e\) = \(a\) 则称 \(e\)是 单位元 0

乘法

\(a\)为任意实数,若 \(a\) * \(e\) = \(a\) 则称 \(e\) 是单位元 1

模乘

模乘的单位元是\(1\pmod{n}\)
证明如下：
对于模 n 乘法，所有模 n 和 a 同余的数都可以表示成
\(a\pmod{n}=kn+a\)
设单位元为\(e\pmod{n}\)，我们将\(e\pmod{n}\)和\(a\pmod{n}\)进行模乘,得:
\(e\pmod{n}\) * \(a\pmod{n}\)
= (\(k_1\)\(n\) + \(e\)) * (\(k_2\)\(n\) + \(a\))
= \(k_1\)\(k_2\)\(n^2\)+\(a\)\(k_1\)\(n\)+\(e\)\(k_2\)\(n\)+\(a\)\(e\)
= (\(k_1\)\(k_2\)\(n\)+\(a\)\(k_1\)+\(e\)\(k_2\))\(n\)+\(a\)\(e\)

有因为 根据单位元的定义: \(e\pmod{n}\) * \(a\pmod{n}\) = \(a\pmod{n}\)
进一步可得: (\(k_1\)\(k_2\)\(n\)+\(a\)\(k_1\)+\(e\)\(k_2\)) \(n\) + \(a\)\(e\) = \(k\)\(n\)+\(a\)

\(\begin{cases}k=k_1k_2n+ak_1+ek_2 \\ e = 1 \end{cases}\)
模乘的单位元是\(1\pmod{n}\)
得证

逆元

在一个集合中，对于某种运算 ，如果任意两个元素的运算结果等于单位元 \(e\) ，则称这两个元素互为逆元。

加法

a为任意实数,\(a\)的逆元是 -\(a\)

乘法

a为任意非零实数,\(a\)的逆元是 \(a^{-1}\) 或 \(\frac{1}{a}\)

模乘

主角登场
 模乘运算中，任意整数 \(a\pmod{n}\) 的逆元表示为： \(a^{-1}\pmod{n}\)
提前避坑
分数的取模运算非常"神奇"
如 解 \(\dfrac{1}{3}\) mod 8
设:\(n\equiv(\dfrac{1}{3})\pmod{8}\)
\(3n\equiv1\pmod{8}\)
\(3n\pmod{8}\) = 1
易得\(n\) = \(3\)

所以 \(\dfrac{1}{3}\) mod \(8\) = \(3\)

根据逆元的定义,可知
\(aa^{-1}\equiv1\pmod{n}\)

引入

学到这我们知道了求(a \(\div\) b)mod \(n\)可以转换为(\(a\)*\(b^{-1}\))mod \(n\) \(a\pmod{n}\) * \(b^{-1}\pmod{n}\)

而 \(b^{-1}\pmod{n}\) 是 \(b\pmod{n}\)的逆元

那么逆元怎么求呢

求解逆元 费马小定理

若\(p\)是质数,则对于任意整数\(a\),有\(a^p\equiv a \pmod{p}\)
进行转换得\(1 \equiv a^{p-1} \pmod{p}\)
\(a^{-1} \equiv a^{p-2} \pmod{p}\)

显然,当你要求\(x^{-1}\)时且 模数 为质数时,用费马小定理求即可

扩展欧几里得定理(\(B\acute{e}zout\)定理)

在这之前你需要学习欧几里得算法也就是求\(\gcd\),不懂的同学可以去看最大公约数(gcd)

对于任意整数\(a\),\(b\), 存在一对整数,满足\(ax\)+\(by\)=\(\gcd(a,b)\)

证明如下:

1、在欧几里得算法的最后一步,即求出\(a_1\)=\(\gcd(a,b)\),\(b_1\) = \(0\) 时显然有一对整数 \(x\) = \(1\) y=\(0\) 满足
\(a_1*1\)+\(b_1\)*\(0\) =\(\gcd(a,b)\) = \(a_1\)
2、若\(b>0\), 则\(\gcd(a,b)\) = \(\gcd(b,a \bmod b)\).假设存在一对整数\(x,y\),满足\(b\) * \(x\)+\((a \bmod b)\) * \(y\) = \(\gcd(b,a \bmod b)\)

转换得: \(bx\)+(\(a\)-\(b \lfloor a/b \rfloor\) )\(y\) = \(ay\)+\(b\)(\(x\) - \(\lfloor a/b \rfloor y\) ) = \(\gcd(b,a \bmod b)\)

所以令 \(x'\) = \(y\), \(y'\) = \(x\) - \(\lfloor a/b \rfloor y\)
就得到了 \(ax'\) + \(by'\)=\(\gcd(a,b)\)
对欧几里得算法的递归过程应用数学归纳法,可知\(B\acute{e}zout\)定理成立

当你要求\(s^{-1}\)时,已知模数为\(n\)(质数)
根据\(ss^{-1} \equiv 1 \pmod{n}\)转化得 \(ss^{-1}\) = \(kn+1\)
\(ss^{-1}\) - \(kn\) = \(1\)
因为 \(k\)的正负无关 可看为 \(ss^{-1}\) + \(kn\) = \(1\)

由于\(ax\)+\(by\)=\(\gcd(a,b)\)
设\(a\) = \(s\),\(b\) = \(n\) ,\(x\) = \(s^{-1}\) , \(y\) = \(k\)
由于\(b\) = \(n\)是质数,所以\(\gcd(a,b)\) = \(1\)

用上述公式递归求出即可
代码实现如下

#include <bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
	int temp,d;
	if (b==0){
		x=1;
		y=0;
		return a;
	}d=exgcd(b,a%b,x,y);
	temp=x;
	x=y;
	y=temp-a/b*y;
	return d;
}
int main(){
	int d,x,y;
	d=exgcd(i,n,x,y);
	return 0;
}

线性同余方程(逆元同理) 题目

给定整数\(a\),\(b\),\(m\),求一个整数\(x\)满足\(a\)\(x \equiv b \pmod{m}\) , 或者给出无解.因为未知数\(x\)的指数是\(1\),我们称之为一次同余方程,也称线性同余方程
\(a\)\(x \equiv b \pmod{m}\)
等价于 \(ax\) = -\(km\) + \(b\) (\(k\) 的正负不重要)
移项 \(a\) * \(x\) + \(k\) * \(m\) = \(b\)
根据\(B\acute{e}zout\)定理 ( \(ax\) + \(by\) = \(\gcd(a,b)\) )
当\(\gcd(a,m)|b\)时,此同余方程有解

设已知的\(a\),\(m\)为\(a\),\(b\),设未知的\(x\),\(k\)为\(x\),\(y\)

求出一组整数\(x_0\),\(y_0\),满足 \(a\) * \(x_0\) + \(b\) * \(y_0\) = \(\gcd(a,b)\)
然后\(x\) = \(x_0\) * \(b\) / \(\gcd(a,b)\)
就是原线性方程的一个解

后记

家人们,博主为了这篇博客整整做了好几天,劳烦家人们点个小赞
Thanks♪(･ω･)ﾉ