利用Fermat小定理,a^{p-1}=1(mod p),所以取x=a^{p-2}就行了,实际计算的时候可以不断地平方并取模.对于你的例子,x=10^15,也可以取模之后得到x=12.
辗转相除法则是寻找ax+py=1的解,这时候p是质数的条件不重要,只需要gcd(a,p)=1,对a,p做辗转相除序列就行了,比如说p=am+r,那么ax+py=a(x+my)+ry,归约成关于(r,a)的问题,对于你的例子,
17=10+7
10=7+3
7=2×3+1
从最后一个式子倒推回去得到
1=7-2×3=7-2×(10-7)=3×7-2×10=3×(17-10)-2×10=3×17-5×10
所以可以取x=-5,或者说x=12 利用Fermat小定理,a^{p-1}=1(mod p),所以取x=a^{p-2}就行了,实际计算的时候可以不断地平方并取模.对于你的例子,x=10^15,也可以取模之后得到x=12.
辗转相除法则是寻找ax+py=1的解,这时候p是质数的条件不重要,只需要gcd(a,p)=1,对a,p做辗转相除序列就行了,比如说p=am+r,那么ax+py=a(x+my)+ry,归约成关于(r,a)的问题,对于你的例子,
17=10+7
10=7+3
7=2×3+1
从最后一个式子倒推回去得到
1=7-2×3=7-2×(10-7)=3×7-2×10=3×(17-10)-2×10=3×17-5×10
所以可以取x=-5,或者说x=12