求26关于mod31的逆元
时间: 2024-06-07 08:05:44 浏览: 16
要求 $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的逆元
要求一个数a在模31下的逆元,需要找到一个数x,使得ax ≡ 1 (mod 31)。我们可以使用扩展欧几里得算法来求解x。以下是求解的步骤:
1. 首先,我们需要确定a和31是否互质。如果它们不互质,那么a在模31下不存在逆元。可以使用欧几里得算法来判断它们的最大公约数,如果gcd(a, 31) != 1,则不存在逆元。
2. 如果a和31互质,我们可以使用扩展欧几里得算法求解逆元。扩展欧几里得算法可以找到一组整数x和y,使得ax + 31y = gcd(a, 31) = 1。
3. 我们只需要取模得到逆元,即x mod 31。
下面是求解11在模31下的逆元的示例:
1. gcd(11, 31) = 1,因此11在模31下存在逆元。
2. 使用扩展欧几里得算法求解:
我们可以先用欧几里得算法求出gcd(11, 31)的值:
31 = 11 * 2 + 9
11 = 9 * 1 + 2
9 = 2 * 4 + 1
因此,gcd(11, 31) = 1,可以继续进行扩展欧几里得算法。
从倒数第二个等式开始,我们可以表示1为前面两个数的线性组合:
1 = 9 - 2 * 4
接下来,我们将9用前面两个数的差表示:
1 = 9 - 2 * (11 - 9 * 1) = 3 * 9 - 2 * 11
最后,我们将11用前面两个数的差表示:
1 = 3 * (31 - 11 * 2) - 2 * 11 = 3 * 31 - 8 * 11
因此,11在模31下的逆元为3,即11 * 3 ≡ 1 (mod 31)。
172/7mod26的逆元怎么求
为了求解172/7 mod 26的逆元,我们首先需要确定7在模数26下是否有逆元。因为7和26互质,所以7在模数26下一定有逆元。
接下来,我们可以使用扩展欧几里得算法来找到7在模数26下的逆元。该算法的步骤如下:
1. 用较大的数26除以较小的数7,得到商3余5,即26 = 7 × 3 + 5。
2. 再用7除以5,得到商1余2,即7 = 5 × 1 + 2。
3. 接着,用5除以2,得到商2余1,即5 = 2 × 2 + 1。
4. 由于余数为1,所以2和7在模数26下互为逆元。
因此,我们可以得到7在模数26下的逆元为2。接着,我们可以使用逆元的定义来求解172/7 mod 26的逆元。即:
(172/7)^(-1) ≡ 7^(-1) * 172^(-1) (mod 26)
由于7在模数26下的逆元为2,所以上式可以化简为:
(172/7)^(-1) ≡ 2 * 172^(-1) (mod 26)
接下来,我们需要求解172在模数26下的逆元。由于172和26不互质,所以172在模数26下不存在逆元。因此,172/7 mod 26也不存在逆元。