5在mod11下的逆元

要求一个数a在模11下的逆元，即找到一个数x，使得ax ≡ 1 (mod 11)。

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

1. 找到一对整数a和b，使得它们的最大公约数为1，即gcd(a,b)=1。

2. 使用扩展欧几里得算法计算a和b的最大公约数gcd(a,b)，同时找到一对整数x和y，使得ax+by=gcd(a,b)。因为gcd(a,b)=1，所以ax+by=1。

3. 如果b是模数，即b=11，那么x就是a在模11下的逆元。

现在我们来实现这个算法：

首先，我们需要找到a和11的最大公约数：

gcd(5, 11) = 1

接下来，我们使用扩展欧几里得算法来计算ax+by=1中的x和y：

11 = 2 × 5 + 1
1 = 11 − 2 × 5

因此，我们得到：

1 = 11 − 2 × 5

这意味着5的逆元在模11下为-2，或者说9。因此，5在模11下的逆元为9。