用欧几里得算法求550mod1769的逆元
时间: 2023-09-30 21:06:06 浏览: 68
首先,我们需要用欧几里得算法求出1769和550的最大公约数:
```
1769 = 3 * 550 + 119
550 = 4 * 119 + 94
119 = 1 * 94 + 25
94 = 3 * 25 + 19
25 = 1 * 19 + 6
19 = 3 * 6 + 1
6 = 6 * 1 + 0
```
因为最后余数为1,所以1769和550互质,也就是说550在模1769下有逆元。
然后,我们可以使用扩展欧几里得算法求出550在模1769下的逆元:
```
1 = 19 - 3 * 6
1 = 19 - 3 * (25 - 19 * 1) = 4 * 19 - 3 * 25
1 = 4 * (94 - 3 * 25) - 3 * 25 = 4 * 94 - 15 * 25
1 = 4 * 94 - 15 * (119 - 94 * 1) = 19 * 94 - 15 * 119
1 = 19 * (550 - 4 * 119) - 15 * 119 = 19 * 550 - 79 * 119
1 = 19 * 550 - 79 * (1769 - 3 * 550) = 238 * 550 - 79 * 1769
```
因此,550在模1769下的逆元为238。
相关问题
用欧几里得算法求550模1769的逆元
首先,我们需要明确什么是模数的逆元。模数的逆元是指在模运算下,能够使得两个数相乘的结果等于1的数。对于模数m,如果存在一个数a,使得a与m互质,那么a模m的逆元就存在。具体求逆元的方法有很多种,其中一种常用的方法是扩展欧几里得算法。
下面是用扩展欧几里得算法求550模1769的逆元的过程:
我们需要求的是a模m的逆元,也就是满足 a * x ≡ 1 (mod m) 的x值。
首先,我们需要求出a与m的最大公约数gcd(a,m)。使用欧几里得算法可以得到:
1769 = 3 * 550 + 119
550 = 4 * 119 + 94
119 = 1 * 94 + 25
94 = 3 * 25 + 19
25 = 1 * 19 + 6
19 = 3 * 6 + 1
6 = 6 * 1 + 0
因此,gcd(550, 1769) = 1。
接下来,我们需要使用扩展欧几里得算法求解x的值。扩展欧几里得算法的基本思想是通过递归地求解gcd(a,b),来得到一组关系式 ax + by = gcd(a,b)。在这里,我们需要求解 ax + my = 1。根据扩展欧几里得算法的推导过程,我们可以得到以下关系式:
1 = 19 - 3 * 6
1 = 19 - 3 * (25 - 19 * 1) = 4 * 19 - 3 * 25
1 = 4 * (94 - 3 * 25) - 3 * 25 = 4 * 94 - 15 * 25
1 = 4 * 94 - 15 * (119 - 94 * 1) = 19 * 94 - 15 * 119
1 = 19 * (550 - 4 * 119) - 15 * 119 = 19 * 550 - 79 * 119
1 = 19 * 550 - 79 * (1769 - 3 * 550) = 238 * 550 - 79 * 1769
因此,x = 238,即550模1769的逆元为238。
matlab 欧几里得算法求乘法逆元
欧几里得算法是一种用于求解两个整数的最大公约数的算法,在数学中也可以用这个算法来计算乘法逆元。所谓乘法逆元,是指在某个模数下,在乘法运算下,使得一个数与其逆元相乘等于模数的1。在MATLAB中,我们可以使用欧几里得算法来求解乘法逆元。
算法的步骤如下:
1. 首先,我们需要确定两个整数a和b以及模数n,其中a和n互质。
2. 利用欧几里得算法,求解a和n的最大公约数gcd(a, n)。
3. 如果gcd(a, n)不等于1,则a在模n下没有乘法逆元。
4. 如果gcd(a, n)等于1,则继续下一步。
5. 利用扩展欧几里得算法,在循环中计算出整数x和y,使得ax + ny = 1。
6. 乘法逆元为x,即使得ax ≡ 1(mod n)成立的x。
下面是一个MATLAB实现的示例:
```matlab
function inv = mul_inverse(a, n)
[gcd, x, ~] = ext_gcd(a, n);
if gcd ~= 1
error('No multiplicative inverse exists.');
else
inv = mod(x, n);
end
end
function [gcd, x, y] = ext_gcd(a, b)
if b == 0
gcd = a;
x = 1;
y = 0;
else
[gcd, x, y] = ext_gcd(b, mod(a, b));
temp = x;
x = y;
y = temp - floor(a/b) * y;
end
end
```
使用上述函数,可以通过传入输入的整数a和模数n,得到a在模n下的乘法逆元。请注意,这个函数只对互质的a和n有效,不满足互质条件时会抛出错误信息。