本篇博客将介绍同余和逆元，以及求逆元的三种方法（因为快速幂是本菜鸡在很久之前c语言还没学完的时候扣了一晚上看懂了，所以默认大家都会了） 放到一起总结一下。拖了好久的说。。。 然后，开始了。。。

给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。（百度百科）

换句话说，就是两个整数a和b对于m取模时的余数相等，称a和b对于模m同余。记作a≡b(mod m)。 举个栗子吧，比如： 6 | (47-35)成立， 因此47≡35（mod 6），分析一下就是47%6=5，35%6=5，满足余数相等，因此说47和35对模6同余。 然后放一些与同余有关的定理吧 要注意的就是当除同余式的时候可能会出现错误。也就是说： a1 * c ≡ b1 * c ( mod m )并不能得出a1 ≡ b1 ( mod m)这一关系式。

下面说一个很有用的东西，也为了给后面的逆元做铺垫吧。这个很简单，大佬们可以直接跳过。

通过这个可以干很多事情，快速幂也用到了上面的两条性质。 这里举个不怎么 寻常的栗子吧， 我们很早之前就知道，如何判断一个数能否被三整除呢？ 是的，将这个数的每一位相加，看所求的和能否被三整除，那么，我们现在就可以用上面的性质来证明这一规律。 假设现在有一个三位数qaq百位是a，十位是b，个位是c，即qaq=100 *a+10 *b+c。 然后我们将qaq对3进行取模可以得到：qaq%3=（100%3） *（a%3）+（10%3） *（b%3) + c%3, 然后继续化简可以得到： qaq%3=（a%3）+（b%3) +（c%3）=（a+b+c)%3 因此只有当（a+b+c)%3=0的时候，qaq才能被3整除，到此证毕。

然后迫不及待的小伙伴们可能发现了，上面的两条性质包括了加减和乘法，遇到除法我们该怎么进行随时取模的运算呢？ 然后就引出了我们此篇博客的重点，逆元。

它是一个可以取消另一给定元素运算的元素。 对于正整数a和m，如果有a*x≡1(mod m)，那么把这个同余方程中x的最小正整数解叫做a模m的逆元。

思考了许久，先给一个前提吧，当然通用方法也会在后面附上。

求a(modm)意义下的逆元,要求a与m互质,否则不存在乘法逆元

简单理解来说，就是化除法为乘法，举个栗子，当我们遇到a/b的时候，我们可以将其变为a*(1/b)，也就是取倒数。只不过是在取模意义下的取倒数操作。 说起来很简单，但是实践起来还是一脸懵逼，本篇总结一下网上流传的三种常用方法吧。

首先引入费马小定理： 这给出定理的证明。（模大佬写博客法） https://www.cnblogs.com/shandongs1/p/7759747.html

然后我们就可以利用这一定理求逆元了，很容易看出来 a(p-1) ≡ 1(mod p)可以变为a*a(p-2)≡ 1 (mod p) 此时a在模p意义下的逆元就很显然的能看出来了，是a(p-2)，然后这个逆元我们就可以通过快速幂来求得，这是很简单很常用的一种方法。 代码（其实就是一个快速幂啦）