1：为什么要使用乘法逆元

1 b frac{1}{b} b1 mod p，这种是无法求模的，数学家就引入了逆元。 逆元：用在模p意义下的整数代替在模p意义下的分数。

A：在非模的情况下

公式：a * b=1 我们就可以说b是a的逆元，也可以说a是b的逆元。逆元==倒数。 ∵ a * 1 a frac{1}{a} a1 = 1 ∵ a * b = 1 ∴ b == 1 a frac{1}{a} a1 性质：a的逆元（倒数）具有唯一性

B：在模的情况下

公式：a * b ≡ equiv ≡ 1（mod p）

我们可以说b是a的逆元，也可以说a是b的逆元。逆元！=倒数。

举例： { a = 5 p = 7 left{ egin{array}{c} a=5 \ p=7 end{array} ight. { a=5p=7

f ( b ) = { 3 , if k is 0 3 + 7 , if k is 1 3 + （ 7 ∗ 2 + 1 ） , if k is 2 3 + （ 7 ∗ k + 1 ） , if k >=3 f(b)= egin{cases} 3, & ext {if $k$ is 0} \ 3 +7, & ext{if $k$ is 1} \ 3 + （7*2+1）, & ext{if $k$ is 2} \ 3+（7*k+1）,& ext{if $k$ >=3} end{cases} f(b)=⎩⎪⎪⎪⎨⎪⎪⎪⎧3,3+7,3+（7∗2+1）,3+（7∗k+1）,if k is 0if k is 1if k is 2if k >=3 在模p的意义下，b为a的 “逆元” 有很多个，但是 b mod p只有一个，上述情况就只有3，也就是合法b的最小正整数。 你会发现：在模p的意义下，b用整数代替了分数。b用3代替了 1 5 frac{1}{5} 51。

是不是有点感觉了，我们再举例一下： 公式： 1 5 frac{1}{5} 51 mod 7 * 5 mod 7=1 3 mod 7 * 5 mod 7=3 * 5 mod 7=15 mod 7 = 1 公式： 6 5 frac{6}{5} 56 mod 7 * 5 mod 7 = 6 6 * 3 mod 7 * 5 mod 7 = 18 mod 7 * 5 mod 7=4 * 5 mod 7 =20 mod 7=6

2：证明逆元 y a ≡ y ∗ b （ m o d    p ） frac{y}{a} equiv y * b（mod ;p） ay≡y∗b（modp）

{ a ∗ b ≡ 1 （ m o d    p ） （ 1 ） left{ egin{array}{c} a * b equiv 1（mod ; p） （1） end{array} ight. { a∗b≡1（modp）（1） { y a ≡ m （ m o d    p ） y a ∗ a ≡ a ∗ m （ m o d    p ） y ≡ a ∗ m （ m o d    p ） y ∗ b ≡ a ∗ b ∗ m （ m o d    p ） 引 用 （ 1 ） ： y ∗ b ≡ m （ m o d    p ） left{ egin{array}{c} frac{y}{a} equiv m（mod ; p）\ frac{y}{a} * a equiv a * m（mod ; p）\ y equiv a * m（mod ; p）\ y * b equiv a * b * m（mod ; p）\ 引用（1）： y * b equiv m（mod ; p）\ end{array} ight. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧ay≡m（modp）ay∗a≡a∗m（modp）y≡a∗m（modp）y∗b≡a∗b∗m（modp）引用（1）：y∗b≡m（modp）

3：如何获得逆元b

费马小定理: a p − 1 ≡ 1 （ m o d    p ） a{^{p-1}} equiv 1（mod ;p） ap−1≡1（modp）

a p − 1 ≡ 1 （ m o d    p ） ⟹ a ∗ a p − 2 ≡ 1 （ m o d    p ） a{^{p-1}} equiv 1（mod ;p）Longrightarrow a * a{^{p-2}} equiv 1（mod ;p） ap−1≡1（modp）⟹a∗ap−2≡1（modp） 在模p的意义下， a p − 2 a{^{p-2}} ap−2就是a的逆元