a\x mod p=a*x^(p-2) mod p

ax mod p=a*x^(p-2) mod p
其中p为质数
为什么?
据说是乘法逆元
nfzzh 1年前 已收到1个回答 举报

heying613 幼苗

共回答了17个问题采纳率:64.7% 举报

确实是乘法逆元的问题.若 a*b mod p = 1 则a和b互为乘法逆元.
x 和 x^(p-2) 互为乘法逆元
因为 由:x*x^(p-2) mod p = 1 (式1) 推出 x^(p-1) mod p = 1 (式2),根据费马小定理,式2是成立的.
所以,x 和 x^(p-2) 互为乘法逆元 .
所以ax 就相当于a*x^(p-2).

1年前

8
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 2.067 s. - webmaster@yulucn.com