求非质数模数的逆元：扩展欧几里得算法详解

首先，需要确定模数'p'是质数还是合数。如果'p'是质数，则可以使用费马小定理求解非零元'a'的逆元：/n/n$$a^{-1} //equiv a^{p-2} //pmod{p}$$/n/n如果'p'是合数，则需要使用扩展欧几里得算法求解非零元'a'的逆元。具体步骤如下：/n/n1. 使用扩展欧几里得算法求解'a'和'p'的最大公约数'd'，并确定'ax + py = d'中的'x'和'y'。/n/n2. 如果'd != 1'，则'a'没有逆元。/n/n3. 如果'd = 1'，则'a'有逆元，且逆元为'x'模'p'下的余数，即'a^{-1} //equiv x //pmod{p}'。/n/n举个例子，假设要求'a = 4'在模数'p = 15'下的逆元。首先，使用扩展欧几里得算法求解'4'和'15'的最大公约数：/n/n$$/gcd(4, 15) = 1$$/n/n然后，确定'4x + 15y = 1'中的'x'和'y'：/n/n$$4 //cdot (-4) + 15 //cdot 1 = 1$$/n/n因此，'4'在模数'15'下的逆元为'x = -4'模'15'下的余数，即'a^{-1} //equiv 11 //pmod{15}'。