运用广义欧几里得除法求 s, t 使得 sa+tb=(a, b)
时间: 2023-06-01 07:02:15 浏览: 337
广义欧几里得除法是一种求解两个整数 a 和 b 的最大公约数的方法,它可以表示成以下形式:
对于任意两个整数 a 和 b,存在一对整数 s 和 t,使得它们满足以下条件:
1. 若 a 和 b 都为 0,则 s = 0,t = 0,a 和 b 的最大公约数为 0。
2. 若 a 和 b 中至少有一个为 0,则 s 和 t 可以为任意整数,a 和 b 的最大公约数为 abs(a) + abs(b)。
3. 若 a 和 b 都不为 0,则令 q 和 r 分别为 a 除以 b 的商和余数,即 a = bq + r,其中 0 <= r < abs(b)。
则有 gcd(a, b) = gcd(b, r),并且存在一对整数 s 和 t,使得 sa + tb = gcd(a, b)。
具体地,s 和 t 可以通过以下递归式计算得出:
s1 = 1,t1 = 0,s2 = 0,t2 = 1
si = si-2 - qi-1 * si-1,ti = ti-2 - qi-1 * ti-1(i >= 3)
其中 si 和 ti 分别表示第 i 次迭代时的 s 和 t,qi 表示 a 除以 b 的商,i 的初始值为 3,一直迭代到 r = 0 为止。
根据广义欧几里得除法的定义,可以得到以下求解 sa tb=(a, b) 的算法:
1. 如果 a 和 b 中至少有一个为 0,则直接令 s 和 t 为任意整数,因为此时 (a, b) = abs(a) + abs(b) = 0。
2. 否则,根据广义欧几里得除法的递归式计算 s 和 t。
3. 最后,将 s 和 t 分别乘以 (a, b)/gcd(a, b),得到 sa 和 tb。
代码如下: