求26关于mod31的逆元

要求 $26$ 在 $\mod 31$ 意义下的逆元，即找到一个整数 $x$，满足 $26x \equiv 1 \pmod{31}$。

可以使用扩展欧几里得算法求解。首先，计算 $31$ 和 $26$ 的最大公约数：

$$\begin{aligned} 31 &= 1 \cdot 26 + 5 \\ 26 &= 5 \cdot 5 + 1 \\ 5 &= 5 \cdot 1 + 0 \end{aligned}$$

可以看出，最大公约数为 $1$，因此 $26$ 在 $\mod 31$ 意义下存在逆元。

接下来，可以使用逆向扩展欧几里得算法求解逆元：

$$\begin{aligned} 1 &= 26 - 5 \cdot 5 \\ &= 26 - 5 \cdot (31 - 26) \\ &= 6 \cdot 26 - 5 \cdot 31 \end{aligned}$$

因此，$26$ 在 $\mod 31$ 意义下的逆元为 $6$。即 $26 \cdot 6 \equiv 1 \pmod{31}$。