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。

相关问题

4关于mod11的逆元

在模11意义下，一个数a的逆元是指另一个数b，使得a*b ≡ 1 (mod 11)。换句话说，b是a在模11意义下的倒数。

我们可以使用扩展欧几里得算法来计算模11意义下一个数的逆元。具体来说，假设我们要计算数a的逆元，我们需要找到一对整数x和y，使得ax + 11y = 1。这样，根据同余的性质，我们可以得到ax ≡ 1 (mod 11)，即a的逆元为x。

下面是一个求逆元的Python代码示例：

def mod_inverse(a, m):
    # 利用扩展欧几里得算法求逆元
    x, y, d = extended_gcd(a, m)
    if d != 1:
        # a和m不互质，不存在逆元
        return None
    else:
        # 返回a在模m意义下的逆元
        return x % m

def extended_gcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, d = extended_gcd(b, a % b)
        return y, x - (a // b) * y, d

在上面的代码中，我们利用了一个名为extended_gcd的函数来计算两个数的最大公约数以及对应的x和y。然后，我们使用mod_inverse函数来计算模11意义下一个数的逆元。如果该数和11不互质，则不存在逆元，函数将返回None。否则，函数将返回该数在模11意义下的逆元。

例如，我们可以使用以下代码来计算3在模11意义下的逆元：

print(mod_inverse(3, 11))  # 输出为 4

因为3和11互质，所以3在模11意义下的逆元为4。

求11关于mod31的逆元

要求11关于mod31的逆元，需要先计算11在模31下的乘法逆元。

根据扩展欧几里得算法，我们可以计算出：

``31 = 2 * 11 + 9
11 = 1 * 9 + 2
9 = 4 * 2 + 1
1 = 9 - 4 * 2
= 9 - 4 * (11 - 1 * 9)
= 5 * 9 - 4 * 11
= 5 * (31 - 2 * 11) - 4 * 11
= -14 * 11 + 5 * 31

因此，11在模31下的乘法逆元为-14，即17。也就是说，$11\times17\equiv1\pmod{31}$。