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

相关问题

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

5关于mod11的逆元

mod 11的逆元是指在模11下，一个数a存在一个数b，使得a*b ≡ 1 (mod 11)。

可以利用扩展欧几里得算法求解mod 11下的逆元。

举例来说，求8在模11下的逆元，即求一个数b，使得8*b ≡ 1 (mod 11)。

首先，我们可以列出扩展欧几里得算法的递推式：gcd(a,b) = gcd(b,a mod b)，同时记录每一步的系数x和y，使得gcd(a,b) = ax + by。因此，我们需要求出gcd(8,11)并且记录每一步的系数x和y。

通过递推，我们可以得到：

gcd(8,11) = gcd(11,8) = gcd(8,3) = gcd(3,2) = gcd(2,1)

同时，我们可以记录每一步的系数x和y：

gcd(8,11) = 3*(-3) + 2*4
gcd(11,8) = 2*(-2) + 3*3
gcd(8,3) = 1*1 + (-2)*3
gcd(3,2) = (-1)*2 + 1*3

将最后一行的式子改写为8*b ≡ 1 (mod 11)的形式，即可得到8在模11下的逆元b，即b=5。

因此，8在模11下的逆元为5。