求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}$。

相关问题

求11关于mod31的逆元

在模31意义下，如果存在一个整数a和b，满足a*b ≡ 1 （mod 31），那么b就是a在模31意义下的逆元。

我们可以使用扩展欧几里得算法来计算模31下的逆元。具体步骤如下：

1. 首先，我们需要找到一个满足条件的整数a。在模31意义下，任何一个不是31的倍数的整数都满足这个条件。例如，我们可以选择a=11。

2. 接下来，我们需要找到整数b和c，使得11b + 31c = gcd(11, 31) = 1。使用扩展欧几里得算法，我们可以得到：

gcd(11, 31) = 11*(-3) + 31*1

因此，b=-3，c=1。

3. 最后，我们将b约束在模31意义下。在模31意义下，-3等价于28，因此11的逆元是28。

因此，11在模31意义下的逆元是28。

用欧几里得算法求550mod1769的逆元

首先，我们需要用欧几里得算法求出1769和550的最大公约数：

1769 = 3 * 550 + 119
550 = 4 * 119 + 94
119 = 1 * 94 + 25
94 = 3 * 25 + 19
25 = 1 * 19 + 6
19 = 3 * 6 + 1
6 = 6 * 1 + 0

因为最后余数为1，所以1769和550互质，也就是说550在模1769下有逆元。

然后，我们可以使用扩展欧几里得算法求出550在模1769下的逆元：

1 = 19 - 3 * 6
1 = 19 - 3 * (25 - 19 * 1) = 4 * 19 - 3 * 25
1 = 4 * (94 - 3 * 25) - 3 * 25 = 4 * 94 - 15 * 25
1 = 4 * 94 - 15 * (119 - 94 * 1) = 19 * 94 - 15 * 119
1 = 19 * (550 - 4 * 119) - 15 * 119 = 19 * 550 - 79 * 119
1 = 19 * 550 - 79 * (1769 - 3 * 550) = 238 * 550 - 79 * 1769

因此，550在模1769下的逆元为238。