质数的定义：只有两个正因数（1和自己）的自然数即为质数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的作用。

如从1至72有20个素数：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71。

乘法逆元，是指数学领域群G中任意一个元素a，都在G中有唯一的逆元a‘，具有性质a×a'=a'×a=e，其中e为该群的单位元。

定义：如果ab≡1（mod m），则称b是a的模m逆，记作a的模m逆是方程ax≡1（mod m）的解。

例如：4关于1模7的乘法逆元为多少？

4X≡1 mod 7 这个方程等价于求一个X和K，满足4X=7K+1，其中X和K都是整数。

若ax≡1 mod f,则称a关于1模f的乘法逆元为x。也可表示为ax≡1(mod f)。

当a与f互素时，a关于模f的乘法逆元有解（并且这个解小于f）。如果不互素，则无解。如果f为素数，则从1到f-1的任意数都与f互素，即在1到f-1之间都恰好有一个关于模f的乘法逆元。

上述也称为逆元的存在性定理。

例如，求5关于模14的乘法逆元：

14=5*2+4

5=4*1+1

说明5与14互素，存在5关于14的乘法逆元。

1=5-4=5-(14-5*2)=5*3-14

因此，5关于模14的乘法逆元为3。

如果还是不理解，就再来看几个例子吧~

<eg1>求5的模7逆。

做辗转相除法，求得整数b，k，使得5b+7k=1，则b是5的模7逆。

计算过程如下：7 = 5+2

5 = 2*2+1

回代 1 = 5-2*2 = 5-2*（7-5）= 3+5-2*7

得 5^-1≡3（mod 7）。

<eg2>求7的模26逆。

方法一：

可以遍历1到26中和26互素的数（3，5，7，9，11，15，17，19，21，23，25），能和7相乘mod 26 = 1的点数就是它的逆，很容易求出7*15=105，26*4=104，所以逆元为15。

方法二：

令7a = 1+26k，很容易得到一组解：a=15，k=4，所以7^-1≡15（mod 26）。

————————————————

版权声明：本文为CSDN博主「你好，明天，，」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/baidu_41774120/article/details/121178487