模11乘法幺元和各元素逆元

在模11的意义下，有：

- 模11乘法幺元为1，即任何数乘以1后模11的余数仍为该数本身。
- 如果a是模11的一个非零剩余类，则a在模11的意义下存在逆元b，使得ab ≡ 1 (mod 11)。其中b也是一个非零剩余类。具体来说，模11的各元素逆元如下：

1^-1 ≡ 1 (mod 11)
2^-1 ≡ 6 (mod 11)
3^-1 ≡ 4 (mod 11)
4^-1 ≡ 3 (mod 11)
5^-1 ≡ 9 (mod 11)
6^-1 ≡ 2 (mod 11)
7^-1 ≡ 8 (mod 11)
8^-1 ≡ 7 (mod 11)
9^-1 ≡ 5 (mod 11)
10^-1 ≡ 10 (mod 11)

其中符号“≡”表示同余。

相关问题

C++求模运算的乘法逆元

对于正整数a和m，如果存在一个正整数x满足ax ≡ 1 (mod m)，那么我们称x为a在模m意义下的乘法逆元。如果不存在这样的x，我们则称a在模m意义下没有乘法逆元。

求模运算的乘法逆元的方法有很多，以下是其中一种方法：

使用扩展欧几里得算法求解a和m的最大公约数gcd(a,m)，如果gcd(a,m)>1，说明a在模m意义下没有乘法逆元；
如果gcd(a,m)=1，那么根据扩展欧几里得算法的推论，可以求解出一组整数x和y，使得ax+my=gcd(a,m)=1；
因为ax ≡ 1 (mod m)，所以ax ≡ 1 + km，其中k是一个整数；
因此，x ≡ (1 + km)/a (mod m)，其中k可以是任意整数，但是为了保证x在模m意义下的值最小，一般取k使得x的值在0~m-1之间。具体地，可以先计算(1 + km)%m，然后再计算 (1 + km)/a mod m。

以上就是求模运算的乘法逆元的基本方法。在实际计算中，可以预处理出所有1~m-1之间的整数在模m意义下的乘法逆元，存储在一个数组中，在需要使用时直接查表就可以了。

11 mod448的乘法逆元

为了求解11在模数448下的乘法逆元，我们需要找到一个数x，使得11x ≡ 1 (mod 448)。

根据扩展欧几里得算法，我们可以求得11在模数448下的乘法逆元为77，即11 x 77 ≡ 1 (mod 448)。

具体计算过程如下：

首先，我们可以使用扩展欧几里得算法求出11和448的最大公约数以及对应的贝祖等式系数。具体来说，我们可以执行以下步骤：

1. 用较小的数去除以较大的数，并记录余数，即：

448 = 11 × 40 + 8

2. 用上一步的除数去除上一步的余数，并记录余数，即：

11 = 8 × 1 + 3

3. 用上一步的除数去除上一步的余数，并记录余数，即：

8 = 3 × 2 + 2

4. 用上一步的除数去除上一步的余数，并记录余数，即：

3 = 2 × 1 + 1

5. 由于余数为1，我们可以停止算法。此时，我们可以将每一步的余数用贝祖等式系数表示，即：

1 = 3 - 2 × 1
= 3 - (8 - 3 × 2) × 1
= 3 × 3 - 8
= (11 - 8 × 1) × 3 - 8
= 11 × 3 - 8 × 4
= 11 × 3 - (448 - 11 × 40) × 4
= 11 × 19 - 448 × 4

根据上面的贝祖等式，我们可以发现11和448的最大公约数为1，且11在模数448下的乘法逆元为19。然而，由于19不是在0到448之间的数，因此我们需要将19转化为在这个范围内的数。具体来说，我们可以执行以下步骤：

1. 计算19除以448的商和余数，即：

19 = 0 × 448 + 19

2. 由于19是我们需要的数，因此我们可以得到11在模数448下的乘法逆元为77，即：

11 × 77 ≡ 1 (mod 448)

因此，11在模数448下的乘法逆元为77。