如何求非质数模数的逆元

首先，需要确定模数 $p$ 是质数还是合数。如果 $p$ 是质数，则可以使用费马小定理求解非零元 $a$ 的逆元：

$$a^{-1} \equiv a^{p-2} \pmod{p}$$

如果 $p$ 是合数，则需要使用扩展欧几里得算法求解非零元 $a$ 的逆元。具体步骤如下：

1. 使用扩展欧几里得算法求解 $a$ 和 $p$ 的最大公约数 $d$，并确定 $ax + py = d$ 中的 $x$ 和 $y$。

2. 如果 $d \neq 1$，则 $a$ 没有逆元。

3. 如果 $d = 1$，则 $a$ 有逆元，且逆元为 $x$ 模 $p$ 下的余数，即 $a^{-1} \equiv x \pmod{p}$。

举个例子，假设要求 $a = 4$ 在模数 $p = 15$ 下的逆元。首先，使用扩展欧几里得算法求解 $4$ 和 $15$ 的最大公约数：

$$\gcd(4, 15) = 1$$

然后，确定 $4x + 15y = 1$ 中的 $x$ 和 $y$：

$$4 \cdot (-4) + 15 \cdot 1 = 1$$

因此，$4$ 在模数 $15$ 下的逆元为 $x = -4$ 模 $15$ 下的余数，即 $a^{-1} \equiv 11 \pmod{15}$。