题目

怎样用费马定理和Euclid算法求ax mod p=1的逆x a、x均为整数,p是素数,a＜p,且gcd(a,p)=1.求大神给个解题证明,或者例题如：10xmod17=1的解题过程.

提问时间：2021-03-25

答案

利用Fermat小定理,a^{p-1}=1(mod p),所以取x=a^{p-2}就行了,实际计算的时候可以不断地平方并取模.对于你的例子,x=10^15,也可以取模之后得到x=12.辗转相除法则是寻找ax+py=1的解,这时候p是质数的条件不重要,只需要gcd...