用推广的Buclid算法求67mod119的逆元。
时间: 2024-02-25 18:56:22 浏览: 145
求模逆元的一种算法
首先,我们需要判断67和119是否互质。因为只有当两个数互质时,才能使用扩展欧几里得算法求其逆元。根据辗转相除法可得:
```
119 = 67 * 1 + 52
67 = 52 * 1 + 15
52 = 15 * 3 + 7
15 = 7 * 2 + 1
7 = 1 * 7 + 0
```
因为最后余数为1,所以67和119是互质的。
接下来,我们使用Buclid算法求67模119的逆元。首先,我们定义:
```
r0 = 119, r1 = 67
s0 = 1, s1 = 0
t0 = 0, t1 = 1
```
然后,我们根据以下公式不断更新$r$、$s$和$t$:
```
ri = ri-2 - qi * ri-1
si = si-2 - qi * si-1
ti = ti-2 - qi * ti-1
```
其中,$qi$表示$r_{i-2}$除以$r_{i-1}$的商。
我们一直进行这个过程,直到$r_i$等于1为止。此时,$t_i$即为67模119的逆元。具体过程如下:
```
r2 = r0 % r1 = 119 % 67 = 52
q1 = r0 // r1 = 119 // 67 = 1
s2 = s0 - q1 * s1 = 1 - 1 * 0 = 1
t2 = t0 - q1 * t1 = 0 - 1 * 1 = -1
r3 = r1 % r2 = 67 % 52 = 15
q2 = r1 // r2 = 67 // 52 = 1
s3 = s1 - q2 * s2 = 0 - 1 * 1 = -1
t3 = t1 - q2 * t2 = 1 - 1 * (-1) = 2
r4 = r2 % r3 = 52 % 15 = 7
q3 = r2 // r3 = 52 // 15 = 3
s4 = s2 - q3 * s3 = 1 - 3 * (-1) = 4
t4 = t2 - q3 * t3 = -1 - 3 * 2 = -7
r5 = r3 % r4 = 15 % 7 = 1
q4 = r3 // r4 = 15 // 7 = 2
s5 = s3 - q4 * s4 = -1 - 2 * 4 = -9
t5 = t3 - q4 * t4 = 2 - 2 * (-7) = 16
```
因为$r_5$等于1,所以67在模119意义下的逆元为$t_5$的模119的余数,即16。
所以,67在模119意义下的逆元为16。
阅读全文